Newsgroup: it.hobby.enigmi
Titolo: primi e fibonacci

Considera la normale sequenza di Fibonacci 1,1,2,3,5,8,13,21,..
E' vero che ogni numero primo divide almeno un termine della successione?
Per esempio 7 divide 21, l'ottavo numero di fibonacci.
Ciao, Silv:o)

...


 Ho sentito solo parlare di questa "sequenza fibonacci"....ma cos'è?
La succesione di Fibonacci comincia due 1 ed ogni termine successivo e' la
somma dei due precedenti.
1, 1, 2(1+1), 3(1+2), 5(2+3), 8 ecc.
Ciao, Silv:o)

Per esempio 7 divide 21, l'ottavo numero di fibonacci.
Non ho la dimostrazione, ma solo una constatazione:
per ogni numero primo p, si trova un multiplo entro i primi
p+1 termini della sequenza di Fibonacci
per esempio
p=7 e' divisore di F_8=21
p=23 e' divisore di F_24=46368
p=11 e' divisore di F_10=55
ciao
paolo

 wrote:
: Non ho la dimostrazione, ma solo una constatazione:
: per ogni numero primo p, si trova un multiplo entro i primi
: p+1 termini della sequenza di Fibonacci
Un ragazzo intelligente potrebbe usare quello che hai scritto come un
ottimo aiutino.
ciao, .mau.

Ho capito perfettamente, grazie!
Ma ora ti (vi) chiedo: che particolarità ha questa serie? A che vantaggi
porta? Chi la conosce a cosa gli potrebbe servire?
così a naso non mi sembra ninete di particolare...potrei inventare serie
infinite in quel modo:
1,2,3,6,11,20,27,....   giusto?

 Ciao, Silv:o)
Non solo, a me sembra che se p è primo, p divida
sempre F_(p+1) exor F_(p-1) :
11 : F_10 = 55   = 11*5
13 : F_14 = 377  = 13*29
17 : F_18 = 2584 = 17*19*2*2*2
19 : idem
23 : F_24 =46368 = 23*7*3*3*2*2*2
...
Crios

 p divida sempre F_(p+1) exor F_(p-1) :
Anche Paolo l'ha notato, e Maurizio dice che e' un bell'aiuto per la
dimostrazione. Ma gia' l'avevo visto su rec.puzzles, dove ho preso il
problema, senza capirci nulla. A me pare che anche li' si faccia una
semplice constatazione.
Set F_1 = 1, F_2 = 1, F_3 = 2 etc. Then a prime p which ends in 1 or 9 will
divide F_n if (p-1) divides n, and a prime p ending in 3 or 7 will divide
F_n if (p+1) divides n. Here F_7 divides 8. This leaves the cases p = 2 and
5, but they are easily dealt with :-)
Che ne dite?
Ciao, Silv:o)

 wrote:
: > Non solo, a me sembra che se p è primo,
: > p divida sempre F_(p+1) exor F_(p-1) :
: 
: Anche Paolo l'ha notato, e Maurizio dice che e' un bell'aiuto per la
: dimostrazione. 
In realta` non lo e`, anche se lo pensavo.
O forse lo e`, ma non sono riuscito a trovare una dimostrazione bella.
Comunque e` abbastanza facile dimostrare che per ogni k c'e` un numero di
fibonacci che e` divisibile per k.
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 v
 
Consideriamo la successione dei valori modulo k. E` ovvio che il numero di
distinte coppie successive di valori e` finito, essendo al piu` k^2 .
Quindi avremo due numeri distinti m e n tali che 
   F_m == F_n (mod k) e F_(m+1) == F_(n+1) (mod k)
ma questo significa che anche F_(m-1) == F_(n-1) (mod k) e via tornando
indietro fino a che avremo F_1 == F_l (mod k) e F_2 == F_(l+1) (mod k)
da cui F_(l-1) == 0 (mod k), qed.
Notare che non ho usato l'ipotesi k primo, ma d'altronde non ho dimostrato
il teorema forte (ad esempio, se non erro il primo n per cui F_n == 0 (mod
10) e` 15)
ciao, .mau.

 10) e` 15)
Non erri : F_15=610
Ma mi pare di aver visto un errore fatale...
La butto giu', se sbaglio mi cospargero' il capo di cenere :
hai solo dimostrato che F(l-1) == 1 (mod k),
ma questo si ottiene entro k-1 (?)
infatti F_8 = 21

 wrote:
: Ma mi pare di aver visto un errore fatale...
: La butto giu', se sbaglio mi cospargero' il capo di cenere :
: hai solo dimostrato che F(l-1) == 1 (mod k),
: ma questo si ottiene entro k-1 (?)
: infatti F_8 = 21
Infatti ho detto che ho dimostrato *un altro risultato*, piu` debole in un
senso (non trovo un resto zero nei primi k+1 fib, ma nei k^2) e piu` forte
in un altro ( k non deve essere primo)
ciao , .mau.


