In matematica una successione di numeri naturali è detta successione completa se ogni intero positivo può essere espresso come somma di valori nella successione, utilizzando ciascun valore al più una volta, ovvero se esistono coefficienti booleani tali che . 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 = 1001012 = 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.
Note
[modifica | modifica wikitesto]- ^ Honsberger, pp. 123-126.
- ^ (EN) Eric W. Weisstein, Complete Sequence, su Wolfram Mathworld. URL consultato il 29 settembre 2023.
