Generazione della sequenza "propria" di Fibonacci

Question

Ho un problema insolito (penso). Per un dato numero F_n (non conosco il valore di n), devo trovare i numeri F_0, F_1 ​​tali che F_ {n} = F_ {n-1} + F_ {n-2}. La difficoltà aggiuntiva è che questa sequenza dovrebbe essere il più lunga possibile (il valore n per F_n dovrebbe essere il più alto) e se esiste più di una soluzione, devo prendere questo con il più piccolo F_0. In breve, devo generare la mia "sequenza" di Fibonacci. Alcuni esempi:

in: F_n = 10; out: F_0 = 0; F_1 = 2;

in: F_n = 17; out: F_0 = 1; F_1 = 5;

in: F_n = 4181; out: F_0 = 0; F_1 = 1;

Quello che ho osservato per ogni sequenza (con "regola di Fibonacci") F_n c'è:

F_n = Fib_n * F_1 + Fib_ {n-1} * F_0

Dove Fib_n è l'n-esimo Numero di Fibonacci È vero soprattutto per la sequenza di Fibonacci. Ma non so se questa osservazione valga qualcosa. Non sappiamo n e il nostro compito è trovare F_1, F_0, quindi penso che non abbiamo ottenuto nulla. Qualche idea?

Answer 1

l'equazione

F_n = Fib_n * F_1 + Fib_{n-1} * F_0 

è un linear Diophantine equation in two variablesF_1 e F_0. Il collegamento presenta un algoritmo efficiente per calcolare una descrizione del set di soluzioni che consente di trovare una soluzione, se esistente, con F_1 >= 0 e F_0 >= 0 e F_0 minimo. È quindi possibile tentare di indovinare n = 0, 1, ... finché non si trova alcuna soluzione.Questo approccio è polinomiale in log(F_n).

Answer 2

Non sono sicuro di cosa stiate cercando. La serie ricorsiva si parla è definito come:

Fn = F{n-1} + F{n-2} 

Chiaramente, se i valori Staring possono essere qualsiasi cosa, siamo in grado di scegliere arbirarlily F{n-1}, che darà F{n-2} (= Fn=F{n-1}). Sapendo che F{n-1} = F{n-2} + F{n-3}, segue che F{n-3} può essere calcolato da F{n-1} and F{n-2}. Ciò significa che è possibile rintracciare i numeri sull'infinito, quindi non esiste una sequenza "più lunga" e ci sono infinite sequenze valide.

In un certo senso si sta calcolando un inverso sequenza di Fibonacci con i valori iniziali F{n} e F{n-1} dove F{i} = F{i+2}-F{i+1}, i sempre diminuendo

UPDATE: Se stai cercando di vincolare il solutionspace ai risultati dove tutti F{i} sono non negativo interi, otterrete solo una manciata (la maggior parte delle volte singleton) soluzioni.

Se si calcolano i numeri originali di Fibonacci (Fib{i}), presto si ottiene F{n} < Fib{i-1}; chiaramente non hai bisogno di andare oltre. Quindi è possibile provare tutte le possibili combinazioni di F{0} e F{1} in modo tale che F{n} <= Fib{i} * F{1}+ Fib{i-1} * F{0} - ci sono solo un numero limitato di possibilità per non-F{0} e F{1} (si può ovviamente escludere F{0}=F{1}=0). Poi vedere quale i (s) è (sono) più alto tra quelli che soddisfano l'uguaglianza - si ottiene F{0} e F{1} così

Answer 3

F_n = Fib_n * F_1 + Fib_ {n-1} * F_0

Dove Fib_n è il numero di Fibonacci n-esimo. È vero soprattutto per la sequenza di Fibonacci. Ma non so se questa osservazione sia uguale a . Non sappiamo n e il nostro compito è trovare F_1, F_0 in modo che io pensi di non aver guadagnato nulla.

Bene, stai cercando la sequenza più lunga, questo significa che vuoi massimizzare n.

Creare una tabella di ricerca per i numeri di fibonacci. Inizia con il massimo n tale che Fib_n <= F_n, la voce precedente nella tabella è fib_n{n-1}. Ora le uniche variabili sono F_1 e F_0. Risolvi lo linear Diophantine equation. Se ha una soluzione, hai finito. In caso contrario, diminuire n di 1 e riprovare finché non si trova una soluzione.

Nota: esiste sempre una soluzione, poiché F_2 = 1 * F_1 + 0 * F_0 ha la soluzione F_2 = F_1.

Answer 4

F _n-1 = rotondo (F _n/φ)

dove φ = (√ 5 + 1)/2.

La prova è lasciata come esercizio per il lettore;^P

aggiornamento Questo non è corretto, torna al tavolo da disegno.

Update 2 Diamo calcolare all'indietro da F _n e F _n-1.

F _n-2 = F _n - F _n-1
F _n-3 = F _n-1 - F _n-2 = F _n-1 - (F _n - F _n-1) = 2F _n-1 - F _n
F _n-4 = F _n-2 - F _n-3 = (F _n - F _n-1) - (2F _n-1 - F _n) = 2F _n - 3F _n-1
F _n-5 = F _n-3 - F _n-4 = (2F _n-1 - F _n) - (2F _n - 3F _n-1) = 5F _n-1 - 3F _n
F _n-6 = F _n-4 - F _n-5 = (2F _n - 3F _n-1) - (5F _n-1 - 3F _n) = 5F _n - 8F _n-1

Si noti il ​​motivo? È facile calcolare qualsiasi membro della sequenza fuori dalla sequenza reale di Fibonacci e gli ultimi due membri. Ma conosciamo solo l'ultimo membro, come possiamo conoscere l'uno prima?

Scriviamo giù il requisito F _i > 0 in termini di F _n-1.

F _n-2 = F _n - F _n-1 F _n-1 < F _n
F _n-3 = 2F _n-1 - F _n F _n-1 > F _n/2
F _n-4 = 2F _n - 3F _n-1 ⇒ F _n-1 < 2F _n/3
F _n-5 = 5F _{n- 1} - 3F _n ⇒ F _n-1 > 3F _n/5

Quindi abbiamo una sequenza di limiti su F _n-1 in termini scritti della sequenza reale di Fibonacci, ognuno più stretto del precedente. L'ultimo limite che è ancora soddisfacente determina F _n-1 che corrisponde alla sequenza più lunga. Se c'è più di un numero che soddisfa l'ultimo limite, utilizzare il più piccolo o il più grande, a seconda che la sequenza abbia una lunghezza pari o dispari.

Ad esempio, se F _n = 101, quindi
101 * 5/8 < F _n-1 < 101 * 8/13 ⇒ F _n-1 = 63

L' soluzione (errata) precedente implicherebbe F _n-1 = 62, che è vicino ma senza sigaro.

Answer 5

Simula il calcolo dei numeri di Fibonacci con una matrice (ma con valori iniziali diversi). [[0 1] [1 1]] per alimentare k produrrà [F_ {n + k}, F_ {n + 1 + k}] se moltiplicato per [F_ {n}, F_ {n + 1}].

Poiché il sollevamento di una matrice a una potenza è un O (log n) (supponendo moltiplicazioni di interi è O (1)), è possibile eseguire l'intero calcolo in O (log n) tempo fino a quando i coefficienti della matrice iniziano a dominare il calcolo.

Non so quanto siano grandi i numeri con cui si sta lavorando, ma l'ennesima potenza di questa matrice è [[F_ {n-1} F_n] [F_n F_ {n + 1}]] . E registra (F_n) ~ n/5 (quindi il miliardesimo numero di Fibonacci avrà circa 200 milioni di cifre).