Newsgroup: it.hobby.enigmi
Titolo: [Quasi-spoiler]1-11-21-1112-3112

Vi ricordate la sequenza 1-11-21-1112-3112?
Il giochino in sè è banale e stranoto, però il procedimento può essere
considerato più in astratto e generare problemi più interessanti.
Continuando la successione abbiamo
1
11
21
1112
3112
211213
312213
212223
114213
31121314
41122314
31221324
21322314
21322314
...
Si arriva al numero 21322314 che si "autodescrive".
Ci si può domandare (come faceva qualcuno poco tempo fa sul ng):
- quanti e quali sono i numeri che si autodescrivono?
- esistono sequenze che non convergono ad uno di essi?
- che cos' altro può succedere ad una sequenza iterando all' infinito l'
algoritmo?
A priori la risposta può essere difficilissima da dare.
Nell' iterazione dell' algoritmo ci sono 2 "forze" in contrasto tra di loro:
da un lato la descrizione "comprime" le sottosequenze in cui i numeri
compaiono molte volte (come 11111111) dall' altro allarga le sequenze più
caotiche (come 1234567890).
Queste due "forze" però tendono ad un certo equilibrio. Più precisamente
esiste una lunghezza limite tale che tutte le sequenze che hanno lunghezza
maggiore vengono accorciate fino a quella lunghezza e non possono più
superarla..
Ancora più precisamente:
facciamo una stima della lunghezza massima che può assumere una sequenza
lunga N dopo una iterazione dell' algoritmo:
Il caso peggiore è quello in cui nella sequenza ci siano tutte le cifre
1,2,3,4,5,6,7,8,9 e 0.
Siccome la sequenza è lunga N ciascuna cifra comparirà al più N volte (per
tenerci larghi).
La scrittura in notazione decimale di N è lunga esattamente [Log(N)]+1 (con
Log in base 10 e "[...]" che è la parte intera). Quindi dopo una iterazione
dell' algoritmo passiamo da una sequenza di lunghezza N ad una sequenza
lunghezza non più grande di 10+10*[Log(N)].
Tutti coloro che conoscono l' andamento del logaritmo sanno che esiste un N*
tale che 10+10*[Log(N*)]<N* e ciò è vero per tutti gli n maggiori di tale
N*.
Dunque tutte le sequenze di lunghezza N* o superiore vengono accorciate
progressivamente fino a raggiungere una lunghezza minore di N*.
Da ciò si vede che per rispondere in modo completo alle domande di cui sopra
è sufficiente analizzare un numero finito di sequenze: quelle più piccole di
quell' N* che abbiamo nominato sopra. Inoltre ora possiamo escludere a
priori che iterando l' algoritmo una sequenza possa espandersi all' infinito
e sappiamo che finirà certamente su un orbita periodica.
Rimane da stabilire quanto è esattamente questo N*.
Da una stima meno rozza di quella sopra ma più complessa viene fuori che
tutte le stringhe lunghe più di 23 caratteri vengono accorciate. Forse la
stima è migliorabile ma non si può scendere sotto i 20 caratteri (infatti
c'è la sequenza 11223344556677889900 che va in 21222324252627282920).
Mi sono anche divertito a fare un programmino che implementa l' algoritmo e
l' ho provato su tutte le sequenze di lunghezza fino a 5, e su alcune di
lunghezza maggiore (non posso testarlo su tutte le sequenze di lunghezza 6 o
più perchè ci metterei una giornata). Dai test fatti risulta questo fatto
curioso: tutte le successioni di sequenze provate (e sono una marea), di
tutte le lunghezze finiscono sempre in orbite periodiche di periodo 1, 2 o
3. Nessuna sequenza genera mai una successione di periodo 4 o maggiore. Come
si spiega?
Ciao
Marco

#include "LordBeotian.h"

Senti... me lo  spieghi questo affare qui sopra? Di che si tratta? Cos'e'
un numero autodescrivente?
... ah, buon anno a tutto il ng! :)
---
Blackstorm
[ICQ #116647346]
No te vayas todavía,
no te vayas por favor,
no te vayas todavía
que hasta la guitarra mia
llora cuando dice adios
[Sevillanas del adios]

 un numero autodescrivente?
Ciao Black, devi sapere che in principio esisteva questo semplice
indovinello:
"Completare la serie:
1
11
21
1112
3112
211213
...?"
(Che tu sicuramente saprai risolvere :) )
A partire dall' idea che sta alla base dell' indovinello nascono le
questioni che spiegavo nel messaggio di prima.
A tale proposito puoi vedere anche le FAQ
http://www.geocities.com/marianoantoniono/faq.htm
Spero che ora l' affare lě sopra ti sembri comprensibile.
Ciao!!

