Simil-Goodstein

[Simo_the_wolf]

si consideri una successione definita in questo modo:

$ a(2) = t $ con $ t>1 $ numero naturale in base $ 2 $

$ a(n+1)= a(n) -1 $ visto in base $ n+1 $.


Ad esempio prendendo $ a(2)= 1000_2(=8) $ avremo:

$ a(3)=(1000-1)_3 = 222_3 (=26) $
$ a(4)=(222-1)_4= 221_4(=41) $
$ a(5)=(221-1)_5=220_5(=61) $
$ a(6)=(220-1)_6 = 215_6(=83) $

e così via.

Dimostrare che:

1. La successione va sempre a $ 0 $ (nel caso della nostra il primo è $ a(3*2^{402653211} -1 ) =0 $ )
2. La successione va a $ 0 $ dopo un numero dispari di termini
3. se $ a(2k+1) $ è il primo termine che è $ 0 $ allora $ k $ è il massimo raggiunto dalla successione (riconvertendola in base 10)

(per capire la motivazione del titolo andate qui ma non preoccupatevi, questo si dimostra... )

[Fabrizio]

Vediamo se ancora mi sbatto a scrivere una soluzione completa per poi scoprire che da qualche parte c'era quella ufficiale, uguale e pubblica.

Riformulo la tesi in modo da includere tutti e tre i punti richiesti da simone, e poi dimostro la mia "nuova" tesi.

Tesi
La successione arriva ad un termine $ a(i)=10_i $.


Lemma 1
Se esiste $ a(i)=10_i $, allora la successione va a zero.
Infatti il termine successivo a questo avrà una sola cifra, ed è quindi chiaro che sottraendo un'unità di volta in volta in un numero finito di passaggi si arriva a zero.

Lemma 2
Se pongo $ a(k)=10 $ allora questo è uno dei massimi raggiunto dalla successione, e $ a(2k+1) $ è il primo $ 0 $
Innanzitutto, se abbiamo un termine di almeno due cifre diverso da 10, il successivo sarà maggiore o uguale, in simboli
$ a(n)= ... + a_1n + a_0 $, e $ a(n+1)= ... + a_1(n+1) + a_0 -1\underline{>}a(n) + a_1 - 1\underline{>}a_n $, dove gli uguali valgono solo se il termine studiato ha due cifre e $ a_1=1 $.
Ora, studio il caso $ a(k)=10 $.
Avrò $ a(k+1)=k+1-1=k $, il primo termine con solo una cifra. Da qui in poi la successione scende, e arriva a zero dopo k termini, cioé con $ a(2k+1) $.
Per gli stessi motivi è chiaro che tutti i termini nella forma $ 1x_i $ sono massimi.

Dimostrazione
Mi resta da dimostrare che la successione arriva effettivamente a 10_i.
In effetti questo fatto potrebbe passare come ovvio, in quanto i termini dela successione, visti in una base sufficientemente grande, sono strettamente decrescenti, (così si poteva dimostrare anche il punto 1) e quindi è inevitabile che il numero delle cifre diminuisca.

[Simo_the_wolf]

In effetti questo fatto potrebbe passare come ovvio, in quanto i termini dela successione, visti in una base sufficientemente grande, sono strettamente decrescenti, (così si poteva dimostrare anche il punto 1) e quindi è inevitabile che il numero delle cifre diminuisca.

qui credo ci siano problemi... quando definisci una base sufficientemente grande alla fine pensi già come ipotesi che la successione finisca e che quindi per questa base sufficientemente grande tutto torna... Cioè, tu hai dimostrato che è la successione va a 0 supponendo che non vada ad infinito e ciò è dimostrare la tesi assumendo la tesi, non ti pare?

[Fabrizio]

Hai ragione, ci ho pensato un po'... provo a manipolare gli stessi concetti, magari ho un po' più di fortuna.

Poniamo per assurdo l'ipotesi che la successione sia infinita.
Considero l'andamento della cifra delle unità:
Ad ogni passaggio questa diminuisce di uno, e quando arriva a zero scala di uno la "decina" ripartendo da una cifra che vale $ i-1 $, dove $ a(i) $ è il termine della successione in questione.
Le unità quindi, continueranno sempre, infinite volte, ad andare a zero.
Per le "decine" vale un discorso analogo, solo che non scalano di uno ad ogni passaggio, ma quando le unità vanno a zero.
Ma questa differenza non cambia nulla, in quanto abbiamo già stabilito che le unità continuano infinite volte ad andare a zero, e quindi le decine a loro volta lo faranno.
Reiteriamo il ragionamento sulle cifre superiori, per accorgerci che alla lunga, la successione ha proprio una fine, $ 0 $.