Hai perfettamente ragione. Avevo fretta ed ho detto due castronerie.
Spero di farmi perdonare dimostrando la tua congettura originale,
usando la primalità :
----------------------------------------------
Sia E_n una successione che soddisfa alla proprietà
	E_(n+2)=E_(n+1) + E_n (in realta' basta molto meno)
Def. dato un k una sottosequenza di E_n (E_a, .. ,E_b)=(0, .. ,0),
	si dice k-fondamentale (k-f) se E_a=E_b=0 (mod p)
	e per ogni a<=x<=b F_x<>0 (mod p)
Ad esempio (0,0) e (0,1,1,2,3,0) sono sequenze 5-f,
lunghe rispettivamente 1 e 5 (...)
Lemma (i), Se p primo, esistono (p-1) sequenze p-f distinte
	e di ugual lunghezza, diverse da (0,0) :
Una SPF esiste (..., stesso arg. di Codogno), moltiplicandola per
m=1..(p-1) si ottengono tutte. Infatti se x=E_a+1 (mod p), qualsiasi
altro y=(E')_a+1 (mod p) di un'altra sequenza p-f si puo' ridurre a
m*x (mod p) se m=y*(x^-1) (il reciproco è ben definito su PK sse x><0
e p primo), e questo basta per metterla in corrispondenza.QED
Lemma (ii), una sequenza p-f, con p primo, è lunga al massimo p+1
Sia l la lunghezza di una p-f, l è anche il numero di coppie successive
(distinte) di valori che questa presenta. Notiamo che due p-f hanno tutte
coppie distinte (...). In totale le coppie sono p^2-1 (tolta la coppia 
banale (0,0)) e esistono (distinte da (0,0)) esattamente p-1 sequenze p-f
per il lemma (i), quindi ipotizzando che queste occupino
tutte le coppie possibili l_max=(p^2-1)/(p-1)=p+1.QED
vale quindi
Th. Per ogni p primo, p divide almeno un F_n per n<=p+1
Infatti dato p primo esiste una sequenza p-fondamentale che è lunga
al massimo p+1 (ii), laddove F_b=0 (mod p), cioè p|F_b.
E' anche immediato dimostrare che preso quel b tale che p|F_b,
si ha anche p|F_(k*b) per ogni k (una sequenza p-f finisce sempre
con un'altra seq. p-f), e quindi anche che F_b|F_(k*b), che è un risultato
classico.
Ufff... che lunga che è venuta...
Crios

 wrote in message 87pbn5$m6n$1...@nslave2.tin.it...

Sbagliato, l'ultimo numero dovrebbe essere 37 :-)
Cmq sì... puoi divertirti a scrivere formule ancora più generali...
Ma su Fibonacci è stato scritto così tanto... ma così tanto...
Poi è incredibile come i numeri di Fibonacci si ritrovino... nella natura!!!
Prendi ad esempio un girasole: la parte centrale è formata da spirali
logaritmiche che si incrociano, andando alcune in un verso, altre
nell'altro.
Il numero di spirali logaritmiche che vanno in un verso è un numero della
sequenza di Fibonacci, e il numero di quelle che vanno nell'altro è il
numero di Fibonacci successivo!!!
Sconcertante, eh?
E se fai caso, anche le foglie di un fiore sono messe in modo tale da
formare angoli tra loro che dividono l'angolo giro in un numero che è pari
ad uno della successione di Fibonacci... non so se sono stato chiaro.
Inoltre: il limite del rapporto tra due termini consecutivi della
successione di Fibonacci tende alla proporzione divina (o sezione aurea: (1
+ sqrt(5))/2 = 1.618...), un numero abbondantemente usato (ed abusato...
basti pensare al nome per immaginare le interpretazioni che ha avuto nei
secoli) in passato nelle arti figurative.
Questa è una caratteristica però di tutte le successioni in cui ogni termine
è la somma dei due precedenti, come anche la successione di Lucas (generata
da 1 e 3).
La proporzione divina è soluzione dell'equazione x^2 = x + 1. Infatti, se
fai il quadrato di 1.618... ottieni 2.618... E adesso prova a fare l'inverso
:-)
Sì, ottieni 0.618... (e credo che a volte si intenda questo numero come
sezione aurea...). La proporzione divina si indica in genere con la lettera
greca "phi" minuscola.
Ora ti insegno un giochetto: prendi un foglio di carta in cui il rapporto
tra larghezza e altezza sia pari alla proporzione divina. Mettilo con lato
più lungo alla base e da sinistra disegna un quadrato di lato pari
all'altezza. Il pezzo rimanente avrà ancora il lato più lungo in proporzione
divina col lato più corto! Nel pezzo rimanente, disegna dal basso un
quadrato... poi lo stacchi da destra... poi dall'alto... poi di nuovo da
sinistra e così via. Prova poi a congiungere gli estremi delle linee che hai
tracciato con una linea curva: otterrai una spirale logaritmica :-)
Che ti avevo detto dei girasoli poco fa? :-)
MaxArt

 wrote:
: > Ma ora ti (vi) chiedo: che particolarità ha questa serie? A che vantaggi
: > porta? Chi la conosce a cosa gli potrebbe servire?
: > così a naso non mi sembra ninete di particolare...potrei inventare serie
: > infinite in quel modo:
: > 1,2,3,6,11,20,27,....   giusto?
: 
: Sbagliato, l'ultimo numero dovrebbe essere 37 :-)
35, vorrai dire!
ciao, .mau.

 35, vorrai dire!
No, 37! La somma dei tre numeri precedenti: 6 + 11 + 20 = 37.
MaxArt

 wrote in message

E perche` la somma deve essere quella dei tre numeri precedenti?
La *mia* serie continua con ... 35, 60, 101, 168 ...
ciao, .mau.