Erzeugen "eigenen" Fibonacci Sequenz

Question

Ich habe ein ungewöhnliches (glaube ich) Problem. Für eine gegebene Zahl F_n (ich kenne den Wert von n nicht) muss ich die Zahlen F_0, F_1 ​​so finden, dass F_ {n} = F_ {n-1} + F_ {n-2}. Die zusätzliche Schwierigkeit ist, dass diese Sequenz so lang wie möglich sein sollte (Wert n für F_n sollte der höchste sein) und wenn es mehr als eine Lösung gibt, muss ich diese mit der kleinsten F_0 nehmen. Kurz gesagt, ich muss meine "eigene" Fibonacci-Sequenz erzeugen. Einige Beispiele:

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

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

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

Was ich für jede Folge beobachtet (mit "Fibonacci-Regel") f_n gibt es:

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

Wo Fib_n ist die n-te Fibonacci-Nummer. Dies gilt insbesondere für die Fibonacci-Sequenz. Aber ich weiß nicht, ob diese Beobachtung irgendwas wert ist. Wir wissen n nicht und unsere Aufgabe ist es, F_1, F_0 zu finden, also denke ich, dass wir nichts gewonnen haben. Irgendwelche Ideen?

Answer 1

Ihre Gleichung

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

ist ein linear Diophantine equation in two variablesF_1 und F_0. Die Verknüpfung stellt einen effizienten Algorithmus zur Verfügung, um eine Beschreibung der Lösungsgruppe zu berechnen, mit der Sie eine Lösung finden können, falls eine solche existiert, mit F_1 >= 0 und F_0 >= 0 und F_0 Minimum. Sie können dann versuchen, n = 0, 1, ... zu schätzen, bis Sie feststellen, dass es keine Lösung gibt.Dieser Ansatz ist ein Polynom in log(F_n).

Answer 2

Ich bin mir nicht sicher, wonach Sie suchen. Die rekursive Serie Sie erwähnen, ist wie folgt definiert:

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

Klar, wenn die staring Werte kann alles sein, wir arbirarlily F{n-1} wählen können, was F{n-2} (= Fn=F{n-1}) geben. Das Wissen, dass F{n-1} = F{n-2} + F{n-3}, folgt, dass F{n-3} kann aus F{n-1} and F{n-2} berechnet werden. Dies bedeutet, dass Sie die Zahlen zurück in die Unendlichkeit verfolgen können, daher gibt es keine "längste" Sequenz und es gibt unendlich viele gültige Sequenzen.

In einer Art und Weise Sie eine inverse Fibonacci-Folge mit Anfangswerte Berechnung F{n} und F{n-1} wo F{i} = F{i+2}-F{i+1}, i immer

UPDATE abnehmend: Wenn Sie die solutionspace zu den Ergebnissen suchen zu beschränken, wo alle F{i} nicht-negativ sind Integer erhalten Sie nur eine Handvoll (meist Singleton) Lösungen. Wenn Sie die ursprünglichen Fibonacci-Zahlen berechnen (Fib{i}), erhalten Sie bald ; klar, du musst nicht weiter gehen. Dann können Sie alle möglichen Kombinationen von F{0} und F{1} so testen, dass F{n} <= Fib{i} * F{1}+ Fib{i-1} * F{0} - es gibt nur eine endliche Anzahl von Möglichkeiten für nicht negative F{0} und F{1} (Sie können natürlich F{0}=F{1}=0 ausschließen). Dann sehen, welche i (n) ist (sind) höchste unter denen, die Gleichheit erfüllen - Sie erhalten F{0} und F{1} sowie

Answer 3

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

Wo Fib_n die n-te Fibonacci-Zahl ist. Dies gilt insbesondere für Fibonacci-Sequenz. Aber ich weiß nicht, ob diese Beobachtung wert ist. Wir wissen n nicht und unsere Aufgabe ist es, F_1, F_0 zu finden, also denke ich, dass wir nichts gewonnen haben.

Nun, Sie suchen nach der längsten Sequenz, das heißt, Sie möchten n maximieren.

Erstellen Sie eine Nachschlagetabelle für Fibonacci-Nummern. Beginnen Sie mit dem größten n, so dass Fib_n <= F_n, der vorherige Eintrag in der Tabelle ist fib_n{n-1}. Jetzt sind die einzigen Variablen F_1 und F_0. Lösen Sie die linear Diophantine equation. Wenn es eine Lösung hat, sind Sie fertig. Wenn nicht, verringern Sie n um 1 und versuchen Sie es erneut, bis Sie eine Lösung gefunden haben.

Hinweis: Eine Lösung existiert immer, da F_2 = 1 * F_1 + 0 * F_0 die Lösung F_2 = F_1 hat.

Answer 4

_{F n-1} = round (F _n/φ)

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

Nachweis wird für den Leser als Übung;^P

aktualisieren Diese falsch ist, wieder auf dem Reißbrett.

Update 2 die rückwärts von _{F n und F n-1} Let berechnen.

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

Beachten Sie das Muster? Es ist leicht, irgendein Mitglied der Sequenz aus der echten Fibonacci-Sequenz und den letzten zwei Mitgliedern zu berechnen. Aber wir kennen nur das letzte Mitglied, wie können wir das vorletzte kennen?

Lassen sich die Forderung F _i > 0 in Bezug auf F n-1 _{aufzuschreiben.}

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

Also haben wir eine Abfolge von Grenzen auf F _n-1 in geschriebenen Begriffen der realen Fibonacci-Sequenz, jede eine fester als die vorherige. Die letzte noch erfüllbare Grenze bestimmt F _n-1, die der längsten Sequenz entspricht. Wenn es mehr als eine Zahl gibt, die die letzte Grenze erfüllt, verwenden Sie entweder die kleinste oder die größte, je nachdem, ob die Sequenz gerade oder ungerade ist.

Wenn beispielsweise F _n = 101, dann
101 * 5/8 < F _n-1 < 101 * 8/13 ⇒ F _n-1 = 63

The vorherige (inkorrekte) Lösung würde bedeuten F _n-1 = 62, das ist nahe, aber keine Zigarre.

Answer 5

Imitieren Sie die Berechnung von Fibonacci-Zahlen mit einer Matrix (aber mit unterschiedlichen Anfangswerten). [[0 1] [1 1]] zur Potenz k ergibt [F_ {n + k}, F_ {n + 1 + k}], wenn es mit [F_ {n}, F_ {n + 1}] multipliziert wird.

Da das Erhöhen einer Matrix auf eine Potenz ein O (log n) ist (unter der Annahme, Multiplikationen von ganzen Zahlen ist O (1)), können Sie die gesamte Berechnung in O (log n) Zeit durchführen, bis Matrix-Koeffizienten zu dominieren beginnen die Berechnung.

Ich weiß nicht, wie groß die Zahlen sind, mit denen Sie gerade arbeiten, aber die n-te Potenz dieser Matrix ist [[F_ {n-1} F_n] [F_n F_ {n + 1}]] . Und log (F_n) ~ n/5 (so wird die milliardste Fibonacci-Zahl ungefähr 200 Millionen Ziffern haben).