Sequenza di Golomb
In matematica, la sequenza di Golomb, che prende il nome dal matematico e ingegnere americano Solomon W. Golomb, è una successione di interi monotona non decrescente nella quale an rappresenta il numero di volte in cui n compare nella successione stessa. La successione inizia con a1 = 1 e ha la proprietà che, per qualsiasi n > 1, an è il primo e unico intero che soddisfa la definizione. Ad esempio, il termine a1 = 1 afferma che il numero 1 appare una e una sola volta nella sequenza, perciò a2 non può essere anch'esso 1, ma può (e deve) essere l'intero successivo, 2. I primi termini della sequenza di Golomb sono
- 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12...
Relazione di ricorrenza modifica
Colin Mallows ha ottenuto una relazione di ricorrenza esplicita per gli elementi della sequenza di Golomb:
- [1].
Una stima asintotica per an è
dove è il valore della sezione aurea (approssimativamente 1.618034)[2].
Note modifica
- ^ (EN) Ronald L. Graham, Donald E. Knuth e Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2ª ed., Addison-Wesley, 1994 [1989], p. 506, ISBN 0-201-55802-5.
- ^ (EN) Y.-F. S. Pétermann, On Golomb's self describing sequence II, in Archiv der Mathematik, vol. 67, n. 6, Birkhäuser-Verlag, 1996, pp. 473-477, DOI:10.1007/BF01270611. URL consultato il 7 agosto 2018.
Bibliografia modifica
- (EN) Graham Everest, Alf van der Poorten, Igor Shparlinski e Thomas Ward, Recurrence Sequences, collana Mathematical Surveys and Monographs, vol. 104, American Mathematical Society, 2003, p. 10, ISBN 0-8218-3387-1.
Collegamenti esterni modifica
- (EN) Sequenza A001462, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
- Un codice Python per calcolare la sequenza di Golomb