On Golomb's self describing sequence. II
type: Item
instance of: scholarly article
title: On Golomb's self describing sequence. II
zbMATH Open document ID: 0865.11022
DOI: 10.1007/BF01270611
published in: Archiv der Mathematik
publication date: 1996-12-15T00:00:00Z
review text: [Part I, cf. J. Number Theory 53, 13-24 (1995; Zbl 0839.11005).] Let \(\{F (n) \}^\infty_{n=1}= \{1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, \dots\}\) be Golomb's self-describing sequence, defined by the condition (i) \(F(1)= 1\); (ii) \(F(n)\) nondecreasing; (iii) \(F(n)\) is the number of integers \(k\) for which \(F(k) =n\). It is known that \(F(n) \sim \varphi^{2- \varphi} n^{\varphi -1}\) as \(n\to \infty\), where \(\varphi= (\sqrt {5}+ 1)/2\) is the golden number, and at least one complete proof of this exists [\textit{N. J. Fine}, Am. Math. Mon. 74, 740-743 (1967)]. There is also a very nice heuristical argument in favor of this, due to \textit{D. Marcus} (loc. cit. p. 740). Briefly, it goes as follows. It seems plausible (1) that there is a good approximation \(f\) of \(F\) which is differentiable and satisfies the approximate functional-differential equation \(f'(t)= (1+ o(1))/ f(f (t))\); and (2) that such an \(f\) satisfies \((*)\) \(f(t) \sim \varphi^{2- \varphi} t^{\varphi-1}\), the latter expression being the unique continuous solution of the functional differential equation \(g(t)= g'(t)/ g(g(t))\) \((t>0)\) with initial condition \(g(0)=0\). The present paper provides complete proofs of (1) and (2), and proposes \((*)\) as an exercise.
Mathematics Subject Classification ID: 11B83
Mathematics Subject Classification ID: 11B75
Mathematics Subject Classification ID: 34K25
zbMATH DE Number: 950074
zbMATH Keywords: Golomb's self-describing sequence
zbMATH Keywords: approximate functional-differential equation
zbMATH Keywords: unique continuous solution
author: Y.-F. S. Pétermann
MaRDI profile type: Publication
cites work: Motivation of Truth Tables From Tautologies
cites work: On Golomb's self describing sequence
cites work: The error term in Golomb's sequence
full work available at URL: https://doi.org/10.1007/bf01270611
OpenAlex ID: W2613456484
description: scientific article; zbMATH DE number 950074