congettura n esima

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
Tomahawk
Nuovo utente
Nuovo utente
Messaggi: 23
Iscritto il: mer set 12, 2012 8:10 pm

congettura n esima

Messaggio da Tomahawk »

la sapevate questa?

http://it.wikipedia.org/wiki/Congettura_di_Collatz


vi incollo pure il mio programmino in python per agevolarvi gli studi nel caso vogliate cimentarvi nella risoluzione:

def collatz(x):
while x != 1:
print x
if x%2 == 0:
x = x/2
else:
x = x*3+1
print x
([{|Daniele|}])

"Amo le nuvole... le nuvole che passano... là, lontano... le nuvole meravigliose." CB
-
"Mi dispiace maestra, le tabelline le ho imparate in base 2"

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: congettura n esima

Messaggio da Pasquale »

Dato x, quanti passaggi occorrono per giungere ad 1?
Se n è il numero di passaggi necessario, per ottenere un n sempre più grande, occorre un x sempre più grande, ma si può sperimentalmente osservare che la velocità di crescita di n è più lenta rispetto alla crescita di x; dunque, tendendo x all'infinito, n potrebbe tendere ad un infinito di ordine inferiore, oppure ad un numero finito, per quanto grande possa essere, la qual cosa
costituirebbe una nuova congettura, che però è facile confutare. Come?

Allego un lento programmino per l'osservazione dei suddetti valori x ed n, in cui vengono stampati solo gli n maggiori dei precedenti al momento che appaiono la prima volta.

LET mas=0
FOR m=1 TO 2000000

LET x=m
LET cont=0

DO
IF MOD(x,2)=1 THEN
LET x=(3*x+1)/2
ELSE
LET x=x/2
END IF
LET cont=cont+1
LOOP UNTIL x=1
IF cont>mas THEN
LET mas=CONT
PRINT m;cont
END IF

NEXT m

Per avere in modo più veloce un'idea delle due diverse velocità, si potrebbe cambiare la prima riga di codice, a titol di esempio, con un:

FOR m=1 TO 10000000000 step 10000
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

modulocomplicato
Livello 4
Livello 4
Messaggi: 122
Iscritto il: lun ott 01, 2012 5:30 pm

Re: congettura n esima

Messaggio da modulocomplicato »

Interessante... però 500 dollari son pochi !!! ;-P

...ora vedo cosa ci fa sopra la mia algebra a modulo complicato...

modulocomplicato
Livello 4
Livello 4
Messaggi: 122
Iscritto il: lun ott 01, 2012 5:30 pm

Re: congettura n esima

Messaggio da modulocomplicato »

Dato che non ho molto tempo da perdere mi dici se lo hai già risolto (si / no) ?

Tanto per non fare lo sbruffone la mia soluzione parte dalla considerazione che:

2^m = 3x+1 (con x dispari) ha molteplici soluzioni negli interi...

Se se forte con i gruppi e hai letto come funziona il mio modulocomplicato concorderai che la soluzione, almeno per n piccoli è semplice... Quindi se ho capito bene la generalizzazione per m qualsiasi è il problema (risolto o irrisolto?)

Ciao
Stefano

Tomahawk
Nuovo utente
Nuovo utente
Messaggi: 23
Iscritto il: mer set 12, 2012 8:10 pm

Re: congettura n esima

Messaggio da Tomahawk »

modulocomplicato ha scritto:(risolto o irrisolto?)
il problema è stato posto negli anni '30 e ad oggi nessuno lo ha mai risolto.
Se n è il numero di passaggi necessario, per ottenere un n sempre più grande, occorre un x sempre più grande, ma si può sperimentalmente osservare che la velocità di crescita di n è più lenta rispetto alla crescita di x

E' falso:

>>> collatz(3)
3 10 5 16 8 4 2 1
>>> collatz(4)
4 2 1
>>>

per x = 3 n =8
per x = 4 n = 3

notare bene che questa mia confutazione non vale solo per numeri piccoli:

collatz(100)
100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
collatz(149)
149 448 224 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1


>>> collatz(2000)
2000 1000 500 250 125 376 188 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
>>> collatz(3000)
3000 1500 750 375 1126 563 1690 845 2536 1268 634 317 952 476 238 119 358 179 538 269 808 404 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Dato x, quanti passaggi occorrono per giungere ad 1?
non è quello il problema, anche se credo che la formula per trovare il numero di passaggi ancora non esista.
La congettura di Collatz asserisce che questo algoritmo giunge sempre a termine, indipendentemente dal valore di partenza.
Per termine si intende quando si arriva ad 1, si potrebbe continuare dopo l'uno ma la congettura è proprio questa: per qualsiasi numero dopo tot ricorsioni si arriva sempre ad 1.
Confutarla significherebbe trovare un valore che genera una sequenza che non arriva mai al valore 1. Non ci provate perchè perdete tempo :)
Tutta(?) la comunità matematica è concorde sul fatto che la congettura sia vera ma nessuno lo ha mai dimostrato.
n potrebbe tendere ad un infinito di ordine inferiore, oppure ad un numero finito
per l'appunto la congettura sostiene che n è _Sempre_ finito
([{|Daniele|}])

