Problem 918 defines an integer sequence by
$$a_1=1,\qquad a_{2k}=2a_k,\qquad a_{2k+1}=a_k-3a_{k+1}.$$
The quantity to compute is the prefix sum
$$S(n)=\sum_{i=1}^{n} a_i$$
at the large input \(n=10^{12}\).
A direct approach would try to generate every term up to \(a_{10^{12}}\), but the index is far too large for that. The recurrence also shows why a one-term viewpoint is insufficient: the odd rule depends on both \(a_k\) and \(a_{k+1}\). The real task is to find a state that stays closed when the index is halved, then express the whole prefix sum through that smaller state.
The solution has two decisive ingredients. First, the correct recursive object is the adjacent pair \((a_n,a_{n+1})\), not a single sequence value. Second, once the prefix sum is grouped into even-odd blocks, it telescopes to a formula involving only one sequence term at roughly half the original index.
If we want \(a_{2k}\), the recurrence gives it immediately from \(a_k\). But for an odd index we have
$$a_{2k+1}=a_k-3a_{k+1},$$
so the value at index \(2k+1\) depends on two neighboring terms at the smaller scale. That means any recursive algorithm based only on \(a_n\) would keep needing one extra value. The natural way to close the recursion is therefore to carry those two values together.
Define the state
$$P(n)=(a_n,a_{n+1}).$$
The base case is immediate:
$$P(1)=(a_1,a_2)=(1,2).$$
Now write \(P(k)=(x,y)=(a_k,a_{k+1})\). Then the recurrence gives two parity-dependent transitions:
$$P(2k)=(a_{2k},a_{2k+1})=(2a_k,\ a_k-3a_{k+1})=(2x,\ x-3y),$$
$$P(2k+1)=(a_{2k+1},a_{2k+2})=(a_k-3a_{k+1},\ 2a_{k+1})=(x-3y,\ 2y).$$
This pair is the exact invariant used by the implementations: once \((a_k,a_{k+1})\) is known, either \((a_{2k},a_{2k+1})\) or \((a_{2k+1},a_{2k+2})\) follows in constant time.
To compute \(P(n)\), the formulas above require only \(P(\lfloor n/2\rfloor)\). Each recursive call therefore makes exactly one smaller call:
$$n,\ \left\lfloor \frac{n}{2} \right\rfloor,\ \left\lfloor \frac{n}{4} \right\rfloor,\ \dots,\ 1.$$
When the recursion unwinds, the parity of each intermediate index chooses which linear transformation to apply. The depth is the number of binary digits of \(n\), so recovering \(a_n\) or \(P(n)\) takes only \(O(\log n)\) arithmetic steps.
The prefix sum becomes tractable when terms are grouped as \((a_{2j},a_{2j+1})\). For every \(j\ge 1\),
$$a_{2j}+a_{2j+1}=2a_j+(a_j-3a_{j+1})=3(a_j-a_{j+1}).$$
This identity is the key simplification. A block at large indices becomes a simple difference of adjacent terms at smaller indices, and differences of that form telescope when summed over \(j\).
Let \(m\ge 1\). For an odd prefix length, isolate the first term and pair the rest:
$$S(2m-1)=a_1+\sum_{j=1}^{m-1}(a_{2j}+a_{2j+1}).$$
Substituting the block identity yields
$$S(2m-1)=1+3\sum_{j=1}^{m-1}(a_j-a_{j+1}).$$
The sum telescopes immediately:
$$\sum_{j=1}^{m-1}(a_j-a_{j+1})=a_1-a_m=1-a_m,$$
so
$$S(2m-1)=1+3(1-a_m)=4-3a_m.$$
For an even prefix, add the final even term \(a_{2m}=2a_m\):
$$S(2m)=S(2m-1)+a_{2m}=4-3a_m+2a_m=4-a_m.$$
That reduces the whole problem to one sequence value:
$$S(2m-1)=4-3a_m,\qquad S(2m)=4-a_m.$$
Because \(10^{12}=2\cdot 5\cdot 10^{11}\), the target answer comes from a single term:
$$S(10^{12})=4-a_{5\cdot 10^{11}}.$$
The first ten terms are
$$a_1=1,\quad a_2=2,\quad a_3=-5,\quad a_4=4,\quad a_5=17,\quad a_6=-10,\quad a_7=-17,\quad a_8=8,\quad a_9=-47,\quad a_{10}=34.$$
To recover \(a_5\), follow the halving chain \(5\to 2\to 1\):
$$P(1)=(1,2),\qquad P(2)=(2,-5),\qquad P(5)=(17,-10).$$
So \(a_5=17\). The closed forms then give
$$S(9)=4-3a_5=4-51=-47,$$
$$S(10)=4-a_5=4-17=-13.$$
Direct summation confirms the same values:
$$1+2-5+4+17-10-17+8-47=-47,$$
$$1+2-5+4+17-10-17+8-47+34=-13.$$
This example already contains the full method used for the large input: compute one carefully chosen term by recursive halving, then substitute it into the appropriate prefix identity.
The C++, Python, and Java implementations all follow the derivation above. None of them expands the sequence up to the target index. Instead, they solve only the single recursive branch forced by repeated halving.
The core routine receives an index \(n\) and returns the adjacent pair \((a_n,a_{n+1})\). The base case is \((1,2)\). For larger \(n\), the implementation first computes the pair at \(\lfloor n/2\rfloor\), then rebuilds the answer with one of the two formulas above depending on whether \(n\) is even or odd.
Because there is only one recursive branch, no table or memoization is necessary. Each level contributes only a handful of additions, subtractions, and doublings.
After the implementation can recover \(a_m\), the prefix sum wrapper is just a parity test on \(n\). If \(n\) is even, it returns \(4-a_{n/2}\). If \(n\) is odd, it returns \(4-3a_{(n+1)/2}\). For the Project Euler input \(10^{12}\), the computation therefore stops at the single term \(a_{5\cdot 10^{11}}\).
The C++ implementation also includes a small built-in validation step: it checks the first ten sequence values against explicit known data and compares the fast prefix formula with direct summation for small indices before printing the large answer. The Python and Java implementations keep only the compact fast path.
Each recursive level halves the index, so computing \((a_n,a_{n+1})\) takes \(O(\log n)\) arithmetic operations. Converting that result into \(S(n)\) adds only \(O(1)\) work.
The recursive form uses \(O(\log n)\) extra memory for the call stack. An iterative reconstruction along the same halving chain could reduce the extra space to \(O(1)\), but for this problem the recursive version is already short and direct.
Problem 918 definiert eine ganzzahlige Folge durch
$$a_1=1,\qquad a_{2k}=2a_k,\qquad a_{2k+1}=a_k-3a_{k+1}.$$
Gesucht ist die Präfixsumme
$$S(n)=\sum_{i=1}^{n} a_i$$
für den sehr großen Zielwert \(n=10^{12}\).
Alle Terme bis \(a_{10^{12}}\) explizit zu erzeugen, ist praktisch ausgeschlossen. Zudem zeigt schon die Formel für ungerade Indizes, dass eine Beschreibung über nur einen einzelnen Wert nicht geschlossen ist: \(a_{2k+1}\) hängt von \(a_k\) und \(a_{k+1}\) ab. Man braucht also einen rekursiven Zustand, der beim Halbieren des Index stabil bleibt, und daraus eine geschlossene Form für die Präfixsumme.
Die Lösung ruht auf zwei aufgabenspezifischen Beobachtungen. Erstens ist das richtige rekursive Objekt das Nachbarpaar \((a_n,a_{n+1})\). Zweitens wird die Präfixsumme nach einer Zerlegung in Gerade-Ungerade-Blöcke teleskopisch und schrumpft auf genau einen Folgenterm bei ungefähr halbiertem Index zusammen.
Für gerade Indizes ist die Rekursion einfach: \(a_{2k}=2a_k\). Bei ungeraden Indizes gilt jedoch
$$a_{2k+1}=a_k-3a_{k+1},$$
und damit hängt der neue Wert von zwei benachbarten kleineren Werten ab. Eine Rekursion, die nur \(a_n\) transportiert, müsste also ständig einen zusätzlichen Nachbarwert nachfordern. Der kleinste wirklich geschlossene Zustand ist daher ein Paar.
Definiere
$$P(n)=(a_n,a_{n+1}).$$
Der Startwert ist sofort bekannt:
$$P(1)=(a_1,a_2)=(1,2).$$
Schreibt man \(P(k)=(x,y)=(a_k,a_{k+1})\), so folgen aus der Definition der Folge die beiden Übergänge
$$P(2k)=(a_{2k},a_{2k+1})=(2a_k,\ a_k-3a_{k+1})=(2x,\ x-3y),$$
$$P(2k+1)=(a_{2k+1},a_{2k+2})=(a_k-3a_{k+1},\ 2a_{k+1})=(x-3y,\ 2y).$$
Genau das ist die Invariante der Implementierungen: Kennt man \((a_k,a_{k+1})\), dann erhält man in konstanter Zeit das passende Paar auf der nächsten Ebene.
Zur Berechnung von \(P(n)\) wird nur \(P(\lfloor n/2\rfloor)\) benötigt. Deshalb erzeugt jeder Rekursionsschritt genau einen kleineren Aufruf:
$$n,\ \left\lfloor \frac{n}{2} \right\rfloor,\ \left\lfloor \frac{n}{4} \right\rfloor,\ \dots,\ 1.$$
Beim Zurückkehren aus der Rekursion entscheidet jeweils die Parität des Zwischenindex, welche der beiden linearen Transformationen angewandt wird. Die Anzahl der Ebenen ist gleich der Anzahl der Binärstellen von \(n\), also kostet die Berechnung nur \(O(\log n)\).
Die Summe vereinfacht sich entscheidend, wenn man Terme als \((a_{2j},a_{2j+1})\) gruppiert. Für jedes \(j\ge 1\) gilt
$$a_{2j}+a_{2j+1}=2a_j+(a_j-3a_{j+1})=3(a_j-a_{j+1}).$$
Damit wird ein Zweierblock großer Indizes auf eine Differenz zweier benachbarter kleinerer Terme reduziert. Genau diese Differenzstruktur erzeugt beim Summieren ein Teleskop.
Sei \(m\ge 1\). Für ein ungerades Präfix trennt man \(a_1\) ab und fasst den Rest in Blöcken zusammen:
$$S(2m-1)=a_1+\sum_{j=1}^{m-1}(a_{2j}+a_{2j+1}).$$
Mit der Blockidentität folgt
$$S(2m-1)=1+3\sum_{j=1}^{m-1}(a_j-a_{j+1}).$$
Diese Summe teleskopiert sofort:
$$\sum_{j=1}^{m-1}(a_j-a_{j+1})=a_1-a_m=1-a_m,$$
also
$$S(2m-1)=1+3(1-a_m)=4-3a_m.$$
Für ein gerades Präfix muss nur noch der letzte gerade Term ergänzt werden:
$$S(2m)=S(2m-1)+a_{2m}=4-3a_m+2a_m=4-a_m.$$
Somit reduziert sich die gesamte Aufgabe auf einen einzigen Folgenterm:
$$S(2m-1)=4-3a_m,\qquad S(2m)=4-a_m.$$
Weil \(10^{12}=2\cdot 5\cdot 10^{11}\) ist, genügt am Ende die Berechnung von
$$S(10^{12})=4-a_{5\cdot 10^{11}}.$$
Die ersten zehn Folgenglieder lauten
$$a_1=1,\quad a_2=2,\quad a_3=-5,\quad a_4=4,\quad a_5=17,\quad a_6=-10,\quad a_7=-17,\quad a_8=8,\quad a_9=-47,\quad a_{10}=34.$$
Um \(a_5\) zu gewinnen, verfolgt man die Halbierungskette \(5\to 2\to 1\):
$$P(1)=(1,2),\qquad P(2)=(2,-5),\qquad P(5)=(17,-10).$$
Daraus folgt \(a_5=17\). Also liefern die geschlossenen Formeln
$$S(9)=4-3a_5=4-51=-47,$$
$$S(10)=4-a_5=4-17=-13.$$
Direktes Addieren bestätigt dieselben Werte:
$$1+2-5+4+17-10-17+8-47=-47,$$
$$1+2-5+4+17-10-17+8-47+34=-13.$$
Damit ist die Gesamtstrategie bereits sichtbar: einen geschickt ausgewählten Folgenterm per Rekursion bestimmen und ihn anschließend in die passende Präfixformel einsetzen.
Die C++-, Python- und Java-Implementierungen folgen exakt dieser Herleitung. Keine von ihnen entwickelt die Folge bis zum Zielindex vollständig; alle benutzen nur die einzelne Rekursionskette, die durch wiederholtes Halbieren entsteht.
Die zentrale Routine erhält einen Index \(n\) und liefert das Paar \((a_n,a_{n+1})\). Der Basisfall ist \((1,2)\). Für größere Indizes wird zunächst das Paar bei \(\lfloor n/2\rfloor\) berechnet und danach, je nach Parität von \(n\), mit einer der beiden Übergangsformeln auf die gewünschte Ebene zurückgehoben.
Da es nur einen rekursiven Zweig gibt, braucht die Implementierung weder Memoisierung noch große Tabellen. Pro Ebene fallen nur wenige Additionen, Subtraktionen und Verdopplungen an.
Sobald \(a_m\) bestimmt werden kann, ist die eigentliche Präfixsumme nur noch eine Fallunterscheidung nach der Parität von \(n\): bei geradem \(n\) wird \(4-a_{n/2}\) verwendet, bei ungeradem \(n\) \(4-3a_{(n+1)/2}\). Für den Problemwert \(10^{12}\) endet die Rechnung deshalb bei dem einzelnen Term \(a_{5\cdot 10^{11}}\).
Die C++-Version enthält zusätzlich eine kleine Selbstkontrolle: Sie überprüft die ersten zehn Folgenglieder gegen bekannte Werte und vergleicht die schnelle Präfixformel für kleine Indizes mit einer direkten Summation, bevor sie die große Zielausgabe druckt. Die Python- und Java-Versionen enthalten nur den kompakten schnellen Pfad.
Jede Rekursionsebene halbiert den Index, also benötigt die Berechnung von \((a_n,a_{n+1})\) \(O(\log n)\) arithmetische Operationen. Die Umwandlung in \(S(n)\) kostet anschließend nur \(O(1)\).
Der zusätzliche Speicherbedarf ist wegen des Rekursionsstapels \(O(\log n)\). Eine iterative Variante entlang derselben Halbierungskette könnte den Zusatzspeicher auf \(O(1)\) drücken, aber für diese Aufgabe ist die rekursive Form bereits knapp und klar.
Problem 918 şu tamsayı dizisini tanımlar:
$$a_1=1,\qquad a_{2k}=2a_k,\qquad a_{2k+1}=a_k-3a_{k+1}.$$
İstenen büyüklük önek toplamdır:
$$S(n)=\sum_{i=1}^{n} a_i$$
ve hedef değer \(n=10^{12}\) kadar büyüktür.
Terimleri sırayla üretip toplamak pratik değildir. Daha önemlisi, bağıntı tek bir terim üzerinde kapanmaz; çünkü \(a_{2k+1}\) aynı anda hem \(a_k\) hem de \(a_{k+1}\) değerini ister. Bu yüzden çözüm önce indeksi ikiye bölünce kapalı kalan doğru durumu bulur, sonra da önek toplamı bu daha küçük durum üzerinden ifade eder.
Çözümün omurgası iki problem-özgü gözleme dayanır. Birincisi, doğal özyinelemeli nesne tek bir \(a_n\) değil, komşu çift \((a_n,a_{n+1})\) değeridir. İkincisi, terimler doğru şekilde çiftlenince önek toplam teleskopik hale gelir ve yaklaşık yarı indeksteki tek bir dizi terimine iner.
Çift indislerde bağıntı basittir: \(a_{2k}=2a_k\). Fakat tek indislerde
$$a_{2k+1}=a_k-3a_{k+1}$$
olduğu için yeni değer, daha küçük ölçekteki iki komşu terime birden bağlıdır. Sadece \(a_n\) taşıyan bir özyineleme bu yüzden sürekli ek bir komşu değere ihtiyaç duyar. Kapalı kalan en küçük durum doğal olarak bir çifttir.
Şöyle tanımlayalım:
$$P(n)=(a_n,a_{n+1}).$$
Başlangıç durumu hemen bulunur:
$$P(1)=(a_1,a_2)=(1,2).$$
\(P(k)=(x,y)=(a_k,a_{k+1})\) yazarsak, dizinin tanımı şu iki dönüşümü verir:
$$P(2k)=(a_{2k},a_{2k+1})=(2a_k,\ a_k-3a_{k+1})=(2x,\ x-3y),$$
$$P(2k+1)=(a_{2k+1},a_{2k+2})=(a_k-3a_{k+1},\ 2a_{k+1})=(x-3y,\ 2y).$$
Uygulamaların koruduğu temel değişmez budur: \((a_k,a_{k+1})\) biliniyorsa, bir üst seviyedeki gerekli komşu çift sabit zamanda yeniden kurulabilir.
\(P(n)\) hesabı için yalnızca \(P(\lfloor n/2\rfloor)\) gerekir. Bu yüzden her özyinelemeli çağrı tam bir daha küçük çağrı üretir:
$$n,\ \left\lfloor \frac{n}{2} \right\rfloor,\ \left\lfloor \frac{n}{4} \right\rfloor,\ \dots,\ 1.$$
Özyineleme geri açılırken her ara indeksin tek mi çift mi olduğuna bakılır ve uygun doğrusal dönüşüm uygulanır. Seviye sayısı \(n\)'nin ikili basamak sayısıyla aynı mertebededir; dolayısıyla \(a_n\) ya da \(P(n)\) hesabı \(O(\log n)\) zamanda yapılır.
Asıl sadeleşme, terimleri \((a_{2j},a_{2j+1})\) blokları halinde toplamaktır. Her \(j\ge 1\) için
$$a_{2j}+a_{2j+1}=2a_j+(a_j-3a_{j+1})=3(a_j-a_{j+1}).$$
Böylece büyük indislerdeki iki terimlik bir blok, daha küçük indislerdeki komşu iki terimin farkına dönüşür. Bu fark yapısı toplandığında teleskopik sadeleşme otomatik olarak ortaya çıkar.
\(m\ge 1\) olsun. Tek uzunluklu bir önekte önce \(a_1\)'i ayırıp geri kalanı bloklar halinde yazarız:
$$S(2m-1)=a_1+\sum_{j=1}^{m-1}(a_{2j}+a_{2j+1}).$$
Blok özdeşliğini yerine koyunca
$$S(2m-1)=1+3\sum_{j=1}^{m-1}(a_j-a_{j+1})$$
elde edilir. Bu toplam teleskopiktir:
$$\sum_{j=1}^{m-1}(a_j-a_{j+1})=a_1-a_m=1-a_m,$$
dolayısıyla
$$S(2m-1)=1+3(1-a_m)=4-3a_m.$$
Çift uzunluklu önek için yalnızca son terimi eklemek gerekir:
$$S(2m)=S(2m-1)+a_{2m}=4-3a_m+2a_m=4-a_m.$$
Sonuç olarak bütün problem tek bir dizi terimine indirgenir:
$$S(2m-1)=4-3a_m,\qquad S(2m)=4-a_m.$$
\(10^{12}=2\cdot 5\cdot 10^{11}\) olduğundan nihai cevap
$$S(10^{12})=4-a_{5\cdot 10^{11}}$$
biçiminde tek bir terimden elde edilir.
Dizinin ilk on terimi şöyledir:
$$a_1=1,\quad a_2=2,\quad a_3=-5,\quad a_4=4,\quad a_5=17,\quad a_6=-10,\quad a_7=-17,\quad a_8=8,\quad a_9=-47,\quad a_{10}=34.$$
\(a_5\) değerini bulmak için yarıya bölme zinciri \(5\to 2\to 1\) izlenir:
$$P(1)=(1,2),\qquad P(2)=(2,-5),\qquad P(5)=(17,-10).$$
Buradan \(a_5=17\) gelir. Kapalı formüller o zaman
$$S(9)=4-3a_5=4-51=-47,$$
$$S(10)=4-a_5=4-17=-13$$
sonuçlarını verir. Doğrudan toplama da aynı değerleri üretir:
$$1+2-5+4+17-10-17+8-47=-47,$$
$$1+2-5+4+17-10-17+8-47+34=-13.$$
Bu küçük örnek tam stratejiyi gösterir: doğru seçilmiş tek bir terimi hesapla, sonra onu uygun önek toplam özdeşliğine yerleştir.
C++, Python ve Java uygulamaları bu türetimi doğrudan izler. Hiçbiri diziyi hedef indekse kadar genişletmez; hepsi yalnızca sürekli yarıya bölünerek oluşan tek özyineleme dalını çözer.
Merkez yordam bir \(n\) indeksi alır ve \((a_n,a_{n+1})\) çiftini döndürür. Taban durum \((1,2)\)'dir. Daha büyük her \(n\) için önce \(\lfloor n/2\rfloor\) seviyesindeki çift hesaplanır, ardından \(n\)'nin paritesine göre yukarıdaki iki formülden biri uygulanarak istenen çift yeniden kurulur.
Yalnızca tek bir alt çağrı olduğu için ne büyük bir tabloya ne de memoization'a ihtiyaç vardır. Her seviyede birkaç toplama, çıkarma ve ikiyle çarpma yeterlidir.
Uygulama \(a_m\) değerini elde edebildiği anda önek toplam yalnızca pariteye bağlı kısa bir sarmalayıcıdır. \(n\) çiftse \(4-a_{n/2}\), tekse \(4-3a_{(n+1)/2}\) kullanılır. Bu yüzden Project Euler girdisinde hesap doğrudan \(a_{5\cdot 10^{11}}\) teriminde biter.
C++ sürümü ayrıca küçük bir yerel doğrulama içerir: ilk on terimi bilinen değerlerle karşılaştırır ve hızlı önek toplam formülünü küçük indislerde doğrudan toplamayla test ettikten sonra büyük çıktıyı üretir. Python ve Java sürümleri ise yalnızca kısa hızlı yolu içerir.
Her özyineleme seviyesi indeksi ikiye böldüğü için \((a_n,a_{n+1})\) hesabı \(O(\log n)\) aritmetik işlem gerektirir. Bu sonucu \(S(n)\)'e çevirmek ek olarak yalnızca \(O(1)\) iş yapar.
Özyinelemeli yazım nedeniyle ek bellek kullanımı \(O(\log n)\)'dir. Aynı yarıya bölme zinciri iteratif kurulsa ek alan \(O(1)\)'e indirilebilirdi; ancak bu problemde özyinelemeli biçim zaten kısa ve nettir.
El problema 918 define la sucesion entera
$$a_1=1,\qquad a_{2k}=2a_k,\qquad a_{2k+1}=a_k-3a_{k+1}.$$
La cantidad pedida es la suma prefijo
$$S(n)=\sum_{i=1}^{n} a_i$$
para el valor grande \(n=10^{12}\).
Generar todos los terminos hasta ese indice no es viable. Ademas, la regla impar deja claro que la recurrencia no se cierra sobre un solo valor, porque \(a_{2k+1}\) depende a la vez de \(a_k\) y de \(a_{k+1}\). La solucion correcta consiste en encontrar un estado que siga cerrado al dividir el indice entre dos y luego reescribir la suma prefijo en funcion de ese estado reducido.
Toda la derivacion se apoya en dos hechos muy concretos de esta sucesion. El primero es que el objeto recursivo natural es el par adyacente \((a_n,a_{n+1})\). El segundo es que, al reagrupar la suma prefijo en bloques par-impar, aparece una cancelacion telescopica que la reduce a un unico termino de la sucesion con indice aproximadamente dividido por dos.
Para indices pares, la regla es sencilla: \(a_{2k}=2a_k\). Pero para indices impares se tiene
$$a_{2k+1}=a_k-3a_{k+1},$$
de modo que el nuevo valor depende de dos terminos vecinos de escala menor. Cualquier recursion que transporte solo \(a_n\) quedaria obligada a pedir un valor adicional en el siguiente paso. El estado minimo realmente cerrado es, por tanto, un par.
Definimos
$$P(n)=(a_n,a_{n+1}).$$
El caso base es inmediato:
$$P(1)=(a_1,a_2)=(1,2).$$
Si escribimos \(P(k)=(x,y)=(a_k,a_{k+1})\), entonces las reglas de la sucesion producen
$$P(2k)=(a_{2k},a_{2k+1})=(2a_k,\ a_k-3a_{k+1})=(2x,\ x-3y),$$
$$P(2k+1)=(a_{2k+1},a_{2k+2})=(a_k-3a_{k+1},\ 2a_{k+1})=(x-3y,\ 2y).$$
Esa es exactamente la invariante que usan las implementaciones: una vez conocido \((a_k,a_{k+1})\), el par de la escala superior se reconstruye con trabajo constante.
Para calcular \(P(n)\), las formulas anteriores solo necesitan \(P(\lfloor n/2\rfloor)\). Por lo tanto, cada llamada genera una unica subllamada mas pequena:
$$n,\ \left\lfloor \frac{n}{2} \right\rfloor,\ \left\lfloor \frac{n}{4} \right\rfloor,\ \dots,\ 1.$$
Cuando la recursion vuelve hacia arriba, la paridad de cada indice intermedio determina cual de las dos transformaciones lineales debe aplicarse. El numero de niveles coincide con el numero de bits de \(n\), y por eso recuperar \(a_n\) cuesta \(O(\log n)\).
La simplificacion decisiva aparece al agrupar los terminos como \((a_{2j},a_{2j+1})\). Para todo \(j\ge 1\),
$$a_{2j}+a_{2j+1}=2a_j+(a_j-3a_{j+1})=3(a_j-a_{j+1}).$$
Asi, cada bloque de dos terminos grandes se convierte en una diferencia entre terminos vecinos con indice menor. Esa forma en diferencias es justamente la que produce el telescopado.
Sea \(m\ge 1\). Para una longitud impar, se separa primero \(a_1\) y luego se agrupa el resto:
$$S(2m-1)=a_1+\sum_{j=1}^{m-1}(a_{2j}+a_{2j+1}).$$
Sustituyendo la identidad de bloque, obtenemos
$$S(2m-1)=1+3\sum_{j=1}^{m-1}(a_j-a_{j+1}).$$
La suma telescopica es inmediata:
$$\sum_{j=1}^{m-1}(a_j-a_{j+1})=a_1-a_m=1-a_m,$$
y por tanto
$$S(2m-1)=1+3(1-a_m)=4-3a_m.$$
Para una longitud par basta anadir el ultimo termino par:
$$S(2m)=S(2m-1)+a_{2m}=4-3a_m+2a_m=4-a_m.$$
Con ello, toda la tarea se reduce a un unico valor de la sucesion:
$$S(2m-1)=4-3a_m,\qquad S(2m)=4-a_m.$$
Como \(10^{12}=2\cdot 5\cdot 10^{11}\), el objetivo final queda en
$$S(10^{12})=4-a_{5\cdot 10^{11}}.$$
Los primeros diez terminos son
$$a_1=1,\quad a_2=2,\quad a_3=-5,\quad a_4=4,\quad a_5=17,\quad a_6=-10,\quad a_7=-17,\quad a_8=8,\quad a_9=-47,\quad a_{10}=34.$$
Para obtener \(a_5\), seguimos la cadena \(5\to 2\to 1\):
$$P(1)=(1,2),\qquad P(2)=(2,-5),\qquad P(5)=(17,-10).$$
De ahi sale \(a_5=17\). Entonces las formulas cerradas dan
$$S(9)=4-3a_5=4-51=-47,$$
$$S(10)=4-a_5=4-17=-13.$$
La suma directa confirma los mismos valores:
$$1+2-5+4+17-10-17+8-47=-47,$$
$$1+2-5+4+17-10-17+8-47+34=-13.$$
Este ejemplo ya contiene la estrategia completa: calcular un solo termino bien elegido mediante division sucesiva del indice y sustituirlo en la identidad correcta para la suma prefijo.
Las implementaciones en C++, Python y Java siguen exactamente esta derivacion. Ninguna expande la sucesion hasta el indice final; todas recorren solo la unica rama recursiva impuesta por la cadena de divisiones entre dos.
La rutina central recibe un indice \(n\) y devuelve el par \((a_n,a_{n+1})\). El caso base es \((1,2)\). Para cualquier \(n\) mayor, la implementacion resuelve primero el subproblema en \(\lfloor n/2\rfloor\) y despues reconstruye el par pedido con una de las dos formulas, segun la paridad de \(n\).
Como solo existe una subllamada por nivel, no hace falta usar memoizacion ni tablas grandes. Cada nivel aporta solo unas pocas sumas, restas y multiplicaciones por dos.
Una vez que la implementacion puede recuperar \(a_m\), la suma prefijo es solo una decision segun la paridad de \(n\): \(4-a_{n/2}\) si \(n\) es par y \(4-3a_{(n+1)/2}\) si \(n\) es impar. Para la entrada concreta del problema, el proceso se detiene en el termino \(a_{5\cdot 10^{11}}\).
La version en C++ incluye ademas una validacion pequena: compara los diez primeros terminos con datos conocidos y contrasta la formula rapida de la suma prefijo con una suma directa para indices pequenos antes de imprimir la salida grande. Las versiones de Python y Java conservan solo el camino rapido.
Cada nivel recursivo divide el indice entre dos, asi que calcular \((a_n,a_{n+1})\) requiere \(O(\log n)\) operaciones aritmeticas. Convertir ese resultado en \(S(n)\) cuesta luego solo \(O(1)\).
El consumo de memoria es \(O(\log n)\) por la profundidad de la recursion. Si se reescribiera el mismo proceso de forma iterativa, el espacio extra podria bajar a \(O(1)\), pero para esta tarea la version recursiva ya es breve y clara.
第 918 题定义了一个整数序列：
$$a_1=1,\qquad a_{2k}=2a_k,\qquad a_{2k+1}=a_k-3a_{k+1}.$$
要求计算它的前缀和
$$S(n)=\sum_{i=1}^{n} a_i$$
其中目标输入是很大的 \(n=10^{12}\)。
如果顺序生成前 \(10^{12}\) 项再求和，代价显然无法接受。更关键的是，这个递推并不是只靠单个 \(a_n\) 就能闭合的普通形式，因为奇数下标公式同时依赖 \(a_k\) 和 \(a_{k+1}\)。因此真正要做的是找到一个在“下标减半”操作下仍然闭合的状态，再把整个前缀和改写成这个较小状态的函数。
这道题的解法建立在两个非常具体的结构上。第一，最自然的递归状态不是单个 \(a_n\)，而是相邻二元组 \((a_n,a_{n+1})\)。第二，把前缀和按“一个偶项加上紧跟的奇项”分组后，会出现望远镜消去，最后只剩下大约一半下标处的一个序列值。
对于偶数下标，递推很简单：\(a_{2k}=2a_k\)。但对于奇数下标，
$$a_{2k+1}=a_k-3a_{k+1},$$
新值同时依赖两个更小尺度上的相邻项。也就是说，如果递归状态只携带 \(a_n\)，下一层仍然会缺少一个邻项信息。要让递推真正封闭，最小而自然的状态就是把这两个相邻值一起带着走。
定义
$$P(n)=(a_n,a_{n+1}).$$
这是该问题下最小的闭合状态。起点立刻可得：
$$P(1)=(a_1,a_2)=(1,2).$$
如果记 \(P(k)=(x,y)=(a_k,a_{k+1})\)，那么由题目给出的递推式直接推出
$$P(2k)=(a_{2k},a_{2k+1})=(2a_k,\ a_k-3a_{k+1})=(2x,\ x-3y),$$
$$P(2k+1)=(a_{2k+1},a_{2k+2})=(a_k-3a_{k+1},\ 2a_{k+1})=(x-3y,\ 2y).$$
这正是实现所维护的不变量：一旦知道 \((a_k,a_{k+1})\)，就能在常数时间内恢复上一层需要的相邻二元组。
从上面的式子可以看出，要求 \(P(n)\)，只需要先知道 \(P(\lfloor n/2\rfloor)\)。因此每一层递归都只会进入一个更小的子问题：
$$n,\ \left\lfloor \frac{n}{2} \right\rfloor,\ \left\lfloor \frac{n}{4} \right\rfloor,\ \dots,\ 1.$$
等递归回溯时，再根据每个中间下标是奇数还是偶数，选择对应的线性变换。层数等于 \(n\) 的二进制位数，所以恢复 \(a_n\) 或 \(P(n)\) 的时间复杂度自然就是 \(O(\log n)\)。
前缀和之所以能大幅简化，关键在于把项写成 \((a_{2j},a_{2j+1})\) 这样的块。对任意 \(j\ge 1\)，都有
$$a_{2j}+a_{2j+1}=2a_j+(a_j-3a_{j+1})=3(a_j-a_{j+1}).$$
这一恒等式非常关键，因为高下标处的两项之和被改写成了较小下标处相邻两项的差，而这种差一旦在 \(j\) 上求和，就会自动产生望远镜消去。
设 \(m\ge 1\)。先看奇数长度前缀，把第一项单独拿出来，其余部分按块分组：
$$S(2m-1)=a_1+\sum_{j=1}^{m-1}(a_{2j}+a_{2j+1}).$$
代入刚才的块恒等式，就有
$$S(2m-1)=1+3\sum_{j=1}^{m-1}(a_j-a_{j+1}).$$
这里的和是标准的望远镜和：
$$\sum_{j=1}^{m-1}(a_j-a_{j+1})=a_1-a_m=1-a_m,$$
因此立刻得到
$$S(2m-1)=1+3(1-a_m)=4-3a_m.$$
若前缀长度是偶数，只需要再加上最后的 \(a_{2m}=2a_m\)：
$$S(2m)=S(2m-1)+a_{2m}=4-3a_m+2a_m=4-a_m.$$
这样，整个问题就被压缩成一个非常小的结论：
$$S(2m-1)=4-3a_m,\qquad S(2m)=4-a_m.$$
因为 \(10^{12}=2\cdot 5\cdot 10^{11}\)，真正要求的答案只需要一个序列值：
$$S(10^{12})=4-a_{5\cdot 10^{11}}.$$
先列出前十项：
$$a_1=1,\quad a_2=2,\quad a_3=-5,\quad a_4=4,\quad a_5=17,\quad a_6=-10,\quad a_7=-17,\quad a_8=8,\quad a_9=-47,\quad a_{10}=34.$$
如果要用二元组递归求 \(a_5\)，只要沿着链 \(5\to 2\to 1\) 向下，再向上重建：
$$P(1)=(1,2),\qquad P(2)=(2,-5),\qquad P(5)=(17,-10).$$
于是 \(a_5=17\)。再代入闭式，就得到
$$S(9)=4-3a_5=4-51=-47,$$
$$S(10)=4-a_5=4-17=-13.$$
直接相加也能验证：
$$1+2-5+4+17-10-17+8-47=-47,$$
$$1+2-5+4+17-10-17+8-47+34=-13.$$
这个例子已经完整展示了解法：先通过递归减半算出一个精心挑选的序列项，再把它代入对应的前缀和公式。
C++、Python 和 Java 三个实现都严格遵循上面的数学结构。它们不会把序列一直展开到目标下标，而是只沿着“不断除以 2”的唯一递归分支向下，再在回溯时重建需要的二元组。
核心过程的输入是 \(n\)，输出是 \((a_n,a_{n+1})\)。基例直接返回 \((1,2)\)。对任意更大的 \(n\)，实现都会先求出 \(\lfloor n/2\rfloor\) 对应的相邻二元组，再依据 \(n\) 的奇偶性套用上面的两条转移公式，恢复当前层的结果。
由于每一层只有一个子调用，所以这里既不需要记忆化，也不需要大型表格。每层真正做的事情只有少量加法、减法和乘以 2。
一旦实现能够提取某个 \(a_m\)，前缀和本身就只剩一次奇偶分支：偶数 \(n\) 用 \(4-a_{n/2}\)，奇数 \(n\) 用 \(4-3a_{(n+1)/2}\)。因此在题目要求的 \(10^{12}\) 上，最后一步就是读取 \(a_{5\cdot 10^{11}}\) 并代入闭式。
C++ 实现还额外带有一段小规模自检：它先核对前十项是否与已知值一致，再把快速前缀和公式与小下标范围内的直接求和结果进行比较，之后才输出大输入的答案。Python 和 Java 实现则保留了精简的快速路径。
每一层递归都会把下标减半，所以求 \((a_n,a_{n+1})\) 只需要 \(O(\log n)\) 次算术运算。把这个结果转换成 \(S(n)\) 之后，只再增加 \(O(1)\) 的工作量。
由于实现采用递归写法，额外空间为 \(O(\log n)\)。如果把同样的减半过程改写成迭代形式，空间可以压到 \(O(1)\)，但对这道题来说递归版本已经足够简洁清晰。
В задаче 918 целочисленная последовательность задается формулами
$$a_1=1,\qquad a_{2k}=2a_k,\qquad a_{2k+1}=a_k-3a_{k+1}.$$
Нужно вычислить префиксную сумму
$$S(n)=\sum_{i=1}^{n} a_i$$
для большого значения \(n=10^{12}\).
Последовательно строить все члены до такого индекса невозможно на практике. Кроме того, рекурсия не замыкается на одном значении: формула для \(a_{2k+1}\) использует одновременно \(a_k\) и \(a_{k+1}\). Поэтому правильный путь состоит в том, чтобы выбрать состояние, устойчивое при делении индекса пополам, а затем выразить через него и саму префиксную сумму.
Решение опирается на два специальных свойства этой последовательности. Во-первых, естественным рекурсивным объектом является соседняя пара \((a_n,a_{n+1})\). Во-вторых, если сгруппировать префиксную сумму в блоки «четный член плюс следующий нечетный», то возникает телескопическое сокращение, и вся задача сводится к одному значению последовательности с индексом примерно вдвое меньше.
Для четных индексов имеем простое правило \(a_{2k}=2a_k\). Но для нечетных индексов выполняется
$$a_{2k+1}=a_k-3a_{k+1},$$
поэтому новый член зависит сразу от двух соседних меньших значений. Если пытаться строить рекурсию только на \(a_n\), на следующем шаге неизбежно будет не хватать еще одного соседа. Значит, минимальное действительно замкнутое состояние должно содержать пару.
Определим
$$P(n)=(a_n,a_{n+1}).$$
Базовая пара известна сразу:
$$P(1)=(a_1,a_2)=(1,2).$$
Если написать \(P(k)=(x,y)=(a_k,a_{k+1})\), то из определения последовательности немедленно следуют переходы
$$P(2k)=(a_{2k},a_{2k+1})=(2a_k,\ a_k-3a_{k+1})=(2x,\ x-3y),$$
$$P(2k+1)=(a_{2k+1},a_{2k+2})=(a_k-3a_{k+1},\ 2a_{k+1})=(x-3y,\ 2y).$$
Именно этот инвариант используют реализации: достаточно знать \((a_k,a_{k+1})\), чтобы за константное время восстановить нужную пару на следующем уровне.
Чтобы вычислить \(P(n)\), достаточно знать только \(P(\lfloor n/2\rfloor)\). Следовательно, каждый вызов порождает ровно один меньший вызов:
$$n,\ \left\lfloor \frac{n}{2} \right\rfloor,\ \left\lfloor \frac{n}{4} \right\rfloor,\ \dots,\ 1.$$
Когда рекурсия идет обратно вверх, четность каждого промежуточного индекса определяет, какое из двух линейных преобразований нужно применить. Число уровней равно числу двоичных разрядов \(n\), поэтому время работы равно \(O(\log n)\).
Решающее упрощение появляется после группировки членов как \((a_{2j},a_{2j+1})\). Для любого \(j\ge 1\) имеем
$$a_{2j}+a_{2j+1}=2a_j+(a_j-3a_{j+1})=3(a_j-a_{j+1}).$$
Тем самым блок из двух больших индексов превращается в разность двух соседних членов с меньшими индексами. Именно такая разностная форма и делает суммирование телескопическим.
Пусть \(m\ge 1\). Для префикса нечетной длины сначала отделим \(a_1\), а остальное сгруппируем по блокам:
$$S(2m-1)=a_1+\sum_{j=1}^{m-1}(a_{2j}+a_{2j+1}).$$
Подстановка блочной формулы дает
$$S(2m-1)=1+3\sum_{j=1}^{m-1}(a_j-a_{j+1}).$$
Эта сумма телескопируется:
$$\sum_{j=1}^{m-1}(a_j-a_{j+1})=a_1-a_m=1-a_m,$$
поэтому
$$S(2m-1)=1+3(1-a_m)=4-3a_m.$$
Для четной длины остается добавить последний четный член:
$$S(2m)=S(2m-1)+a_{2m}=4-3a_m+2a_m=4-a_m.$$
Значит, вся задача сводится к одному значению последовательности:
$$S(2m-1)=4-3a_m,\qquad S(2m)=4-a_m.$$
Так как \(10^{12}=2\cdot 5\cdot 10^{11}\), для целевого входа достаточно вычислить
$$S(10^{12})=4-a_{5\cdot 10^{11}}.$$
Первые десять членов последовательности таковы:
$$a_1=1,\quad a_2=2,\quad a_3=-5,\quad a_4=4,\quad a_5=17,\quad a_6=-10,\quad a_7=-17,\quad a_8=8,\quad a_9=-47,\quad a_{10}=34.$$
Чтобы получить \(a_5\), достаточно пройти по цепочке \(5\to 2\to 1\):
$$P(1)=(1,2),\qquad P(2)=(2,-5),\qquad P(5)=(17,-10).$$
Следовательно, \(a_5=17\). После этого закрытые формулы дают
$$S(9)=4-3a_5=4-51=-47,$$
$$S(10)=4-a_5=4-17=-13.$$
Прямое сложение подтверждает те же значения:
$$1+2-5+4+17-10-17+8-47=-47,$$
$$1+2-5+4+17-10-17+8-47+34=-13.$$
В этом примере уже видна вся стратегия: вычислить один правильно выбранный член последовательности через рекурсивное деление индекса пополам и подставить его в нужную формулу для префиксной суммы.
Реализации на C++, Python и Java следуют одному и тому же математическому плану. Ни одна из них не разворачивает последовательность до целевого индекса; вместо этого все они проходят только по единственной цепочке деления пополам.
Центральная процедура принимает индекс \(n\) и возвращает \((a_n,a_{n+1})\). Базовый случай равен \((1,2)\). Для любого большего \(n\) сначала решается подзадача при \(\lfloor n/2\rfloor\), после чего текущая пара восстанавливается одной из двух переходных формул в зависимости от четности.
Поскольку на каждом уровне есть только один рекурсивный спуск, никакая мемоизация и никакие большие таблицы не нужны. Работа каждого уровня состоит лишь из нескольких сложений, вычитаний и удвоений.
Как только реализация умеет получать \(a_m\), префиксная сумма сводится к выбору между двумя формулами: \(4-a_{n/2}\) для четного \(n\) и \(4-3a_{(n+1)/2}\) для нечетного \(n\). Поэтому для реального входа задача заканчивается на одном терме \(a_{5\cdot 10^{11}}\).
Версия на C++ содержит также небольшую встроенную проверку: она сверяет первые десять членов с известными значениями и сравнивает быструю формулу префиксной суммы с прямым суммированием на малых индексах, а уже потом печатает большой ответ. Версии на Python и Java оставляют только компактный быстрый путь.
На каждом уровне рекурсии индекс делится пополам, поэтому вычисление \((a_n,a_{n+1})\) требует \(O(\log n)\) арифметических операций. Преобразование этого результата в \(S(n)\) стоит затем всего \(O(1)\).
Дополнительная память равна \(O(\log n)\) из-за глубины рекурсии. Если переписать тот же процесс итеративно, память можно было бы снизить до \(O(1)\), но для данной задачи рекурсивная форма уже достаточно компактна и прозрачна.
تعرف المسألة 918 متتالية صحيحة بالعلاقات
$$a_1=1,\qquad a_{2k}=2a_k,\qquad a_{2k+1}=a_k-3a_{k+1}.$$
والمطلوب هو حساب مجموع البادئة
$$S(n)=\sum_{i=1}^{n} a_i$$
عند القيمة الكبيرة \(n=10^{12}\).
توليد جميع الحدود حتى هذا الموضع غير عملي تماما. والاهم من ذلك ان العلاقة لا تنغلق على حد واحد فقط، لان صيغة \(a_{2k+1}\) تعتمد على \(a_k\) و\(a_{k+1}\) معا. لذلك يجب البحث عن حالة تبقى مغلقة عند تنصيف الفهرس، ثم اعادة كتابة مجموع البادئة بدلالة تلك الحالة الاصغر.
تعتمد الفكرة كلها على حقيقتين خاصتين بهذه المتتالية. الاولى ان الحالة العودية الطبيعية ليست قيمة منفردة، بل الزوج المتجاور \((a_n,a_{n+1})\). والثانية ان جمع الحدود في كتل من النوع «حد زوجي ثم الحد الفردي الذي يليه» يجعل مجموع البادئة يتلاشى تلسكوبيا حتى يبقى حد واحد فقط من المتتالية عند فهرس يقارب النصف.
في الفهارس الزوجية نحصل مباشرة على
$$a_{2k}=2a_k.$$
لكن في الفهارس الفردية لدينا
$$a_{2k+1}=a_k-3a_{k+1},$$
وهذا يعني ان القيمة الجديدة تعتمد على حدين متجاورين من المستوى الاصغر. ولو حاولنا بناء العودية على \(a_n\) وحده فسنظل نحتاج دائما الى قيمة مجاورة اضافية. لذلك فان اصغر حالة مغلقة حقا هي زوج من الحدود المتجاورة.
نعرف
$$P(n)=(a_n,a_{n+1}).$$
وزوج البداية معروف مباشرة:
$$P(1)=(a_1,a_2)=(1,2).$$
واذا كتبنا \(P(k)=(x,y)=(a_k,a_{k+1})\)، فان تعريف المتتالية يعطي
$$P(2k)=(a_{2k},a_{2k+1})=(2a_k,\ a_k-3a_{k+1})=(2x,\ x-3y),$$
$$P(2k+1)=(a_{2k+1},a_{2k+2})=(a_k-3a_{k+1},\ 2a_{k+1})=(x-3y,\ 2y).$$
وهذا هو الثابت الذي تحافظ عليه التطبيقات: متى عرفنا \((a_k,a_{k+1})\) امكن اعادة بناء الزوج المطلوب في المستوى الاعلى بزمن ثابت.
من الصيغ السابقة نرى ان حساب \(P(n)\) يحتاج فقط الى \(P(\lfloor n/2\rfloor)\). لذلك كل مستوى عودي يولد استدعاء اصغر واحدا فقط:
$$n,\ \left\lfloor \frac{n}{2} \right\rfloor,\ \left\lfloor \frac{n}{4} \right\rfloor,\ \dots,\ 1.$$
وعند الرجوع من العودية تحدد زوجية كل فهرس متوسط او فرديته اي التحويلين الخطيين يجب تطبيقه. وعدد المستويات يساوي عدد الخانات الثنائية في \(n\)، ولهذا يكون الزمن \(O(\log n)\).
التبسيط الحاسم يظهر عندما نجمع الحدود على شكل \((a_{2j},a_{2j+1})\). لكل \(j\ge 1\) لدينا
$$a_{2j}+a_{2j+1}=2a_j+(a_j-3a_{j+1})=3(a_j-a_{j+1}).$$
وهكذا تتحول كل كتلة كبيرة من حدين متتاليين الى فرق بين حدين متجاورين عند فهارس اصغر. وهذه البنية الفارقية هي التي تجعل المجموع يتلاشى تلسكوبيا.
ليكن \(m\ge 1\). في حالة بادئة بطول فردي نفصل \(a_1\) اولا ثم نجمع الباقي في كتل:
$$S(2m-1)=a_1+\sum_{j=1}^{m-1}(a_{2j}+a_{2j+1}).$$
وبالتعويض عن صيغة الكتلة نحصل على
$$S(2m-1)=1+3\sum_{j=1}^{m-1}(a_j-a_{j+1}).$$
وهذا مجموع تلسكوبي مباشر:
$$\sum_{j=1}^{m-1}(a_j-a_{j+1})=a_1-a_m=1-a_m,$$
ومن ثم
$$S(2m-1)=1+3(1-a_m)=4-3a_m.$$
اما في حالة البادئة الزوجية فلا نحتاج الا الى اضافة الحد الاخير \(a_{2m}=2a_m\):
$$S(2m)=S(2m-1)+a_{2m}=4-3a_m+2a_m=4-a_m.$$
وبذلك تختزل المسألة كلها الى حد واحد من المتتالية:
$$S(2m-1)=4-3a_m,\qquad S(2m)=4-a_m.$$
وبما ان \(10^{12}=2\cdot 5\cdot 10^{11}\)، فان الجواب المطلوب يختزل الى
$$S(10^{12})=4-a_{5\cdot 10^{11}}.$$
الحدود العشرة الاولى من المتتالية هي
$$a_1=1,\quad a_2=2,\quad a_3=-5,\quad a_4=4,\quad a_5=17,\quad a_6=-10,\quad a_7=-17,\quad a_8=8,\quad a_9=-47,\quad a_{10}=34.$$
ولاستخراج \(a_5\) نتابع سلسلة التنصيف \(5\to 2\to 1\):
$$P(1)=(1,2),\qquad P(2)=(2,-5),\qquad P(5)=(17,-10).$$
اذن \(a_5=17\). وبعدها تعطينا الصيغ المغلقة
$$S(9)=4-3a_5=4-51=-47,$$
$$S(10)=4-a_5=4-17=-13.$$
والجمع المباشر يؤكد القيمتين نفسيهما:
$$1+2-5+4+17-10-17+8-47=-47,$$
$$1+2-5+4+17-10-17+8-47+34=-13.$$
هذا المثال يوضح الخطة كلها: احسب حدا واحدا مختارا بعناية بالاعتماد على تنصيف الفهرس، ثم عوضه في هوية مجموع البادئة المناسبة.
تتبع تطبيقات C++ وPython وJava الخطة الرياضية نفسها تماما. لا يقوم اي منها بتوسيع المتتالية حتى الفهرس النهائي؛ بل تكتفي كلها باتباع فرع عودي واحد ناتج عن التنصيف المتكرر.
الروتين المركزي يستقبل \(n\) ويعيد \((a_n,a_{n+1})\). حالة الاساس هي \((1,2)\). وكلما كان \(n\) اكبر، تحل الشيفرة اولا المسألة الاصغر عند \(\lfloor n/2\rfloor\)، ثم تعيد بناء الزوج الحالي باحدى صيغتي الانتقال بحسب كون \(n\) زوجيا او فرديا.
ولان كل مستوى يملك استدعاء فرعيا واحدا فقط، فلا حاجة الى اي حفظ جدولي او الى بنى كبيرة. العمل في كل مستوى لا يتجاوز بضع عمليات جمع وطرح ومضاعفة.
بمجرد ان تستطيع الشيفرة استخراج \(a_m\)، يصبح مجموع البادئة اختيارا بين صيغتين فقط: \(4-a_{n/2}\) عندما يكون \(n\) زوجيا، و\(4-3a_{(n+1)/2}\) عندما يكون \(n\) فرديا. ولهذا تنتهي مسألة Project Euler الفعلية عند الحد \(a_{5\cdot 10^{11}}\).
تحتوي نسخة C++ ايضا على فحص صغير مدمج: فهي تقارن الحدود العشرة الاولى بقيم معروفة، ثم تختبر صيغة مجموع البادئة السريعة مقابل جمع مباشر عند فهارس صغيرة قبل طباعة الجواب الكبير. اما نسختا Python وJava فتحتفظان بالمسار السريع المختصر فقط.
كل مستوى عودي يقسم الفهرس على اثنين، لذلك يحتاج حساب \((a_n,a_{n+1})\) الى \(O(\log n)\) من العمليات الحسابية. وبعد ذلك لا يتطلب تحويل هذه النتيجة الى \(S(n)\) الا \(O(1)\) من العمل الاضافي.
استهلاك الذاكرة هو \(O(\log n)\) بسبب عمق العودية. ولو كتبت الفكرة نفسها بصورة تكرارية لامكن خفض الذاكرة الاضافية الى \(O(1)\)، لكن الصياغة العودية هنا قصيرة وواضحة بما يكفي.