La zeta di Fibonacci
Fra le serie di grosso interesse non c'è solo la zeta di Riemann. In realtà è possibile studiare qualsiasi serie inverso di determinati valori numerici generabili con una formula. Se i valori generabili sono i numeri di Fibonacci, allora traslando il tutto nel piano complesso, possiamo lavorare con la zeta di Fibonacci, definita come:
F(s) = suminf(k=1, 1.0/(fibonacci(k)^s))
Tale serie è di interesse sia per indagare nuovi metodi, sia per la sua somiglianza alla zeta di Riemann.
Essa è oggi studiata soprattutto nel mondo orientale; ed è difficile trovare su INTERNET materiale e informazioni su tale argomento, se non su libri da acquistare o su articoli tecnici riservati e a pagamento.
Un articolo libero per farvi rendere conto della problematica è al link:
http://www.gruppoeratostene.com/articoli/ZFRT.pdf
Buona lettura.
sabato 23 gennaio 2010
mercoledì 20 gennaio 2010
Guazzabugli palindromi
Guazzabugli palindromi
Sia a = (10^n+1)^k, con n>0 e k>0
I quesiti che ci poniamo sono:
1 che tipo di numero è a per ogni n e k?
2 quale è il numero di cifre nc che si ottiene?
3 nc dipende da n o da k?
4 quanto vale "a" senza fare calcoli, esiste
una regola?
Un metodo di indagine è quello numerico che aiuta subito a farsi delle idee. Per cui scriviamo qualche
riga di comando su PARI/GP del tipo:
k=1
for(n=1,4,a=(10^n+1)^k;if(isprime(a)==1,print1("Yes"));print(a));
poi variamo k e vediamo cosa otteniamo ripetendo le righe precedenti.
Scopriamo subito che possiamo rispondere alla prima domanda che possiamo ottenere numeri palindromi (non per tutti i valori di k) e non sempre numeri primi.
Un numero palindromo è un numero la cui metà è una versione riflessa rispetto ad un asse verticale. Se ad esempio scriviamo 10 e lo ribaltiamo in 01 e mettiamo insieme le cose otteniamo 1001 che è un numero palindromo.
Se usiamo la forma generatrice precedente per k=1 otteniamo:
11
101
1001
10001
E' n o k da cui dipende il numero di cifre nc? Nel seguito intendiamo con nc il valore del numero di cifre del primo numero che otterremo con n=1 e k fissato.
Ad esempio se poniamo k=2 e facciamo sempre variare n nel for tra 1 e 4 ci accorgiamo che dipende da k: nc = k+1.
Per k=2 otteniamo:
121
10201
1002001
100020001
121, il primo numero, è di nc=k+1=3 cifre difatti.
Per k=3 otteniamo:
1331
1030301
1003003001
1000300030001
Per k=4 otteniamo:
14641
104060401
1004006004001
10004000600040001
Per k=5 otteniamo:
161051
10510100501
1005010010005001
100050010001000050001
Da qui vediamo che la "palindromia" viene meno in alcuni casi a partire da k>4. Se nc è pari non c'è un valore centrale rispetto al quale c'è la riflessione. Se nc è dispari esiste un valore centrale o pivot.
Alcune regole che possiamo fissare sono le seguenti:
A) agli estremi esiste sia un 1 a destra che un 1 a sinistra.
B) il gruppo di zeri che appaiono sono n-1 ed il gruppo si ripete per ogni cifra non nulla per intervallarle. Se n=1 non ci sono zeri.
C) esiste una regola per passare dal numero ottenuto con n=1 e k=b al numero con n=1 k=b+1 in particolare si sommano le cifre del numero con n=1 e k=b aggiungendo alla fine un 1 a destra e sinistra
esempio n=1 e k=3
1 3 3 1
dalla destra:
3+1=4
3+3=6
1+3=4
numero ricavato:
1 4 6 4 1
D) esiste una regola per passare dal numero ottenuto con n=1 e k=b al numero con n=2 k=b
in particolare si aggiungono zeri in quantità pari a n-1
Esempio:
numero ricavato per n=1 e k=3
1 4 6 4 1
1 0 4 0 6 0 4 0 1
Esempi più complessi
n=1 k=4
1 4 6 4 1
n=1 k=5
Da destra è:
4+1=5
6+4=10 0 si scrive e si riporta 1
4+6=10 0 questa somma non si fa perchè nel caso nc dispari il pivot si somma una sola volta
1+4+1 il +1 è il resto del 10 precedente
1 6 1 0 5 1
Per n=1 e k=6
5+1=6
5+0=5
1+0=1
6+1=7
1+6=7
1 7 7 1 5 6 1
Per n=1 e k=7
6+1=7
5+6=11 1 si scrive e 1 di riporto
1+5+1=7
7+1=8
7+7=14 4 si scrive e 1 di riporto
1+7+1=9
1 9 4 8 7 1 7 1
Convinti?
Se vogliamo poi vedere quali sono numeri primi, nel caso che dobbiamo lavorare su molti numeri, allora vi consiglio di farli stampare prima su file da PARI/GP e poi usare WinPFGW.
Alla prox.
Sia a = (10^n+1)^k, con n>0 e k>0
I quesiti che ci poniamo sono:
1 che tipo di numero è a per ogni n e k?
2 quale è il numero di cifre nc che si ottiene?
3 nc dipende da n o da k?
4 quanto vale "a" senza fare calcoli, esiste
una regola?
Un metodo di indagine è quello numerico che aiuta subito a farsi delle idee. Per cui scriviamo qualche
riga di comando su PARI/GP del tipo:
k=1
for(n=1,4,a=(10^n+1)^k;if(isprime(a)==1,print1("Yes"));print(a));
poi variamo k e vediamo cosa otteniamo ripetendo le righe precedenti.
Scopriamo subito che possiamo rispondere alla prima domanda che possiamo ottenere numeri palindromi (non per tutti i valori di k) e non sempre numeri primi.
Un numero palindromo è un numero la cui metà è una versione riflessa rispetto ad un asse verticale. Se ad esempio scriviamo 10 e lo ribaltiamo in 01 e mettiamo insieme le cose otteniamo 1001 che è un numero palindromo.
Se usiamo la forma generatrice precedente per k=1 otteniamo:
11
101
1001
10001
E' n o k da cui dipende il numero di cifre nc? Nel seguito intendiamo con nc il valore del numero di cifre del primo numero che otterremo con n=1 e k fissato.
Ad esempio se poniamo k=2 e facciamo sempre variare n nel for tra 1 e 4 ci accorgiamo che dipende da k: nc = k+1.
Per k=2 otteniamo:
121
10201
1002001
100020001
121, il primo numero, è di nc=k+1=3 cifre difatti.
Per k=3 otteniamo:
1331
1030301
1003003001
1000300030001
Per k=4 otteniamo:
14641
104060401
1004006004001
10004000600040001
Per k=5 otteniamo:
161051
10510100501
1005010010005001
100050010001000050001
Da qui vediamo che la "palindromia" viene meno in alcuni casi a partire da k>4. Se nc è pari non c'è un valore centrale rispetto al quale c'è la riflessione. Se nc è dispari esiste un valore centrale o pivot.
Alcune regole che possiamo fissare sono le seguenti:
A) agli estremi esiste sia un 1 a destra che un 1 a sinistra.
B) il gruppo di zeri che appaiono sono n-1 ed il gruppo si ripete per ogni cifra non nulla per intervallarle. Se n=1 non ci sono zeri.
C) esiste una regola per passare dal numero ottenuto con n=1 e k=b al numero con n=1 k=b+1 in particolare si sommano le cifre del numero con n=1 e k=b aggiungendo alla fine un 1 a destra e sinistra
esempio n=1 e k=3
1 3 3 1
dalla destra:
3+1=4
3+3=6
1+3=4
numero ricavato:
1 4 6 4 1
D) esiste una regola per passare dal numero ottenuto con n=1 e k=b al numero con n=2 k=b
in particolare si aggiungono zeri in quantità pari a n-1
Esempio:
numero ricavato per n=1 e k=3
1 4 6 4 1
1 0 4 0 6 0 4 0 1
Esempi più complessi
n=1 k=4
1 4 6 4 1
n=1 k=5
Da destra è:
4+1=5
6+4=10 0 si scrive e si riporta 1
4+6=10 0 questa somma non si fa perchè nel caso nc dispari il pivot si somma una sola volta
1+4+1 il +1 è il resto del 10 precedente
1 6 1 0 5 1
Per n=1 e k=6
5+1=6
5+0=5
1+0=1
6+1=7
1+6=7
1 7 7 1 5 6 1
Per n=1 e k=7
6+1=7
5+6=11 1 si scrive e 1 di riporto
1+5+1=7
7+1=8
7+7=14 4 si scrive e 1 di riporto
1+7+1=9
1 9 4 8 7 1 7 1
Convinti?
Se vogliamo poi vedere quali sono numeri primi, nel caso che dobbiamo lavorare su molti numeri, allora vi consiglio di farli stampare prima su file da PARI/GP e poi usare WinPFGW.
Alla prox.
martedì 19 gennaio 2010
Numeri primi e WinPFGW
Numeri primi e WinPFGW
La prima cosa è scaricare il programma da INTERNET al link che vi ho segnalato al blog precedente; unzippare il tutto in una cartella e lanciare l'eseguibile WinPFGW.exe col click del mouse.
La prima cosa da imparare sono i comandi che possiamo digitare sulla "command line". Clicchiamo su Help, poi su Contents, poi mettiamo il check in Pfgwdoc.txt, clicchiamo su Print e stampiamo sul Desktop un file
di tipo .xps che chiamiamo Help. Otterremo un documento di help da consultare.
Un primo esempio di uso sono le "query" col comando -q, per verificare la primalità di un numero.
Verifichiamo ad esempio se è primo il numero 1+3*10^5825+100^5825. Scriviamo nella "command line" la riga:
-q1+3*10^5825+100^5825
e premiamo Start. Scopriremo che è un 3-PRP (un probabile primo). Se vogliamo salvare il nostro lavoro in append ad un file di nome work.txt scriveremo invece:
-q1+3*10^5825+100^5825 -lwork.txt (Vedi figura).
Se, invece, abbiamo molti numeri da fargli valutare apriamo un file di nome pfgw.txt nella stessa directory.
Usiamo ad esempio WordPad come editor e scriviamo:
2^3-1
2^31-1
3
7
6
e salviamolo
A questo punto lasciamo vuota la "command line". WinPFGW esaminerà il file e produrrà un file denominato pfgw-prime.txt dove metterà solo i numeri primi.
Di solito il file potrebbe essere generato da un Programma in PARI/GP. Ad esempio potremmo scrivere un file pfgw.txt che al variare di i da 1 a 100 calcola (10^i-1)^2 e siamo interessati a vedere quali sono i numeri primi. Il file prodotto lo dobbiamo però aprire prima in WordPad, che riconosce i "carriage return" di PARI/GP, e salvarlo. A questo punto il file lo possiamo dare in pasto a WinPFGW per controllare la primalità dei numeri prodotti. Semplice no?
Gli altri comandi e possibilità sperimentatele col doc di help.
Alla prox
La prima cosa è scaricare il programma da INTERNET al link che vi ho segnalato al blog precedente; unzippare il tutto in una cartella e lanciare l'eseguibile WinPFGW.exe col click del mouse.
La prima cosa da imparare sono i comandi che possiamo digitare sulla "command line". Clicchiamo su Help, poi su Contents, poi mettiamo il check in Pfgwdoc.txt, clicchiamo su Print e stampiamo sul Desktop un file
di tipo .xps che chiamiamo Help. Otterremo un documento di help da consultare.
Un primo esempio di uso sono le "query" col comando -q, per verificare la primalità di un numero.
Verifichiamo ad esempio se è primo il numero 1+3*10^5825+100^5825. Scriviamo nella "command line" la riga:
-q1+3*10^5825+100^5825
e premiamo Start. Scopriremo che è un 3-PRP (un probabile primo). Se vogliamo salvare il nostro lavoro in append ad un file di nome work.txt scriveremo invece:
-q1+3*10^5825+100^5825 -lwork.txt (Vedi figura).
Se, invece, abbiamo molti numeri da fargli valutare apriamo un file di nome pfgw.txt nella stessa directory.
Usiamo ad esempio WordPad come editor e scriviamo:
2^3-1
2^31-1
3
7
6
e salviamolo
A questo punto lasciamo vuota la "command line". WinPFGW esaminerà il file e produrrà un file denominato pfgw-prime.txt dove metterà solo i numeri primi.
Di solito il file potrebbe essere generato da un Programma in PARI/GP. Ad esempio potremmo scrivere un file pfgw.txt che al variare di i da 1 a 100 calcola (10^i-1)^2 e siamo interessati a vedere quali sono i numeri primi. Il file prodotto lo dobbiamo però aprire prima in WordPad, che riconosce i "carriage return" di PARI/GP, e salvarlo. A questo punto il file lo possiamo dare in pasto a WinPFGW per controllare la primalità dei numeri prodotti. Semplice no?
Gli altri comandi e possibilità sperimentatele col doc di help.
Alla prox
lunedì 18 gennaio 2010
Numeri primi: tools e linguaggi
Numeri primi: tools e linguaggi
Lo studio della Teoria dei Numeri, richiede non solo la conoscenza della teoria, ma anche sperimentazione numerica. Spesso essa è fatta con tools scaricabili da INTERNET, realizzati da gruppi internazionali di studio, oppure implementabili con le proprie mani con un linguaggio matematico adeguato. Vi segnalo una serie di risorse indispensabili, a volte free e ottenibili da INTERNET.
Per i linguaggi il problema fondamentale è disporre di un linguaggio capace di trattare numeri con moltissime cifre, possibilmente senza limiti molto bassi sul numero di cifre e con una ottima velocità di esecuzione. Se non ha questa caratteristica lo sforzo per programmare non vale la candela. A volte sono necessari computer a 64 bit, ma nella maggior parte dei casi è sufficiente un linguaggio con adeguate librerie software (e un PC a 32 bit), che permetta di trattare tali numeri, anche se, spesso un pò a discapito della semplicità e della chiarezza, a causa delle funzionalità fornite dalla libreria. Ovviamente se l'obiettivo è di grande valore la difficoltà passa in secondo piano. Sia i tools, sia i linguaggi che i CAS permettono grafici 2D e 3D (zeta di Riemann, grafici di funzione, etc).
Linguaggi consigliabili
- GMP Arithmetic without limitations
http://www.gmplib.org/
E' un linguaggio C-like, con una sua libreria che permette di poter lavorare con numeri interi di grosse dimensioni. Ha una ottima velocità di esecuzione, tale da essere superiore a tanti altri linguaggi (compreso PARI/GP), ma a discapito della chiarezza di programmazione. Lo preferisco quando mi è chiaro l'algoritmo, il problema o la congettura perchè l'ho provata, ad esempio, prima con PARI/GP, su numero di cifre più bassi.
Quando però si ha a che fare con numeri molto grandi, il tempo di elaborazione aumenta ed avere un linguaggio veloce e poi un PC veloce (frequenza di clock) aiuta molto. Spesso i programmi si possono compilare in modo da sfruttare al massimo anche l'architettura hardware disponibile (AMD, INTEL, etc)
Poi dipende anche dal problema che si affronta, se si può lavorare in parallelo, allora avere un PC del tipo Core 2 Quad o superiore e a 64 bit, questo ci migliora la qualità della vita!
Un avvertimento classico sulle congetture: attenzione che spesso le più belle congetture si infrangono su numeri di moltissime cifre! Non provatele solo su numeri bassi.
- PARI/GP
http://pari.math.u-bordeaux.fr/
E' un linguaggio di scripting di matematica che permette, grazie a molte funzionalità, di poter scrivere programmi di test per le proprie prove, congetture e calcoli. Spesso è preferibile realizzare prima l'algoritmo in PARI/GP, che richiede meno tempo, meno complicazioni e maggiore linearità per fare la verifica delle proprie idee, per poi realizzare successivamente il tutto con GMP per poter lavorare con numeri grandissimi, maggiore velocità e minor impegno di RAM.
- WinHugs
http://www.haskell.org/haskellwiki/WinHugs
E' un linguaggio funzionale di programmazione, per chi è più attratto dalla notazione matematica come programmazione.Ha minori prestazioni rispetto ai primi due.
CAS
Poi esistono tool di calcolo e di grafica, definiti CAS=Computer Aided System, per calcolare derivate, integrali, espressioni etc. come:
- Maxima
http://maxima.sourceforge.net/
Eccellente
- R
http://www.r-project.org/
Eccellente
Motori
Esistono anche motori che permettono di valutare equazioni ed espressioni come quello Wolfram. La scelta di uno di essi dipende anche dal tipo di problema da affrontare.
Tools analisi numerica per recordman
I tools per l'analisi dei numeri primi, composti, di Mersenne, di Fermat, di Proth etc, sono quelli di maggiore fascino per i recordman.
Nel seguito vi segnalo dei siti, che di solito danno anche informazioni sull'utilizzo o sui numeri che può ricercare. In ogni caso vi consiglio un pò di pratica.
A che possono servire?
- a verificare se un numero è primo se non si dispone di un sito su cui verificare
- a creare liste di numeri che rispettano delle regole (palinfromi, formule, etc)
per dare la lista ottenuta in pasto ad un successivo tool per determinare se nella lista
c'è un numero primo
Ecco una lista molto valida, di tolls veri 'coltellini svizzeri' del ricercatore di matematica applicata o dell'informatico e del recordman:
- WinPFGW
http://www.fermatsearch.org/download.html
- NewPGen
http://primes.utm.edu/programs/NewPGen/
Se cerchiamo grandi numeri primi della forma kb^n +1 o kb^n -1; oppure coppie di numeri gemelli molto grandi, o di Sophie Germain primes, o una catena di lunghezza due. In poche parole è un 'setacciatore'. Può servire per creare liste di 'numeri candidati primi' di un certo tipo da sottoporre ad altri tools.
- Proth
http://primes.utm.edu/programs/gallot/
Implementazione del Teorema di Proth per la ricerca di primi nella forma Proth
Si può sfruttare NewPGen per creare una lista da dare in pasto poi a Proth
Teorema di Proth (1878): Sia N = k2^n + 1 with 2^n > k. Se vi è un intero a tale che
a^((N-1)/2) = -1 (mod N),
allora N is prime.
E' un test utile : si applica ai primi di Cullen, ai fattori di Fermat, ai primi della congettura di Sierpinski etc.
- Primeform
http://pages.prodigy.net/chris_nash/primeform.html#Download
Per trovare Probable Prime
- FermFact
http://www.fermatsearch.org
Per i numeri di Fermat
- Generalized Fermat Prime search
http://pagesperso-orange.fr/yves.gallot/primes/download.html
- Primo oppure New Primo
http://www.ellipsa.eu/
Primalità de numeri, Basato sulle curve ECPP
Alla prox
Lo studio della Teoria dei Numeri, richiede non solo la conoscenza della teoria, ma anche sperimentazione numerica. Spesso essa è fatta con tools scaricabili da INTERNET, realizzati da gruppi internazionali di studio, oppure implementabili con le proprie mani con un linguaggio matematico adeguato. Vi segnalo una serie di risorse indispensabili, a volte free e ottenibili da INTERNET.
Per i linguaggi il problema fondamentale è disporre di un linguaggio capace di trattare numeri con moltissime cifre, possibilmente senza limiti molto bassi sul numero di cifre e con una ottima velocità di esecuzione. Se non ha questa caratteristica lo sforzo per programmare non vale la candela. A volte sono necessari computer a 64 bit, ma nella maggior parte dei casi è sufficiente un linguaggio con adeguate librerie software (e un PC a 32 bit), che permetta di trattare tali numeri, anche se, spesso un pò a discapito della semplicità e della chiarezza, a causa delle funzionalità fornite dalla libreria. Ovviamente se l'obiettivo è di grande valore la difficoltà passa in secondo piano. Sia i tools, sia i linguaggi che i CAS permettono grafici 2D e 3D (zeta di Riemann, grafici di funzione, etc).
Linguaggi consigliabili
- GMP Arithmetic without limitations
http://www.gmplib.org/
E' un linguaggio C-like, con una sua libreria che permette di poter lavorare con numeri interi di grosse dimensioni. Ha una ottima velocità di esecuzione, tale da essere superiore a tanti altri linguaggi (compreso PARI/GP), ma a discapito della chiarezza di programmazione. Lo preferisco quando mi è chiaro l'algoritmo, il problema o la congettura perchè l'ho provata, ad esempio, prima con PARI/GP, su numero di cifre più bassi.
Quando però si ha a che fare con numeri molto grandi, il tempo di elaborazione aumenta ed avere un linguaggio veloce e poi un PC veloce (frequenza di clock) aiuta molto. Spesso i programmi si possono compilare in modo da sfruttare al massimo anche l'architettura hardware disponibile (AMD, INTEL, etc)
Poi dipende anche dal problema che si affronta, se si può lavorare in parallelo, allora avere un PC del tipo Core 2 Quad o superiore e a 64 bit, questo ci migliora la qualità della vita!
Un avvertimento classico sulle congetture: attenzione che spesso le più belle congetture si infrangono su numeri di moltissime cifre! Non provatele solo su numeri bassi.
- PARI/GP
http://pari.math.u-bordeaux.fr/
E' un linguaggio di scripting di matematica che permette, grazie a molte funzionalità, di poter scrivere programmi di test per le proprie prove, congetture e calcoli. Spesso è preferibile realizzare prima l'algoritmo in PARI/GP, che richiede meno tempo, meno complicazioni e maggiore linearità per fare la verifica delle proprie idee, per poi realizzare successivamente il tutto con GMP per poter lavorare con numeri grandissimi, maggiore velocità e minor impegno di RAM.
- WinHugs
http://www.haskell.org/haskellwiki/WinHugs
E' un linguaggio funzionale di programmazione, per chi è più attratto dalla notazione matematica come programmazione.Ha minori prestazioni rispetto ai primi due.
CAS
Poi esistono tool di calcolo e di grafica, definiti CAS=Computer Aided System, per calcolare derivate, integrali, espressioni etc. come:
- Maxima
http://maxima.sourceforge.net/
Eccellente
- R
http://www.r-project.org/
Eccellente
Motori
Esistono anche motori che permettono di valutare equazioni ed espressioni come quello Wolfram. La scelta di uno di essi dipende anche dal tipo di problema da affrontare.
Tools analisi numerica per recordman
I tools per l'analisi dei numeri primi, composti, di Mersenne, di Fermat, di Proth etc, sono quelli di maggiore fascino per i recordman.
Nel seguito vi segnalo dei siti, che di solito danno anche informazioni sull'utilizzo o sui numeri che può ricercare. In ogni caso vi consiglio un pò di pratica.
A che possono servire?
- a verificare se un numero è primo se non si dispone di un sito su cui verificare
- a creare liste di numeri che rispettano delle regole (palinfromi, formule, etc)
per dare la lista ottenuta in pasto ad un successivo tool per determinare se nella lista
c'è un numero primo
Ecco una lista molto valida, di tolls veri 'coltellini svizzeri' del ricercatore di matematica applicata o dell'informatico e del recordman:
- WinPFGW
http://www.fermatsearch.org/download.html
- NewPGen
http://primes.utm.edu/programs/NewPGen/
Se cerchiamo grandi numeri primi della forma kb^n +1 o kb^n -1; oppure coppie di numeri gemelli molto grandi, o di Sophie Germain primes, o una catena di lunghezza due. In poche parole è un 'setacciatore'. Può servire per creare liste di 'numeri candidati primi' di un certo tipo da sottoporre ad altri tools.
- Proth
http://primes.utm.edu/programs/gallot/
Implementazione del Teorema di Proth per la ricerca di primi nella forma Proth
Si può sfruttare NewPGen per creare una lista da dare in pasto poi a Proth
Teorema di Proth (1878): Sia N = k2^n + 1 with 2^n > k. Se vi è un intero a tale che
a^((N-1)/2) = -1 (mod N),
allora N is prime.
E' un test utile : si applica ai primi di Cullen, ai fattori di Fermat, ai primi della congettura di Sierpinski etc.
- Primeform
http://pages.prodigy.net/chris_nash/primeform.html#Download
Per trovare Probable Prime
- FermFact
http://www.fermatsearch.org
Per i numeri di Fermat
- Generalized Fermat Prime search
http://pagesperso-orange.fr/yves.gallot/primes/download.html
- Primo oppure New Primo
http://www.ellipsa.eu/
Primalità de numeri, Basato sulle curve ECPP
Alla prox
domenica 3 gennaio 2010
Fibonacci e dintorni
Proseguiamo con qualche altra strabiliante cosa legata ai numeri di Fibonacci.
Triangoli pitagorici
Charles Raine trovò che se si considerano 4 numeri di Fibonacci di seguito Fk,Fk+1,Fk+2,Fk+3
e consideriamo un triangolo rettangolo con cateti a, b e ipotenusa c, allora è:
a=Fk*Fk+3
b=2*(Fk+1*Fk+2)
c^2 = a^2+b^2
esaminiamo ad esempio la sequenza di Fibonacci:
1,1,2,3,5,8,13,21,34,...
Se prendiamo ..3,5,8,13,...
a=3*13=39
b=2(5*8)=80
c=89
P. Simson, matematico scozzese, trovò invece che:
Fk-1Fk+1-Fk^2=(-1)^k
Catalan, invece, che:
2^(n-1)Fn = Sum(i=0,n,5^i* (n i) )
dove (n i) per semplicità di notazione è il coefficiente binomiale.
Lo so, la formula di Catalan vi ricorda i numeri primi di Mersenne! Purtroppo la primalità dei numeri di Mersenne non è legabile alla primabilità dei numeri di Fibonacci. Ad esempio se poniamo che:
n-1=p n=p+1 con p numero primo allora è:
2^p - 1 = [1/Fp+1 Sum ( i=0, p+1,5^i * (p+1 i) )] -1
Se 2^p - 1 = Mp è primo allora p è primo e non è vero il contrario.
Per i numeri di Fibonacci se l'indice è primo è primo anche il valore Fn.
Ora le domande sono:
1 Se Mp è primo è primo anche Fp+1?
2 Se Fp+1 è primo lo è anche Mp?
Risposta alla prima domanda: Non sempre .
La serie di Fibonacci è tale che
F(0)=0, F(1)=1 e F(k)=F(k-1)+F(k-2)
quindi:
1,1,2,3,5,8,13,21,34,...
Se p=3 Mp=7 primo allora Fp+1=F4=3 primo
Se p=5 Mp=31 primo allora Fp+1=F6=8 NON PRIMO! (contro-esempio)
Quindi non ha senso nemmeno la seconda domanda se non è verificata la prima.
Diversi contributi dell'autore sono su:
http://it.wikipedia.org/wiki/Successione_di_Fibonacci
In tale contributo c'è anche come la primalità di un numero di Mersenne è legata invece a quello di un numero di Fibonacci.
Alla prox
Triangoli pitagorici
Charles Raine trovò che se si considerano 4 numeri di Fibonacci di seguito Fk,Fk+1,Fk+2,Fk+3
e consideriamo un triangolo rettangolo con cateti a, b e ipotenusa c, allora è:
a=Fk*Fk+3
b=2*(Fk+1*Fk+2)
c^2 = a^2+b^2
esaminiamo ad esempio la sequenza di Fibonacci:
1,1,2,3,5,8,13,21,34,...
Se prendiamo ..3,5,8,13,...
a=3*13=39
b=2(5*8)=80
c=89
P. Simson, matematico scozzese, trovò invece che:
Fk-1Fk+1-Fk^2=(-1)^k
Catalan, invece, che:
2^(n-1)Fn = Sum(i=0,n,5^i* (n i) )
dove (n i) per semplicità di notazione è il coefficiente binomiale.
Lo so, la formula di Catalan vi ricorda i numeri primi di Mersenne! Purtroppo la primalità dei numeri di Mersenne non è legabile alla primabilità dei numeri di Fibonacci. Ad esempio se poniamo che:
n-1=p n=p+1 con p numero primo allora è:
2^p - 1 = [1/Fp+1 Sum ( i=0, p+1,5^i * (p+1 i) )] -1
Se 2^p - 1 = Mp è primo allora p è primo e non è vero il contrario.
Per i numeri di Fibonacci se l'indice è primo è primo anche il valore Fn.
Ora le domande sono:
1 Se Mp è primo è primo anche Fp+1?
2 Se Fp+1 è primo lo è anche Mp?
Risposta alla prima domanda: Non sempre .
La serie di Fibonacci è tale che
F(0)=0, F(1)=1 e F(k)=F(k-1)+F(k-2)
quindi:
1,1,2,3,5,8,13,21,34,...
Se p=3 Mp=7 primo allora Fp+1=F4=3 primo
Se p=5 Mp=31 primo allora Fp+1=F6=8 NON PRIMO! (contro-esempio)
Quindi non ha senso nemmeno la seconda domanda se non è verificata la prima.
Diversi contributi dell'autore sono su:
http://it.wikipedia.org/wiki/Successione_di_Fibonacci
In tale contributo c'è anche come la primalità di un numero di Mersenne è legata invece a quello di un numero di Fibonacci.
Alla prox
venerdì 1 gennaio 2010
Giochiamo con i numeri di Fibonacci
Iniziamo ad esaminare un tema apparentemente semplice ma che ha ancora vasti settori in cui indagare ulteriormente: i numeri di Fibonacci.
Numeri di Fibonacci classici
I numeri di Fibonacci sono i numeri della successione di Fibonacci:
0, 1, 1, 2, 3, 5, 8, 13, 21,. . . . . ciascuno dei quali, dopo il secondo è la somma dei due precedenti.
In generale è:
F(0)=0
F(1)=1
F(k)= F(k-1)+F(k-2)
I numeri di Fibonacci possono anche essere considerati come una funzione di numeri interi non negativi:
n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
F (n) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
La soluzione esatta in forma chiusa per questa funzione è chiamata "formula di Binet":
F (n) = (Phi ^ n - Phip ^ n) / sqrt (5) (per tutti intero n> = 0 oppure n <0),
dove
Phi = (1 + sqrt (5)) / 2 = 1,61803398874989484820 ... (Golden Ratio)
Phip = Phi Prime = (1 - sqrt (5)) / 2 = 1 - Phi = -1/Phi = -0,61803398874989484820 ...,
Poiché F (k) è un intero e l'entità delle Phip ^ n / sqrt (5) è inferiore a 1 / 2 per n> = 0,
una forma variante della formula è:
F(k) = ceil (Phi ^ n / sqrt (5)), n> = 0.
Se si dispone di un numero di Fibonacci si può calcolare il suo indice: k = indFib (F (k))
La formula è la seguente:
indFib(k) = 0 if |k| < 1, altrimenti
iindFib(k) = ceil (Log (sqrt (5) * abs( k )) / Log (Phi)).
Ad esempio, indFib (144) = 12. E' accurata se k è un numero di Fibonacci.
Un numero di Fibonacci si verifica con isFib (k)
Un numero di Fibonacci deve essere un numero intero e si deve ottenere un quadrato perfetto da 5 * x ^ 2 + 4 o 5 * x ^ 2 - 4.
I numeri di Fibonacci possono essere definiti anche per n negativi:
F(–2*k) = –F(2*k) F (-2 * k) =-F (2 * k)
F(–2*k – 1) = F(2*k + 1) F (-2 * k - 1) F = (2 * k + 1)
n = ..., –6, –5, –4, –3, –2, –1, 0, 1, 2, 3, 4, 5, 6, ...
F(n) = ..., –8, 5, –3, 2, –1, 1, 0, 1, 1, 2, 3, 5, 8, ...
La funzione continua analitica:
Fe(x) = (Phi^x – 1 / Phi^x) / Sqrt(5),
passa attraverso tutti i numeri di Fibonacci, anche n = x (n positivo o negativo).
La funzione continua analitica:
Fo (x) = (Phi ^ x + 1 / Phi ^ x) / sqrt (5),
passa attraverso tutti i numeri di Fibonacci di n dispari = x (n positivo o negativo).
La funzione continua analitica:
Fib(x) = (1 + cos(x*Pi))*Fe(x)/2 + (1 – cos(x*Pi))*Fo(x)/2,
passa attraverso tutti i numeri di Fibonacci per ogni n = x (n positivo o negativo).
Questa ultima espressione può essere ridotta a:
Fib(x) = (Phi^x – cos(x*Pi) / Phi^x) / sqrt(5)
Questa formula può anche essere usato per calcolare la funzione di Fibonacci generalizzata di una
variabile complessa.Ad esempio:
Fib (3 + 4 * i) = -5248.51130,72837,20182,8 ... -14195.96228,83530,10885,8 ... * i. * I.
E' pur vero che Fib (x 2) = Fib (x 1) + Fib (x).
Ad esempio Fib (3,6 + 4,7 * i) = Fib (2,6 + 4,7 * i) + Fib (1.6 + 4.7 * I).
Numeri complessi di Fibonacci
Un numero complesso di Fibonacci è un numero complesso z la cui parte reale Re(z) è un numero di Fibonacci F(k).
Ad esempio z=8-i è un numero complesso di Fibonacci perchè Re(z)=8=F(6).
Proprietà dei numeri complessi di Fibonacci
Il rapporto di numeri complessi di Fibonacci con k dispari e n > 0 è tale che:
[F(k) - n*i] / [F(k-1)-(n-1)*i] = [F(k+n)+i*(-1)^(n-1)] / [F(k+(n-1)]
dove F(k+n)=Sum(i=k+1,n-1,F(i))
Ad esempio:
(5 - i ) / 3-i = 8 + i / 5
(13 - i ) / 8-i = 21 + i / 13
(8 - 2i) / (5 - i) = (21 - i) / 13
(13 - 3i)/(8 - 2i) = (55 + i)/34 (13 - 3i) / (8 - 2i) = (55 + i) / 34
Per k pari e n > 0 la formula non vale per i numeri complessi ma solo per i numeri interi sostituendo 1 a i,
ovvero:
[F(k) - n] / [F(k-1)-(n-1)] = [F(k+n)+(-1)^(n-1)] / [F(k+(n-1)]
dove F(k+n)=Sum(i=k+1,n-1,F(i))
(8 - 1) / (5 - 1) = (13 + 1) / 8.
(13 - 2) / 8 - 1) = (34 - 1) / 21
(8 - 3)/(5 - 2) = (34 + 1)/21 (8 - 3) / (5 - 2) = (34 + 1) / 21
Legame con il triangolo di Tartaglia o con i coefficienti binomiali
Il triangolo di Tartaglia o di Pascal è noto. Ebbene se si considerano le diagonali che dall'alto a destra scendono verso sinistra si individuano i numeri di Fibonacci.
La relazione esistente è difatti:
Fib(n)= Sum(k=0,n-1,(n-k-1 k) ) = Sum(k=1,n,(n-k k-1) )
dove per semplicità la notazione (n-k-1 k) rappresenta un coefficiente binomiale
Teorema
Ogni numero di Fibonacci è un fattore di (un numero infinito di) numeri di Fibonacci successivi oppure ogni k-th numero di Fibonacci è un multiplo di F (k)". E' equivalente a dire matematicamente che:
Se Fib(k) = m allora Fib(n*k) = t con m|t
Si dimostra in due modi possibili:
1.mo modo:
Dai coefficienti binomiali
Fib(k) = Sum(i=1,k-1, (k-i i-1) ) = m
Fib(n*k) = Sum(i=1,n*k-1, (n*k-i i-1) ) = t
2.do modo:
Costruiamo una tabella mettendo x se il risultato m di m=Fib(k) non è un divisore di Fib(k) e * se lo è:
i 3 4 5 6 7 8 9 10 11 12
Fib(i) 2 3 5 8 13 21 34 55 89 144
2=Fib(3) * x x * x x * x x *
3=Fib(4) x * x x x * x x x *
5=Fib(5) x x * x x x x * x x
Proseguendo si vede ad esempio che:
- 2 è un fattore ogni 3 Fib(k)
- 3 è un fattore ogni 4 Fib(k)
- 5 è un fattore ogni 5 Fib(k)
etc
Teorema
I numeri di Fibonacci vicini non hanno fattori in comune oppure Fib (k) e Fib (k +1) sono coprimi.
Se Fib(k)=m*a e Fib(k+1)=m*b per assurdo allora Fib(k+2)=Fib(k)+Fib(k+1)=m*(a+b)
Il che vorrebbe dire che tutta la serie di Fibonacci dovrebbe avrebbe lo stesso fattore m in comune,
il che non è vero.
=== Teorema di Vorob’ev ===
gcd( F(m), F(n) ) = F( gcd(m,n) )
Numeri di Fibonacci primi
Come corollario di prima, se l'indice di un numero di Fibonacci è un multiplo di k, il numero di Fibonacci è composto.
Se il numero di Fibonacci è un primo lo è anche l'indice.
Non è vero il contrario. Infatti ad esempio
F (19) = 4.181 e F (19) non è primo perché 113x37 = 4.181
Il più grande numero primo di Fibonacci F (81.839) è stato segnalato in aprile 2001 da David Broadbent e Bouk de Water.
La serie di numeri indice dei numeri primi di Fibonacci è A001605 Sloane
Numeri di Fibonacci e fattori primi speciali
Se guardiamo i fattori primi di un numero di Fibonacci, ci sarà almeno uno di loro che non è mai apparso come un fattore in ogni numero di Fibonacci in precedenza.
Questo è noto come teorema di Carmichael e si applica a tutti i numeri di Fibonacci, tranne casi particolari:
Fib (1) = 1 (non ha fattori primi),
Fib (2) = 1 (non ha fattori primi),
Fib (6) = 8, che ha solo il fattore primo 2, che è anche Fib (3),
Fib (12) = 144, che anche solo il 2 e 3, come i suoi fattori primi e questi sono apparsi in precedenza come Fib (3) = 2 e Fib (4) = 3.
Alla prox
Numeri di Fibonacci classici
I numeri di Fibonacci sono i numeri della successione di Fibonacci:
0, 1, 1, 2, 3, 5, 8, 13, 21,. . . . . ciascuno dei quali, dopo il secondo è la somma dei due precedenti.
In generale è:
F(0)=0
F(1)=1
F(k)= F(k-1)+F(k-2)
I numeri di Fibonacci possono anche essere considerati come una funzione di numeri interi non negativi:
n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
F (n) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
La soluzione esatta in forma chiusa per questa funzione è chiamata "formula di Binet":
F (n) = (Phi ^ n - Phip ^ n) / sqrt (5) (per tutti intero n> = 0 oppure n <0),
dove
Phi = (1 + sqrt (5)) / 2 = 1,61803398874989484820 ... (Golden Ratio)
Phip = Phi Prime = (1 - sqrt (5)) / 2 = 1 - Phi = -1/Phi = -0,61803398874989484820 ...,
Poiché F (k) è un intero e l'entità delle Phip ^ n / sqrt (5) è inferiore a 1 / 2 per n> = 0,
una forma variante della formula è:
F(k) = ceil (Phi ^ n / sqrt (5)), n> = 0.
Se si dispone di un numero di Fibonacci si può calcolare il suo indice: k = indFib (F (k))
La formula è la seguente:
indFib(k) = 0 if |k| < 1, altrimenti
iindFib(k) = ceil (Log (sqrt (5) * abs( k )) / Log (Phi)).
Ad esempio, indFib (144) = 12. E' accurata se k è un numero di Fibonacci.
Un numero di Fibonacci si verifica con isFib (k)
Un numero di Fibonacci deve essere un numero intero e si deve ottenere un quadrato perfetto da 5 * x ^ 2 + 4 o 5 * x ^ 2 - 4.
I numeri di Fibonacci possono essere definiti anche per n negativi:
F(–2*k) = –F(2*k) F (-2 * k) =-F (2 * k)
F(–2*k – 1) = F(2*k + 1) F (-2 * k - 1) F = (2 * k + 1)
n = ..., –6, –5, –4, –3, –2, –1, 0, 1, 2, 3, 4, 5, 6, ...
F(n) = ..., –8, 5, –3, 2, –1, 1, 0, 1, 1, 2, 3, 5, 8, ...
La funzione continua analitica:
Fe(x) = (Phi^x – 1 / Phi^x) / Sqrt(5),
passa attraverso tutti i numeri di Fibonacci, anche n = x (n positivo o negativo).
La funzione continua analitica:
Fo (x) = (Phi ^ x + 1 / Phi ^ x) / sqrt (5),
passa attraverso tutti i numeri di Fibonacci di n dispari = x (n positivo o negativo).
La funzione continua analitica:
Fib(x) = (1 + cos(x*Pi))*Fe(x)/2 + (1 – cos(x*Pi))*Fo(x)/2,
passa attraverso tutti i numeri di Fibonacci per ogni n = x (n positivo o negativo).
Questa ultima espressione può essere ridotta a:
Fib(x) = (Phi^x – cos(x*Pi) / Phi^x) / sqrt(5)
Questa formula può anche essere usato per calcolare la funzione di Fibonacci generalizzata di una
variabile complessa.Ad esempio:
Fib (3 + 4 * i) = -5248.51130,72837,20182,8 ... -14195.96228,83530,10885,8 ... * i. * I.
E' pur vero che Fib (x 2) = Fib (x 1) + Fib (x).
Ad esempio Fib (3,6 + 4,7 * i) = Fib (2,6 + 4,7 * i) + Fib (1.6 + 4.7 * I).
Numeri complessi di Fibonacci
Un numero complesso di Fibonacci è un numero complesso z la cui parte reale Re(z) è un numero di Fibonacci F(k).
Ad esempio z=8-i è un numero complesso di Fibonacci perchè Re(z)=8=F(6).
Proprietà dei numeri complessi di Fibonacci
Il rapporto di numeri complessi di Fibonacci con k dispari e n > 0 è tale che:
[F(k) - n*i] / [F(k-1)-(n-1)*i] = [F(k+n)+i*(-1)^(n-1)] / [F(k+(n-1)]
dove F(k+n)=Sum(i=k+1,n-1,F(i))
Ad esempio:
(5 - i ) / 3-i = 8 + i / 5
(13 - i ) / 8-i = 21 + i / 13
(8 - 2i) / (5 - i) = (21 - i) / 13
(13 - 3i)/(8 - 2i) = (55 + i)/34 (13 - 3i) / (8 - 2i) = (55 + i) / 34
Per k pari e n > 0 la formula non vale per i numeri complessi ma solo per i numeri interi sostituendo 1 a i,
ovvero:
[F(k) - n] / [F(k-1)-(n-1)] = [F(k+n)+(-1)^(n-1)] / [F(k+(n-1)]
dove F(k+n)=Sum(i=k+1,n-1,F(i))
(8 - 1) / (5 - 1) = (13 + 1) / 8.
(13 - 2) / 8 - 1) = (34 - 1) / 21
(8 - 3)/(5 - 2) = (34 + 1)/21 (8 - 3) / (5 - 2) = (34 + 1) / 21
Legame con il triangolo di Tartaglia o con i coefficienti binomiali
Il triangolo di Tartaglia o di Pascal è noto. Ebbene se si considerano le diagonali che dall'alto a destra scendono verso sinistra si individuano i numeri di Fibonacci.
La relazione esistente è difatti:
Fib(n)= Sum(k=0,n-1,(n-k-1 k) ) = Sum(k=1,n,(n-k k-1) )
dove per semplicità la notazione (n-k-1 k) rappresenta un coefficiente binomiale
Teorema
Ogni numero di Fibonacci è un fattore di (un numero infinito di) numeri di Fibonacci successivi oppure ogni k-th numero di Fibonacci è un multiplo di F (k)". E' equivalente a dire matematicamente che:
Se Fib(k) = m allora Fib(n*k) = t con m|t
Si dimostra in due modi possibili:
1.mo modo:
Dai coefficienti binomiali
Fib(k) = Sum(i=1,k-1, (k-i i-1) ) = m
Fib(n*k) = Sum(i=1,n*k-1, (n*k-i i-1) ) = t
2.do modo:
Costruiamo una tabella mettendo x se il risultato m di m=Fib(k) non è un divisore di Fib(k) e * se lo è:
i 3 4 5 6 7 8 9 10 11 12
Fib(i) 2 3 5 8 13 21 34 55 89 144
2=Fib(3) * x x * x x * x x *
3=Fib(4) x * x x x * x x x *
5=Fib(5) x x * x x x x * x x
Proseguendo si vede ad esempio che:
- 2 è un fattore ogni 3 Fib(k)
- 3 è un fattore ogni 4 Fib(k)
- 5 è un fattore ogni 5 Fib(k)
etc
Teorema
I numeri di Fibonacci vicini non hanno fattori in comune oppure Fib (k) e Fib (k +1) sono coprimi.
Se Fib(k)=m*a e Fib(k+1)=m*b per assurdo allora Fib(k+2)=Fib(k)+Fib(k+1)=m*(a+b)
Il che vorrebbe dire che tutta la serie di Fibonacci dovrebbe avrebbe lo stesso fattore m in comune,
il che non è vero.
=== Teorema di Vorob’ev ===
gcd( F(m), F(n) ) = F( gcd(m,n) )
Numeri di Fibonacci primi
Come corollario di prima, se l'indice di un numero di Fibonacci è un multiplo di k, il numero di Fibonacci è composto.
Se il numero di Fibonacci è un primo lo è anche l'indice.
Non è vero il contrario. Infatti ad esempio
F (19) = 4.181 e F (19) non è primo perché 113x37 = 4.181
Il più grande numero primo di Fibonacci F (81.839) è stato segnalato in aprile 2001 da David Broadbent e Bouk de Water.
La serie di numeri indice dei numeri primi di Fibonacci è A001605 Sloane
Numeri di Fibonacci e fattori primi speciali
Se guardiamo i fattori primi di un numero di Fibonacci, ci sarà almeno uno di loro che non è mai apparso come un fattore in ogni numero di Fibonacci in precedenza.
Questo è noto come teorema di Carmichael e si applica a tutti i numeri di Fibonacci, tranne casi particolari:
Fib (1) = 1 (non ha fattori primi),
Fib (2) = 1 (non ha fattori primi),
Fib (6) = 8, che ha solo il fattore primo 2, che è anche Fib (3),
Fib (12) = 144, che anche solo il 2 e 3, come i suoi fattori primi e questi sono apparsi in precedenza come Fib (3) = 2 e Fib (4) = 3.
Alla prox
Iscriviti a:
Post (Atom)
Post