...?"
312213
Esatto?
--------------------------------
Inviato via 
http://usenet.iol.it
 

 Esatto?
Sě!!


L'affare e' chiarissimo, qll che e' meno chiaro e' cosa hai fatto tu e
cosa vuol dire che le serie tendono ad avere un periodo di 3 o 4... che
cavolo e' un periodo?


 cavolo e' un periodo?
Dicevo che ho fatto (cosa peraltro per nulla difficile) un programma in
pascal che calcola le successioni con l' algoritmo della descrizione:
1 -> 11 -> 21 -> 1112 -> ecc...
oppure
45575 -> 143517 -> 2113141517 -> 511213141517 -> ecc...
Una successione di numeri del tipo descritto sopra è "un' orbita periodica
di periodo 1" (espressione presa in prestito dalla teoria dei sistemi
dinamici) se è una ripetizione infinita dello stesso numero:
A -> A -> A -> A -> ...
Ha periodo 2 se è un' alternarsi infinito di 2 numeri:
A -> B -> A -> B -> A -> B -> ...
Ha periodo 3 se si alternano 3 numeri:
A -> B -> C -> A -> B -> C -> A -> B -> C -> ...
Periodo4:
A -> B -> C -> D -> A -> B -> C -> D -> A -> B -> C -> D -> ...
Quindi ad esempio un numero che si autodescrive genera una successione di
periodo 1.
Risultato sperimentale: *sembra* che tutti i numeri presi come numeri
iniziali generino - dopo alcune iterazioni - delle sequenze di periodo 1, 2
o 3. Nessun numero genera mai una sequenza di periodo 4 o più. (Come mai?
Boh...)
Ad ogni modo qualsiasi problema ci si ponga su queste successioni risulta un
problema decidibile, e questo grazie al fatto che (come scrivevo nel primo
msg) tutte le successioni finiscono prima o poi in un numero di lunghezza
minore di 23 cifre.
Ti sembra che tutto cominci ad avere un senso?
Se no chiedi e ti sarà risposto...
Ciao!!

 Se no chiedi e ti sarà risposto...
ora mi sorge un dubbio spontaneo. Continuando l'analisi, sara' tappa forza
l'analisi di numeri che contengono piu' di 9 cifre tutte uguali...
esempio:
333333333333333
sono quindici.
Come lo descrivo?
153?
che chiaramente andra in
151311
151341
15141331
15142341
1524131231
...
eccetera...
Come la mettiamo?


 algoritmo?
