Project Euler Problem 2 asks for the sum of the even-valued Fibonacci terms that do not exceed four million. The implementations generalize that statement to an arbitrary limit \(N\), but the underlying stream is the same one used in the problem: \(1,2,3,5,8,13,\dots\).
So the real task is not to generate all integers up to \(N\), but to understand the special structure of the Fibonacci sequence well enough to identify and accumulate only the relevant terms.
Let the Fibonacci sequence for this problem be
$$F_1=1,\qquad F_2=2,\qquad F_{n+2}=F_{n+1}+F_n\quad(n\ge 1).$$
We want
$$S(N)=\sum_{\substack{n\ge 1\\F_n\le N\\F_n\text{ even}}}F_n.$$
The important mathematical objects are the recurrence itself, the parity pattern of the terms, and the invariant that consecutive Fibonacci numbers determine the next state completely.
Because every term is the sum of the previous two, once two consecutive terms are known, the entire future of the sequence is fixed. Starting from \(F_1=1\) and \(F_2=2\), the first values are
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\dots$$
This recurrence immediately gives a useful implementation invariant: if at some moment we hold two consecutive terms \((F_k,F_{k+1})\), then one update step replaces them by \((F_{k+1},F_{k+2})\). That is exactly what the code exploits.
The fastest conceptual simplification comes from looking at the recurrence modulo \(2\). Since parity is all that matters here, reduce each term to \(0\) or \(1\):
$$F_1\equiv 1,\qquad F_2\equiv 0\pmod 2.$$
Now track consecutive pairs modulo \(2\):
$$\bigl(F_n,F_{n+1}\bigr)\equiv (1,0)\to(0,1)\to(1,1)\to(1,0)\pmod 2.$$
The pair returns after three steps, so the parity pattern is periodic with period \(3\). Therefore
$$F_n\text{ is even}\iff n\equiv 2\pmod 3.$$
That identifies the even-valued subsequence exactly:
$$E_m=F_{3m-1}\qquad(m\ge 1),$$
whose first terms are \(2,8,34,144,\dots\).
Sampling every third Fibonacci term produces its own linear recurrence. Write
$$A=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix},\qquad \begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix}=A^{n-1}\begin{pmatrix}2\\ 1\end{pmatrix}.$$
Advancing three Fibonacci steps at a time means multiplying by
$$A^3=\begin{pmatrix}3 & 2\\ 2 & 1\end{pmatrix}.$$
This matrix has trace \(4\) and determinant \(-1\), so its characteristic polynomial is
$$\lambda^2-4\lambda-1=0.$$
Any scalar sequence obtained by repeated multiplication with \(A^3\) therefore satisfies
$$x_{m+2}=4x_{m+1}+x_m.$$
In particular, the even Fibonacci terms obey
$$\boxed{E_{m+2}=4E_{m+1}+E_m,\qquad E_1=2,\qquad E_2=8.}$$
This recurrence is often used for an even-only solution. The implementations discussed here do not need it, but it explains why the even terms grow so quickly and regularly.
There is also a clean identity for the sum of the first \(m\) even Fibonacci terms. Start from the basic recurrence in the rearranged form
$$F_{n+2}=2F_n+F_{n-1}.$$
Set \(n=3j-1\). Since \(E_j=F_{3j-1}\), this becomes
$$F_{3j+1}-F_{3j-2}=2E_j.$$
Summing from \(j=1\) to \(m\) makes the middle terms telescope:
$$2\sum_{j=1}^{m}E_j=\sum_{j=1}^{m}\left(F_{3j+1}-F_{3j-2}\right)=F_{3m+1}-F_1=F_{3m+1}-1.$$
Hence
$$\boxed{\sum_{j=1}^{m}E_j=\frac{F_{3m+1}-1}{2}.}$$
So once the last even Fibonacci term below the limit is known, the whole sum can be recovered from one later Fibonacci number. The code still uses direct iteration because it is simpler and already fast enough.7
The Fibonacci terms below \(100\) are
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89.$$
The even ones are \(2,8,34\), so the required sum is
$$2+8+34=44.$$
In the subsequence notation this is \(E_1+E_2+E_3\). The closed identity gives the same result immediately:
$$E_1+E_2+E_3=\frac{F_{10}-1}{2}=\frac{89-1}{2}=44.$$
The C++, Python, and Java implementations keep two consecutive Fibonacci terms and a running total. Before each loop iteration, the stored pair is exactly \((F_k,F_{k+1})\) for some \(k\). The second term is the current candidate because the stream starts at \(1,2\), so the first value that can contribute is already in that position.
Each iteration does three things: it checks whether the current Fibonacci term is still within the limit, it adds that term to the sum if it is even, and it advances the pair to the next consecutive pair. This preserves the invariant \((F_k,F_{k+1})\mapsto(F_{k+1},F_{k+2})\).
The loop stops as soon as the current term exceeds the limit. Since Fibonacci numbers are strictly increasing after the first two positive terms, every eligible even term is visited exactly once and no extra bookkeeping is required. The implementations also include the checkpoint \(N=100\mapsto 44\), matching the worked example above.
Let \(t\) be the largest index with \(F_t\le N\). Because Fibonacci numbers grow exponentially, \(t=\Theta(\log N)\). The implementations perform constant work per generated term, so the running time is
$$O(\log N).$$
Only a fixed number of integer variables is stored, so the memory usage is
$$O(1).$$
An implementation based on the even-only recurrence \(E_{m+2}=4E_{m+1}+E_m\) would improve only the constant factor, not the asymptotic order.
In Problem 2 von Project Euler soll die Summe aller geraden Fibonacci-Zahlen bestimmt werden, die \(4{,}000{,}000\) nicht überschreiten. Die Implementierungen verallgemeinern das auf eine beliebige Schranke \(N\), aber die Folge selbst ist dieselbe wie in der Aufgabenstellung: \(1,2,3,5,8,13,\dots\).
Die eigentliche Schwierigkeit besteht also nicht darin, bis \(N\) alle Zahlen zu durchsuchen, sondern die Struktur der Fibonacci-Folge so zu nutzen, dass genau die relevanten geraden Glieder erfasst werden.
Für diese Aufgabe sei die Fibonacci-Folge definiert durch
$$F_1=1,\qquad F_2=2,\qquad F_{n+2}=F_{n+1}+F_n\quad(n\ge 1).$$
Gesucht ist
$$S(N)=\sum_{\substack{n\ge 1\\F_n\le N\\F_n\text{ gerade}}}F_n.$$
Die entscheidenden mathematischen Objekte sind die Rekurrenz selbst, das Paritätsmuster der Folge und die Invariante, dass zwei aufeinanderfolgende Fibonacci-Zahlen den nächsten Zustand vollständig bestimmen.
Da jedes Glied die Summe der beiden vorherigen ist, ist die gesamte Zukunft der Folge festgelegt, sobald zwei aufeinanderfolgende Werte bekannt sind. Ausgehend von \(F_1=1\) und \(F_2=2\) erhält man
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\dots$$
Daraus ergibt sich direkt eine nützliche Implementierungsinvariante: Wenn zu einem Zeitpunkt das Paar \((F_k,F_{k+1})\) vorliegt, dann liefert ein Aktualisierungsschritt das nächste Paar \((F_{k+1},F_{k+2})\). Genau diese Beobachtung nutzen die Programme.
Die wichtigste Vereinfachung erhält man, wenn man die Rekurrenz modulo \(2\) betrachtet. Für die Parität zählt nur, ob ein Glied \(0\) oder \(1\) modulo \(2\) ist:
$$F_1\equiv 1,\qquad F_2\equiv 0\pmod 2.$$
Verfolgt man Paare aufeinanderfolgender Werte modulo \(2\), so entsteht
$$\bigl(F_n,F_{n+1}\bigr)\equiv (1,0)\to(0,1)\to(1,1)\to(1,0)\pmod 2.$$
Das Paar kehrt also nach drei Schritten zurück. Die Parität ist deshalb periodisch mit Periode \(3\), und damit gilt
$$F_n\text{ ist gerade}\iff n\equiv 2\pmod 3.$$
Die geraden Fibonacci-Zahlen bilden somit die Teilfolge
$$E_m=F_{3m-1}\qquad(m\ge 1),$$
deren erste Werte \(2,8,34,144,\dots\) sind.
Wenn man nur jedes dritte Fibonacci-Glied betrachtet, entsteht wieder eine lineare Rekurrenz. Schreibe
$$A=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix},\qquad \begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix}=A^{n-1}\begin{pmatrix}2\\ 1\end{pmatrix}.$$
Drei Fibonacci-Schritte auf einmal entsprechen der Matrix
$$A^3=\begin{pmatrix}3 & 2\\ 2 & 1\end{pmatrix}.$$
Diese Matrix hat Spur \(4\) und Determinante \(-1\), also das charakteristische Polynom
$$\lambda^2-4\lambda-1=0.$$
Jede skalare Folge, die durch wiederholte Multiplikation mit \(A^3\) entsteht, erfüllt daher
$$x_{m+2}=4x_{m+1}+x_m.$$
Insbesondere gilt für die geraden Fibonacci-Zahlen
$$\boxed{E_{m+2}=4E_{m+1}+E_m,\qquad E_1=2,\qquad E_2=8.}$$
Diese Rekurrenz eignet sich für eine Lösung, die nur gerade Glieder erzeugt. Die Implementierungen hier brauchen sie nicht, aber sie erklärt die Struktur der Teilfolge sehr gut.
Für die ersten \(m\) geraden Fibonacci-Zahlen gibt es eine kompakte Summenformel. Aus der Grundrekurrenz folgt in umgestellter Form
$$F_{n+2}=2F_n+F_{n-1}.$$
Setzt man \(n=3j-1\), so erhält man mit \(E_j=F_{3j-1}\)
$$F_{3j+1}-F_{3j-2}=2E_j.$$
Summiert man dies für \(j=1,\dots,m\), dann teleskopieren die Zwischenterme:
$$2\sum_{j=1}^{m}E_j=\sum_{j=1}^{m}\left(F_{3j+1}-F_{3j-2}\right)=F_{3m+1}-F_1=F_{3m+1}-1.$$
Also gilt
$$\boxed{\sum_{j=1}^{m}E_j=\frac{F_{3m+1}-1}{2}.}$$
Damit ließe sich die Summe aus einem einzigen späteren Fibonacci-Wert ablesen, sobald das letzte gerade Glied unterhalb der Schranke bekannt ist. Der direkte Durchlauf bleibt trotzdem die einfachere Implementierung.7
Die Fibonacci-Zahlen unter \(100\) sind
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89.$$
Die geraden Glieder sind \(2,8,34\), also ist die gesuchte Summe
$$2+8+34=44.$$
In der Schreibweise der Teilfolge ist das \(E_1+E_2+E_3\). Die geschlossene Formel liefert denselben Wert sofort:
$$E_1+E_2+E_3=\frac{F_{10}-1}{2}=\frac{89-1}{2}=44.$$
Die C++-, Python- und Java-Implementierungen speichern zwei aufeinanderfolgende Fibonacci-Zahlen sowie eine laufende Summe. Vor jeder Schleifeniteration ist das gespeicherte Paar genau \((F_k,F_{k+1})\) für ein geeignetes \(k\). Der zweite Wert ist der aktuelle Kandidat, weil die Folge mit \(1,2\) beginnt und damit das erste beitragende Glied bereits an dieser Stelle steht.
In jeder Iteration geschieht genau Folgendes: Zuerst wird geprüft, ob der aktuelle Fibonacci-Wert noch innerhalb der Schranke liegt. Falls er gerade ist, wird er zur Summe addiert. Danach wird das Paar auf das nächste aufeinanderfolgende Paar aktualisiert. Dadurch bleibt die Invariante \((F_k,F_{k+1})\mapsto(F_{k+1},F_{k+2})\) erhalten.
Die Schleife endet, sobald der aktuelle Wert die Schranke überschreitet. Da die Fibonacci-Zahlen nach den ersten beiden positiven Gliedern streng wachsen, wird jedes zulässige gerade Glied genau einmal besucht. Außerdem enthalten die Implementierungen die Prüfstelle \(N=100\mapsto 44\), passend zum obigen Beispiel.
Sei \(t\) der größte Index mit \(F_t\le N\). Wegen des exponentiellen Wachstums der Fibonacci-Folge gilt \(t=\Theta(\log N)\). Pro erzeugtem Glied wird nur konstanter Aufwand betrieben, also beträgt die Laufzeit
$$O(\log N).$$
Gespeichert werden nur wenige Ganzzahlen, daher ist der Speicherbedarf
$$O(1).$$
Auch eine Implementierung mit der Rekurrenz \(E_{m+2}=4E_{m+1}+E_m\) hätte dieselbe asymptotische Ordnung; sie würde nur einen kleineren konstanten Faktor erreichen.
Project Euler 2, \(4{,}000{,}000\)'u aşmayan çift Fibonacci terimlerinin toplamını ister. Uygulamalar bunu genel bir \(N\) sınırına açıyor, ancak kullanılan sayı akışı yine aynı: \(1,2,3,5,8,13,\dots\).
Dolayısıyla mesele \(N\)'e kadar bütün sayıları taramak değil, Fibonacci dizisinin yapısını kullanarak sadece katkı yapan çift terimleri güvenilir biçimde toplamaktır.
Bu problem için Fibonacci dizisini
$$F_1=1,\qquad F_2=2,\qquad F_{n+2}=F_{n+1}+F_n\quad(n\ge 1)$$
şeklinde tanımlayalım. İstenen büyüklük
$$S(N)=\sum_{\substack{n\ge 1\\F_n\le N\\F_n\text{ çift}}}F_n$$
olur. Buradaki temel matematiksel nesneler yinelemenin kendisi, terimlerin tek-çift düzeni ve iki ardışık Fibonacci sayısının bir sonraki durumu tamamen belirlemesidir.
Her terim kendinden önce gelen iki terimin toplamı olduğu için, iki ardışık değer bilindiğinde dizinin geri kalanı da sabitlenmiş olur. \(F_1=1\) ve \(F_2=2\) ile başlayan akış
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\dots$$
şeklindedir. Bu gözlem doğrudan bir uygulama değişmezi verir: eğer bir anda elimizde \((F_k,F_{k+1})\) çifti varsa, tek güncelleme adımı bizi \((F_{k+1},F_{k+2})\) çiftine götürür. Kod tam olarak bunu kullanır.
En önemli sadeleşme, yinelemeyi \(2\) modunda inceleyince ortaya çıkar. Burada sadece parite önemli olduğu için terimleri \(0\) ve \(1\) olarak düşünmek yeterlidir:
$$F_1\equiv 1,\qquad F_2\equiv 0\pmod 2.$$
Ardışık terim çiftlerini \(2\) modunda izlersek
$$\bigl(F_n,F_{n+1}\bigr)\equiv (1,0)\to(0,1)\to(1,1)\to(1,0)\pmod 2$$
döngüsünü görürüz. Çift üç adım sonra aynı duruma döndüğü için parite örüntüsünün periyodu \(3\)'tür. Dolayısıyla
$$F_n\text{ çifttir}\iff n\equiv 2\pmod 3.$$
Böylece çift Fibonacci alt dizisi tam olarak
$$E_m=F_{3m-1}\qquad(m\ge 1)$$
şeklinde yazılır; ilk birkaç terim \(2,8,34,144,\dots\) olur.
Her üçüncü Fibonacci terimini örneklemek, yeni bir doğrusal yineleme üretir. Şunu yazalım:
$$A=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix},\qquad \begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix}=A^{n-1}\begin{pmatrix}2\\ 1\end{pmatrix}.$$
Bir seferde üç Fibonacci adımı ilerlemek ise
$$A^3=\begin{pmatrix}3 & 2\\ 2 & 1\end{pmatrix}$$
matrisiyle çarpmaya karşılık gelir. Bu matrisin izi \(4\), determinantı \(-1\) olduğundan karakteristik polinomu
$$\lambda^2-4\lambda-1=0$$
olur. Bu yüzden \(A^3\)'ün tekrarlı uygulanmasıyla elde edilen her skaler dizi
$$x_{m+2}=4x_{m+1}+x_m$$
bağıntısını sağlar. Özellikle çift Fibonacci terimleri için
$$\boxed{E_{m+2}=4E_{m+1}+E_m,\qquad E_1=2,\qquad E_2=8.}$$
Bu, sadece çift terimleri üreten klasik yinelemedir. Buradaki uygulamalar buna ihtiyaç duymuyor, ama alt dizinin neden bu kadar düzenli büyüdüğünü açıklar.
İlk \(m\) çift Fibonacci teriminin toplamı için güzel bir kapalı özdeşlik de vardır. Temel yinelemeyi şöyle yeniden yazabiliriz:
$$F_{n+2}=2F_n+F_{n-1}.$$
\(n=3j-1\) koyup \(E_j=F_{3j-1}\) kullanırsak
$$F_{3j+1}-F_{3j-2}=2E_j$$
elde edilir. Bunu \(j=1\)'den \(m\)'ye kadar topladığımızda ara terimler teleskopik olarak sadeleşir:
$$2\sum_{j=1}^{m}E_j=\sum_{j=1}^{m}\left(F_{3j+1}-F_{3j-2}\right)=F_{3m+1}-F_1=F_{3m+1}-1.$$
Sonuç olarak
$$\boxed{\sum_{j=1}^{m}E_j=\frac{F_{3m+1}-1}{2}.}$$
Yani sınırın altındaki son çift Fibonacci terimini bildiğimiz anda, toplamı bir sonraki uygun Fibonacci değeri üzerinden de okuyabiliriz. Kod yine de doğrudan dolaşımı tercih eder; çünkü daha sade ve zaten yeterince hızlıdır.7
\(100\)'ün altındaki Fibonacci terimleri
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89$$
olur. Bunların çift olanları \(2,8,34\) olduğuna göre toplam
$$2+8+34=44$$
çıkar. Alt dizi gösteriminde bu \(E_1+E_2+E_3\)'tür. Kapalı özdeşlik de aynı sonuca gider:
$$E_1+E_2+E_3=\frac{F_{10}-1}{2}=\frac{89-1}{2}=44.$$
C++, Python ve Java uygulamaları iki ardışık Fibonacci terimi ile bir koşan toplam tutar. Her döngü iterasyonunun başında saklanan çift, uygun bir \(k\) için tam olarak \((F_k,F_{k+1})\)'dir. Akış \(1,2\) ile başladığı için sınanacak güncel terim ikinci bileşendir.
Her adımda üç şey yapılır: güncel Fibonacci teriminin hâlâ sınır içinde olup olmadığına bakılır, çiftse toplama eklenir ve ardından çift bir sonraki ardışık çifte güncellenir. Böylece \((F_k,F_{k+1})\mapsto(F_{k+1},F_{k+2})\) değişmezi korunur.
Güncel terim sınırı aştığında döngü durur. Fibonacci sayıları ilk iki pozitif terimden sonra sıkı biçimde arttığı için uygun her çift terim tam bir kez ziyaret edilir. Uygulamalarda ayrıca \(N=100\mapsto 44\) kontrolü bulunur; bu da yukarıdaki örnekle birebir uyumludur.
\(F_t\le N\) koşulunu sağlayan en büyük indeks \(t\) olsun. Fibonacci sayıları üstel büyüdüğü için \(t=\Theta(\log N)\) olur. Üretilen her terim için sabit iş yapıldığından çalışma süresi
$$O(\log N)$$
olur. Saklanan değişken sayısı sabit kaldığı için bellek kullanımı
$$O(1)$$
seviyesindedir. Sadece çift terim yinelemesini kullanan bir çözüm yalnızca sabit çarpanı küçültür; asimptotik sınıf değişmez.
El Problema 2 de Project Euler pide sumar los términos pares de Fibonacci que no superan \(4{,}000{,}000\). Las implementaciones generalizan la idea a un límite arbitrario \(N\), pero la sucesión utilizada es exactamente la misma: \(1,2,3,5,8,13,\dots\).
Por tanto, el reto no consiste en revisar todos los enteros hasta \(N\), sino en aprovechar la estructura de Fibonacci para localizar y acumular solo los términos que realmente contribuyen a la suma.
Para este problema definimos la sucesión de Fibonacci por
$$F_1=1,\qquad F_2=2,\qquad F_{n+2}=F_{n+1}+F_n\quad(n\ge 1).$$
Queremos calcular
$$S(N)=\sum_{\substack{n\ge 1\\F_n\le N\\F_n\text{ par}}}F_n.$$
Los objetos matemáticos decisivos son la recurrencia básica, el patrón de paridad de la sucesión y la invariante de que dos términos consecutivos determinan por completo el siguiente estado.
Cada término es la suma de los dos anteriores, así que conocer dos términos consecutivos fija todo el futuro de la sucesión. Partiendo de \(F_1=1\) y \(F_2=2\), obtenemos
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\dots$$
Esto da una invariante muy útil para la implementación: si en un momento tenemos el par \((F_k,F_{k+1})\), un único paso de actualización lo convierte en \((F_{k+1},F_{k+2})\). Ese es exactamente el mecanismo que usan los programas.
La simplificación conceptual más importante surge al estudiar la recurrencia módulo \(2\). Como aquí solo importa la paridad, basta con reducir cada término a \(0\) o \(1\):
$$F_1\equiv 1,\qquad F_2\equiv 0\pmod 2.$$
Si seguimos pares consecutivos módulo \(2\), aparece el ciclo
$$\bigl(F_n,F_{n+1}\bigr)\equiv (1,0)\to(0,1)\to(1,1)\to(1,0)\pmod 2.$$
El par regresa tras tres pasos, así que el patrón de paridad tiene periodo \(3\). En consecuencia,
$$F_n\text{ es par}\iff n\equiv 2\pmod 3.$$
Eso identifica la subsecuencia par de forma exacta:
$$E_m=F_{3m-1}\qquad(m\ge 1),$$
cuyos primeros términos son \(2,8,34,144,\dots\).
Tomar un término de cada tres produce otra recurrencia lineal. Escribamos
$$A=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix},\qquad \begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix}=A^{n-1}\begin{pmatrix}2\\ 1\end{pmatrix}.$$
Avanzar tres pasos de Fibonacci de una vez equivale a multiplicar por
$$A^3=\begin{pmatrix}3 & 2\\ 2 & 1\end{pmatrix}.$$
Esta matriz tiene traza \(4\) y determinante \(-1\), así que su polinomio característico es
$$\lambda^2-4\lambda-1=0.$$
Por ello, cualquier sucesión escalar obtenida al aplicar repetidamente \(A^3\) satisface
$$x_{m+2}=4x_{m+1}+x_m.$$
En particular, los términos pares de Fibonacci cumplen
$$\boxed{E_{m+2}=4E_{m+1}+E_m,\qquad E_1=2,\qquad E_2=8.}$$
Esta recurrencia sirve para una solución que genere solo términos pares. Las implementaciones descritas aquí no la necesitan, pero sí ayuda a explicar la estructura del problema.
También existe una identidad limpia para la suma de los primeros \(m\) términos pares. Partimos de la recurrencia básica reescrita como
$$F_{n+2}=2F_n+F_{n-1}.$$
Tomando \(n=3j-1\) y usando \(E_j=F_{3j-1}\), obtenemos
$$F_{3j+1}-F_{3j-2}=2E_j.$$
Al sumar para \(j=1,\dots,m\), los términos intermedios telescopan:
$$2\sum_{j=1}^{m}E_j=\sum_{j=1}^{m}\left(F_{3j+1}-F_{3j-2}\right)=F_{3m+1}-F_1=F_{3m+1}-1.$$
Luego
$$\boxed{\sum_{j=1}^{m}E_j=\frac{F_{3m+1}-1}{2}.}$$
Así, una vez conocido el último término par por debajo del límite, la suma completa puede leerse a partir de un Fibonacci posterior. El código aun así prefiere la iteración directa porque ya es simple y suficientemente rápida.7
Los términos de Fibonacci menores que \(100\) son
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89.$$
Los términos pares son \(2,8,34\), así que la suma pedida es
$$2+8+34=44.$$
En la notación de la subsecuencia, esto es \(E_1+E_2+E_3\). La identidad cerrada produce el mismo resultado:
$$E_1+E_2+E_3=\frac{F_{10}-1}{2}=\frac{89-1}{2}=44.$$
Las implementaciones en C++, Python y Java mantienen dos términos consecutivos de Fibonacci y una suma acumulada. Antes de cada iteración del bucle, el par almacenado es exactamente \((F_k,F_{k+1})\) para algún \(k\). El segundo término es el candidato actual porque la sucesión comienza con \(1,2\) y el primer valor que puede aportar ya está en esa posición.
Cada iteración hace tres cosas: comprueba si el término actual sigue dentro del límite, lo añade a la suma si es par y después avanza al siguiente par consecutivo. Eso preserva la invariante \((F_k,F_{k+1})\mapsto(F_{k+1},F_{k+2})\).
El bucle termina cuando el término actual supera el límite. Como los números de Fibonacci crecen estrictamente una vez fijados los dos primeros positivos, cada término par válido se visita exactamente una vez. Además, las implementaciones incluyen la comprobación \(N=100\mapsto 44\), que coincide con el ejemplo trabajado.
Sea \(t\) el mayor índice tal que \(F_t\le N\). Como los números de Fibonacci crecen exponencialmente, \(t=\Theta(\log N)\). El trabajo por término generado es constante, de modo que el tiempo total es
$$O(\log N).$$
Solo se almacenan unas pocas variables enteras, así que el uso de memoria es
$$O(1).$$
Una versión basada directamente en \(E_{m+2}=4E_{m+1}+E_m\) mejoraría solo la constante, no el orden asintótico.
Project Euler 第 2 题要求求出所有不超过 \(4{,}000{,}000\) 的偶数斐波那契项之和。这里的实现把它推广到了任意上界 \(N\)，但所处理的数列与题目完全一致，都是 \(1,2,3,5,8,13,\dots\)。
因此，关键不在于把 \(N\) 以下的整数逐个检查一遍，而在于抓住斐波那契递推的结构，只访问那些真正会进入答案的项。
在这道题中，把斐波那契数列写成
$$F_1=1,\qquad F_2=2,\qquad F_{n+2}=F_{n+1}+F_n\quad(n\ge 1).$$
我们要求的是
$$S(N)=\sum_{\substack{n\ge 1\\F_n\le N\\F_n\text{ 为偶数}}}F_n.$$
真正重要的数学对象有三个：原始递推关系、项的奇偶周期，以及“两个相邻斐波那契数就足以决定下一状态”这一不变量。
由于每一项都是前两项之和，所以一旦知道了两个相邻项，整个后续数列就完全确定。以 \(F_1=1\)、\(F_2=2\) 为起点，前几项是
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\dots$$
这立刻给出一个非常适合程序实现的不变量：如果某一时刻保存的是 \((F_k,F_{k+1})\)，那么一次更新之后就会变成 \((F_{k+1},F_{k+2})\)。代码正是围绕这个事实构造的。
最有用的简化来自模 \(2\) 分析。因为这里只关心奇偶性，所以每一项只需要看成 \(0\) 或 \(1\)：
$$F_1\equiv 1,\qquad F_2\equiv 0\pmod 2.$$
继续追踪相邻两项在模 \(2\) 下的变化，会得到
$$\bigl(F_n,F_{n+1}\bigr)\equiv (1,0)\to(0,1)\to(1,1)\to(1,0)\pmod 2.$$
也就是说，这个状态对在三步之后回到起点，因此奇偶模式的周期是 \(3\)。于是有
$$F_n\text{ 为偶数}\iff n\equiv 2\pmod 3.$$
这就把偶数项子序列精确地写成了
$$E_m=F_{3m-1}\qquad(m\ge 1),$$
它的前几项是 \(2,8,34,144,\dots\)。
每隔三项抽样一次，本身仍然会形成一个线性递推。记
$$A=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix},\qquad \begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix}=A^{n-1}\begin{pmatrix}2\\ 1\end{pmatrix}.$$
一次前进三个斐波那契步长，相当于乘以
$$A^3=\begin{pmatrix}3 & 2\\ 2 & 1\end{pmatrix}.$$
这个矩阵的迹是 \(4\)，行列式是 \(-1\)，因此其特征多项式为
$$\lambda^2-4\lambda-1=0.$$
所以，由反复乘以 \(A^3\) 得到的任意标量序列都满足
$$x_{m+2}=4x_{m+1}+x_m.$$
特别地，偶数斐波那契项满足
$$\boxed{E_{m+2}=4E_{m+1}+E_m,\qquad E_1=2,\qquad E_2=8.}$$
这就是常见的“只生成偶数项”的递推。这里的实现并没有采用它，因为直接扫描相邻项已经足够快，但这个递推很好地揭示了偶数子序列的内部结构。
前 \(m\) 个偶数斐波那契项还有一个很整洁的求和恒等式。先把基本递推改写为
$$F_{n+2}=2F_n+F_{n-1}.$$
令 \(n=3j-1\)，并代入 \(E_j=F_{3j-1}\)，就得到
$$F_{3j+1}-F_{3j-2}=2E_j.$$
对 \(j=1,\dots,m\) 求和时，中间项会望远镜式抵消：
$$2\sum_{j=1}^{m}E_j=\sum_{j=1}^{m}\left(F_{3j+1}-F_{3j-2}\right)=F_{3m+1}-F_1=F_{3m+1}-1.$$
因此
$$\boxed{\sum_{j=1}^{m}E_j=\frac{F_{3m+1}-1}{2}.}$$
这说明，只要知道上界以下最后一个偶数斐波那契项处在什么位置，就可以通过更靠后的一个 Fibonacci 值直接恢复总和。实现仍然选择直接迭代，因为那条主线更简洁、也完全足够高效。7
小于 \(100\) 的斐波那契项为
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89.$$
其中偶数项是 \(2,8,34\)，所以答案为
$$2+8+34=44.$$
在子序列记号下，这就是 \(E_1+E_2+E_3\)。上面的闭式同样立刻给出
$$E_1+E_2+E_3=\frac{F_{10}-1}{2}=\frac{89-1}{2}=44.$$
C++、Python 和 Java 的实现都维护两个相邻的斐波那契数以及一个累加和。每次循环开始时，保存的二元组恰好是某个 \((F_k,F_{k+1})\)。由于数列起点是 \(1,2\)，第二个分量正好就是当前需要判断是否计入答案的那一项。
每轮循环做三件事：先检查当前项是否仍未超过上界；若它是偶数，则把它加入总和；然后把这对相邻项推进到下一对。于是循环始终保持不变量 \((F_k,F_{k+1})\mapsto(F_{k+1},F_{k+2})\)。
当当前项超过上界时，循环结束。由于从最初几个正项开始，斐波那契数严格递增，所以每一个合法的偶数项都会被访问且只会被访问一次。实现中还包含 \(N=100\mapsto 44\) 的检查点，与上面的算例完全一致。
设 \(t\) 是满足 \(F_t\le N\) 的最大下标。由于斐波那契数呈指数增长，\(t=\Theta(\log N)\)。实现对每一个生成出的斐波那契项只做常数次操作，因此时间复杂度为
$$O(\log N).$$
程序只保存固定数量的整数变量，所以空间复杂度为
$$O(1).$$
如果改用偶数子序列递推 \(E_{m+2}=4E_{m+1}+E_m\)，只能改进常数因子，不能改变渐近复杂度等级。
Во второй задаче Project Euler требуется найти сумму всех чётных чисел Фибоначчи, не превосходящих \(4{,}000{,}000\). Реализации обобщают это на произвольную границу \(N\), но рассматриваемая последовательность остаётся той же самой: \(1,2,3,5,8,13,\dots\).
Значит, важно не перебирать все числа до \(N\), а использовать структуру рекуррентной последовательности так, чтобы посещать только те члены, которые действительно входят в ответ.
В этой задаче последовательность Фибоначчи задаётся так:
$$F_1=1,\qquad F_2=2,\qquad F_{n+2}=F_{n+1}+F_n\quad(n\ge 1).$$
Нужно вычислить
$$S(N)=\sum_{\substack{n\ge 1\\F_n\le N\\F_n\text{ чётно}}}F_n.$$
Ключевые математические объекты здесь: сама рекурренция, периодичность чётности и инвариант о том, что две соседние числа Фибоначчи полностью определяют следующий шаг.
Поскольку каждый член равен сумме двух предыдущих, знание двух соседних значений полностью фиксирует дальнейшее поведение последовательности. При старте с \(F_1=1\) и \(F_2=2\) получаем
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\dots$$
Отсюда сразу следует удобный инвариант реализации: если в некоторый момент хранятся два соседних члена \((F_k,F_{k+1})\), то одно обновление переводит состояние в \((F_{k+1},F_{k+2})\). Именно это и делает код.
Главное упрощение возникает при рассмотрении рекурренции по модулю \(2\). Здесь важна только чётность, то есть значения \(0\) и \(1\):
$$F_1\equiv 1,\qquad F_2\equiv 0\pmod 2.$$
Если проследить пары соседних членов по модулю \(2\), получится цикл
$$\bigl(F_n,F_{n+1}\bigr)\equiv (1,0)\to(0,1)\to(1,1)\to(1,0)\pmod 2.$$
Пара возвращается к исходному состоянию через три шага, значит, чётность периодична с периодом \(3\). Следовательно,
$$F_n\text{ чётно}\iff n\equiv 2\pmod 3.$$
Это точно выделяет чётную подпоследовательность:
$$E_m=F_{3m-1}\qquad(m\ge 1),$$
и её первые члены равны \(2,8,34,144,\dots\).
Если брать каждый третий член Фибоначчи, снова получается линейная рекуррентная последовательность. Обозначим
$$A=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix},\qquad \begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix}=A^{n-1}\begin{pmatrix}2\\ 1\end{pmatrix}.$$
Переход сразу на три шага вперёд задаётся матрицей
$$A^3=\begin{pmatrix}3 & 2\\ 2 & 1\end{pmatrix}.$$
Её след равен \(4\), а определитель равен \(-1\), поэтому характеристический многочлен имеет вид
$$\lambda^2-4\lambda-1=0.$$
Отсюда любая скалярная последовательность, возникающая при повторном применении \(A^3\), удовлетворяет соотношению
$$x_{m+2}=4x_{m+1}+x_m.$$
В частности, для чётных чисел Фибоначчи получаем
$$\boxed{E_{m+2}=4E_{m+1}+E_m,\qquad E_1=2,\qquad E_2=8.}$$
Это стандартная рекурренция для решения, которое генерирует только чётные члены. Здесь она не используется напрямую, но хорошо объясняет внутреннюю структуру задачи.
Для суммы первых \(m\) чётных членов есть удобная формула. Начнём с основной рекурренции в виде
$$F_{n+2}=2F_n+F_{n-1}.$$
Подставляя \(n=3j-1\) и учитывая \(E_j=F_{3j-1}\), получаем
$$F_{3j+1}-F_{3j-2}=2E_j.$$
Если просуммировать это по \(j=1,\dots,m\), средние слагаемые сократятся телескопически:
$$2\sum_{j=1}^{m}E_j=\sum_{j=1}^{m}\left(F_{3j+1}-F_{3j-2}\right)=F_{3m+1}-F_1=F_{3m+1}-1.$$
Значит,
$$\boxed{\sum_{j=1}^{m}E_j=\frac{F_{3m+1}-1}{2}.}$$
То есть, зная последний чётный член ниже границы, можно выразить всю сумму через один более поздний член Фибоначчи. Реализация всё равно выбирает прямой проход: он проще и уже достаточно эффективен.7
Числа Фибоначчи, меньшие \(100\), таковы:
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89.$$
Чётные среди них: \(2,8,34\), поэтому искомая сумма равна
$$2+8+34=44.$$
В обозначениях подпоследовательности это \(E_1+E_2+E_3\). Закрытая формула даёт тот же результат:
$$E_1+E_2+E_3=\frac{F_{10}-1}{2}=\frac{89-1}{2}=44.$$
Реализации на C++, Python и Java хранят два соседних числа Фибоначчи и текущую сумму. Перед каждой итерацией цикла сохранённая пара имеет вид \((F_k,F_{k+1})\) для некоторого \(k\). Второй элемент пары является текущим кандидатом, потому что последовательность начинается с \(1,2\), и первое потенциально учитываемое значение уже находится там.
Каждая итерация делает три шага: проверяет, не вышел ли текущий член за предел \(N\), прибавляет его к сумме, если он чётный, и затем сдвигает пару к следующей соседней паре. Благодаря этому инвариант \((F_k,F_{k+1})\mapsto(F_{k+1},F_{k+2})\) сохраняется на всём протяжении выполнения.
Цикл прекращается, когда текущий член превышает границу. Так как числа Фибоначчи после начальных положительных членов растут строго монотонно, каждый допустимый чётный член посещается ровно один раз. В реализациях также есть контрольный пример \(N=100\mapsto 44\), совпадающий с разобранным выше случаем.
Пусть \(t\) - наибольший индекс, для которого \(F_t\le N\). Из-за экспоненциального роста чисел Фибоначчи имеем \(t=\Theta(\log N)\). На каждый сгенерированный член тратится константное время, поэтому общая трудоёмкость равна
$$O(\log N).$$
Хранится лишь постоянное число целочисленных переменных, следовательно, расход памяти равен
$$O(1).$$
Если бы использовалась только рекурренция \(E_{m+2}=4E_{m+1}+E_m\), улучшился бы лишь постоянный множитель, но не асимптотический порядок.
تطلب المسألة الثانية من Project Euler إيجاد مجموع حدود فيبوناتشي الزوجية التي لا تتجاوز \(4{,}000{,}000\). أمّا التطبيقات هنا فتعمم ذلك إلى حد علوي عام \(N\)، لكن المتتالية نفسها هي المتتالية المعروفة في نص المسألة: \(1,2,3,5,8,13,\dots\).
لذلك فالمطلوب ليس فحص جميع الأعداد حتى \(N\)، بل استغلال بنية متتالية فيبوناتشي بحيث نزور فقط الحدود التي تدخل فعلاً في المجموع.
في هذه المسألة نعرّف متتالية فيبوناتشي كما يلي:
$$F_1=1,\qquad F_2=2,\qquad F_{n+2}=F_{n+1}+F_n\quad(n\ge 1).$$
والمطلوب حساب
$$S(N)=\sum_{\substack{n\ge 1\\F_n\le N\\2\mid F_n}}F_n.$$
العناصر الرياضية الحاسمة هنا هي علاقة التكرار الأساسية، والنمط الدوري للزوجية، والثابت الذي يقول إن حدين متتاليين من فيبوناتشي يكفيان لتحديد الحالة التالية بالكامل.
بما أن كل حد هو مجموع الحدين السابقين، فإن معرفة حدين متتاليين تكفي لتحديد جميع الحدود اللاحقة. انطلاقاً من \(F_1=1\) و\(F_2=2\)، نحصل على
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\dots$$
ومن هنا نحصل مباشرة على ثابت مناسب جداً للتنفيذ: إذا كانت الحالة الحالية هي \((F_k,F_{k+1})\)، فإن خطوة تحديث واحدة تحولها إلى \((F_{k+1},F_{k+2})\). وهذا هو بالضبط ما تعتمد عليه الشيفرات.
أهم تبسيط مفاهيمي يأتي من دراسة العلاقة التكرارية بترديد \(2\). بما أن ما يهمنا هو الزوجية فقط، يكفي أن نمثل كل حد بالقيمتين \(0\) أو \(1\):
$$F_1\equiv 1,\qquad F_2\equiv 0\pmod 2.$$
وعند تتبع الأزواج المتتالية بترديد \(2\) يظهر المسار الدوري
$$\bigl(F_n,F_{n+1}\bigr)\equiv (1,0)\to(0,1)\to(1,1)\to(1,0)\pmod 2.$$
يعود الزوج إلى حالته الابتدائية بعد ثلاث خطوات، لذلك يكون نمط الزوجية دورياً بفترة \(3\). ومن ثم
$$2\mid F_n\iff n\equiv 2\pmod 3.$$
وهذا يحدد المتتالية الفرعية الزوجية بدقة على أنها
$$E_m=F_{3m-1}\qquad(m\ge 1),$$
وأول حدودها هي \(2,8,34,144,\dots\).
إذا أخذنا كل حد ثالث من فيبوناتشي فإننا نحصل مرة أخرى على متتالية خطية. لنكتب
$$A=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix},\qquad \begin{pmatrix}F_{n+1}\\ F_n\end{pmatrix}=A^{n-1}\begin{pmatrix}2\\ 1\end{pmatrix}.$$
والانتقال ثلاث خطوات دفعة واحدة يكافئ الضرب في
$$A^3=\begin{pmatrix}3 & 2\\ 2 & 1\end{pmatrix}.$$
أثر هذه المصفوفة يساوي \(4\)، ومحددها يساوي \(-1\)، ولذلك يكون كثير الحدود المميز لها
$$\lambda^2-4\lambda-1=0.$$
ومن هنا فإن أي متتالية عددية تُستخرج من التكرار المتتالي لـ \(A^3\) تحقق
$$x_{m+2}=4x_{m+1}+x_m.$$
وبشكل خاص فإن الحدود الزوجية من فيبوناتشي تحقق
$$\boxed{E_{m+2}=4E_{m+1}+E_m,\qquad E_1=2,\qquad E_2=8.}$$
هذه هي العلاقة المشهورة للحل الذي يولد الحدود الزوجية فقط. التنفيذات هنا لا تحتاج إليها مباشرة، لكنها تشرح لماذا تنمو هذه المتتالية الفرعية بنمط منتظم وواضح.
يوجد أيضاً تطابق لطيف لمجموع أول \(m\) من الحدود الزوجية. نبدأ بإعادة كتابة العلاقة الأساسية على الصورة
$$F_{n+2}=2F_n+F_{n-1}.$$
وبوضع \(n=3j-1\) مع \(E_j=F_{3j-1}\) نحصل على
$$F_{3j+1}-F_{3j-2}=2E_j.$$
وعندما نجمع هذه العلاقة من \(j=1\) إلى \(m\)، تتلاشى الحدود الوسطية على نحو تلسكوبي:
$$2\sum_{j=1}^{m}E_j=\sum_{j=1}^{m}\left(F_{3j+1}-F_{3j-2}\right)=F_{3m+1}-F_1=F_{3m+1}-1.$$
إذن
$$\boxed{\sum_{j=1}^{m}E_j=\frac{F_{3m+1}-1}{2}.}$$
أي إن معرفة آخر حد زوجي تحت السقف تكفي لاستخراج المجموع كله من حد فيبوناتشي لاحق واحد. ومع ذلك يختار التنفيذ المرور المباشر لأنه أبسط، ولأنه سريع بما فيه الكفاية بالفعل.7
حدود فيبوناتشي الأصغر من \(100\) هي
$$1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89.$$
والحدود الزوجية منها هي \(2,8,34\)، ولذلك يكون المجموع المطلوب
$$2+8+34=44.$$
وبترميز المتتالية الفرعية هذا هو \(E_1+E_2+E_3\). كما أن الصيغة المغلقة تعطي النتيجة نفسها فوراً:
$$E_1+E_2+E_3=\frac{F_{10}-1}{2}=\frac{89-1}{2}=44.$$
تحتفظ تطبيقات C++ وPython وJava بحدين متتاليين من فيبوناتشي مع مجموع جارٍ. وقبل كل دورة من الحلقة تكون الحالة المخزنة هي بالضبط \((F_k,F_{k+1})\) لبعض \(k\). والحد الثاني هو الحد الحالي المرشح للإضافة لأن المتتالية تبدأ بـ \(1,2\)، وبالتالي فإن أول حد قد يساهم في الجواب موجود هناك منذ البداية.
كل دورة تنفذ ثلاث عمليات: تتحقق أولاً من أن الحد الحالي لم يتجاوز السقف، ثم تضيفه إلى المجموع إذا كان زوجياً، ثم تدفع الزوج إلى الزوج التالي من الحدود المتتالية. وبهذا يُحفَظ الثابت \((F_k,F_{k+1})\mapsto(F_{k+1},F_{k+2})\) طوال التنفيذ.
تتوقف الحلقة عندما يتجاوز الحد الحالي القيمة \(N\). وبما أن أعداد فيبوناتشي تصبح متزايدة بصرامة بعد البداية الموجبة، فإن كل حد زوجي صالح يُزار مرة واحدة فقط. كما تتضمن التطبيقات نقطة تحقق \(N=100\mapsto 44\)، وهي مطابقة تماماً للمثال السابق.
لتكن \(t\) أكبر فهرس يحقق \(F_t\le N\). وبسبب النمو الأسي لأعداد فيبوناتشي فإن \(t=\Theta(\log N)\). ومع كون العمل في كل خطوة ثابتاً، فإن الزمن الكلي يساوي
$$O(\log N).$$
ولا تُخزَّن إلا مجموعة ثابتة من المتغيرات الصحيحة، ولذلك يكون استهلاك الذاكرة
$$O(1).$$
ولو استُخدمت علاقة الحدود الزوجية فقط \(E_{m+2}=4E_{m+1}+E_m\)، فلن يتغير سوى العامل الثابت لا الرتبة التقاربية.