Numeri Creazionali, la metafora dell'aquilone e la sequenza di Collatz, gli automi cellulari

Introduzione
In questo blog introduciamo prima una problematica ancora vicina alla Teoria dei Numeri, poi successivamente problemi di settori apparentemente diversi ma dove la struttura sottostante è sempre guidata da modelli matematici.


Numeri creazionali

Il numero creazionale di un numero n, che indichiamo col simbolo C(n), è il minor numero di cifre che occorre usare per costruire n.

Facciamo delle "ipotesi creazionali di base":
1) è possibile usare le operazioni +,*,-,/,^
2) è possibile usare i digit D=1,2 ma non necessariamente da usare insieme

Se n=80, D=1 allora C(80) <= 13

Difatti:

80=5*4*4=(1+1+1+1+1)*(1+1+1+1)*(1+1+1+1)

Abbiamo usato solo il digit 1, ma se usassimo anche il 2?
Esempio:
n=81, D=1,2 allora C(81)<=5
81=(2^(2+1)+1)^2

n = 20 D=1,2 C(20) <= 5
20 = 2^(2+2)+2+2

n=120 D=1,2 C(120)<=6
120 = ((2+1)^2+2)^2-1

n=567 D=1,2 C(567)<=8
567 = (2^(2+2+2)-1)*(2+1)^2

Una strategia algoritmica semplice è:
a) ritenere il massimo valore pari al numero n stesso (come somma di 1);
b) individuare il minimo valore possiamo con la potenza k di 2 più grande ma tale che il tutto sia minore o uguale a n stesso (2^k <= n), con k trasformato come somma di 2 e/o 1 o anche prodotti o potenze di 2, sommando, infine, se necessario 1 o altre potenze di 2.

Ad esempio:
C(21)<=6
21 = 2^(2^2) + 2^2 + 1

C(27)<=8
27 = 2^(2^2) + 2^(2+1) + 2 + 1

E' possibile per un fissato n, D=1,2 e le 5 operazioni considerate poter calcolare direttamente, senza algoritmo ma con una formula, il numero minimo di cifre necessarie a creare n?

Sequenza di Collatz
Un problema di interesse in ambito studio del chaos è quello suggerito dalla metafora dell'aquilone o dei chicchi di grandine.

Immaginiamo che ci siano folate di vento che portano verso l'alto oggetti leggeri come i chicchi di grandine o aeroplanini di carta, meglio ancora degli aquiloni.

Immaginiamo che l'aquilone parta da una altezza h (un numero), scende in basso in picchiata e poi una folata di vento lo riporta in alto, poi di nuovo scende in basso e così via fino ad atterrare al suolo (suolo = 1).

Ebbene il problema di Collatz o la sequenza di Collatz si genera a partire da un numero n, se n è pari lo si divide per 2, se n è dispari lo si moltiplica per 3 e si somma 1. Il procedimento si itera sul risultato.

La sequenza termina sempre a 1? E' ciclica, aciclica o convergente a 1?

Un lavoro su questo argomento è al link http://www.rudimathematici.com/Bookshelf/notes/RTC03.pdf
Il software è disponibile su www.gruppoeratostene.com

Solo oggi si sta iniziando ad usare la "computer graphic" per comprendere la struttura esistente dietro la matematica.Perchè ci sono schemi nascosti?

I numeri che si ottengono come output sono le traettorie seguite dall'aquilone prima di giungere al suolo (=1); ma alcuni numeri si presentano più frequentemente e il valore massimo raggiungibile nella traettoria o glide è un numero abbastanza interessante (gli autori presentano una Congettura sul Massimo nella glide); ad esempio 9232 è un massimo che si presenta in più di 350 numeri tra i gli iniziali 1000 interi.

Ma perchè nell'ambito della glide alcuni numeri sono più frequenti e ci sono determinati raggruppamenti?

Il problema di Collatz è scollegato dalla Teoria dei numeri? Gli autori mostrano anche un possibile legame con i numeri di Mersenne ed indagano su diversi teoremi.

Il problema di Collatz rientra in settori tipici molto importanti: Automi Cellulari (AC), Social Network Analisys, Chaos, Frattali, Robotica, batrachioni, Sistemi complessi  etc. settori oggi molto studiati.

