{"entities":{"Q1896582":{"pageid":1907324,"ns":120,"title":"Item:Q1896582","lastrevid":71097291,"modified":"2026-04-13T19:27:47Z","type":"item","id":"Q1896582","labels":{"en":{"language":"en","value":"On Golomb's self describing sequence"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 792466"}},"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":"Q1896582$1876D714-AD4D-43CB-AADA-73B490F8B4AC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c522fb7da3c2aec07459ca4a6118cb6cab9a6fed","datavalue":{"value":{"text":"On Golomb's self describing sequence","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1896582$156C6A94-D469-4D7C-A6DA-1675CA74A291","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"684151bd5f80167a4680f623578ad5200c0d2252","datavalue":{"value":"0839.11005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896582$5268E362-DBD7-48DB-8863-2ADE12F21C01","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e6cac328d206d9ef9b7afb3fb4ca5d1d204199af","datavalue":{"value":{"entity-type":"item","numeric-id":167107,"id":"Q167107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896582$A382E58D-D5D8-471F-8354-AD50EC202FD6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2019bd08bd1a78f71db4e49a4128dd769f77f07f","datavalue":{"value":{"time":"+1995-10-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":"Q1896582$8BB65370-5FF7-4D93-A388-F4DFFD1F4EB8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e08d6a44ecc06439f53a85afbb2b33d5d8ac42f","datavalue":{"value":"The self-describing sequence introduced by \\textit{S. W. Golomb} [Problem 5407, Am. Math. Mon. 73, 674 (1966)] is defined by: \\(F(1) = 1\\), \\(F(n) = \\# \\{m; F(m) = n\\}\\) and \\(F\\) is nondecreasing. It has been proved by \\textit{N. J. Fine} [Solution to Problem 5407, Am. Math. Mon. 74, 740-743 (1967)]\\ that \\(F(n) = cn^{\\varphi - 1} + E(n)\\), where \\(\\varphi = {1 + \\sqrt 5 \\over 2}\\) is the golden ratio, \\(c = \\varphi^{2 - \\varphi}\\) and \\(E(n) = o(n^{\\varphi - 1})\\). D. E. Knuth asked whether a better bound can be found for \\(E(n)\\) and whether \\(E(n)\\) is bounded. Computations by \\textit{I. Vardi} confirmed the boundedness of \\(E\\) and he proved [J. Number Theory 40, No. 1, 1-11 (1992; Zbl 0758.11012)]\\ that \\(E(n) = O({n^{\\varphi - 1} \\over \\log n})\\). Vardi conjectured that \\(E(n) = \\Omega_\\pm ({n^{\\varphi - 1} \\over \\log n})\\).   The author of the paper under review shows that \\(E(n) = \\Omega_\\pm (n^{\\varphi - 1 - \\varepsilon})\\) \\(\\forall \\varepsilon > 0\\). The proof is both ingenious and elementary which makes it very interesting.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896582$5D4098AC-2ADB-4850-9096-BF01F591E9AF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ab8eef56e70f4344928a6ab2df1e044698959c62","datavalue":{"value":"11B83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896582$68A2D84B-EFAE-4BA4-99DC-A87A4DFCBE6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4bceb4852f142c7ae840ef027a3d11ea672a1bc4","datavalue":{"value":"11B75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896582$380E85E0-2472-41E3-9EAF-968AB1D0F45B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b85c221f9847adc30512692a640a50dd4e3d1cb","datavalue":{"value":"05A16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896582$4405A3A3-681D-4A35-A4AC-81ECD88C2277","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a8a81231b008431545666805fa46e09fab5a2f37","datavalue":{"value":"792466","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896582$55A10E4E-5D01-4B86-A768-B1F04F3BA292","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"736a571b25fcc4871b19e93daf8d59f8d009038a","datavalue":{"value":"Golomb's sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896582$F9202137-6462-431C-BFCA-3EBB6675C2E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1843aa31bf71abecd617c1a9754785112ac3423f","datavalue":{"value":"golden ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896582$1B641666-ADF7-4C9C-8DE5-93B96B46DEE9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c890dedc6ec5ac1c64d6e76a77cbce8bcc4570e6","datavalue":{"value":{"entity-type":"item","numeric-id":1750164,"id":"Q1750164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896582$7CC9E14F-F805-4146-8954-3CCB887E0221","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"845abdf0c3e7df8eeaf94dc258fde16321cf5952","datavalue":{"value":{"entity-type":"item","numeric-id":187638,"id":"Q187638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896582$7A4F3601-61C1-4AE5-87A6-3E82DD67EB7A","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":"Q1896582$D779D7E7-7C0C-4B75-BBE1-72060370A96A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6143c6c3f97483f1f4773a9fdc241f48c892ccae","datavalue":{"value":"https://doi.org/10.1006/jnth.1995.1076","type":"string"},"datatype":"url"},"type":"statement","id":"Q1896582$642CA488-8CAF-4659-A22E-3A3A7D925A5B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e57b84a9bf7a4d02f474efbf3c1e68e726da163f","datavalue":{"value":"W2083883398","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896582$D7009DDE-4C52-47C6-9DE0-91ED6A608A0F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"85a0a94884515647e1e690f671fbe49ee516b87c","datavalue":{"value":"10.1006/JNTH.1995.1076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896582$3BF641F7-9964-46F8-8A5E-5F99DD5127E0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"914834ae795c7580b68c974614bd5d8adac657dc","datavalue":{"value":{"entity-type":"item","numeric-id":1366666,"id":"Q1366666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2aa5b6313c77ae15b3cd78cabfc9ab15f2ee2c17","datavalue":{"value":{"amount":"+0.9639224410057068","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":"Q1896582$CAB812FB-A70B-4083-BB80-941F23B89C07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b22531d6224840fc802c1ed5679841d650d2dbb","datavalue":{"value":{"entity-type":"item","numeric-id":1809050,"id":"Q1809050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96c123b1c6ceb72b1b6aadea07520423888dfcbe","datavalue":{"value":{"amount":"+0.963834583759308","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":"Q1896582$1A2CEBFA-A5F0-4E84-944D-FE4CC2B2BC61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40ea057e436a7736f789abf53a89c62d7a7a4f83","datavalue":{"value":{"entity-type":"item","numeric-id":1816489,"id":"Q1816489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c5c0050e0cbbcefe4985da9ea54b6157242062a","datavalue":{"value":{"amount":"+0.9056380987167358","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":"Q1896582$E3A82C43-432A-4BEA-B0F6-D67AD4769CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53d899ca2584c714513d514cdcce4bf74c6c7f73","datavalue":{"value":{"entity-type":"item","numeric-id":1890402,"id":"Q1890402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c5c0050e0cbbcefe4985da9ea54b6157242062a","datavalue":{"value":{"amount":"+0.9056380987167358","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":"Q1896582$CA716F48-A12C-4FD9-9B99-74EA85AE5E9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0864f91a4716eefd6425f17bb299b8844cfbb838","datavalue":{"value":{"entity-type":"item","numeric-id":1129757,"id":"Q1129757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"149bb64ae02cabba5f2499c7809784ff1449d2f0","datavalue":{"value":{"amount":"+0.8772074580192566","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":"Q1896582$54E20C5C-4DBD-4F5E-88AD-69EDD4E55DA0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On Golomb's self describing sequence","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_Golomb%27s_self_describing_sequence"}}}}}