Successione completa

In matematica una successione di numeri naturali $S=\left\{s_{n}\right\}_{n\in \mathbb {N} }$ è detta successione completa se ogni intero positivo $x$ può essere espresso come somma di valori nella successione, utilizzando ciascun valore al più una volta, ovvero se esistono coefficienti booleani $a_{i}\in \left\{0,1\right\}$ tali che $x=\sum _{i}a_{i}s_{i}$ . Qualsiasi successione completa può essere utilizzata per codificare numeri interi come stringhe di bit. In generale, queste rappresentazioni potrebbero non essere uniche.

Esempi

[modifica | modifica wikitesto]

Non tutte le successioni sono complete. Ad esempio, la successione dei numeri pari non è completa perché è impossibile rappresentare un numero dispari come somma di numeri pari.

Le potenze di 2

[modifica | modifica wikitesto]

La successione delle potenze di due (1, 2, 4, 8, ...) è una sequenza completa. Il sistema numerico binario offre un modo diretto per esprimere un numero naturale come somma delle potenze di 2 (ad esempio 37 = 100101₂ = 1 + 4 + 32). Questa successione è minima, poiché nessun valore può essere rimosso da essa senza rendere impossibile la rappresentazione di alcuni numeri naturali.

La successione di Fibonacci

[modifica | modifica wikitesto]

I numeri di Fibonacci costituiscono un altro esempio di successione completa. Togliere un qualsiasi numero dalla successione di Fibonacci non altera la sua completezza: questa proprietà deriva dal fatto che la somma dei primi k numeri di Fibonacci è uguale al (k+2)-esimo numero di Fibonacci meno 1^[1]^[2]. La codifica di Fibonacci è una codificazione entropica per la rappresentazione dei numeri interi basata sulla completezza della successione di Fibonacci.