{"entities":{"Q378342":{"pageid":380109,"ns":120,"title":"Item:Q378342","lastrevid":61462428,"modified":"2026-04-10T23:31:25Z","type":"item","id":"Q378342","labels":{"en":{"language":"en","value":"A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron-Frobenius theory"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6225328"}},"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":"Q378342$6735A096-0484-409B-A2FF-78B6C4230712","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0477823a37ca77f0b3b4ea698f00bdc205b4e74e","datavalue":{"value":{"text":"A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron-Frobenius theory","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q378342$A82843FA-B1A4-4224-B9AB-EB0B1C10FBCF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1e9fd57f79873530f4efca747737606f27e9d12c","datavalue":{"value":"1278.91028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378342$02AC737F-A24D-4F74-9020-6E2B81433CC4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1948172daa46442222e070757b29802cb238c10d","datavalue":{"value":{"entity-type":"item","numeric-id":226794,"id":"Q226794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$A1C073FB-52C0-476D-A218-670354A349DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b6bbac7776c86e7b210e50b0fbd4384dd156182e","datavalue":{"value":{"entity-type":"item","numeric-id":378341,"id":"Q378341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$9DC6FEE0-9375-4A83-AB54-6EE35E74D038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4df2688b2437516b3f79c8112e320cdff04c56ca","datavalue":{"value":{"entity-type":"item","numeric-id":923675,"id":"Q923675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$BFDC5B28-B062-4AC4-B296-3A6488F17F20","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ef8712371e142c87c3e57daa1955918131611e11","datavalue":{"value":{"entity-type":"item","numeric-id":267073,"id":"Q267073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$2374997A-5D43-4C29-B7B7-56E69B5B3CDA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9da4a2887762bfc0135842b48e115e887ee73eaa","datavalue":{"value":{"time":"+2013-11-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":"Q378342$FD6DE8B7-78E4-457F-992B-67B08328271D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"31a120ba7362e4f04371c15e3cf923a407bf74b7","datavalue":{"value":"Recently, Gurvich introduced an interesting generalization of Wythoff's game. Let \\(a\\), \\(b\\) be positive integers. In the subtraction game \\(\\mathrm{NIM}(a,b)\\) played with two piles with respectively \\(x\\) and \\(y\\) token, it is allowed to remove \\(x'\\) and \\(y'\\) token from these two piles if and only if \\(0\\leq x'\\leq x\\), \\(0\\leq y'\\leq y\\), \\(0<x'+y'\\) and either \\(|x'-y'|<a\\) or \\(\\min(x',y')<b\\). For the normal version of the game, a recursive characterization of the set of \\(P\\)-positions \\(\\{(x_n,y_n)\\mid n\\geq 0\\}\\) based on a generalization of the minimum excludant (mex) operator is known. Contrarily to the usual setting, note that \\(\\mathbb{Z}_{\\geq 1}\\setminus \\{x_n,y_n\\mid n\\geq 0\\}\\) is infinite.  In this paper, the authors consider the limit \\(\\ell(a,b)=\\lim_{n\\to\\infty}x_n/n\\). They prove that it exists and is equal to \\(a/(r-1)\\), where \\(r>1\\) is the Perron root of the polynomial  \\[ z^{b+1}-z-1-\\sum_{i=1}^{a-1}z^{\\lceil ib/a\\rceil} \\]  whenever \\(a,b\\) are coprime. This polynomial is the characteristic polynomial of a non-negative square matrix depending only on \\(a\\) and \\(b\\). Moreover, if \\(a=da'\\) and \\(b=db'\\), then \\(\\ell(a,b)=d\\, \\ell(a',b')\\). The values \\(x_n\\) and \\(y_n\\) can be computed in \\(O(g(a,b)\\log n)\\) iterations, where \\(g(a,b)\\) is a constant. Even if closed formulas for \\(x_n\\) and \\(y_n\\) are not known, a polynomial algorithm to play \\(\\mathrm{NIM}(a,b)\\) is derived. In the last section, the mis\u00e8re version is also considered (this leads only to minor modifications).","type":"string"},"datatype":"string"},"type":"statement","id":"Q378342$E92D5EA0-E9FC-4034-B3A8-44AC2594E340","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ee087b51e799847d019fb8239a9d1ca2f0176191","datavalue":{"value":{"entity-type":"item","numeric-id":236475,"id":"Q236475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$266EF7AA-ABEF-4A71-9C66-8E376E9DA255","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b62273aea3375cefac54cd8688def5a3b6704b92","datavalue":{"value":"91A46","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378342$45A026E1-2CF9-49FD-94FC-5D91A009C93E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b98cb7058a1e8e644c33a49a426b651c0e594493","datavalue":{"value":"91A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378342$A3F6FF6D-8E40-4D80-BBB0-778B35FA02AB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d51473178df5abd7f077ee59ae1455bce3c3d7ed","datavalue":{"value":"6225328","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378342$0614BBAB-3144-4D2A-A4D0-3D0E29A2A583","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"535d360cb8c0c1aa80f78a968709bdfad17bee58","datavalue":{"value":"combinatorial games","type":"string"},"datatype":"string"},"type":"statement","id":"Q378342$3FA04C83-38BB-4EA5-A95B-99AE60F294FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7a91a4c0c897d065a4103affe35165afa722379","datavalue":{"value":"impartial games","type":"string"},"datatype":"string"},"type":"statement","id":"Q378342$5572FEBD-D195-401D-A04F-CB8911EBE028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa47eeb5fa38829b7763bfcf3b5c37337682232d","datavalue":{"value":"Wythoff's game","type":"string"},"datatype":"string"},"type":"statement","id":"Q378342$F1F78D94-49AB-4414-8491-C54E338F554B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b44744a38573117888a0b367b05309198eb1dc49","datavalue":{"value":"Nim game","type":"string"},"datatype":"string"},"type":"statement","id":"Q378342$EE385140-7F5A-4D58-84CA-739DD70E068D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0f3c5e8eed063b522de83860eee868e03e5a232","datavalue":{"value":"Perron-Frobenius theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q378342$E0A9922D-71D1-463F-8894-4299576C781B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4b11770519dd97fde0d6def9c471611beb3f719","datavalue":{"value":"Collatz-Wielandt formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q378342$55D93CF9-88AD-4D8A-9D28-DE5997F3E175","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93e221e61d1b5dd2fdd58ddee95372114709c92f","datavalue":{"value":"asymptotic","type":"string"},"datatype":"string"},"type":"statement","id":"Q378342$BD4F0E68-3E15-4C57-9122-704EB46C7A09","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f2d39350c933716be468af3c3541e4f6bbe07f12","datavalue":{"value":"Q59560511","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378342$04E9C9E3-7A0D-40C8-976F-34043258E951","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":"Q378342$98C8A37A-1DA2-47F3-9173-ADA92A872FF8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"355e84b6db83884077af41940e267df8dc8abd66","datavalue":{"value":"https://doi.org/10.1007/s00182-012-0338-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q378342$F0D180B7-54D0-4957-BB94-BDA0269807FB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a47dc11cf5c87c788a3f7dc2dafb78c882476c4","datavalue":{"value":"W2017633279","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378342$8B28A693-8F66-4DD6-8699-5093435F2CBD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"54eecec17742b191be9c59853a2308b615ea6ed6","datavalue":{"value":{"entity-type":"item","numeric-id":2703803,"id":"Q2703803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$EFE1488C-45F1-4EF1-A4B2-BAE86813FF49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ab3bdd7d7fbfac1006a4b16e8a3687950389993","datavalue":{"value":{"entity-type":"item","numeric-id":4099541,"id":"Q4099541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$4CA261E3-FBF0-494E-B176-5AC2A5FCBBDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3470f7c7f8ef5485a9b0ad7e1e0b26d5292e157","datavalue":{"value":{"entity-type":"item","numeric-id":5823285,"id":"Q5823285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$2A7CEB1C-25C5-41FC-9681-D6D27289B82C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc0268566ed4c4a0250fbfe1850681e6a8d95988","datavalue":{"value":{"entity-type":"item","numeric-id":4740359,"id":"Q4740359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$7C2C9605-210D-45A6-99FC-7E05DA30CF10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9428708190f1ae2ad10484d448f590ea67854095","datavalue":{"value":{"entity-type":"item","numeric-id":761983,"id":"Q761983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$6B9ED8C9-53D0-4970-BC1D-08D7D7C25A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed0a7b85e331f6254b3e7a1666c2d76fbab8bee8","datavalue":{"value":{"entity-type":"item","numeric-id":1884999,"id":"Q1884999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$BF1A6D83-C49C-4C7D-B37F-71B7FFECD6B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4949e31c07a204b09af41b60ed3b974b2b229813","datavalue":{"value":{"entity-type":"item","numeric-id":2949120,"id":"Q2949120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$ED65DE55-06D2-4B15-9E18-14475CCC87F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1f30d437b0ea8053aa40a0f15733413d572c57e","datavalue":{"value":{"entity-type":"item","numeric-id":1752444,"id":"Q1752444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$7C565634-26B5-4D7C-B199-B0DE9502476C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbf5feb103a91939cd4d1fbb24c74c7ffa130bf6","datavalue":{"value":{"entity-type":"item","numeric-id":423891,"id":"Q423891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$E87C7239-5E96-46F2-B0CE-1AB963FAC108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee586427a0ebc703401dfae0b0a665eb8ee3a673","datavalue":{"value":{"entity-type":"item","numeric-id":3377540,"id":"Q3377540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$9529A94B-8B68-45E3-83E9-3293CCE95534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9554feb86de8ae8f5a851cf183d8afd001a10412","datavalue":{"value":{"entity-type":"item","numeric-id":3400108,"id":"Q3400108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$6B67FD38-2D61-45A0-870F-918F3939C84E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd634f03a3d0433bbb4e5044ebc58dccdd48ecc3","datavalue":{"value":{"entity-type":"item","numeric-id":2949125,"id":"Q2949125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378342$8F27BD67-DB27-4858-8ABC-2B43FC80894D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5d2b4661345c505a12e8b432fdf77bfa74dccfb7","datavalue":{"value":"10.1007/S00182-012-0338-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378342$C26D108E-1185-4F70-83C2-04C8288A4C44","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"f30c713dc3b2f105626e6513ce2059e24094044a","datavalue":{"value":"journals/ijgt/BorosGO13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378342$F3236BDA-AF55-4206-81C1-ADF54EA68884","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b769900cdae2689aa5eb76a2a6a253a2244364cb","datavalue":{"value":{"entity-type":"item","numeric-id":1025554,"id":"Q1025554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"478fb1611ee3e0e879f9d17ee258477cfdb97e48","datavalue":{"value":{"amount":"+0.8126921653747559","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":"Q378342$A8ED2EEC-7C37-4579-9418-6EFD7CE40AB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ece6cc32fa05cef077c7fea25f61a93e2d40c1b4","datavalue":{"value":{"entity-type":"item","numeric-id":4650120,"id":"Q4650120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"224e1a9e1211252c09f6fc7b308f0fd7306d56fb","datavalue":{"value":{"amount":"+0.8051917552947998","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":"Q378342$06EEA063-7962-4C33-AA92-B1B335D410EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1eb9053fa0f5986722d8ad262053dc7d4bd5460b","datavalue":{"value":{"entity-type":"item","numeric-id":5413800,"id":"Q5413800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23e0b48aac50c9abbf920a892fb9aae10fcc5693","datavalue":{"value":{"amount":"+0.7971827983856201","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":"Q378342$E978CAF6-0183-47D7-A0AA-BCAFBAC0DFB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d54df9e8cda37f4d2a4a6e8f3505dc80d79a1fc","datavalue":{"value":{"entity-type":"item","numeric-id":761983,"id":"Q761983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"975361e1311738fa102ff3a72612678236680743","datavalue":{"value":{"amount":"+0.7970318794250488","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":"Q378342$9F73099F-91E8-4618-BF34-32E5BC12F36D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13360db80f7287fe84b5672bb79c8acaaf7def0e","datavalue":{"value":{"entity-type":"item","numeric-id":3635508,"id":"Q3635508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad49133fe83afa13fb6d73ff92a83a45ef86c92a","datavalue":{"value":{"amount":"+0.7927320003509521","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":"Q378342$65C021E4-232A-4BBE-88E4-C788CDF6791F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron-Frobenius theory","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial_algorithm_for_a_two_parameter_extension_of_Wythoff_NIM_based_on_the_Perron-Frobenius_theory"}}}}}