"Amo le nuvole... le nuvole che passano... là, lontano... le nuvole meravigliose." CB
-
"Mi dispiace maestra, le tabelline le ho imparate in base 2"

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: congettura n esima

Messaggio da Pasquale »

Non mi sono spiegato bene.... anche se c'è un x1 < x2 che richiede più passaggi (per giungere a 1) di quanti non ne richieda x2, per trovare un x che richieda più passaggi di quanti ne abbia richiesto x1, bisogna cercarlo fra quelli maggiori di x1; potrebbe accadere anche per un valore minore di x1, ma certamente ve ne saranno molti di più per gli x>x1.
In sostanza, più cresce x più è possibile ottenere un numero n di passaggi più alto di tutti i precedenti ottenuti per i vari x di minor valore.

Poi, per la questione finito/infinito, intendevo che al crescere di x con tendenza all'infinito, abbiamo valori crescenti di n (con tutte le discontinuità che vogliamo, ma in tendenza inesorabilmente crescenti), con n che tende dunque all'infinito; cioè non esiste un n che non potrà mai essere superato, se si utilizza un x grande a sufficienza.

In sostanza, si trattava di ovvie considerazioni.
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

modulocomplicato
Livello 4
Livello 4
Messaggi: 122
Iscritto il: lun ott 01, 2012 5:30 pm

Re: congettura n esima

Messaggio da modulocomplicato »

Innanzitutto grazie TomaHawk, mi hai dato un'assit formidabile !

Spero possa interessare. (riveduto e corretto nei refusi ore 18.30)

Prima consiglio di rileggere il mio post "come si chiama questa operazione" perchè spiega come funziona l'algebra a modulo complicato... cioè un orologio le cui tacche sul quadrante cambiano ad ogni giro e tale per cui alle 12, segna sempre il valore del numero dei giri compiuti elevato alla potenza (scelta)...

Cioè se creiamo un orologio a modulo complicato M2 (quadrato) al primo giro alle 12 segnerà (su un display elettronico posto sopra la tacca delle 12) 1, al secondo giro 4, al terzo 9 etc...

Cioè | A^2 | M2 = 0 (un quadrato di un intero qualsiasi, modulo M2 = 2x-1) restituisce sempre resto zero...

Ma restituisce anche (con il numero di giri) il valore della radice A, qualora questa non fosse consociuta...

Come ho spiegato per me estrarre una radice m-nesima con questo "metodo" è molto facile (anche a mano)... quindi questo problema calza a pennello.

Come si vede la sequenza va in chiusura ogni qual volta si arriva ad un numero dispari che messo nella funzione

f(n)= 3n+1 da 2^m.

Infatti 2^m è (e viene) sempre divisibile per due fino ad 1.... punto d'uscita dell'algoritmo

Quindi la condizione è :

2^m = 3n+1

o radice M-ESIMA DI (3n+1) = 2

L'algebra a modulo complicato dice che qualsiasi potenza è rappresentabile come una somma di "moduli compicati" cioè:

A^m = sommatoria per x che va da 1 ad A di (X^m-(X-1)^m)

Da questo si ricava che il modulo complicato è:

Mm = (X^m-(X-1)^m)

che si ottiene facilmente dal Triangolo di Tartaglia per lo sviluppo di (x-1)^m per l'm in questione,

- eliminando il primo termine (X^m) e cambiando di segno quelli che rimangono.

Quindi per fare la radice m-esima, basta prendere il numero A e sottrargli il risultato di Mm calcolato per x che va da 1 ad A. Se le sottrazioni successive terminano ad A con un resto zero, allora A è la radice esatta di A^m.

Esempio: radice quadrata di 4:
M2= 2x-1 tabulo:

x Mmx 4
1 2x-1 = 2-1=1 4-1 = 3
2 2x-1= 4-1= 3 3-3 = 0 2 è la radice esatta di 4

(è banale, ma se capito ha conseguenze nella teoria dei gruppi non altrettanto banali...)

Dato che in questo problema la radice vale proprio 2, allora è tutto molto semplice perchè:

- qualsiasi sia la potenza m, "1" è proprio il primo valore che assume Mm (quale che sia m) al primo giro

- quindi da 3n+1 sottrarremo sempre 1, cioè avremo sempre e solo 3n

- La congettura ci dice anche che la radice è 2, quindi basta calcolare Mm per il 2° valore che può assumere la variabile x al suo interno, e cioè mettiamo 2 al posto di x, quindi otteniamo un numero e non più una variabile...

Non resta che eguagliare valore A^m-1 e vedere se da resto zero.

