{"entities":{"Q644852":{"pageid":646700,"ns":120,"title":"Item:Q644852","lastrevid":51360719,"modified":"2026-01-17T22:28:04Z","type":"item","id":"Q644852","labels":{"en":{"language":"en","value":"Star reduction among minimal length addition chains"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5968764"}},"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":"Q644852$A3F8C068-287C-4E4E-9D4A-7503A7F0765F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e70c29c78e50dfc393af3b94177a89e46d1f13ac","datavalue":{"value":{"text":"Star reduction among minimal length addition chains","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q644852$1C27B0D2-17BD-4BCE-A57C-4A38F784FF25","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c459c89adf72d495677420dc9ed4e2cab9cc399a","datavalue":{"value":"1241.11143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q644852$7B1D3E09-77AE-458C-9D91-03374EC10ED7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"507494f532fc054a5d3ac97577e8fb8c53fe0c06","datavalue":{"value":{"entity-type":"item","numeric-id":644842,"id":"Q644842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$FAF883BE-8532-4EE8-8182-1793DCEFC1A2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$33473CC3-6D70-413F-A24C-A6E0E7B6CF35","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4b07dd7a3eff452db33a6650b9ef90702ab02d89","datavalue":{"value":{"time":"+2011-11-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q644852$3B2B47DE-196B-45E7-93A7-7F4ABE06460A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fcd4867a33a569cbfdf57f0254b41d76f5f9221f","datavalue":{"value":"An addition chain for a natural number \\(n\\) is a sequence \\(1=a_0 < a_1 < \\cdots < a_r =n\\) of integers such that for each \\(0 < i \\leq r\\), \\(a_i = a_j+a_k\\) for some \\(0\\leq k \\leq j <i\\). The minimal length of an addition chain for \\(n\\) is denoted by \\(\\ell(n)\\). If the above integer \\(j=i-1\\), the step \\(i\\) is called a \\textit{star step}. It is known that there is a minimal length addition chain for \\(n\\) such that the last four steps are star steps. The author conjectures that this even true that there is a minimal length addition chain for \\(n\\) such that the last \\(\\lfloor \\ell(n)/2 \\rfloor\\) steps are star steps and he verified that this holds for \\(n\\leq 2^{18}\\). An application of this conjecture leads to significant progress for the cost of computing a minimal addition chain for \\(n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q644852$9E409439-DE55-4E62-B7E6-898586BFC679","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7b37a6de3a76a2f46603d2a1e14f19e4a44922ce","datavalue":{"value":{"entity-type":"item","numeric-id":168882,"id":"Q168882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$D4DAADF5-E6D3-4CB7-8B5C-2469672A7B56","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"7648e264a01e1ac608cc86dbe77496edbcddb05a","datavalue":{"value":"11Y55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q644852$6CAE2F04-5051-4041-8077-51F1C9D090EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1bcdc2a107fd2414d151e8610f3471a8784e75bf","datavalue":{"value":"68W01","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q644852$D011E91A-D82D-442C-A5F9-6BD9F797FD76","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a08cd9e1ff0e951126b5537be4eaba42f2b5c07","datavalue":{"value":"5968764","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q644852$8BABFDD8-8468-4B9A-BE16-7AA6E09B162B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a4a0b04d2193aebc548250967fb7266e15ac67a","datavalue":{"value":"addition chain","type":"string"},"datatype":"string"},"type":"statement","id":"Q644852$F4BCF97A-C8A1-45A6-8878-3754BA02D911","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfbcaaf2f1a9ac15831ae6c3d4dd30c7f84e33bb","datavalue":{"value":"branch and bound algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q644852$432E5A6B-47D0-4142-B899-4A770E837D9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd2175bd2d291290e91083e8036364494c8bcb8b","datavalue":{"value":"minimal length addition chain","type":"string"},"datatype":"string"},"type":"statement","id":"Q644852$50AE66A8-3512-47B6-8E91-C56FEF13B547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"288ec8d19c883855ade0a5322d3519d88ac84661","datavalue":{"value":"star chain","type":"string"},"datatype":"string"},"type":"statement","id":"Q644852$32882304-13B1-4989-8ED3-2180EE2ACC60","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":"Q644852$C460953E-3964-45B3-BA22-28CF36D674B5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"51abf963c4d503288a9d7d8fcda86b4a1862b53b","datavalue":{"value":"https://doi.org/10.1007/s00607-010-0122-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q644852$9573C585-B6AD-4F7D-A2B2-18D83619B32E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ef600a66e76a3a86528f670875f4954e16a90d94","datavalue":{"value":"W2076450152","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q644852$152AC17A-6581-4DE3-B3DD-E6BD04C89ABB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"787bd344f00935336578ef81c17e1b4407a4dc4a","datavalue":{"value":{"entity-type":"item","numeric-id":854698,"id":"Q854698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$8085702F-08DC-4371-A187-605A7227C1C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d6d07328a8fef902402c4e3e8a32b27923612b2","datavalue":{"value":{"entity-type":"item","numeric-id":4538083,"id":"Q4538083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$D98C2297-297E-4C8D-9F11-20957C11034D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf7ea85479a3002488ec55e62dab5552b23b4cdb","datavalue":{"value":{"entity-type":"item","numeric-id":4279677,"id":"Q4279677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$795CCA1E-473B-402C-9258-FAC6F4B92A6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e40651885e589ae16736b2ed26430168a8207418","datavalue":{"value":{"entity-type":"item","numeric-id":3875826,"id":"Q3875826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$4BDDC6A8-6CD0-4C6E-8436-00A3F9119D38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2f6c372d905f2d2d72c3db39f20b32a30094ce","datavalue":{"value":{"entity-type":"item","numeric-id":3912017,"id":"Q3912017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$C53702FB-E32D-4C8B-B587-DDCFE749B565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc4c2f534223ec34c41fed80e42cbca489663773","datavalue":{"value":{"entity-type":"item","numeric-id":3689092,"id":"Q3689092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$FDAF0E2C-CE19-4E1C-A0D4-5FD9C4ADEFA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f599791702a9cb19723e336659c4b955dfbb04a4","datavalue":{"value":{"entity-type":"item","numeric-id":4209277,"id":"Q4209277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$3A0C5B68-2FF1-4BAA-AD25-C2717C692148","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80187e65c3d02218a1c1b84468898391dd828b52","datavalue":{"value":{"entity-type":"item","numeric-id":4145254,"id":"Q4145254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$D26FB1C0-E45F-4B94-AB63-F86F83E8E567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ed8f781acc8100b35634af0ade8e1b1c189e0cd","datavalue":{"value":{"entity-type":"item","numeric-id":4365757,"id":"Q4365757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$B890CC4A-A4A3-4E17-B3FA-7649E5215965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64a386e94ed5147b5aa2b981e021433b9799f0d5","datavalue":{"value":{"entity-type":"item","numeric-id":1204967,"id":"Q1204967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$2B3E859D-7623-4569-8EF0-F84A3A1BF446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73923f554874c30dd5af1f023bc8f7f7bfc2efe3","datavalue":{"value":{"entity-type":"item","numeric-id":4733937,"id":"Q4733937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$BAE39B94-D735-4D5A-B047-76D854A2EF15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bfe71f8893f5fc00e261684dc3d2f06ed549a8d","datavalue":{"value":{"entity-type":"item","numeric-id":1393436,"id":"Q1393436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$A6C768A0-D08D-4E04-8B45-78165C0619CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22dcb7d49ac0b16b30000ef907f558235df79aac","datavalue":{"value":{"entity-type":"item","numeric-id":1313870,"id":"Q1313870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$4D43972C-8AFB-4F23-84B2-06D08939F500","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5497d93fd8ee00c31be834c1790d685d7b361717","datavalue":{"value":{"entity-type":"item","numeric-id":4268707,"id":"Q4268707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q644852$7999ECB5-CEC0-4FBF-9721-EEB4C025D17B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7aacf05da71da971cb4b74e39ea8f5dd30b739c7","datavalue":{"value":"10.1007/S00607-010-0122-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q644852$E616B106-587A-46CF-9A85-5C73ABD51667","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dae23b0b2cbd4f2a8552ecd1f0707500ab5ed2aa","datavalue":{"value":{"entity-type":"item","numeric-id":854698,"id":"Q854698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d484461c5794f1185af502c1ada46aea5c53ad33","datavalue":{"value":{"amount":"+0.8865517377853394","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":"Q644852$24E8D621-B11C-4B13-B78D-94226DFF07E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aba69ca16faf825e19479352d5ae7a450866fd22","datavalue":{"value":{"entity-type":"item","numeric-id":644848,"id":"Q644848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd9377f433d22144f3c3fe39c1eb824166c1dfa0","datavalue":{"value":{"amount":"+0.8163434863090515","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":"Q644852$56EB37D0-DA26-45C0-97ED-D420309078F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71aa833b82ce80da2018db05e8374b257371f7dd","datavalue":{"value":{"entity-type":"item","numeric-id":4268707,"id":"Q4268707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab56e91496dd069a14b78caff6446064e22259f7","datavalue":{"value":{"amount":"+0.8113377690315247","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":"Q644852$6635117D-22E8-48CB-9500-B52250E479C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fb931cda3bad9e8070b71750b5e78cd8ae574fe","datavalue":{"value":{"entity-type":"item","numeric-id":3351437,"id":"Q3351437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e4f9f6afde6acb3d54d9cec5b610f863814cb0e","datavalue":{"value":{"amount":"+0.8096514344215393","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":"Q644852$1154489A-1F47-4B83-9C1F-7D6A2C9CB25E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"caa98f91b5b9124cd2705bef4e14ab2b5f3c2f0a","datavalue":{"value":{"entity-type":"item","numeric-id":644844,"id":"Q644844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4cbf696ccd587ba9c745dadc825455f342cf897","datavalue":{"value":{"amount":"+0.7949855923652649","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":"Q644852$1A5A4FEF-0139-41C8-BAC1-57B7EF8602D4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:644852","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:644852"}}}}}