{"entities":{"Q2567414":{"pageid":2578157,"ns":120,"title":"Item:Q2567414","lastrevid":48563914,"modified":"2026-01-05T05:48:30Z","type":"item","id":"Q2567414","labels":{"en":{"language":"en","value":"Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2211896"}},"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":"Q2567414$FF584856-CD7E-4EA2-812C-0A1DDDD3914A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f48a2c0cceb22c23f9d8077a998ab7760c2bc944","datavalue":{"value":{"text":"Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2567414$29C14267-2320-4829-BC8F-C6E0EEB7D1C4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dc0ff7cbc434ec7f5f807e192923aa63454f35e5","datavalue":{"value":"1072.11007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2567414$90528E54-A7D0-44A1-B49C-F60DA605F6D8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"875726fb3f17580e8af3a39d31498dd0e33fc926","datavalue":{"value":{"entity-type":"item","numeric-id":205838,"id":"Q205838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$51CC1194-6A5D-4BE1-AEF5-0CF54975644F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"615950119797f35f49728e278e9727b73c5c7f8e","datavalue":{"value":{"entity-type":"item","numeric-id":168620,"id":"Q168620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$58FDA6DD-E773-4A95-8CDA-159C751504E1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6b603c86410fe658d427579de04e3032a0442b94","datavalue":{"value":{"time":"+2005-10-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2567414$70558D4A-EC46-4765-8E34-E3181C8DF86A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e5f64724ab1087e04b95a3a8886d84f29b8c21a2","datavalue":{"value":"Let \\(\\{G_j\\}\\) denote a sequence of integers. The cost of the (redundant) digit expansion \\(n= \\sum_{j\\geq 0}\\varepsilon_j G_j, \\varepsilon_j\\in {\\mathbb Z}\\) is defined as  \\[  c({\\mathbf \\varepsilon}(n))= \\sum_{j\\geq 0}| \\varepsilon_j|.  \\]  In the present paper minimal expansions with respect to two base sequences are examined.  In part one \\(G_j=F_j\\), where \\(F_j\\) denotes the \\(j\\)th term of the Fibonacci sequence. A sequence \\({\\mathbf \\varepsilon}=(\\dots,\\varepsilon_2,\\varepsilon_1)\\in \\{0,\\pm 1\\}^{\\mathbb N}\\) with finitely many nonzero elements is called admissible, if \\(\\varepsilon_1=0\\) and none of the patterns \\((-1,1),(1,1),(-1,0,1),(1,0,1),(1,0,0,1)\\) or their negatives appear as subsequences of \\(\\mathbf \\varepsilon\\). An admissible sequence \\({\\mathbf\\varepsilon}\\) is called an admissible expansion of an integer \\(n\\), if \\(n=\\sum_{j\\geq 1}\\varepsilon_j F_j\\). Then there is a unique admissible expansion of every integer \\(n\\). Moreover it is minimal with respect to the cost function and can be calculated by a greedy algorithm and it cannot be calculated by a deterministic transducer from right to left. However, it is possible to calculate some minimal expansion from right to left.  In part two some result about the Fibonacci expansion is ported back to the \\(q\\)-ary case, i.e. when \\(G_j=q^j\\) for a fixed integer \\(q\\geq 2\\). It is proved that the symmetric signed digit expansion can be computed by a greedy algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2567414$9249717C-CE37-45CD-8515-E7561E66E50D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e840e979351f221ec22f6596521c1e78c9e12ea1","datavalue":{"value":"11A63","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2567414$A89ADD52-8AF1-4C74-9ABE-7D30E7EC414B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ccc5a5c9dd2865ab4417f7cabfcec0ef477e1206","datavalue":{"value":"11B39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2567414$9E4E6CF4-F97F-4171-B801-60B3E8A13F36","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d4931bbb8df2e9c5d41a99c720cdfd789834c371","datavalue":{"value":"2211896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2567414$D3BBCBC8-40DB-4AA2-A0DD-E77D1C5D56C6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3577cf6d55d0c0db005b6a322876013cf2a42ac1","datavalue":{"value":"redundant number systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2567414$1A9922F4-9938-41B0-9AC2-8C465283D135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f919daf07d32d8cf0a19b0a8f56c9fda2fe44dcf","datavalue":{"value":"Fibonacci numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2567414$FFBFE097-F7D7-488B-9925-B460BF0E7CFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bab71d1679a0534be10fa3fec82a9c0e1813b9c4","datavalue":{"value":"Greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2567414$42D64C1A-C07E-4883-8833-30C7692DF6E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41cc83eb486e57774556b3a0952cf1a7025d3766","datavalue":{"value":"optimal digit expansions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2567414$E7D53D2A-1E6E-4C2B-8BF3-FC566B34707F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5017b2bd17b257ad3fd6a92f86114c9608a3136f","datavalue":{"value":{"entity-type":"item","numeric-id":1161771,"id":"Q1161771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$8BBC1332-FCD4-491D-A4DA-4F9469C27D20","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":"Q2567414$106CD372-AD99-4900-8CCD-6CB123DFD425","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"720897de029fd5ac9be11ea7a09038c837d208eb","datavalue":{"value":"https://doi.org/10.1007/s10998-004-0523-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q2567414$D6DA6474-7C37-4B23-91FA-21229E8BACDB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a2563847012fd2fe6cc469283d8c978375adbbac","datavalue":{"value":"W2034555731","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2567414$278622D6-AFC6-4E86-B4CE-A0AC22CD1A1C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e7611f857f5b6b7f23934eab42ae5ba324e06e3","datavalue":{"value":{"entity-type":"item","numeric-id":5805321,"id":"Q5805321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$B55CB5BA-C358-4906-80F8-61A99624D40C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55f95ca76a35762b1cbb433b87773469bdd7d5c","datavalue":{"value":{"entity-type":"item","numeric-id":3893337,"id":"Q3893337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$7D384AD0-22D2-469D-8061-4C9BC2CDEB84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40963a2d6f60cbe666032c1fe2ed015bcf050c6c","datavalue":{"value":{"entity-type":"item","numeric-id":4458955,"id":"Q4458955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$F84D28E8-C3B0-426A-97E8-CE0015C8E76F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd78fd7539746ce39fface229dfdce943e7717ba","datavalue":{"value":{"entity-type":"item","numeric-id":4320535,"id":"Q4320535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$47751BD1-1CF0-4E6E-80C6-B5967A5B44A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b634f7ce971c8844d77cfe7b4ce4d3d30d699aa","datavalue":{"value":{"entity-type":"item","numeric-id":558126,"id":"Q558126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$431F64E5-2BC6-483F-A4BC-96AA752A5262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38d1705d9bdca0648a82dd226a49dfc3ddb852b2","datavalue":{"value":{"entity-type":"item","numeric-id":5945716,"id":"Q5945716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$3B45D58B-AEE8-4E44-8895-6BD5D166440E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87ac755ec4ec9928e31b11f0514e8f9c11bb6380","datavalue":{"value":{"entity-type":"item","numeric-id":1395012,"id":"Q1395012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$6280D1EC-A17A-40E7-9954-F6F7EB62A911","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd0d3ee49942b7d4ab5ec3afec4ce378d32eb663","datavalue":{"value":{"entity-type":"item","numeric-id":3417025,"id":"Q3417025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$BF0B470F-C328-4F8C-9A5F-7B58C6751CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80067af41d85b4a4b96d687cf20df8ceb735152a","datavalue":{"value":{"entity-type":"item","numeric-id":5672799,"id":"Q5672799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$6E0CBC50-F813-4D34-8523-B1BA928FD214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62772a0f1253c0acdb40f41ffb9bb28282d1fbd1","datavalue":{"value":{"entity-type":"item","numeric-id":5202278,"id":"Q5202278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$9741C34A-F9A5-4D62-82F1-3F4822DE95BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a29f3e0c75866192e5ee2025f7bb4fd46918197","datavalue":{"value":{"entity-type":"item","numeric-id":5665234,"id":"Q5665234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2567414$5350B99C-50A6-4901-B637-F792187C6E5E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3858da1ce19a624ef050f58c118da637f5790316","datavalue":{"value":"10.1007/S10998-004-0523-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2567414$DC2E6EAC-E997-461B-8DBA-C4D4FA001255","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fe7c3e46203e40a1f9668c23de09c12a5dfb2e9","datavalue":{"value":{"entity-type":"item","numeric-id":5945716,"id":"Q5945716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b4c41ef8dccbc9f65e6100d862a7009aa80ce7e","datavalue":{"value":{"amount":"+0.8195272088050842","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":"Q2567414$A3A6D83C-B8CF-492F-878C-15858F7A71E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d4a2618b0b969b8a7033df6091cf2632977548d","datavalue":{"value":{"entity-type":"item","numeric-id":3612245,"id":"Q3612245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54d8ec988753b80f9ebccb586c7917ee67d17514","datavalue":{"value":{"amount":"+0.8145912289619446","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":"Q2567414$CF41E523-7262-475C-9760-475873423C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85a19b6d7245d3748470fedae73b4fa078fab9f6","datavalue":{"value":{"entity-type":"item","numeric-id":1969298,"id":"Q1969298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea442cf05ee07dfd8f1f0227d3a0f8ad663e8c88","datavalue":{"value":{"amount":"+0.8107225894927979","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":"Q2567414$D08DD915-4B02-47A6-84E8-D72826E01A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50ae30e586037e3adecb258003cd8b6ef3fc014c","datavalue":{"value":{"entity-type":"item","numeric-id":2808574,"id":"Q2808574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71e97dca9e32677a994ea0c9b554af78b4ef464b","datavalue":{"value":{"amount":"+0.810429036617279","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":"Q2567414$C529D713-42B6-4D40-955F-BCD286F2F0BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"961f476ff6b46845f0cb1950085b161b66836dcf","datavalue":{"value":{"entity-type":"item","numeric-id":653321,"id":"Q653321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75342b0d7f15c4cff4d4d5648896641a140eb49c","datavalue":{"value":{"amount":"+0.803594708442688","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":"Q2567414$55886AAA-B2CC-440F-B36C-18D3BE7AAE87","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2567414","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2567414"}}}}}