{"entities":{"Q490248":{"pageid":492015,"ns":120,"title":"Item:Q490248","lastrevid":62228409,"modified":"2026-04-11T04:39:06Z","type":"item","id":"Q490248","labels":{"en":{"language":"en","value":"The number of moves of the largest disc in shortest paths on Hanoi graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6389209"}},"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":"Q490248$BEE24AC9-FC63-446E-854D-A534E1640833","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2516e11dd87214b13e1101e6b991c8ac11c68625","datavalue":{"value":{"text":"The number of moves of the largest disc in shortest paths on Hanoi graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q490248$7D1175EA-3BF0-465F-8E14-AD645472C1E4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"16a0118329b2d91fae18ec23c40cf0d1ce9208c8","datavalue":{"value":"1305.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490248$ADFE128A-32C0-46E7-ABA1-E224F967A820","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"170dcc18270d3581e6593d615aa56e27a81f75b5","datavalue":{"value":{"entity-type":"item","numeric-id":404597,"id":"Q404597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$5E697D4F-4184-4F26-9F39-DFEB946345C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ac1f7eed377c2103f77b44a5df916bc3f579d8b","datavalue":{"value":{"entity-type":"item","numeric-id":490247,"id":"Q490247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$E720FD66-4BAB-4BDD-90F8-62C7B777174A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9936bc212ee0f58c956363273f70d217577567ed","datavalue":{"value":{"entity-type":"item","numeric-id":327692,"id":"Q327692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$69855479-620E-4E9B-AEC3-DABF7D09CF1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b3be69c113d144cb6a9b87f1c3c7f697398fb012","datavalue":{"value":{"entity-type":"item","numeric-id":327693,"id":"Q327693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$4CB35BB6-8984-4641-A54D-015E2B85153B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$5B8BB746-A14A-4E70-9E6F-A36E34FB57B8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8bb6c16b18fb3fcb7c20a96f2fcd94ae71f0f929","datavalue":{"value":{"time":"+2015-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q490248$5C9F9F62-07DD-45FB-A560-EE0B5837203D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1fedfb4e62a33d230aba8d027f41faced8e621aa","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p38","type":"string"},"datatype":"url"},"type":"statement","id":"Q490248$FCD18CA7-A70D-4C8D-8D39-B31F8AF8E039","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3e4c482af0afa8e6126c9d8ba40850e2e210c6e0","datavalue":{"value":"Summary: In contrast to the widespread interest in the Frame-Stewart conjecture (FSC) about the optimal number of moves in the classical Tower of Hanoi task with more than three pegs, this is the first study of the question of investigating shortest paths in Hanoi graphs \\(H_p^n\\) in a more general setting. Here \\(p\\) stands for the number of pegs and \\(n\\) for the number of discs in the Tower of Hanoi interpretation of these graphs. The analysis depends crucially on the number of \\textit{largest disc moves} (LDMs). The patterns of these LDMs will be coded as binary strings of length \\(p-1\\) assigned to each pair of starting and goal states individually. This will be approached both analytically and numerically. The main theoretical achievement is the existence, at least for all \\(n\\geqslant p(p-2)\\), of optimal paths where \\(p-1\\) LDMs are necessary. Numerical results, obtained by an algorithm based on a modified breadth-first search making use of symmetries of the graphs, lead to a couple of conjectures about some cases not covered by our ascertained results. These, in turn, may shed some light on the notoriously open FSC.","type":"string"},"datatype":"string"},"type":"statement","id":"Q490248$E6986793-5AD6-4648-9433-F580D4EB1ACB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490248$5E354165-4A05-4262-BC91-C83659C6D60A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490248$F51CF96B-AADE-42E3-9B54-8179ADD8DBD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490248$A58DE2A3-1959-4B83-A3C5-BE0B564996A7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"26d139527ae7c73677efa54b1a3eef464a01043f","datavalue":{"value":"6389209","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490248$C934A8DB-55E2-4F32-B4B0-7EEB0A37A11F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b38c60002ac13323f3a82a9b2094195836e1d56","datavalue":{"value":"Tower of Hanoi","type":"string"},"datatype":"string"},"type":"statement","id":"Q490248$CFFCD299-8F74-4083-B432-6A03989028AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"683090baa720b09738eb8f961ee4b8496da39072","datavalue":{"value":"Hanoi graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q490248$9F7BC755-3381-44E2-8162-0A65BAA186E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69d0c99f1e5283b31715a9c7d799852fe62c506e","datavalue":{"value":"shortest paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q490248$31CA4B9D-2E09-44D6-B9B6-F7B2E857BE26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e77f9655f91e78614e2e5b6e37753d7aaba8e2a2","datavalue":{"value":"symmetries","type":"string"},"datatype":"string"},"type":"statement","id":"Q490248$7E8A3745-8218-4B65-892F-E6790255E58A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfa71e439ec4028df02c3244a2a76dc52ffb0dae","datavalue":{"value":"breadth-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q490248$BC0D51E2-BEDD-466A-85EF-4B2DC9FCBABB","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":"Q490248$F56C72DC-696C-4F7A-942C-C42F7F00887F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f9e33733f738abf3491955c6761d458942116df","datavalue":{"value":{"entity-type":"item","numeric-id":4949857,"id":"Q4949857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$96BCDD66-0EBC-4356-B7CB-E94D41295878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9194e9b150f8488fef979658da21ddd0e60751fc","datavalue":{"value":{"entity-type":"item","numeric-id":3651735,"id":"Q3651735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$4F67A6BC-F354-4CB3-8B23-ABC0366D5CAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"444709b0498adc646eb066488eb6cbe55f00f470","datavalue":{"value":{"entity-type":"item","numeric-id":5753988,"id":"Q5753988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$F8CA2B2A-8722-4024-8E37-DA22752D7976","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"809281c6a5a9c405c419d7ea0bf571684e6545d8","datavalue":{"value":{"entity-type":"item","numeric-id":1813640,"id":"Q1813640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$B4260493-F3B7-4B61-964D-7758D5A0136D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ae0613724df5f5a34ee5c6bd3d74b1a1f0716d9","datavalue":{"value":{"entity-type":"item","numeric-id":406332,"id":"Q406332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$29D70427-FBBC-43EE-82AC-1E60211FD7C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85ed23a6df901c324259ea30965ac432b56b1608","datavalue":{"value":{"entity-type":"item","numeric-id":1775033,"id":"Q1775033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$1CC1C2B5-58CA-4BEE-8BB9-3A8B454A59F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"052f18e881f04f7b29ede7373523dcaa96bd5867","datavalue":{"value":{"entity-type":"item","numeric-id":2919650,"id":"Q2919650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$8907BA89-BDB7-4E7F-A9A2-03D5C6C28B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79514d79b664c3c5d5fd71086790c1b8b9364cb3","datavalue":{"value":{"entity-type":"item","numeric-id":411656,"id":"Q411656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$6B1BAB2C-AADF-40B7-83D7-44E270D2B9D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81b99f1bd71d3cd7477483a4fe734af49829bd8a","datavalue":{"value":{"entity-type":"item","numeric-id":1926020,"id":"Q1926020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$CE3D1560-9048-4FF3-916B-21E54E19E3C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"057bea3de214e2c1334d5f22ae9077447f9c7518","datavalue":{"value":{"entity-type":"item","numeric-id":4209980,"id":"Q4209980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$FD1D51BA-CE2B-4F4F-BA61-9E3E3EA9B43A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f5b687c5933d9d7c02cd9400b9c13e60143f14b","datavalue":{"value":{"entity-type":"item","numeric-id":1613371,"id":"Q1613371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$F4772940-EF0B-4A6F-AD1C-619EBD82BBBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6e08a73ea70ec3e4aa331ea3695ab47a28da039","datavalue":{"value":{"entity-type":"item","numeric-id":3803164,"id":"Q3803164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$8CC81833-70BD-44B2-A00A-7CCA7EB02DC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d67f6300b029844fbd1d20de3c2c7102cf82d8b4","datavalue":{"value":{"entity-type":"item","numeric-id":3060163,"id":"Q3060163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$2A530705-F919-44EE-80B0-821F205E589E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"978210024942465c623cc68009bdf76c6fa28467","datavalue":{"value":{"entity-type":"item","numeric-id":5757379,"id":"Q5757379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$CB8EF3D8-1185-4702-B41A-30D672DF05A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9c9c579c6007c4f53482b3a61b4b8815534079d","datavalue":{"value":{"entity-type":"item","numeric-id":3668869,"id":"Q3668869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490248$291F049E-286E-4E95-AE3E-6B81C901C5DC","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"45ab87183c9c3d484732320a31a60bb7590b1208","datavalue":{"value":"bafkreibeewdejemy3fkgdhbwfzmg2patb3qhflrcv35jxxvyodw47ubuzy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490248$571C41D0-A522-4CCA-8E75-239EED3B6BF3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ddc3e44009d068b77f3c1943dc44ec2b3f589f7","datavalue":{"value":{"entity-type":"item","numeric-id":427887,"id":"Q427887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95ac900976937dedc6ffebc97dabfc9643164e68","datavalue":{"value":{"amount":"+0.8363014459609985","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":"Q490248$90346029-EE59-4373-BAFA-CBCD4978C8FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"117e6e8cc104d29e79ecb45095f25b5e26317b7c","datavalue":{"value":{"entity-type":"item","numeric-id":391208,"id":"Q391208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5377d863facdad56c2a640a705b97f3f443ef870","datavalue":{"value":{"amount":"+0.8329121470451355","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":"Q490248$C0F96E57-2CAE-439C-9976-DE35482B92E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17c98517e9d7e0605d4745d4325bade29b2d5a4e","datavalue":{"value":{"entity-type":"item","numeric-id":2161227,"id":"Q2161227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46b407fc84837bab654f38a3a65353608bb9cf2e","datavalue":{"value":{"amount":"+0.8278107047080994","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":"Q490248$E29524CA-03E1-4CCC-90E1-E2F43A18CB43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ae18b330cc8e3aad91aeedd965b36b899a34aef","datavalue":{"value":{"entity-type":"item","numeric-id":4949857,"id":"Q4949857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc039817363139c76233cd7ba448bb9bc4fe58ba","datavalue":{"value":{"amount":"+0.8268060684204102","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":"Q490248$4FDF8F77-96CD-4393-AC9C-161B1B9D0009","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7da27c617dadb2a6c44e47ddba3104ef83c04de","datavalue":{"value":{"entity-type":"item","numeric-id":4651482,"id":"Q4651482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1f2e4603f951e43c6226406ba9b7fba4b761861","datavalue":{"value":{"amount":"+0.8183293342590332","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":"Q490248$2E03E850-6276-4CE8-9DE1-6915D105CD96","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The number of moves of the largest disc in shortest paths on Hanoi graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_number_of_moves_of_the_largest_disc_in_shortest_paths_on_Hanoi_graphs"}}}}}