Detta così, sembra si riesca a trovare una formula che leghi il $ t $iniziale a $ k $... sapresti trovarla?

[Simo_the_wolf]

Sì ok la mia idea in effetti è trovare quando va precisamente a zero questa successione e bisogna un po' inventarsi delle funzioni che ci dicono "quando va a 0" una determinata funzione.

Se ad esempo $ a(k)=10 $ quando sarà $ a(f(k))=0 $ oppure se $ a(k)=100 $ quando sarà $ a(f_1 (k) )=0 $ ??? e così via...

[Fabrizio]

Non ho capito se hai già una soluzione o la stai ancora cercando... comunque ci provo:

Se $ a(k)=10 $ allora $ a(2k+1)=0 $, ma è anche $ a(k_1)=20 \rightarrow a(2k_1+1)=10 $, e questa dovrebbe valere per scalare le "decine".
Definendo quindi $ f(x)=2x+1 $ abbiamo che se $ a(k_2)=100 \rightarrow a(f^{k_2+1}(k_2))=0 $, perché ci sono $ k_2+1 $ "decine" da scalare.
Mi ricavo poi un attimo che $ f^{n}(k)=2^n(k+1)-1 $, e fin qui mi sembra giusto, anche perché funziona con $ a(2)=100 \rightarrow a(23)=0 $ e altri casi semplici.


Ora provo ad allargare la formula per farla funzionare con quel bel numeretto che hai citato prima...

Di nuovo, vedo che se $ a(k_3)=200 $, torna $ a(f^{k_3+1}(k_3))=100 $, e posso generalizzare...
Definisco un'altra funzione dalla mia $ f(x) $ iniziale, in questo modo: $ g(x)=f^{x+1}(x) $, per poter scrivere meglio $ a(k_3)=200 \rightarrow a(g(k_3)=100 $.
Allora viene naturale $ a(k_4)=1000 \rightarrow a(g^{k_4+1}(k_4))=0 $.
Vorrei ricavarmi la formula bella anche per $ g^n(x) $, ma facciamo che prima mi trovo a mano $ g^3(2) $ per vedere se torna.
Allora: $ g(2)=23 $, $ g(23)=2^{24}\times24-1=402653183 $ (grazie derive )
E allora $ g(402653183)=2^{402653183}\times402653183-1=3\times2^{402653211} -1 $, proprio quel numeretto di prima.
Ora che sono confortato, provo a scrivere una vera formula. ( e qua viene il bello)


Cominciamo col definire una serie di funzioni, la famiglia delle $ f_n(x) $.
Sia $ f_0(x)=x+1 $, $ f_1(x)=2x+1 $, $ f_2(x)=g(x)=x^{x+1}(x+1)-1 $...
Insomma, penso avrai già capito, $ f_{n+1}(x)=f_{n}^{x+1}(x) $.

Ora guardiamo il numero in base 2, al passaggio iniziale. Basta guardare quali posti sono occupati da cifre 1 per costruire una funzione "su misura":
Prendo le funzioni della famiglia $ f_n(x) $ corrispondenti ai posti occupati dagli 1, e le dispongo in modo che la più grande abbia come argomento quella più sotto, e così via essendo l'ultimo argomento il 2.
Faccio un esempio:
$ a(2)= 1011101 $:
Il primo 0 si ha per $ a(k) $, dove $ k= f_6(f_4(f_3(f_2(f_0(2))))) $, trovandosi gli 1 in posto 0, 2, 3, 4, 6.

La formula compendia tutti i casi particolari trovati prima, e funziona per tutti i casi banali provati.
Ora, non non penso di saperla scrivere meglio di così, in effetti visto che numerino è uscito solo con $ f_3 $, non penso ci sia un modo (semplice) per scriverla più sinteticamente...

[Simo_the_wolf]

io la soluzione la conoscevo ed è esattamente come la tua esprimendo il numero di passi per andare a 0 mediante una formula ora è chiaro che quella robba è un numero finito. Trovare una formula "chiusa" non credo sia possibile... però secondo me era carino il fatto che già con numeri piccoli la successione ci metta tantissimo tempo ad andare a zero