Successione di Ulam

In teoria dei numeri, una successione di Ulam è una sequenza di numeri interi tale che ogni suo membro sia esprimibile, in uno e un solo modo, come somma di due membri precedenti e distinti della successione. Una successione di Ulam è indicata con i suoi primi due termini: (a, b) indica la successione di Ulam in cui a è il primo membro e b il secondo, con a < b. Se non diversamente specificato, si intende per successione di Ulam la successione di Ulam (1, 2). I numeri appartenenti a tale ultima successione sono chiamati numeri di Ulam.

La successione prende il nome dal suo scopritore, il matematico Stanisław Ulam, che la studiò inizialmente per cercare un analogo unidimensionale degli automi cellulari[1][2].

Successione di Ulam (1, 2)

La successione di Ulam (1, 2) inizia con U₁=1 e U₂=2. Dato che, per definizione, i successivi termini devono essere in un unico modo la somma di due distinti termini precedenti, 3 è un membro di questa successione di Ulam, visto che è la somma di 1 e 2. 4 è anch'esso un termine, dato che 4=1+3 (2+2 non conta, perché gli addendi devono essere distinti). 5 invece non lo è, dato che vi sono due modi per scriverlo come somma di due precedenti termini della successione (5=2+3=1+4).
I primi termini della successione di Ulam (1, 2), ovvero i primi numeri di Ulam, sono: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114[3].
I primi numeri di Ulam ad essere anche numeri primi sono: 2, 3, 11, 13, 47, 53, 97, 131, 197, 241, 409, 431, 607, 673, 739, 751, 983, 991, 1103, 1433, 1489, 1531, 1553[4].
L'unica coppia conosciuta di numeri di Ulam consecutivi è [47;48], a parte i casi banali di [1;2], [2;3] e [3;4]. Non esistono triplette di numeri di Ulam consecutivi a parte [1;2;3] e [2;3;4]. Almeno fino ai valori esplorati, l'n-esimo numero di Ulam è dato approssimativamente da n·13,73. Inoltre, circa il 60% dei numeri di Ulam conosciuti differisce di 2 da un altro numero di Ulam. Ulam congetturò che l'insieme dei numeri di Ulam avesse densità asintotica nulla, ma in realtà i numeri di Ulam sembrano avere una densità di circa 0,07396.

Altre successioni di Ulam

Primi termini di alcune successioni di Ulam

${\displaystyle (a,b)}$	Successione di Ulam ${\displaystyle (a,b)}$
(1, 2)	1, 2, 3, 4, 6, 8, 11, 13, 16, 18, ...[3]
(1, 3)	1, 3, 4, 5, 6, 8, 10, 12, 17, 21, ...[5]
(1, 4)	1, 4, 5, 6, 7, 8, 10, 16, 18, 19, ...[6]
(1, 5)	1, 5, 6, 7, 8, 9, 10, 12, 20, 22, ...[7]
(2, 3)	2, 3, 5, 7, 8, 9, 13, 14, 18, 19, ...[8]
(2, 4)	2, 4, 6, 8, 12, 16, 22, 26, 32, 36, ...[9]
(2, 5)	2, 5, 7, 9, 11, 12, 13, 15, 19, 23, ...[10]

Proprietà generali

Infinitezza dei termini

Ogni successione di Ulam ha infiniti termini. Infatti, se, per assurdo, esistessero solo n termini, si potrebbe considerare l'insieme M dei numeri maggiori di U_n ed esprimibili in maniera univoca come somma di due dei primi n termini. Poniamo p = U_n-1+U_n: sicuramente p è un numero esprimibile come somma di due dei primi n termini della successione, ed è anche facile vedere che questa scomposizione è unica[11]. Quindi p appartiene a M e questo dimostra che M è un insieme non vuoto. Applicando il principio del buon ordinamento, è possibile trovare m, il minimo intero di M: m è sicuramente maggiore di U_n e quindi diverso dai primi n termini (U₁...U_n)[12]. Dunque, l'esistenza di m contraddice l'ipotesi iniziale sulla finitezza della successione.

Successioni di Ulam regolari

Una successione di Ulam è detta 'regolare' se le differenze tra i suoi termini successivi diventano prima o poi periodiche. Tutte le successioni di Ulam aventi solo un numero finito di numeri pari sono regolari[13][14][15][16]. In particolare, tutte le successioni di Ulam (2, b) con b dispari e maggiore di 3 sono regolari[15][17][18] - e hanno esattamente due termini pari[18]; anche le successioni di Ulam (4, b) con b > 5 e congruo ad 1 modulo 4 (cioè esprimibile nella forma 4k+1) sono tutte regolari[19], e hanno esattamente tre membri pari[19]. Allo stato attuale delle conoscenze, non sembra invece che la successione di Ulam (1, 2) sia regolare.

Generalizzazioni

Le successioni di Ulam si possono generalizzare nelle successioni s-additive, in cui dopo i primi 2 s termini ogni membro della successione deve potere essere espresso come somma di due precedenti termini in esattamente s modi. Le normali successioni di Ulam sono successioni 1-additive[17]. È stato congetturato che tutte le sequenze 0-additive (quelle cioè in cui ogni successivo termine non può essere espresso in nessun modo come somma di due termini precedenti) finiscano con l'essere regolari[14][20].
Un'ulteriore generalizzazione è data dalle successioni (s, t)-additive, in cui dopo i primi ts numeri ogni termine deve poter essere espresso come somma di t precedenti termini in esattamente s modi.

