{"entities":{"Q1185813":{"pageid":1196562,"ns":120,"title":"Item:Q1185813","lastrevid":70222248,"modified":"2026-04-13T13:16:44Z","type":"item","id":"Q1185813","labels":{"en":{"language":"en","value":"The error term in Golomb's sequence"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 35850"}},"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":"Q1185813$261A483D-506F-482A-B978-7D340FCFABCA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"70adcc87d44163c35e8ae25b0deb4af313bc6542","datavalue":{"value":{"text":"The error term in Golomb's sequence","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1185813$E4222CDD-AD90-406F-B461-411D64CF0FF3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"425ea4cb6febfd42abf0158bf272b0353a128d76","datavalue":{"value":"0758.11012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185813$F9E7230F-F37D-434F-92FF-D91E851A551A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9b995d55a553e38b49117e85749552e7ecaa64ae","datavalue":{"value":"10.1016/0022-314X(92)90024-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185813$2B319CC4-5F5F-436C-90A2-EB04696802DF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"29675f2d17d730ca4a0bd41500f993f15533f902","datavalue":{"value":{"entity-type":"item","numeric-id":215574,"id":"Q215574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185813$12FD55BA-E681-42D0-A774-FAAC2898D138","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":"Q1185813$968E93C5-A502-49C6-A195-0D13A08110CF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1185813$C43BE368-E998-4C19-8469-5060C75CF6A1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"70e5ee1b02cbcfc49d5c87bdbdedbbb67c45a395","datavalue":{"value":"S. Golomb has defined a sequence of integers \\((F(n))_ n\\) by \\(F(1)=1\\), \\(F(n)=\\#\\{m\\); \\(F(m)=n\\}\\) and \\(F\\) is nondecreasing, so that  \\[ (F(n))_ n=1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,\\dots\\;. \\]  He asked for an asymptotic formula for \\(F\\), and it has been proved that \\(F(n)\\sim cn^{\\varphi-1}\\), where \\(c=\\varphi^{2-\\varphi}\\), and \\(\\varphi\\) is the golden ratio.   The main result of this paper is an estimation of the error term (which answers a question of Knuth). The author proves  \\[ E(n)=F(n)- cn^{\\varphi-1}=O\\left({n^{\\varphi-1}\\over {\\log n}}\\right). \\]  Although this estimation does not seem sharp in view of numerical computations by Knuth (showing that \\(E(n)\\leq .51\\) for \\(n\\leq 400\\)) the author conjectures that  \\[ E(n)=\\Omega_ \\pm\\left( {n^{\\varphi-1} \\over {\\log n}}\\right), \\]  and even gives a stronger conjecture. In the last part of the paper the author shows how to compute \\(F(n)\\) for large values of \\(n\\), using the enumeration of a special kind of trees.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1185813$FA30FC90-0CB1-471C-9238-575823A24024","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4bceb4852f142c7ae840ef027a3d11ea672a1bc4","datavalue":{"value":"11B75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185813$9B12863A-29AD-4BF1-98A7-F763F1CE9435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b85c221f9847adc30512692a640a50dd4e3d1cb","datavalue":{"value":"05A16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185813$F4B38BD4-69D5-4C83-94A9-066E74380289","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1eefd97f12b504bc71626bcdf203acc1b4c418e7","datavalue":{"value":"35850","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185813$6ED292A6-D41A-4CD4-B1E3-52FEF31B4E5F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87104056501ba802518456193ec74c1d6f191cf4","datavalue":{"value":"Golomb sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1185813$5AEC3C26-5788-478E-8794-13D314247359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3ad664bdb61639423187e7b4f75e8f6aa38e4bb","datavalue":{"value":"self-describing sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1185813$C799B684-B980-4A11-AB74-C75053606747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6688c344f33dc03f98812e9df1a1620433cfe7cb","datavalue":{"value":"enumeration of trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1185813$64163808-FF80-40C4-9C8C-FAA75DA11A2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"729fdbdfe5a33bade8948482bf29e45a154564ef","datavalue":{"value":"asymptotic formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q1185813$01B41133-96FD-494B-A39B-1ECD7C047232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"266c64a00b7f284e6bcffe3838a1782bf97744d4","datavalue":{"value":"error term","type":"string"},"datatype":"string"},"type":"statement","id":"Q1185813$97F6E744-20E7-4371-B2F9-A0FAC532E944","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":"Q1185813$4EE0D9A6-8D3C-4605-9889-822979B39077","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":"Q1185813$B965292C-B3D8-4018-A19B-CDC1D919C199","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"58d85a10a6a04197d39365dd1c0bbaaea02f2282","datavalue":{"value":{"entity-type":"item","numeric-id":3207312,"id":"Q3207312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185813$AB1900BF-89C8-4642-A395-9C78D146D7D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4ceaf264558a7350621ded2b54ec08733a56d80","datavalue":{"value":{"entity-type":"item","numeric-id":5904955,"id":"Q5904955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185813$BAAFF64C-1371-4321-8947-529A019AD90F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5e13a59abc81509ed517f7c85fa111838b6d2b3","datavalue":{"value":{"entity-type":"item","numeric-id":4774085,"id":"Q4774085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185813$7D0DB502-AECA-4120-9FC2-C454CA8095D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf9b43bb259d051f6e312dbb5997a6b7ba416319","datavalue":{"value":{"entity-type":"item","numeric-id":3735790,"id":"Q3735790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185813$B21B9E67-89E1-4DE7-A5F1-49BCDE8E0F20","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"94847a5ddd3a918c636c8baa0b18d206fd6ade97","datavalue":{"value":"https://doi.org/10.1016/0022-314x(92)90024-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q1185813$DDD1F07C-D39B-49CD-B81C-3F883186C69D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e0aeb017c982a12ba6d9c66ab0ef61117863de1d","datavalue":{"value":"W2082611794","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185813$5B1B0D9A-926B-483C-842C-1D40C8CBF0E5","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":"d814ddb8c6925e90153fb46dd47b92f7c42cb5c2","datavalue":{"value":{"amount":"+0.8368354439735413","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":"Q1185813$918B3AEE-1C76-451C-A3FB-E11A0F31FB98","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":"ad082f1da3f71d65897b20bb5e1b0a175a147a2c","datavalue":{"value":{"amount":"+0.8357117772102356","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":"Q1185813$2EBC0621-45E2-4109-AAF8-1FF931FE1254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccf72662421989c7f46a75c977dab87b3954a44f","datavalue":{"value":{"entity-type":"item","numeric-id":1896582,"id":"Q1896582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"100c95fbfc85d36b4a0bfe3f22ecf46eb7b58982","datavalue":{"value":{"amount":"+0.8339900374412537","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":"Q1185813$A4F3C732-3C4F-4E71-BF02-201A6E6ED1A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abe2188370c63a7235ac93a55bab50711b4cf4f0","datavalue":{"value":{"entity-type":"item","numeric-id":4685499,"id":"Q4685499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"100c95fbfc85d36b4a0bfe3f22ecf46eb7b58982","datavalue":{"value":{"amount":"+0.8339900374412537","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":"Q1185813$FB4EC5D8-CCCA-4343-B248-241A3CB021F0","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":"bb3c2772b8ffefb11a53c1e303459f20c3c18b28","datavalue":{"value":{"amount":"+0.8282530903816223","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":"Q1185813$9BC5FA89-8910-46BB-BA1B-B80FAC55CFEC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The error term in Golomb's sequence","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_error_term_in_Golomb%27s_sequence"}}}}}