Visualizza un messaggio singolo
Vecchio 23-01-13, 11:53   #1029
Erasmus
Utente Super
 
L'avatar di Erasmus
 
Data di registrazione: Feb 2008
Ubicazione: Unione Europea
Messaggi: 6,374
Predefinito Re: Un po' di calcoli ... un po' di logica....

Ben tornato, Miza!
-----------------------
Quote:
aspesi Visualizza il messaggio
Si tratta del triangolo di Sierpinski in decimale.
Mai sentito nominare prima.

Miza: mettiamo da parte la "costruibilità con riga e compasso" e spostiamoci sulla questione (equivalente) di sapere per quali N (naturali dispari) " la determinazione del coseno di un N-esimo di angolo giro è un "problema di 2° grado".
-----------------
Ho verificato (ancora prima di leggere qua) che il meccanismo funziona (almeno) fino al prossimo numero primo di Fermat cioè
p(4) = 2^(2^4) + 1 = 2^16 + 1 = (2^8)^2 + 1 = 256^2 + 1 = 65537.
NB: I "numeri primi di Fermat" sono i numeri primi del tipo p(n) = 1 + 2^(2^n).
Tali sono i p(n) per n da 0 a 4 compresi.
p(0)= 3; p(1) = 5; p(2) = 17; p(3) = 257 (primo); p(4) = 65537 (primo).
Codice:

 C(8, k)––>                 1  0  0  0  0  0 0  0  1          =        257
 C(9, k)––>               1  1  0  0  0  0  0  0  1  1        =      3·257
C(10, k)––>             1  0  1  0  0  0  0  0  1  0  1       =      5·257
C(11, k)––>           1  1  1  1  0  0  0  0  1  1  1  1      =    3·5·257
C(12, k)––>         1  0  0  0  1  0  0  0  1  0  0  0  1     =     17·257
C(13, k)––>       1  1  0  0  1  1  0  0  1  1  0  0  1  1    =   3·17·257
C(14, k)––>     1  0  1  0  1  0  1  0  1  0  1  0  1  0  1   =   5·17·257
C(15, k)––>   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  = 3·5·17·257
C(16, k)––> 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 =      65537
. . .
Se mettiamo in ordine crescente gli interi N fattorizzabili in fattori semplici del tipo dei p(n) di Fermat otteniamo proprio gli nteri espressi in base 2 dalle righe del "Triangolo di Trataglia" ridotte modulo 2.
Non è necessario calcolare i coefficienti C(r, k) (della riga Nr. r di posto in riga Nr. k) del Trinagolo di Trataglia (ossia in numero di combinazioni di r elementi a k a k). Si può applicare la regola
C(r, k) + C(r, k+1) = C(r+1, k+1)
direttamente ai coefficienti ridotti modulo 2, (che così valgono 0 quando sono pari e 1 quando sono dispari).
In pratica, sempre si comincia con 1 e si termina con 1; si guarda la riga di sopra: se là ci sono di seguito due caratteri uguali si mette 0 e se no si mette 1.
Si ottiene subito 'sto triangolo di Sierpinski («semplice come una colomba ma astuto come un sierpente», per dirla col Vangelo!)
0 | 1
1 | 1 1
2 | 1 0 1
3 | 1 1 1 1
4 |1 0 0 0 1
5 |1 1 0 0 1 1
6 |1 0 1 0 1 0 1
7 |1 1 1 1 1 1 1 1
8 |1 0 0 0 0 0 0 0 1
9 |1 1 0 0 0 0 0 0 1 1
...

Fermat aveva asserito che i suoi p(n) sono tutti primi [per ogni n naturale]. Ma un secolo dopo Eulero si è accorto che p(5) non è primo! Infatti
p(5) = 2^(2^5) + 1 = 2^32 + 1 = 4 294 967 297 = 641·6700417.
Lui non aveva la calcolatrice! E non era tanto masochista da tentare il crivello di Eratostene sul successivo p(6) = 2^64 + 1 [20 cifre decimali]; e quindi, se fosse primo, il provarlo richiederebbe di disporre già di tutti i primi minori di 2^32 ≈ 4,29 miliardi.
Ma oggi, col computer, si può cercare se ci sono altri p(n) primi per n ben maggiore di 6 (ma ... non troppo! I p(n) crescono sbalorditivamente con n ).
Con la potenza degli attuali computer, di p(n) primi con n > 4 non se sono trovati!
Si congettura, dunque, che i "primi di Fermat" siano solo quei cinque p(n) per n da 0 a 4 inclusi.
La questione resta aperta. E penso che non sia meno difficoltosa di quella del famoso "Ultimo Teorema di Fermat".

==========
Ritorniamo sul "problema di Gauß".
Dire che un poligono regolare è [teoricamente] "costruibile con riga e compasso" equivale a dire che il problema di determinare il coseno dell'angolo al centro sotteso ad un lato è un problema di 2° grado; ossia che tale numero è determinabile
• con una equazione o con un sistema [di equazioni] di 2° grado, oppure
• da una cascata di sistemi ciascuno dei quali è al massimo di 2° grado.

Sia allora N un numero [dispari] tale che la determinazione di
c(N) = cos(2π/N)
costituisca un "problema di 2° grado".
Gauß ha dimostrato che N deve essere
• un numero primo di Fermat, ossia essere primo e del tipo 2^(2^n) + 1, oppure
• prodotto di fattori primi semplici ciascuno dei quali è un "primo di Fermat"

Penso che il triangolo di Serpinski soddisfi indefinitamente la regola che i numeri in base 2 espressi dalle righe sono prodotti di fattori primi tutti semplici e tutti del tipo
p(n) = 2^(2^n) + 1
Purtroppo, però, (come per il numero di lati dei poligoni regolari), raggiunto il prossimo p(n), le righe esprimeranno prodotti contenenti fattori primi diversi da ogni p(n), e proprio dalla presenza del 641 che è fattore di 2^(2^5^ + 1.

Ricordo infine che
p(0)·p(1)·p(2)·p(3)·...·p(n–1) = p(n) – 2
E siccome p(n) – 1 è una potenza di 2, succede che (in notazione binaria):
• i p(n) sono di 2^n + 1 cifre (binarie), iniziano con 1, terminano con 1 e le altre cifre sono tutte 0.
• i p(n) – 2 sono di 2^n cifre tutte uguali a 1.

-------------
Miza e/o Luciano, che programmano (quasi) quotidianamente, ci mettono un attimo a prolungare il triangolo di Sierpinski fino alla riga Nr. 64.
A partire da dove mi sono fermato io e fino alla riga Nr. 32 esclusa dovrebbero trovare i prodotti dei fattori semplici di 2^32 – 1 che sono
[3, 5, 17, 257, 65537] {insieme dei primi 5 p(n), cioè dei 5 "primi di Fermat"}
in tutte le combinazioni possibili dei primi quattro e la presenza fissa del più grosso ( 65537).
Dopo la riga Nr. 17 , dovrebbero trovare una cosa analoga con l'aggiunta di i p(5) = 2^32 + 1 = 4294967297 al detto insieme di fattori: tutte le combinazioni possibili dei fattori dell'insieme
[3, 5, 17, 257, 65537]
con l'aggiunta del fattore fisso 4294967297, che però non è primo.

------------
__________________
Erasmus
«NO a nuovi trattati intergovernativi!»
«SI' alla "Costituzione Europea" federale, democratica e trasparente!»

Ultima modifica di Erasmus : 28-01-14 13:50. Motivo: Correzione errori di scrittura
Erasmus non in linea   Rispondi citando