Successione completa

In matematica una successione di numeri naturali ${\displaystyle S=\left\{s_{n}\right\}_{n\in \mathbb {N} }}$ è detta successione completa se ogni intero positivo ${\displaystyle x}$ può essere espresso come somma di valori nella successione, utilizzando ciascun valore al più una volta, ovvero se esistono coefficienti booleani ${\displaystyle a_{i}\in \left\{0,1\right\}}$ tali che ${\displaystyle 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

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

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

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.

Note

1. Honsberger, pp. 123-126.
2. (EN) Eric W. Weisstein, Complete Sequence, su Wolfram Mathworld. URL consultato il 29 settembre 2023.

Bibliografia

• (EN) Ross Honsberger, Mathematical Gems III, Washington, Mathematical Association of America, 1985, OCLC 12490887.