Quindi (per vedere se 2^2 è un punto di uscita) la risolvente è:

(3n+1)-1 = Mm |2 (Mm calcolato per x=2)

Ricordo tartaglia:

m 1
1 1
2 1 2 1
3 1 3 3 1
etc...

Ci chiediamo se esiste un n (dispari) tale per cui la radice m esima di (3n+1) dia un valore esatto, pari a 2.

Esempio il caso m=2

quindi per m=2 ci chiediamo se


(3n+1)-1 = Mm |2 dato che M2|2 = (2x-1)|x=2 = 4 quindi verifichiamo se:

3n+1 = 4 con qualche n dispari. la soluzione è (ovviamente)

n= 1

Infatti radq(4) = 2

Ora il caso m=3

Si complica un po' perchè il "modulo complicato" è 3x^2-3x+1 che va calcolato per x=2

M3|3 = 3x^2-3x+1 = 3*4-3*2+1 = 7 ora ci chiediamo se:

(3n+1)-1 = Mm |3 = 7 Ovviamente

n= 7/3 non è nè intero ne' dispari, quindi 2^3=8 non sarà mai un punto di uscita dall'algoritmo.

Attenzione: non si confondi il risultato di (3n+1) con n=5 che da il punto di uscita 16 con quello (8) che si trova su alcune rappresentazioni della dimostrazione del Gruppoeratostene

Ora il caso m=4

M4|2 = 4x^3-6x^2+4x-1 = 4*8 - 6*4 +4*2 - 1 = 15 si verifica che:

3n = 15 ? ovviamente si per n= 5 cioe 2^4 = 16 è un punto di uscita dell'algoritmo

Etc...

Quindi non tutti gli m soddisfano 2^m= 3n+1, ma ce ne sono comunque infiniti che soddisfano tale condizione fra le infinite potenze intere "m".

Attenzione: l'ultima parte di questa affermazione va dimostrata !

Per tagliare corto perchè sono in ufficio... mettiamola così:

Cosa siamo facendo ?

Ci stiamo chiedendo se: (3n+1)-1 = Mm|2 (con m qualsiasi)

ma: Mm|2 è per costruzione SEMPRE un dispari (qualsiavolgia somma/sottrazione di pari alla qualsiavoglia potenza +-1)

quindi ci chiediamo :

se un pari può essere uguale alla differenza fra due dispari: fatto ben assodato, magari non tutti ma ce ne saranno di certo moltissimi... infiniti ! ;-P

Attenzione: non mi sono posto il problema del punto di ingresso in quanto per quale che sia, il "fantastico" algoritmo lo riporta, prima o poi, sempre ad un dispari e fin tanto che quel dispari non è tale da soddisfare la condizione che messo nella f(n) dia un 2^m, continua a cercarlo.... e dato che come abbiamo visto ci sono infiniti dispari che portano al punto di uscita, prima o poi uno di questi verrà sempre raggiunto, infatti la peculiarità dell'algoritmo è proprio quella di "spazzolare" i dispari con frequenza 3* numero dispari. Tale frequenza è la più elevata possibile (solo 1 è più elevata...)

E' interessante vedere come si sviluppa l'algoritmo: ad esempio provate con n=7 e troverete un anello abbastanza corto, mentre per n=9 è molto più lungo... almeno se i conti che ho fatto a mano ieri notte non erano cannati...

Di solito pecco sempre di presunzione, quindi tutto quanto scritto potrbbe essere un'emerita fesseria... e sono sempre più propenso a credere che prima o poi qualcuno mi insignerà di un bell'ignobel...

Il vantaggio di essere asini e saperlo, è che puoi sbagliare senza il terrore di perdere l'ambito titolo...

Non è acqua santa ! Parliamone !

Ciao
Stefano

Ilops
Nuovo utente
Nuovo utente
Messaggi: 1
Iscritto il: ven apr 17, 2020 6:13 am

Re: congettura n esima

Messaggio da Ilops »

Salve stavo rappresentando la congettura di Collatz ed ho pensato a questo modo:

n.operazioni n.scelto

oo 1
0 w 1
1 2 2 1
2 1 4 2 1
3 0 1 4 2 1
4 5 16 8 4 2 1
5 5+w 5 16 8 4 2 1
6 3
7 3+w
8 13
9 13+w
10 53
11 17
12 227
13 11
14 23
15 7
16 7+w
17 29
18 61
19 19
20 37

Ho notato che con i multipli di 2, 3 e 5 si coprivano tutte le operzioni, mentre con i numeri primi non si copriva 0, 3, 5, 9 e 16 operazioni. Cosi sono ricorso ai primi irreali di Eisenstain che hanno come controprova la formula 3n+1 come Collatz. Inoltre l'ultimo numero primo irreale indispensabile è 13+w come il numero essenziale di Graham. Che ne dite?

Rispondi