{"entities":{"Q932826":{"pageid":934674,"ns":120,"title":"Item:Q932826","lastrevid":65557713,"modified":"2026-04-12T03:25:05Z","type":"item","id":"Q932826","labels":{"en":{"language":"en","value":"Catalan and Motzkin numbers modulo 4 and 8"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5300779"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$559A29D5-45DE-4209-AFED-7AA57CD76D74","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0229694c0f96e374110fcf5d908047589c50f21c","datavalue":{"value":{"text":"Catalan and Motzkin numbers modulo 4 and 8","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q932826$3B6CE004-296E-4693-8D93-13FEA5069C91","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"472b0459778ab07c791d06f1e4070ed2aff0c6f6","datavalue":{"value":"1149.11008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932826$D8814FE1-E5E4-40B1-AA48-069092E4424C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b02d6c6f899f19b0f6085f8012327357619b05c","datavalue":{"value":{"entity-type":"item","numeric-id":404289,"id":"Q404289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$CCD60F11-CD29-4DDF-A021-318444E5C4EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"80d48711fa6f19f6e434c877ae5b6c4ad65f0d6e","datavalue":{"value":{"entity-type":"item","numeric-id":405252,"id":"Q405252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$1D156DFF-ADF4-4DB6-8CFE-CE1E407092FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc1ec06b13b7bf9626a3cb15da0db3c3a7d3d051","datavalue":{"value":{"entity-type":"item","numeric-id":221614,"id":"Q221614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$6FFAF131-8D5D-44C6-9803-292538BFCB49","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$11099BFB-D013-418C-9EF9-4736CF047403","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"37182800059ed633e356c0f78cd13f10c8c7f234","datavalue":{"value":{"time":"+2008-07-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q932826$AF2F1A89-9FD1-49C6-84E5-439D6E358EEA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"63d415e9abd7b5769b7263c2079c06ee81fb66ab","datavalue":{"value":"\\noindent Let \\(C_n\\) and \\(M_n\\) be the \\(n\\)th Catalan and Motzkin numbers, respectively. It is well-known and easy to prove that \\(C_n\\) is odd if and only if \\(n+1\\) is a power of \\(2\\). The values of \\(n\\) for which \\(M_n\\) is odd were classified by \\textit{E.~Deutsch} and \\textit{B. E. Sagan} [J. Number Theory 117, No. 1, 191--215 (2006; Zbl 1163.11310)]. This nice paper goes further and looks at Catalan and Motzkin numbers modulo \\(4\\) and \\(8\\).   The Catalan numbers modulo \\(8\\) are classified in Theorem 4.2. For example, they are zero modulo 8 if the binary expansion of \\(n+1\\) has at least \\(4\\) bits. For values of \\(n\\) with \\(n+1\\) having at most three bits, \\(C_n\\) is not zero modulo \\(8\\). Further, \\(C_n\\) is never \\(3\\) modulo \\(4\\).   The Motzkin numbers modulo \\(8\\) are classified in Theorem 5.5. As a byproduct of their results, the authors conclude that \\(M_n\\) is zero modulo \\(4\\) if and only if \\(n+\\delta=(4i+2\\delta-1)4^{j+1}\\) for some integers \\(i\\geq 0\\), \\(j\\geq 0\\), \\(\\delta\\in \\{1,2\\}\\), thus confirming a conjecture of Deutsch and Sagan. Furthermore, \\(M_n\\) is never zero modulo \\(8\\).   The proofs use Kummer's theorem on the exponent of a prime dividing a binomial coefficient and Lucas' theorem giving the value of \\({n\\choose k}\\) modulo a prime \\(p\\) in terms of the product of the binomial coefficients of the corresponding \\(p\\)-adic digits and involve a detailed analysis of the binary expansion of \\(n\\). For example, after finding \\(C_n\\) modulo \\(8\\) for all \\(n\\), the authors find \\(M_n\\) modulo \\(8\\) via the formula  \\[  M_n=\\sum_{k\\geq 0} {n\\choose {2k}}C_k.  \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q932826$54F0F3F4-4E5E-45AD-86EA-D6431632A5CD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"703b972b22485bef255b74098d9fff85c5de5ec5","datavalue":{"value":{"entity-type":"item","numeric-id":168881,"id":"Q168881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$59231CAB-1BC5-421F-A6A5-FBB33EDE53D8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"34693e52bda3b7dbf741569b62f785c0e006d8ef","datavalue":{"value":"11B65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932826$5F5A8AB1-5C06-4EB2-872F-AF686F7643F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ab8eef56e70f4344928a6ab2df1e044698959c62","datavalue":{"value":"11B83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932826$626FBE41-9FEE-4F0E-A7A9-BB5C71D499FF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"36b32b62dcf4c87489a3f5b9e53dda100afb8e50","datavalue":{"value":"5300779","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932826$8E1EF709-1641-4F1B-9929-398336E1AD74","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6446a09148e6b50d4c67679d5d3356b034df7902","datavalue":{"value":"Catalan numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q932826$BF10BBDC-BEDB-44B5-BC6A-3F7A91633A1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ebf3a342008060e6dd99e07cd0a05a318026977","datavalue":{"value":"Motzkin numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q932826$BBDBFD5C-8A96-4A37-9654-A6E43EC67BA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b62118851911eb4c917a62f014500e49911db66","datavalue":{"value":"binomial coefficients modulo 8","type":"string"},"datatype":"string"},"type":"statement","id":"Q932826$46F5D467-D4CD-4078-954E-88A554DA13BB","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$EF1D62D5-6480-4FDA-932F-B46EFBF4924B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d8a148760ae689fa54fe26a71e175a827c4487b","datavalue":{"value":"https://doi.org/10.1016/j.ejc.2007.06.019","type":"string"},"datatype":"url"},"type":"statement","id":"Q932826$B008855D-B726-4E80-ABA2-99D8A7EA5E16","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8bd474529e61299125538ee1aea4fbcd3451d97c","datavalue":{"value":"W2048492341","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932826$A29FFD48-E241-4704-9CF2-191B7ACFA488","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"066824940940bf5b23713fee66e873cd679d1fb1","datavalue":{"value":{"entity-type":"item","numeric-id":2264794,"id":"Q2264794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$5EE7AD7C-D6BA-43E1-9BDC-F130B7A973A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2463aecaeca8df6282921e96b884f0d3f79eb738","datavalue":{"value":{"entity-type":"item","numeric-id":916686,"id":"Q916686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$2273562D-DEDC-4750-81AF-9C947A7B0A67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92320d8d52476818665c9cbe35631ecb2928c125","datavalue":{"value":{"entity-type":"item","numeric-id":3358798,"id":"Q3358798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$4B5688C2-A9CF-4240-9981-B78D519992D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9004d48d247fe0f921a26f64834fbb90f01b5cfa","datavalue":{"value":{"entity-type":"item","numeric-id":2490154,"id":"Q2490154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$B98BBBDB-B859-40F3-8220-5B1BDF86F2E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa2c6f412899be375dc8652e900e6dbd79351197","datavalue":{"value":{"entity-type":"item","numeric-id":5895359,"id":"Q5895359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$1A8D3C34-2C82-42B0-9E40-6B6A52BE9F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6874d9c247832990446e7fab5ffc8f531f5e83a9","datavalue":{"value":{"entity-type":"item","numeric-id":3528878,"id":"Q3528878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$6DD339C7-1A5E-4F6A-9D75-4CB58E2529FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e85b6bbf7c4ed32065797e55859272b8be31382","datavalue":{"value":{"entity-type":"item","numeric-id":1162538,"id":"Q1162538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$8EFD42AF-31F1-43EA-90BF-7DC90D3EEFF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d1194d6044d1ab9b9e639a11d0fc37616d5685a","datavalue":{"value":{"entity-type":"item","numeric-id":1378294,"id":"Q1378294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$6A1827DD-70B0-4072-9BD1-67927D6FE791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c97761aae21eb89516e448839cb6f7a406921ac","datavalue":{"value":{"entity-type":"item","numeric-id":1774133,"id":"Q1774133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$EC83D101-8891-4B86-97EE-50760C0B1499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"753449f83aa218bccc37343e6e5416046b4ae5fa","datavalue":{"value":{"entity-type":"item","numeric-id":1835692,"id":"Q1835692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$A9FA946E-99DF-4E6A-BC56-323975CCC8D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2dbd4a93b0fabfd7eb88bd8e0ca72f40b4fba2e","datavalue":{"value":{"entity-type":"item","numeric-id":4236280,"id":"Q4236280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$6D71D160-0556-4D76-BC93-4BD88CFF8D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"405436cc00976353a4262985c44bef1a92c618ac","datavalue":{"value":{"entity-type":"item","numeric-id":3150942,"id":"Q3150942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q932826$A3557B31-E6E6-4C89-89F3-8818F4B6D2CF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f64047b0d453f382c78bf3deb78fc70e42291f5f","datavalue":{"value":"10.1016/J.EJC.2007.06.019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q932826$51A08EDF-146F-4BE0-89B9-81B25D110D0D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"985f32bbbed3a6a5104c15ba94ca23c59624d21a","datavalue":{"value":{"entity-type":"item","numeric-id":1753020,"id":"Q1753020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f09449493872680552fb8f433db564f341d4bd17","datavalue":{"value":{"amount":"+0.8522549867630005","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q932826$46CC345A-096B-4517-B76C-6E55AEB6EB75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a75242461e66803c31876aaaaeab7c6fa657d07","datavalue":{"value":{"entity-type":"item","numeric-id":2490154,"id":"Q2490154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25df3c2463807ac57db06e27d9032e9f62e6cbe3","datavalue":{"value":{"amount":"+0.8242841362953186","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q932826$68B02DDD-D0F0-4BC1-A238-4520038C6E4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56f16d62f99ffed234733b090fc2310f7a103501","datavalue":{"value":{"entity-type":"item","numeric-id":640433,"id":"Q640433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6c657bd3281500d56b05eb1a5a4f8d5d7520821","datavalue":{"value":{"amount":"+0.783048689365387","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q932826$D184A183-1CA1-4588-B920-87E2CFC7D274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0aa28e62de3e57a0c5bb72dc766f3aad23030722","datavalue":{"value":{"entity-type":"item","numeric-id":3569513,"id":"Q3569513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f7d070c4f787ca3eac06701a53bdfa49cb5fd9e","datavalue":{"value":{"amount":"+0.7792350053787231","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q932826$13FFD7A5-72C5-496C-936B-9EAECD8FA779","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffd00598ecd14e75dd2b13a33df3c082b58a2030","datavalue":{"value":{"entity-type":"item","numeric-id":1663803,"id":"Q1663803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa95fd3ed60bb2aea04963514ea919a90c3ba36d","datavalue":{"value":{"amount":"+0.7774388194084167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q932826$4B1F9381-FAC3-4D42-908F-60190327518A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Catalan and Motzkin numbers modulo 4 and 8","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Catalan_and_Motzkin_numbers_modulo_4_and_8"}}}}}