Hi there. You may be interested in this entry from the rec.puzzles
archive:
In the following kind of series each line is derived from the last by
the transformation (for example):
... z z z x x y y y ... ->
... 3 z 2 x 3 y ...
John Horton Conway analyzed this in "The Weird and Wonderful Chemistry
of Audioactive Decay" (T M Cover & B Gopinath (eds) OPEN PROBLEMS IN
COMMUNICATION AND COMPUTATION, Springer-Verlag (1987)).  You can also
find his most complete FRACTRAN paper in this collection.
First, he points out that under this sequence, you frequently get
adjacent subsequences XY which cannot influence each other in any
future derivation of the sequence rule.  The smallest such are called
"atoms" or "elements".  As Conway claims to have proved, there are 92
atoms which show up eventually in every sequence, no matter what the
starting value (besides <> and <22>), and always in the same non-zero
limiting proportions.
Conway named them after some other list of 92 atoms.  As a puzzle, see
if you can recreate the list from the following, in decreasing atomic
number:
U Pa Th Ac Ra Fr Rn Ho.AT Po Bi Pm.PB Tl Hg Au Pt Ir Os Re Ge.Ca.W Ta
HF.Pa.H.Ca.W Lu Yb Tm 
ER.Ca.Co
 HO.Pm Dy Tb Ho.GD 
EU.Ca.Co
 Sm PM.Ca.Zn
Nd Pr Ce 
LA.H.Ca.Co
 Ba Cs Xe I Ho.TE 
Eu.Ca.SB
 Pm.SN In Cd Ag Pd Rh
Ho.RU 
Eu.Ca.TC
 Mo Nb Er.ZR 
Y.H.Ca.Tc
 SR.U Rb Kr Br Se As GE.Na Ho.GA
Eu.Ca.Ac.H.Ca.ZN Cu Ni Zn.CO Fe Mn CR.Si V Ti Sc 
Ho.Pa.H.CA.Co
 K Ar
Cl S P Ho.SI Al Mg Pm.NA Ne F O N C B Be 
Ge.Ca.LI
 He 
Hf.Pa.H.Ca.Li
Uranium is 3, Protactinium is 13, etc.  Rn => Ho.AT means the
following:  Radon forms a string that consists of two atoms, Holmium
on the left, and Astatine on the right. I capitalize the symbol for At
to remind you that Astatine, and not Holmium, is one less than Radon
in atomic number.  As a check, against you or me making a mistake, Hf
is 111xx, Nd is 111xxx, In and Ni are 111xxxxx, K is 111x, and H is
22.
Next see if you can at least prove that any atom other than Hydrogen,
eventually (and always thereafter) forms strings containing all 92
atoms.
The grand Conway theorem here is that every string eventually forms
(within a universal time limit) strings containing all the 92 atoms in
certain specific non-zero limiting proportions, and that digits N
greater than 3 are eventually restricted to one of two atomic patterns
(ie, abc...N and def...N for some {1,2,3} sequences abc... and
def...), which Conway calls isotopes of Np and Pu.  (For N=2, these
are He and Li), and that these transuranic atoms have a zero limiting
proportion.
The longest lived exotic element is Methuselum (2233322211N) which
takes about 25 applications to reduce to the periodic table.
Conway gives many results on the ultimate behavior of strings under
this transformation: for example, taking the sequence derived from 1
(or any other string except 2 2), the limit of the ratio of length of
the (n+1)th term to the length of the nth term as n->infinity is a
fixed constant, namely
            1.30357726903429639125709911215255189073070250465940...
This number is from Ilan Vardi, "Computational Recreations in
Mathematica", Addison Wesley 1991, page 13.
Another sequence that is related but not nearly as interesting is:
1, 11, 21, 1112, 3112, 211213, 312213, 212223, 114213, 31121314,
41122314, 31221324, 21322314,
and 21322314 generates itself, so we have a cycle.

 Come la mettiamo?
La mettiamo che prima o poi arriva ad un numero che si autodescrive o ad una
successione periodica. Dov'è il problema? Cosa ti turba?
Ciao!!
Marco


Ok... tendenzialmente tende a diminuire il numero di cifre necessarie, no?
In prima battuta, dovrebbe esser vero... si, torna tutto...
Ora ho solo una curiosita'... mi spediresti il programma che hai fatto? +
che altro il codice... sono curioso di sapere come hai risolto certe
questioni...:)
L'indirizzo e' nel campo from...


 essere un caso.
