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].

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.

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]

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.

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.

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.

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].

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).

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

• (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).

Portale Matematica: accedi alle voci di Teknopedia che trattano di Matematica