In ambito AC la sequenza di Collatz è in effetti  un AC monodimensionale (d=1) lineare  con raggio r=2/3 (infatti in ambito computer graphic il grafico è indicativo di chaos o di frattale) e secondo la classificazione dello studioso Stephen Wolfram è un AC di Classe 1, cioè partendo da n la sua evoluzione porta ad uno stato omeogeneo (sempre lo stesso, l'1) indipendentemente dall'input n.

Batrachioni e chaos
In una rete (Social Network o una rete di automi cellulari) l'evoluzione tiene almeno conto di quello che è accaduto nelle vicinanze, o anche NON immediatamente vicino (dipende dal problema). Il chaos, i batrachioni, i frattali, le trasformazioni lineari, le funzioni biettive e i mapping sono argomenti di notevole interesse per diverse discipline, tra cui anche la Social Network Analisys.

Una cosa che potrebbe sembrare inaspettata è la complessità che può emergere da semplici formule iterative, dando luogo a rappresentazioni di chaos, di frattali etc.

Un pò come le formule iterative di Fibonacci ne esistono altre altrettanto interessanti, come quelle delle curve dei "batrachioni". Il termine deriva dal greco batracen ovvero rana (in letteratura anche "small frog"), proprio perchè le curve che si ottengono sembrano dei saltelli all'infinito di rane che diminuiscono di altezza (ma non di ampiezza). Le curve sono tipicamente frattali perchè sul bordo presentano oscillazioni auto-somiglianti.

Una formula dovuta a Hofstadter-Conway è del tipo:

a[i]=a[a[i-1]]+a[i-a[i-1]]
con a[1]=1 e a[2]=1

Di interesse è il valore a[i]/i. Conway dimostrò che per lim n->inf a[n]=1/2.

Una sequenza caotica altrettanto interessante è:
a[i]=a[a[i-1]]+a[i-a[i-2]-1]
con a[1]=1 e a[2]=1

altre ancora che sono possibili sono:
       a[i]=a[a[i-1]]+a[i-a[i-2]-1];

L'ultima che fa riferimento ad elementi non adiacenti è:
   a[i]=a[a[i-2]]+a[i-a[i-3]-v];   con v=1,2

Vedi http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html

Interessanti sono anche le BlancMange Function Vedi http://mathworld.wolfram.com/BlancmangeFunction.html


Automi cellulari
Gli automi cellulari sono "sistemi complessi" usati per modellare gli dinamica dei flussi dei liquidi, le reazioni chimiche, incendi boschivi, la propagazione e nascita delle piante, di animali, e virus, percolazione del caffè, colata lavica, morfologia urbana e territoriale, inondazioni, diffusione degli inquinanti, etc

Sono spesso dette "strutture omogenee", "strutture cellulari" e "tabelle iterative".
 
Alcuni di questi automi cellulari si comportano in maniera strana e casuale, altri in modo ordinato, alla "frattale".

Si può avere anche una rete di automi cellulari, ognuno dei quali con regole simili ad altri (omogeneità). Di solito valgono le proprietà di Parallelismo (al tempo t parallelamente avvengono azioni su ogni cella o individuo), Omogeneità (stesse regole al tempo t per tutti i nodi della rete o individui, Località (lo stato di un individuo al tempo discreto t+1 dipende dal proprio stato e quello dei vicini). 

Il concetto di automa cellulare è nato negli anni '50 con von Neumann e Stanlislaw Ulam. Conway ideò l'automa cellulare Life (Vita). Martin Gardner pubblicizzò la cosa come un gioco su Scientific American nell'ottobre del '70.


Ogni equazione differenziale si può tradurre in un automa cellulare (equazioni a differenze finite ad esempio). Da qui ad esempio si può usare l'equazione del calore per studiare una rete (anche una Social Network), ipotizzando che per il problema in questione la diffusione del calore sia un modello matematico adatto alla rete.


Life è il punto di partenza per chi vuole apprendere gli automi cellulari.  Vedi gioco http://www.bitstorm.org/gameoflife/

Gli automi monodimensionali studiati da Wolfram sono l'altro punto di partenza.
Vedi http://alpha01.dm.unito.it/personalpages/cerruti/Az1/wolfram.html

Per Collatz come AC vedi http://demonstrations.wolfram.com/CollatzProblemAsACellularAutomaton/
e l'articolo http://arxiv.org/PS_cache/nlin/pdf/0502/0502061v1.pdf   Tra l'altro si tratta di un AC "non invertibile"; difatti se per ogni n si giunge sempre a 1 è difficile risalire al valore n di partenza nella sequenza di Collatz.

Per una introduzione al Social Network Analysis Vedi http://www.slideshare.net/marcomuzza/social-network-analysis-presentation-919991

Gli AC hanno una notevole importanza anche per lo studio di difficili equazioni come le equazioni di Navier-Stokes (altro problema del millennio).


Alla prox