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

## Successione di Ulam (1, 2)

La successione di Ulam (1, 2) inizia con U$_1$=1 e U$_2$=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. 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. 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 :
| $(a,b)$ | Successione di Ulam $(a,b)$ |
| (1, 2) | 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, ... |
| (1, 3) | 1, 3, 4, 5, 6, 8, 10, 12, 17, 21, ... |
| (1, 4) | 1, 4, 5, 6, 7, 8, 10, 16, 18, 19, ... |
| (1, 5) | 1, 5, 6, 7, 8, 9, 10, 12, 20, 22, ... |
| (2, 3) | 2, 3, 5, 7, 8, 9, 13, 14, 18, 19, ... |
| (2, 4) | 2, 4, 6, 8, 12, 16, 22, 26, 32, 36, ... |
| (2, 5) | 2, 5, 7, 9, 11, 12, 13, 15, 19, 23, ... |

## 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. 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$_1$...U$_n$). 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. In particolare, tutte le successioni di Ulam (2, b) con b dispari e maggiore di 3 sono regolari - e hanno esattamente due termini pari; 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, e hanno esattamente tre membri pari. 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. È 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. 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, $t$)-additive che iniziano con 1 sono anche chiamate successioni di Stöhr: l'$h$-successione di Stöhr è la successione (0, $h$)-additiva che inizia con 1. Per definizione, ogni termine dell'$h$-successione di Stöhr è il primo numero a non poter essere espresso come somma di $h$ precedenti numeri della successione.
Primi termini di alcune successioni di Stöhr :
| $h$ | $h$-successione di Stöhr |
| 2 | 1, 2, 4, 7, 10, 13, 16, 19, 22, 25, ... |
| 3 | 1, 2, 4, 8, 15, 22, 29, 36, 43, 50, ... |
| 4 | 1, 2, 4, 8, 16, 31, 46, 61, 76, 91, ... |
| 5 | 1, 2, 4, 8, 16, 32, 63, 94, 125, 156, ... |
I primi $h+1$ termini dell'$h$-successione di Stöhr sono le potenze di due da 0 ad $h$. I termini successivi sono dati da $(2^{h}-1)(n-h)+1$.

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