Successioni di Stöhr

Le successioni (0, ${\displaystyle t}$)-additive che iniziano con 1 sono anche chiamate successioni di Stöhr: l'${\displaystyle h}$-successione di Stöhr è la successione (0, ${\displaystyle h}$)-additiva che inizia con 1. Per definizione, ogni termine dell'${\displaystyle h}$-successione di Stöhr è il primo numero a non poter essere espresso come somma di ${\displaystyle h}$ precedenti numeri della successione.

Primi termini di alcune successioni di Stöhr

${\displaystyle h}$	${\displaystyle h}$-successione di Stöhr
2	1, 2, 4, 7, 10, 13, 16, 19, 22, 25, ...[21]
3	1, 2, 4, 8, 15, 22, 29, 36, 43, 50, ...[22]
4	1, 2, 4, 8, 16, 31, 46, 61, 76, 91, ...[23]
5	1, 2, 4, 8, 16, 32, 63, 94, 125, 156, ...[24]

I primi ${\displaystyle h+1}$ termini dell'${\displaystyle h}$-successione di Stöhr sono le potenze di due da 0 ad ${\displaystyle h}$. I termini successivi sono dati da ${\displaystyle (2^{h}-1)(n-h)+1}$[25].

Successioni generalizzate di Fibonacci

Se si modifica la definizione della successione di Ulam prendendo come termine successivo il più grande numero che sia la somma di due precedenti termini in uno e in un solo modo, anziché il più piccolo, si ottiene la successione di Fibonacci[15]. In generale, cambiando in questo modo la definizione della successione di Ulam (a, b) si ottiene la successione generalizzata di Fibonacci (a, b, -1, 1).

Note

1. (EN) Ulam, Stanisław, Combinatorial analysis in infinite sets and some physical theories, in SIAM Review, vol. 6, n. 4, 1964, pp. 343-355.
2. (EN) Ulam, Stanisław, Problems in Modern Mathematics, Wiley-Interscience, 1964, XI.
3. (EN) Sequenza A002858, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
4. (EN) Sequenza A068820, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
5. (EN) Sequenza A002859, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
6. (EN) Sequenza A003666, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
7. (EN) Sequenza A003667, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
8. (EN) Sequenza A001857, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
9. (EN) Sequenza A048951, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
10. (EN) Sequenza A007300, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
11. Infatti, se prendiamo una diversa scomposizione U_k+U_h, almeno uno dei due addendi deve essere diverso da U_n-1 o da U_n, e quindi minore di esso: pertanto, si avrebbe sicuramente U_k+U_h < U_n-1+U_n e le due scomposizioni non darebbero lo stesso risultato
12. necessariamente il nuovo membro U_n+1 della successione. Infatti, appartenendo a M è esprimibile come somma univoca dei primi n termini della successione. Inoltre, siccome è il minimo di M, non possono esistere altri membri della successione compresi tra U_n e m che possano permettere una diversa scomposizione di m.
13. (EN) Steven R. Finch, Conjectures About 1-Additive Sequences, in Fibonacci Quaterly, vol. 29, 1991, pp. 209-214.
14. (EN) Steven R. Finch, Are 0-Additive Sequences Always Regular?, in American Mathematical Monthly, vol. 99, 1992, pp. 671-673.
15. (EN) Steven R. Finch, On the Regularity of Certain 1-Additive Sequences, in Journal of Combinatorial Theory, Series A, vol. 60, 1992, pp. 123-130, DOI:10.1016/0097-3165(92)90042-S.
16. (EN) Steven R. Finch, Patterns in 1-Additive Sequences, in Experimental Mathematics, vol. 1, n. 1, 1992, pp. 57-63 (archiviato dall'url originale il 20 gennaio 2018).
17. (FR) Raymond Queneau, Sur les suites s-additives, in Journal of Combinatorial Theory, Series A, vol. 12, n. 1, 1972, pp. 31-71, DOI:10.1016/0097-3165(72)90083-0..
18. (EN) Schmerl, James; Spiegel, Eugene, The regularity of some 1-additive sequences, in Journal of Combinatorial Theory, Series A, vol. 66, n. 1, 1994, pp. 172-175, DOI:10.1016/0097-3165(94)90058-2.
19. Cassaigne, Julien; Finch, Steven R., A class of 1-additive sequences and quadratic recurrences, in Experimental Mathematics, vol. 4, n. 1, 1995, pp. 49-60.
20. (EN) Richard K. Guy, Unsolved Problems in Number Theory, 2ª ed., New York, Springer-Verlag, 1994, pp. 110 e 233, ISBN 0-387-94289-0.
21. (EN) Sequenza A033627, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
22. (EN) Sequenza A026474, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
23. (EN) Sequenza A051039, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
24. (EN) Sequenza A051040, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
25. (EN) Sequenza A193911, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.

Voci correlate

• Successione di Mian-Chowla
• Successione di Fibonacci
• Algoritmo ricorsivo

Collegamenti esterni

• (EN) Eric W. Weisstein, Successione di Ulam, su MathWorld, Wolfram Research.
• (EN) Ulam number, in PlanetMath.
• "Come determinare i Numeri di Ulam", su vivalascuola.it. URL consultato l'11 ottobre 2012 (archiviato dall'url originale il 31 ottobre 2013).