Anche a me sembra un caso.
Il ciclo da tre IHMO risulta derivare sempre da questo modello :
51.22.13.34.15.1x.1y
51.22.23.14.25.1x.1y	(#1#)
41.42.13.14.25.1x.1y
Io ho trovato un metodo rapido per trovare tutti i cicli, ecco la deduzione :
0.sia F:{Stringa}->{Stringa} la funzione in questione
1.ogni stringa immagine e' formata da coppie (quantita'_i, simbolo_i)
2.dal precedente, tutte le stringhe dei cicli hanno tale forma
4.i simboli_i sono tutte cifre distinte, per costruzione
5.ogni simbolo presente nella stringa S lo e' anche in F(S), per costruzione
6.dal prec., il numero di coppie (qi,si) e' non decrescente da S a S'=F(S)
7.dal prec., nei cicli il numero di coppie (qi,si) di ogni stringa componente e' costante
8.dal prec. per costruz., i simboli s_i di un ciclo sono gli stessi in tutte le sue
   stringhe componenti
9.da 4 e 8, in un ciclo, per trovare la quantita' in F(S) di un dato simbolo_i, basta conteggiarlo
   nelle sole quantita'_i di S e aggiungere 1; al piu', se non vi compare, si conta 1	
Il risultato chiave e' l'ultimo.
Dice che per ottenere le quantita'_i di F(S) basta avere le quantita'_i di S.
Quindi basta applicarlo su *ogni* possibile partizione (di Eulero) di ogni possibile
lunghezza delle stringhe di un ciclo (fino a 23 dice, un po' largo, LordBeotian)!
esempio, voglio trovare un ciclo formato da 7 coppie (qi,si), puo' essere lunga solo 14
e applico il risultato (9) :
una partizione da 7 e' (2,2,2,2,2,2,2), 14=2+2+2+2+2+2+2
-> (8,1,1,1,1,1,1) 7 ripetizioni di '2' e nessuna di tutti gli altri 6 simboli
-> (6,2,1,1,1,1,1) 
-> (5,2,2,1,1,1,1)
-> (5,3,2,1,1,1,1)  <------|
-> (4,2,2,2,1,1,1)         |
-> (4,4,2,1,1,1,1)         |
-> (5,3,2,1,1,1,1) ciclo!--|
i simboli si possono ricostruire : il 5 e' degli uni (51), il 3 del 4 (34), e quindi (22), 
dunque 51.22.34.1x.1y.1z.1w e da (8) tra {x,y,z,w} dev'esserci anche il 3 ed il 5
ovvero 51.22.13.34.15.1z.1w  che e' il primo numero di (#1#) !
Quelle prodotte sono gia' partizioni valide, per provare che e' l'unico ciclo basta testare
le altre possibilita'.
Se si cerca bene si trova : (4,3,2,2,1,1,1) autodescrivente -> 41.23.32.24.1x.1y.1z
Altro esempio nel sistema ternario :
cerco un ciclo da 2 coppie, sara' lungo 4,5 o 6 simboli es. 6=5+1
   <DEC>   <TER>
-> (5,1) = (12,1)
-> (4,2) = (11,2)
-> (3,2) = (10,2) impossibile per (8) : tre simboli per 2 posti 
da 6 resta ancora (3,3) = (10,10) -> (3,3) Eccolo! 100.101
Tutti quanti sono 7, tutti autodescriventi : 22 111.1x 100.101 10.111.22 20.21.102 e 100.101.22
in binario invece : 111 e 110.1001=(3,4)
In decimale esistono moltissimi cicli, la gran parte punti fissi di F(), pochi cicli da 2
e solo i 10 cicli da 3 descritti in (#1#).
Questo dipende (suppongo) dall'"effetto di attrazione" che ha la sequenza N1.32.23.2N....
seguita da N-1 uni.
Ciao^2.