Project Euler 702 asks for the exact value of a quantity \(S(N)\) coming from the jumping-flea process. For the real input \(N=123456789\), any direct simulation is far too large, so the solution used by the implementation rewrites the problem as a short dyadic decomposition plus a recursively reduced correction term.
The important point is that the geometry of the statement has already been compressed into arithmetic. Instead of tracking every move, the computation only needs powers of two around \(N\), one final gap term \(2^\lambda-N\), and a memoized Euclidean-style kernel on reduced integer pairs.
Let
$$\lambda=\lfloor\log_2 N\rfloor+1,$$
so that
$$2^{\lambda-1}\le N<2^\lambda.$$
The implementation evaluates \(S(N)\) by splitting it into a closed bulk contribution and a family of correction terms.
The top-level identity used by the implementation is
$$S(N)=\frac{N(3N+1)}{2}(\lambda+1)-\sum_{d=2}^{\lambda} C(N,2^d)+2C(N,2^\lambda-N).$$
The factor \(\lambda\) is simply the bit length of \(N\). This formula says that the whole answer is controlled by the powers of two that bracket \(N\), plus one last correction measuring the distance from \(N\) to the next power of two.
That already changes the scale of the task: instead of a huge search, we only need \(\lambda-1=O(\log N)\) correction evaluations.
The correction term is written as
$$C(u,v)=(v-1)(v-2)-\Phi(u,v),$$
where \(\Phi(u,v)\) is the genuinely recursive part. The quadratic piece \((v-1)(v-2)\) is immediate, so the computational difficulty is concentrated entirely in \(\Phi\).
Before doing anything else, the first argument is reduced modulo the second. Only the residue of \(u\) modulo \(v\) matters. If that reduced value is \(0\) or \(1\), then the recursion stops and
$$\Phi(u,v)=0.$$
This base case is the mechanism that makes the descent finite.
Assume the reduced first argument is \(a\), with \(2\le a<v\). Write
$$q=\left\lfloor\frac{v}{a}\right\rfloor,\qquad r=v\bmod a.$$
Then all three implementations use the exact identity
$$\Phi(u,v)=\frac{q(q+1)a(a-1)}{4}+(q+1)\Phi(a,r)-q\,\Phi(a,a-r).$$
The first term summarizes an entire quotient block in closed form. The remaining two terms are smaller subproblems. Both new moduli, \(r\) and \(a-r\), are strictly smaller than \(a\), so the recursion shrinks in the same spirit as the Euclidean algorithm.
The polynomial factor
$$\frac{q(q+1)a(a-1)}{4}$$
is always an integer. The reason is that \(q(q+1)\) is even and \(a(a-1)\) is also even, so their product is divisible by \(4\).
No floating-point approximation is needed anywhere. Every recursive branch stays in integer arithmetic, which is why memoization can store exact values and why the final result agrees across the C++, Python, and Java implementations.
The same reduced pair can appear from several top-level correction terms. Once \(\Phi(a,v)\) has been computed, every later request for the same pair is just a table lookup.
This matters because the outer formula repeatedly asks for nearby dyadic moduli. Memoization collapses a large recursion tree into a much smaller directed acyclic graph of distinct residue pairs.
For \(N=5\), we have \(\lambda=\lfloor\log_2 5\rfloor+1=3\). Therefore
$$S(5)=\frac{5(3\cdot5+1)}{2}(3+1)-C(5,4)-C(5,8)+2C(5,3).$$
The closed bulk term is
$$\frac{5\cdot16}{2}\cdot4=160.$$
Now compute the corrections.
For \(C(5,4)\), reducing \(5\bmod 4\) gives \(1\), so \(\Phi(5,4)=0\). Hence
$$C(5,4)=(4-1)(4-2)=6.$$
For \(C(5,3)\), the reduced first argument is \(2\). Then \(q=\lfloor 3/2\rfloor=1\) and \(r=1\), so
$$\Phi(5,3)=\frac{1\cdot2\cdot2\cdot1}{4}+2\Phi(2,1)-\Phi(2,1)=1.$$
Therefore
$$C(5,3)=(3-1)(3-2)-1=1.$$
For \(C(5,8)\), we have \(a=5\), \(q=1\), \(r=3\). Thus
$$\Phi(5,8)=\frac{1\cdot2\cdot5\cdot4}{4}+2\Phi(5,3)-\Phi(5,2)=10+2\cdot1-0=12,$$
because \(5\bmod 2=1\), so \(\Phi(5,2)=0\). Therefore
$$C(5,8)=(8-1)(8-2)-12=42-12=30.$$
Putting the pieces together,
$$S(5)=160-6-30+2\cdot1=126,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations all follow the same structure. They first compute \(\lambda\), then form the bulk term \(\frac{N(3N+1)}{2}(\lambda+1)\), then subtract the dyadic corrections \(C(N,2^d)\) for \(2\le d\le\lambda\), and finally add \(2C(N,2^\lambda-N)\).
Each correction evaluation begins by reducing the first argument modulo the second. If the reduced value is \(0\) or \(1\), the answer is immediate. Otherwise the implementation computes the quotient \(q\), the remainder \(r\), applies the recurrence above, and stores the result in a memo table keyed by the reduced pair.
The compiled implementations widen intermediate products for the quadratic term before converting back to a 64-bit result, while Python uses arbitrary-precision integers automatically. Algorithmically, though, the three versions are the same, and they agree with the published checkpoints \(S(3)=42\), \(S(5)=126\), \(S(123)=167178\), and \(S(12345)=3185041956\).
The outer decomposition uses only \(O(\log N)\) correction terms because \(\lambda\) is the bit length of \(N\). The real cost is determined by the number of distinct reduced pairs that appear during the recursive descent.
If \(M\) denotes the number of distinct memoized states, then the running time is \(O(M)\) after hash-table lookups, and the memory usage is also \(O(M)\). In practice \(M\) stays small because each uncached step replaces the current modulus by values below the current residue, giving Euclidean-style shrinkage rather than combinatorial explosion.
Project Euler 702 verlangt den exakten Wert einer Größe \(S(N)\), die aus dem Prozess des springenden Flohs entsteht. Für die echte Eingabe \(N=123456789\) ist jede direkte Simulation viel zu groß, daher schreibt die Implementierung das Problem als kurze dyadische Zerlegung plus einen rekursiv reduzierten Korrekturterm um.
Entscheidend ist, dass die Geometrie der Aufgabenstellung bereits in reine Arithmetik übersetzt wurde. Anstatt jeden Sprung zu verfolgen, braucht die Rechnung nur die Zweierpotenzen um \(N\), einen letzten Abstandsterm \(2^\lambda-N\) und einen memoisierten Kern auf reduzierten Zahlenpaaren.
Setze
$$\lambda=\lfloor\log_2 N\rfloor+1,$$
also
$$2^{\lambda-1}\le N<2^\lambda.$$
Die Implementierung berechnet \(S(N)\), indem sie einen geschlossenen Hauptterm von einer Familie von Korrekturen trennt.
Die verwendete Hauptformel lautet
$$S(N)=\frac{N(3N+1)}{2}(\lambda+1)-\sum_{d=2}^{\lambda} C(N,2^d)+2C(N,2^\lambda-N).$$
Der Parameter \(\lambda\) ist einfach die Bitlänge von \(N\). Die Formel sagt, dass die gesamte Antwort von den Zweierpotenzen um \(N\) und von einer letzten Korrektur abhängt, die den Abstand zur nächsten Zweierpotenz misst.
Damit schrumpft das Problem sofort: Statt eines riesigen Suchraums brauchen wir nur \(\lambda-1=O(\log N)\) Korrekturwerte.
Der Korrekturterm wird geschrieben als
$$C(u,v)=(v-1)(v-2)-\Phi(u,v),$$
wobei \(\Phi(u,v)\) der eigentliche rekursive Kern ist. Der quadratische Anteil \((v-1)(v-2)\) ist sofort bekannt; die gesamte Schwierigkeit steckt also in \(\Phi\).
Bevor rekursiv weitergerechnet wird, reduziert man das erste Argument modulo dem zweiten. Nur die Restklasse von \(u\) modulo \(v\) ist relevant. Ist der reduzierte Wert \(0\) oder \(1\), dann endet die Rekursion und es gilt
$$\Phi(u,v)=0.$$
Dieser Basisfall sorgt dafür, dass der Abstieg tatsächlich terminiert.
Sei das reduzierte erste Argument \(a\) mit \(2\le a<v\). Schreibe
$$q=\left\lfloor\frac{v}{a}\right\rfloor,\qquad r=v\bmod a.$$
Dann verwenden alle drei Implementierungen die exakte Identität
$$\Phi(u,v)=\frac{q(q+1)a(a-1)}{4}+(q+1)\Phi(a,r)-q\,\Phi(a,a-r).$$
Der erste Summand fasst einen ganzen Quotientenblock in geschlossener Form zusammen. Die beiden übrigen Summanden sind kleinere Teilprobleme. Die neuen Moduli \(r\) und \(a-r\) sind strikt kleiner als \(a\), also schrumpft die Rekursion im Geist des euklidischen Algorithmus.
Der Polynomfaktor
$$\frac{q(q+1)a(a-1)}{4}$$
ist immer ganzzahlig. Denn \(q(q+1)\) ist als Produkt zweier aufeinanderfolgender Zahlen gerade, und \(a(a-1)\) ist aus demselben Grund ebenfalls gerade. Das Produkt ist also durch \(4\) teilbar.
Es tauchen nirgends Gleitkommazahlen auf. Jede Verzweigung bleibt in exakter Ganzzahlarithmetik, weshalb sich die Werte sicher memoisiert speichern und exakt wiederverwenden lassen.
Dasselbe reduzierte Paar kann aus mehreren Korrekturtermen der äußeren Summe entstehen. Sobald \(\Phi(a,v)\) einmal berechnet wurde, ist jede spätere Anfrage nur noch ein Tabellenzugriff.
Das ist wichtig, weil die Hauptformel viele benachbarte dyadische Moduli abfragt. Memoisierung macht aus einem großen Rekursionsbaum einen viel kleineren azyklischen Graphen aus tatsächlich verschiedenen Restpaaren.
Für \(N=5\) ist \(\lambda=\lfloor\log_2 5\rfloor+1=3\). Also
$$S(5)=\frac{5(3\cdot5+1)}{2}(3+1)-C(5,4)-C(5,8)+2C(5,3).$$
Der geschlossene Hauptterm ist
$$\frac{5\cdot16}{2}\cdot4=160.$$
Nun berechnen wir die Korrekturen.
Für \(C(5,4)\) ist \(5\bmod 4=1\), also \(\Phi(5,4)=0\). Damit folgt
$$C(5,4)=(4-1)(4-2)=6.$$
Für \(C(5,3)\) ist das reduzierte erste Argument \(2\). Dann gilt \(q=\lfloor 3/2\rfloor=1\) und \(r=1\), also
$$\Phi(5,3)=\frac{1\cdot2\cdot2\cdot1}{4}+2\Phi(2,1)-\Phi(2,1)=1.$$
Daher
$$C(5,3)=(3-1)(3-2)-1=1.$$
Für \(C(5,8)\) haben wir \(a=5\), \(q=1\), \(r=3\). Also
$$\Phi(5,8)=\frac{1\cdot2\cdot5\cdot4}{4}+2\Phi(5,3)-\Phi(5,2)=10+2\cdot1-0=12,$$
denn \(5\bmod 2=1\), also \(\Phi(5,2)=0\). Somit
$$C(5,8)=(8-1)(8-2)-12=42-12=30.$$
Insgesamt erhält man
$$S(5)=160-6-30+2\cdot1=126,$$
genau den Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst bestimmen sie \(\lambda\), bilden dann den Hauptterm \(\frac{N(3N+1)}{2}(\lambda+1)\), subtrahieren die dyadischen Korrekturen \(C(N,2^d)\) für \(2\le d\le\lambda\) und addieren am Ende \(2C(N,2^\lambda-N)\).
Jede Korrekturauswertung beginnt mit der Reduktion des ersten Arguments modulo dem zweiten. Ist der reduzierte Wert \(0\) oder \(1\), ist das Ergebnis sofort bekannt. Andernfalls berechnet die Implementierung Quotient \(q\), Rest \(r\), wendet die Rekursionsformel an und speichert das Resultat in einer Memo-Tabelle, die durch das reduzierte Zahlenpaar indiziert ist.
Die kompilierten Implementierungen erweitern Zwischenprodukte des quadratischen Terms vorübergehend auf breitere Zahltypen, während Python automatisch Ganzzahlen beliebiger Präzision benutzt. Algorithmisch sind die drei Fassungen jedoch identisch, und sie stimmen bei den bekannten Kontrollwerten \(S(3)=42\), \(S(5)=126\), \(S(123)=167178\) und \(S(12345)=3185041956\) überein.
Die äußere Zerlegung benötigt nur \(O(\log N)\) Korrekturterme, weil \(\lambda\) die Bitlänge von \(N\) ist. Die eigentliche Laufzeit wird durch die Anzahl der verschiedenen reduzierten Paare bestimmt, die während des rekursiven Abstiegs auftreten.
Bezeichnet \(M\) die Zahl dieser memoisierten Zustände, dann liegt die Laufzeit nach Hash-Tabellen-Zugriffen bei \(O(M)\), und auch der Speicherbedarf ist \(O(M)\). Praktisch bleibt \(M\) klein, weil jeder neue Rekursionsschritt die aktuellen Moduli unter den aktuellen Rest drückt und damit euklidisch schrumpft statt kombinatorisch zu explodieren.
Project Euler 702, zıplayan pire sürecinden gelen \(S(N)\) niceliğinin tam değerini ister. Gerçek girdi \(N=123456789\) için doğrudan simülasyon yapmak imkansız boyuttadır; bu yüzden uygulama problemi kısa bir ikili ölçek ayrışımına ve özyinelemeli olarak küçülen bir düzeltme terimine çevirir.
Buradaki esas nokta, sorudaki geometrinin zaten aritmetiğe indirgenmiş olmasıdır. Her sıçramayı tek tek izlemek yerine hesaplama, yalnızca \(N\)'i çevreleyen 2 kuvvetlerine, son boşluk terimi \(2^\lambda-N\)'ye ve küçültülmüş tamsayı çiftleri üzerinde memoize edilen Öklid-benzeri bir çekirdeğe ihtiyaç duyar.
Şunu tanımlayalım:
$$\lambda=\lfloor\log_2 N\rfloor+1,$$
dolayısıyla
$$2^{\lambda-1}\le N<2^\lambda.$$
Uygulama \(S(N)\)'yi kapalı bir ana terim ile bir düzeltme ailesini ayırarak hesaplar.
Uygulamanın kullandığı üst düzey özdeşlik şudur:
$$S(N)=\frac{N(3N+1)}{2}(\lambda+1)-\sum_{d=2}^{\lambda} C(N,2^d)+2C(N,2^\lambda-N).$$
\(\lambda\), \(N\)'nin bit uzunluğudur. Bu formül, cevabın tamamının \(N\)'i kuşatan 2 kuvvetleri ile \(N\)'den sonraki ilk 2 kuvvetine olan uzaklığı ölçen son düzeltmeden geldiğini söyler.
Böylece problem hemen küçülür: dev bir arama yerine yalnızca \(\lambda-1=O(\log N)\) adet düzeltme hesabı gerekir.
Düzeltme terimi şu biçimde yazılır:
$$C(u,v)=(v-1)(v-2)-\Phi(u,v).$$
Burada \(\Phi(u,v)\) gerçekten özyinelemeli olan kısımdır. \((v-1)(v-2)\) açıkça bilindiği için, hesaplamanın zor tarafı bütünüyle \(\Phi\) içinde toplanır.
Her şeyden önce ilk argüman ikinciye göre modulo alınır. Yani yalnızca \(u\)'nun \(v\)'ye göre kalan sınıfı önemlidir. Bu küçültülmüş değer \(0\) veya \(1\) ise özyineleme biter ve
$$\Phi(u,v)=0$$
olur. Sonlu inişi sağlayan temel durum budur.
Küçültülmüş ilk argüman \(a\) olsun ve \(2\le a<v\) varsayalım. Şimdi
$$q=\left\lfloor\frac{v}{a}\right\rfloor,\qquad r=v\bmod a$$
yazalım. O zaman üç uygulamanın da kullandığı tam bağıntı
$$\Phi(u,v)=\frac{q(q+1)a(a-1)}{4}+(q+1)\Phi(a,r)-q\,\Phi(a,a-r)$$
şeklindedir. İlk terim, aynı bölüm değerine sahip bütün bir bloğu kapalı biçimde toplar. Sonraki iki terim daha küçük alt problemlerdir. Yeni modüller olan \(r\) ve \(a-r\), \(a\)'dan kesin olarak küçüktür; bu nedenle özyineleme Öklid algoritmasındaki gibi aşağı doğru iner.
Polinom katsayısı
$$\frac{q(q+1)a(a-1)}{4}$$
her zaman tamsayıdır. Çünkü \(q(q+1)\) ardışık iki sayının çarpımı olduğundan çifttir; aynı biçimde \(a(a-1)\) da çifttir. Bu iki çift çarpanın çarpımı \(4\)'e tam bölünür.
Hiçbir yerde kayan nokta yaklaşımı kullanılmaz. Her dal tam sayı aritmetiğinde kalır; bu yüzden memoizasyon tam değerleri güvenli biçimde saklayabilir ve daha sonra aynen yeniden kullanabilir.
Aynı küçültülmüş çift, dış toplamın birden fazla düzeltme teriminden ortaya çıkabilir. \(\Phi(a,v)\) bir kez hesaplandıktan sonra, sonraki istekler yalnızca tablo erişimidir.
Bu önemlidir; çünkü ana formül birbirine yakın birçok ikili modülü sorgular. Memoizasyon, büyük bir özyineleme ağacını gerçekten farklı kalan çiftlerinden oluşan çok daha küçük yönlü çevrimsiz bir grafa dönüştürür.
\(N=5\) için \(\lambda=\lfloor\log_2 5\rfloor+1=3\) olur. Dolayısıyla
$$S(5)=\frac{5(3\cdot5+1)}{2}(3+1)-C(5,4)-C(5,8)+2C(5,3).$$
Kapalı ana terim
$$\frac{5\cdot16}{2}\cdot4=160$$
değerini verir. Şimdi düzeltmeleri hesaplayalım.
\(C(5,4)\) için \(5\bmod 4=1\) olduğundan \(\Phi(5,4)=0\). O halde
$$C(5,4)=(4-1)(4-2)=6.$$
\(C(5,3)\) için küçültülmüş ilk argüman \(2\)'dir. Burada \(q=\lfloor 3/2\rfloor=1\) ve \(r=1\) olur; dolayısıyla
$$\Phi(5,3)=\frac{1\cdot2\cdot2\cdot1}{4}+2\Phi(2,1)-\Phi(2,1)=1.$$
Bu yüzden
$$C(5,3)=(3-1)(3-2)-1=1.$$
\(C(5,8)\) için \(a=5\), \(q=1\), \(r=3\) elde edilir. Böylece
$$\Phi(5,8)=\frac{1\cdot2\cdot5\cdot4}{4}+2\Phi(5,3)-\Phi(5,2)=10+2\cdot1-0=12,$$
çünkü \(5\bmod 2=1\) olduğundan \(\Phi(5,2)=0\). Sonuç olarak
$$C(5,8)=(8-1)(8-2)-12=42-12=30.$$
Tüm parçaları birleştirince
$$S(5)=160-6-30+2\cdot1=126$$
elde edilir; bu da uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamalarının yapısı aynıdır. Önce \(\lambda\) hesaplanır, sonra \(\frac{N(3N+1)}{2}(\lambda+1)\) ana terimi oluşturulur, ardından \(2\le d\le\lambda\) için ikili düzeltmeler \(C(N,2^d)\) çıkarılır ve son olarak \(2C(N,2^\lambda-N)\) eklenir.
Her düzeltme hesabı, ilk argümanı ikinciye göre modulo alarak başlar. Küçültülmüş değer \(0\) veya \(1\) ise sonuç anında bilinir. Aksi halde uygulama bölüm \(q\) ve kalan \(r\) değerlerini hesaplar, yukarıdaki özyinelemeyi uygular ve sonucu küçültülmüş çiftle anahtarlanan bir memo tablosuna kaydeder.
Derlenmiş sürümler ikinci derece terimin ara çarpımlarını daha geniş sayı türleriyle güvence altına alır; Python ise doğal olarak keyfi uzunlukta tamsayılar kullanır. Yine de algoritma üç dilde de aynıdır ve \(S(3)=42\), \(S(5)=126\), \(S(123)=167178\), \(S(12345)=3185041956\) kontrol değerleriyle tutarlıdır.
Dış ayrışım yalnızca \(O(\log N)\) adet düzeltme terimi içerir; çünkü \(\lambda\), \(N\)'nin bit uzunluğudur. Asıl maliyeti belirleyen şey, özyinelemeli iniş sırasında ortaya çıkan farklı küçültülmüş çiftlerin sayısıdır.
Bu memoize edilmiş durumların sayısına \(M\) dersek, hash tablo erişimlerinden sonra çalışma süresi \(O(M)\), bellek kullanımı da \(O(M)\) olur. Pratikte \(M\) küçük kalır; çünkü her yeni dal mevcut modülü mevcut kalanın altına indirir ve böylece birleşik bir patlama yerine Öklid-benzeri bir küçülme görülür.
Project Euler 702 pide el valor exacto de una cantidad \(S(N)\) asociada al proceso de la pulga saltarina. Para la entrada real \(N=123456789\), una simulación directa es totalmente inviable, así que la implementación reescribe el problema como una descomposición diádica corta más un término corrector que se reduce recursivamente.
Lo importante es que la geometría del enunciado ya quedó comprimida en aritmética. En lugar de seguir cada salto, el cálculo solo necesita las potencias de \(2\) alrededor de \(N\), un término final de hueco \(2^\lambda-N\) y un núcleo memoizado de estilo euclidiano sobre pares enteros reducidos.
Definimos
$$\lambda=\lfloor\log_2 N\rfloor+1,$$
de modo que
$$2^{\lambda-1}\le N<2^\lambda.$$
La implementación evalúa \(S(N)\) separando una contribución principal cerrada y una familia de correcciones.
La identidad de nivel superior usada por la implementación es
$$S(N)=\frac{N(3N+1)}{2}(\lambda+1)-\sum_{d=2}^{\lambda} C(N,2^d)+2C(N,2^\lambda-N).$$
El parámetro \(\lambda\) no es más que la longitud binaria de \(N\). La fórmula dice que toda la respuesta queda determinada por las potencias de \(2\) que rodean a \(N\) y por una corrección final que mide la distancia hasta la siguiente potencia de \(2\).
Eso reduce drásticamente el tamaño del problema: en vez de un espacio enorme de búsqueda, solo hacen falta \(\lambda-1=O(\log N)\) evaluaciones correctoras.
El término corrector se escribe como
$$C(u,v)=(v-1)(v-2)-\Phi(u,v),$$
donde \(\Phi(u,v)\) es la parte verdaderamente recursiva. La pieza cuadrática \((v-1)(v-2)\) es inmediata, así que toda la dificultad computacional se concentra en \(\Phi\).
Antes de cualquier paso recursivo, el primer argumento se reduce módulo el segundo. Solo importa el residuo de \(u\) módulo \(v\). Si ese valor reducido es \(0\) o \(1\), la recursión se detiene y
$$\Phi(u,v)=0.$$
Ese caso base es lo que garantiza que el descenso termine.
Supongamos que el primer argumento reducido es \(a\), con \(2\le a<v\). Escribimos
$$q=\left\lfloor\frac{v}{a}\right\rfloor,\qquad r=v\bmod a.$$
Entonces las tres implementaciones usan la identidad exacta
$$\Phi(u,v)=\frac{q(q+1)a(a-1)}{4}+(q+1)\Phi(a,r)-q\,\Phi(a,a-r).$$
El primer término resume en forma cerrada un bloque completo con el mismo cociente. Los otros dos son subproblemas más pequeños. Los nuevos módulos, \(r\) y \(a-r\), son estrictamente menores que \(a\), de modo que la recursión decrece con la misma lógica que el algoritmo de Euclides.
El factor polinómico
$$\frac{q(q+1)a(a-1)}{4}$$
siempre es un entero. \(q(q+1)\) es par por ser producto de enteros consecutivos, y \(a(a-1)\) también es par por la misma razón. Por tanto, el producto total es divisible por \(4\).
No aparece aproximación en coma flotante. Todas las ramas trabajan solo con enteros, lo que permite almacenar valores exactos en la memoización y reutilizarlos sin pérdida alguna.
El mismo par reducido puede surgir desde varias correcciones de la suma exterior. Una vez calculado \(\Phi(a,v)\), cualquier aparición posterior se resuelve con una simple consulta a tabla.
Esto importa porque la fórmula principal pide muchos módulos diádicos cercanos entre sí. La memoización convierte un gran árbol recursivo en un grafo acíclico mucho más pequeño formado solo por los pares residuales realmente distintos.
Para \(N=5\), se tiene \(\lambda=\lfloor\log_2 5\rfloor+1=3\). Entonces
$$S(5)=\frac{5(3\cdot5+1)}{2}(3+1)-C(5,4)-C(5,8)+2C(5,3).$$
El término principal cerrado vale
$$\frac{5\cdot16}{2}\cdot4=160.$$
Ahora calculamos las correcciones.
Para \(C(5,4)\), el residuo \(5\bmod 4\) es \(1\), así que \(\Phi(5,4)=0\). Por tanto
$$C(5,4)=(4-1)(4-2)=6.$$
Para \(C(5,3)\), el primer argumento reducido es \(2\). Entonces \(q=\lfloor 3/2\rfloor=1\) y \(r=1\), de donde
$$\Phi(5,3)=\frac{1\cdot2\cdot2\cdot1}{4}+2\Phi(2,1)-\Phi(2,1)=1.$$
Así,
$$C(5,3)=(3-1)(3-2)-1=1.$$
Para \(C(5,8)\), tenemos \(a=5\), \(q=1\), \(r=3\). Luego
$$\Phi(5,8)=\frac{1\cdot2\cdot5\cdot4}{4}+2\Phi(5,3)-\Phi(5,2)=10+2\cdot1-0=12,$$
porque \(5\bmod 2=1\), así que \(\Phi(5,2)=0\). Entonces
$$C(5,8)=(8-1)(8-2)-12=42-12=30.$$
Reuniendo todo,
$$S(5)=160-6-30+2\cdot1=126,$$
que coincide con el valor de control usado por la implementación.
Las implementaciones en C++, Python y Java siguen exactamente la misma secuencia. Primero calculan \(\lambda\), luego forman el término principal \(\frac{N(3N+1)}{2}(\lambda+1)\), después restan las correcciones diádicas \(C(N,2^d)\) para \(2\le d\le\lambda\), y finalmente añaden \(2C(N,2^\lambda-N)\).
Cada evaluación correctora empieza reduciendo el primer argumento módulo el segundo. Si el valor reducido es \(0\) o \(1\), el resultado ya es inmediato. En caso contrario, la implementación calcula el cociente \(q\), el resto \(r\), aplica la recurrencia anterior y guarda el resultado en una tabla de memoización indexada por el par reducido.
Las versiones compiladas amplían temporalmente los productos intermedios del término cuadrático para conservar exactitud; Python, por su parte, usa enteros de precisión arbitraria de forma nativa. Aun así, las tres versiones son algorítmicamente idénticas y coinciden en los valores de control \(S(3)=42\), \(S(5)=126\), \(S(123)=167178\) y \(S(12345)=3185041956\).
La descomposición exterior solo contiene \(O(\log N)\) términos correctores porque \(\lambda\) es la longitud binaria de \(N\). El coste real viene dado por cuántos pares reducidos distintos aparecen durante el descenso recursivo.
Si \(M\) es el número de estados memoizados distintos, entonces el tiempo total es \(O(M)\) tras las búsquedas en tabla hash, y la memoria también es \(O(M)\). En la práctica, \(M\) permanece pequeño porque cada paso no almacenado sustituye el módulo actual por valores menores que el residuo actual, produciendo un decrecimiento de tipo euclidiano en lugar de una explosión combinatoria.
Project Euler 702 要求计算一个来自跳蚤跳跃过程的量 \(S(N)\) 的精确值。对真实输入 \(N=123456789\) 而言，任何逐步模拟都不现实，所以实现采用的是一种完全不同的思路：先把整体答案拆成一个封闭主项，再加上一组可以递归化简的修正项。
关键在于，题目里的几何过程已经被压缩成纯算术对象。实现并不跟踪每一次跳跃，而是只关心 \(N\) 附近的若干个 \(2\) 的幂、最后一个差值项 \(2^\lambda-N\)，以及一个建立在“约化整数对”上的欧几里得式记忆化递推核。
设
$$\lambda=\lfloor\log_2 N\rfloor+1,$$
因此
$$2^{\lambda-1}\le N<2^\lambda.$$
实现对 \(S(N)\) 的求值，是把一个显式主项和若干修正项分开处理。
实现使用的顶层恒等式是
$$S(N)=\frac{N(3N+1)}{2}(\lambda+1)-\sum_{d=2}^{\lambda} C(N,2^d)+2C(N,2^\lambda-N).$$
其中 \(\lambda\) 就是 \(N\) 的二进制位数。这个公式说明，最终答案只由两部分控制：一部分是显式的主项，另一部分是围绕 \(N\) 的这些二次幂尺度上的修正，再加上距离下一次幂边界的最后修正。
这一步已经把问题规模大幅压缩。原本如果直接从过程本身入手，会面对庞大的状态空间；而现在只需要处理 \(\lambda-1=O(\log N)\) 个修正值。
修正函数被写成
$$C(u,v)=(v-1)(v-2)-\Phi(u,v).$$
这里 \(\Phi(u,v)\) 才是真正需要递归计算的部分，而 \((v-1)(v-2)\) 是显式的二次式，因此计算难点全部集中在 \(\Phi\) 上。
在进入递推之前，先把第一个参数对第二个参数取模。换句话说，真正重要的只是 \(u\) 在模 \(v\) 意义下的剩余类。如果这个约化后的值是 \(0\) 或 \(1\)，那么递推立刻停止，并且有
$$\Phi(u,v)=0.$$
这个基例正是整个递归能够快速结束的原因。
设约化后的第一个参数为 \(a\)，并且满足 \(2\le a<v\)。记
$$q=\left\lfloor\frac{v}{a}\right\rfloor,\qquad r=v\bmod a.$$
那么三个实现共同使用的精确递推式为
$$\Phi(u,v)=\frac{q(q+1)a(a-1)}{4}+(q+1)\Phi(a,r)-q\,\Phi(a,a-r).$$
第一项把一个完整的“同商块”一次性汇总成封闭公式；后面两项则是更小的子问题。新的模数 \(r\) 和 \(a-r\) 都严格小于 \(a\)，因此递推会像欧几里得算法那样不断向更小的参数下降。
其中的多项式因子
$$\frac{q(q+1)a(a-1)}{4}$$
一定是整数。原因很直接：\(q(q+1)\) 是两个连续整数的乘积，所以必为偶数；\(a(a-1)\) 同样是连续整数的乘积，也必为偶数；因此总乘积一定能被 \(4\) 整除。
整个过程完全不需要浮点数。每一个递归分支都只在整数范围内运算，所以记忆化表里保存的是精确值，而不是近似值。这也是三个语言版本能够逐项一致的根本原因。
同一个约化状态 \((a,v)\) 可能会从外层公式中的不同修正项反复出现。一旦 \(\Phi(a,v)\) 被算出，之后再次遇到同样的状态时，就只需要一次表查询。
这一点很重要，因为顶层公式会连续请求很多彼此接近的二进制尺度。记忆化把一个潜在上非常庞大的递归树，压缩成只包含“真正不同状态”的有向无环图。
当 \(N=5\) 时，\(\lambda=\lfloor\log_2 5\rfloor+1=3\)。因此
$$S(5)=\frac{5(3\cdot5+1)}{2}(3+1)-C(5,4)-C(5,8)+2C(5,3).$$
显式主项为
$$\frac{5\cdot16}{2}\cdot4=160.$$
接下来逐个计算修正项。
对 \(C(5,4)\)，先算 \(5\bmod 4=1\)，于是 \(\Phi(5,4)=0\)。所以
$$C(5,4)=(4-1)(4-2)=6.$$
对 \(C(5,3)\)，约化后第一个参数是 \(2\)。此时 \(q=\lfloor 3/2\rfloor=1\)，\(r=1\)，所以
$$\Phi(5,3)=\frac{1\cdot2\cdot2\cdot1}{4}+2\Phi(2,1)-\Phi(2,1)=1.$$
因此
$$C(5,3)=(3-1)(3-2)-1=1.$$
对 \(C(5,8)\)，有 \(a=5\)、\(q=1\)、\(r=3\)。于是
$$\Phi(5,8)=\frac{1\cdot2\cdot5\cdot4}{4}+2\Phi(5,3)-\Phi(5,2)=10+2\cdot1-0=12,$$
因为 \(5\bmod 2=1\)，所以 \(\Phi(5,2)=0\)。从而
$$C(5,8)=(8-1)(8-2)-12=42-12=30.$$
最后汇总得到
$$S(5)=160-6-30+2\cdot1=126,$$
这与实现中的校验值完全一致。
C++、Python 和 Java 三个实现的算法结构完全相同。它们先求出 \(\lambda\)，构造主项 \(\frac{N(3N+1)}{2}(\lambda+1)\)，然后依次减去 \(2\le d\le\lambda\) 时的二进制修正 \(C(N,2^d)\)，最后再加上 \(2C(N,2^\lambda-N)\)。
每次计算修正项时，都会先把第一个参数对第二个参数取模。如果约化值是 \(0\) 或 \(1\)，答案立即返回。否则实现会算出商 \(q\) 和余数 \(r\)，套用上面的递推式，并把结果存入一个以约化整数对为键的记忆化表中。
C++ 和 Java 版本会在二次项的中间乘法处使用更宽的整数表示，以避免溢出；Python 则天然支持任意精度整数。虽然数值安全细节不同，但三种语言的算法完全一致，并且都满足已知校验值 \(S(3)=42\)、\(S(5)=126\)、\(S(123)=167178\)、\(S(12345)=3185041956\)。
外层分解只包含 \(O(\log N)\) 个修正项，因为 \(\lambda\) 本身就是 \(N\) 的二进制位数。真正决定成本的是递归下降过程中出现了多少个不同的约化状态。
若记这些不同的记忆化状态数为 \(M\)，那么在哈希表查找视为常数开销时，总时间复杂度为 \(O(M)\)，空间复杂度也为 \(O(M)\)。实践中 \(M\) 很小，因为每一个新的未缓存递推都会把当前模数缩到当前余数以下，从而表现出欧几里得式收缩，而不是组合爆炸。
Project Euler 702 требует найти точное значение величины \(S(N)\), связанной с процессом прыгающей блохи. Для реального входа \(N=123456789\) прямое моделирование совершенно непригодно, поэтому реализация переписывает задачу в виде короткого двоичного разложения и рекурсивно уменьшаемого корректирующего члена.
Суть в том, что геометрия условия уже сжата до арифметики. Вместо отслеживания каждого прыжка вычисление использует только степени двойки вокруг \(N\), последний разностный член \(2^\lambda-N\) и мемоизированное евклидово ядро на приведенных парах целых чисел.
Положим
$$\lambda=\lfloor\log_2 N\rfloor+1,$$
тогда
$$2^{\lambda-1}\le N<2^\lambda.$$
Реализация вычисляет \(S(N)\), отделяя явный основной член от семейства поправок.
Используемая верхнеуровневая формула такова:
$$S(N)=\frac{N(3N+1)}{2}(\lambda+1)-\sum_{d=2}^{\lambda} C(N,2^d)+2C(N,2^\lambda-N).$$
Число \(\lambda\) есть просто длина двоичной записи \(N\). Формула показывает, что ответ полностью определяется степенями двойки, окружающими \(N\), и последней поправкой, измеряющей расстояние до следующей степени двойки.
Тем самым задача резко упрощается: вместо огромного пространства состояний нужно вычислить лишь \(\lambda-1=O(\log N)\) корректирующих значений.
Корректирующая функция записывается как
$$C(u,v)=(v-1)(v-2)-\Phi(u,v),$$
где \(\Phi(u,v)\) и есть по-настоящему рекурсивная часть. Квадратичный член \((v-1)(v-2)\) известен сразу, поэтому вся вычислительная сложность сосредоточена именно в \(\Phi\).
Перед любым рекурсивным шагом первый аргумент заменяется на остаток по модулю второго. Значит, важна только остаточная часть \(u\) по модулю \(v\). Если после этого получаем \(0\) или \(1\), рекурсия завершается, и
$$\Phi(u,v)=0.$$
Именно этот базовый случай делает спуск конечным.
Пусть приведенный первый аргумент равен \(a\), где \(2\le a<v\). Запишем
$$q=\left\lfloor\frac{v}{a}\right\rfloor,\qquad r=v\bmod a.$$
Тогда все три реализации используют точное тождество
$$\Phi(u,v)=\frac{q(q+1)a(a-1)}{4}+(q+1)\Phi(a,r)-q\,\Phi(a,a-r).$$
Первое слагаемое в закрытом виде суммирует целый блок с одинаковым частным. Два оставшихся слагаемых являются меньшими подзадачами. Новые модули \(r\) и \(a-r\) строго меньше \(a\), поэтому рекурсия убывает в духе алгоритма Евклида.
Полиномиальный множитель
$$\frac{q(q+1)a(a-1)}{4}$$
всегда является целым числом. Действительно, \(q(q+1)\) четно как произведение соседних чисел, и \(a(a-1)\) также четно по той же причине. Следовательно, их произведение делится на \(4\).
Никакой арифметики с плавающей точкой не требуется. Каждая ветвь работает только с целыми числами, поэтому значения можно безопасно мемоизировать и затем повторно использовать без ошибок округления.
Одна и та же приведенная пара может возникать из нескольких корректирующих членов внешней суммы. Как только \(\Phi(a,v)\) однажды посчитана, любое повторное появление той же пары сводится к обращению к таблице.
Это важно, потому что верхняя формула запрашивает много близких двоичных модулей. Мемоизация превращает потенциально огромный рекурсивный лес в гораздо меньший ациклический граф из действительно разных остаточных состояний.
Для \(N=5\) имеем \(\lambda=\lfloor\log_2 5\rfloor+1=3\). Значит,
$$S(5)=\frac{5(3\cdot5+1)}{2}(3+1)-C(5,4)-C(5,8)+2C(5,3).$$
Явный основной член равен
$$\frac{5\cdot16}{2}\cdot4=160.$$
Теперь вычислим поправки.
Для \(C(5,4)\) остаток \(5\bmod 4\) равен \(1\), следовательно \(\Phi(5,4)=0\). Поэтому
$$C(5,4)=(4-1)(4-2)=6.$$
Для \(C(5,3)\) приведенный первый аргумент равен \(2\). Тогда \(q=\lfloor 3/2\rfloor=1\), \(r=1\), и потому
$$\Phi(5,3)=\frac{1\cdot2\cdot2\cdot1}{4}+2\Phi(2,1)-\Phi(2,1)=1.$$
Отсюда
$$C(5,3)=(3-1)(3-2)-1=1.$$
Для \(C(5,8)\) получаем \(a=5\), \(q=1\), \(r=3\). Тогда
$$\Phi(5,8)=\frac{1\cdot2\cdot5\cdot4}{4}+2\Phi(5,3)-\Phi(5,2)=10+2\cdot1-0=12,$$
поскольку \(5\bmod 2=1\), а значит \(\Phi(5,2)=0\). Следовательно,
$$C(5,8)=(8-1)(8-2)-12=42-12=30.$$
Собирая все вместе, получаем
$$S(5)=160-6-30+2\cdot1=126,$$
что в точности совпадает с контрольным значением реализации.
Реализации на C++, Python и Java устроены одинаково. Сначала они находят \(\lambda\), затем строят основной член \(\frac{N(3N+1)}{2}(\lambda+1)\), после этого вычитают двоичные поправки \(C(N,2^d)\) для \(2\le d\le\lambda\) и в конце добавляют \(2C(N,2^\lambda-N)\).
Каждое вычисление поправки начинается с приведения первого аргумента по модулю второго. Если приведенное значение равно \(0\) или \(1\), ответ известен сразу. Иначе реализация вычисляет частное \(q\), остаток \(r\), применяет рекуррентную формулу и сохраняет результат в таблице мемоизации, индексированной приведенной парой.
Компилируемые версии расширяют промежуточные произведения квадратичного члена до более широкого числового представления, а Python естественным образом использует целые числа произвольной длины. При этом алгоритм во всех трех языках одинаков, и все версии согласуются с контрольными значениями \(S(3)=42\), \(S(5)=126\), \(S(123)=167178\) и \(S(12345)=3185041956\).
Внешнее разложение содержит только \(O(\log N)\) корректирующих членов, потому что \(\lambda\) есть длина двоичной записи \(N\). Реальная стоимость определяется числом различных приведенных пар, возникающих в ходе рекурсивного спуска.
Если обозначить число таких мемоизированных состояний через \(M\), то после учета обращений к хеш-таблице время работы равно \(O(M)\), а память также равна \(O(M)\). На практике \(M\) остается небольшим, потому что каждый новый шаг заменяет текущий модуль числами, меньшими текущего остатка, то есть наблюдается евклидово сжатие, а не комбинаторный взрыв.
تطلب مسألة Project Euler 702 إيجاد القيمة الدقيقة لكمية \(S(N)\) المرتبطة بعملية البرغوث القافز. بالنسبة إلى الإدخال الحقيقي \(N=123456789\)، فإن أي محاكاة مباشرة تصبح غير عملية تمامًا، ولذلك تعيد الخوارزمية صياغة المسألة على شكل تفكيك ثنائي قصير مع حد تصحيحي يُختزل تكراريًا.
الفكرة الأساسية أن الوصف الهندسي في نص المسألة جرى ضغطه إلى صورة حسابية بحتة. بدل تتبع كل قفزة على حدة، يكفي التعامل مع قوى العدد \(2\) المحيطة بـ \(N\)، ومع حد الفجوة الأخير \(2^\lambda-N\)، ومع نواة تكرارية ذات طابع إقليدي مع تخزين مؤقت للحالات المختزلة.
لنعرّف
$$\lambda=\lfloor\log_2 N\rfloor+1,$$
وبالتالي
$$2^{\lambda-1}\le N<2^\lambda.$$
تعتمد الخوارزمية على فصل \(S(N)\) إلى حد رئيسي مغلق ومجموعة من حدود التصحيح.
المتطابقة العليا المستخدمة هي
$$S(N)=\frac{N(3N+1)}{2}(\lambda+1)-\sum_{d=2}^{\lambda} C(N,2^d)+2C(N,2^\lambda-N).$$
الكمية \(\lambda\) ليست إلا طول التمثيل الثنائي للعدد \(N\). وتقول هذه الصيغة إن الجواب كله تحدده قوى \(2\) التي تحيط بـ \(N\)، مع تصحيح أخير يقيس المسافة حتى القوة التالية للعدد \(2\).
وبهذا يتقلص حجم المسألة فورًا: بدل فضاء بحث ضخم، نحتاج فقط إلى \(\lambda-1=O(\log N)\) من حدود التصحيح.
يُكتب حد التصحيح على الصورة
$$C(u,v)=(v-1)(v-2)-\Phi(u,v).$$
وهنا تمثل \(\Phi(u,v)\) الجزء التكراري الحقيقي، أما الجزء \((v-1)(v-2)\) فهو حد تربيعي صريح. لذلك تتركز الصعوبة الحسابية كلها في حساب \(\Phi\).
قبل أي خطوة تكرارية، يُختزل الوسيط الأول بترديده modulo الوسيط الثاني. أي إن المهم هو فقط باقي \(u\) عند القسمة على \(v\). فإذا كانت القيمة المختزلة \(0\) أو \(1\)، تتوقف العملية مباشرة ويصبح
$$\Phi(u,v)=0.$$
وهذه الحالة الأساسية هي التي تجعل الهبوط التكراري منتهيًا وسريعًا.
لنفترض أن الوسيط الأول بعد الاختزال هو \(a\) مع \(2\le a<v\). عندئذ نكتب
$$q=\left\lfloor\frac{v}{a}\right\rfloor,\qquad r=v\bmod a.$$
ثم تستخدم التطبيقات الثلاثة المتطابقة الدقيقة التالية:
$$\Phi(u,v)=\frac{q(q+1)a(a-1)}{4}+(q+1)\Phi(a,r)-q\,\Phi(a,a-r).$$
الحد الأول يلخّص كتلة كاملة من الحدود التي تشترك في نفس خارج القسمة. أما الحدّان الآخران فهما مسألتان فرعيتان أصغر. وبما أن المقدارين الجديدين \(r\) و\(a-r\) أصغر من \(a\) دائمًا، فإن التكرار يهبط كما يحدث في خوارزمية إقليدس.
إن العامل كثير الحدود
$$\frac{q(q+1)a(a-1)}{4}$$
هو دائمًا عدد صحيح. فالجداء \(q(q+1)\) زوجي لأنه حاصل ضرب عددين متتاليين، وكذلك \(a(a-1)\) زوجي للسبب نفسه، ولذلك يكون حاصل الضرب الكلي قابلًا للقسمة على \(4\).
لا حاجة إلى أي تقريب عشري. جميع الفروع التكرارية تعمل على الأعداد الصحيحة فقط، ولهذا يمكن تخزين القيم بدقة تامة ثم إعادة استخدامها من دون أي خطأ تقريبي.
قد يظهر الزوج المختزل نفسه أكثر من مرة انطلاقًا من حدود تصحيح مختلفة في الصيغة الخارجية. وما إن تُحسب القيمة \(\Phi(a,v)\) مرة واحدة، حتى تصبح كل إعادة ظهور لاحقة مجرد قراءة من الجدول.
وهذا مهم لأن الصيغة العليا تطلب عدة مقاييس ثنائية متقاربة. التخزين المؤقت يحوّل شجرة تكرارية كبيرة إلى رسم بياني موجّه لا دوري أصغر بكثير، لا يحتوي إلا الحالات المختلفة فعلًا.
عند \(N=5\) نجد أن \(\lambda=\lfloor\log_2 5\rfloor+1=3\). إذن
$$S(5)=\frac{5(3\cdot5+1)}{2}(3+1)-C(5,4)-C(5,8)+2C(5,3).$$
أما الحد الرئيسي الصريح فيساوي
$$\frac{5\cdot16}{2}\cdot4=160.$$
نحسب الآن حدود التصحيح واحدًا واحدًا.
بالنسبة إلى \(C(5,4)\)، فإن \(5\bmod 4=1\)، ومن ثم \(\Phi(5,4)=0\). وبالتالي
$$C(5,4)=(4-1)(4-2)=6.$$
أما \(C(5,3)\)، فبعد الاختزال يصبح الوسيط الأول \(2\). عندئذ \(q=\lfloor 3/2\rfloor=1\) و\(r=1\)، لذا
$$\Phi(5,3)=\frac{1\cdot2\cdot2\cdot1}{4}+2\Phi(2,1)-\Phi(2,1)=1.$$
ومن ثم
$$C(5,3)=(3-1)(3-2)-1=1.$$
وبالنسبة إلى \(C(5,8)\)، نحصل على \(a=5\) و\(q=1\) و\(r=3\). لذلك
$$\Phi(5,8)=\frac{1\cdot2\cdot5\cdot4}{4}+2\Phi(5,3)-\Phi(5,2)=10+2\cdot1-0=12,$$
لأن \(5\bmod 2=1\)، ومن ثم \(\Phi(5,2)=0\). إذًا
$$C(5,8)=(8-1)(8-2)-12=42-12=30.$$
وبجمع كل الأجزاء نحصل على
$$S(5)=160-6-30+2\cdot1=126,$$
وهو بالضبط نفس مقدار التحقق المستخدم في التنفيذ.
تتبع تطبيقات C++ وPython وJava نفس البنية تمامًا. فهي تبدأ بحساب \(\lambda\)، ثم تكوّن الحد الرئيسي \(\frac{N(3N+1)}{2}(\lambda+1)\)، وبعد ذلك تطرح التصحيحات الثنائية \(C(N,2^d)\) لكل \(2\le d\le\lambda\)، ثم تضيف في النهاية \(2C(N,2^\lambda-N)\).
كل عملية تقييم لحد تصحيحي تبدأ باختزال الوسيط الأول modulo الوسيط الثاني. فإذا كانت القيمة المختزلة \(0\) أو \(1\)، كان الجواب فوريًا. وإلا فإن التنفيذ يحسب خارج القسمة \(q\) والباقي \(r\)، ويطبق العلاقة التكرارية السابقة، ثم يخزن النتيجة في جدول مؤقت مفهرس بالزوج المختزل.
في النسخ المترجمة، تُوسَّع الضروب الوسيطة في الحد التربيعي مؤقتًا إلى تمثيل عددي أوسع للمحافظة على الدقة؛ أما Python فيستفيد طبيعيًا من الأعداد الصحيحة ذات الدقة غير المحدودة. ومع اختلاف تفاصيل السلامة العددية، تبقى الخوارزمية واحدة في اللغات الثلاث، وتطابق قيم التحقق المعروفة \(S(3)=42\)، \(S(5)=126\)، \(S(123)=167178\)، و\(S(12345)=3185041956\).
لا يحتوي التفكيك الخارجي إلا على \(O(\log N)\) من حدود التصحيح لأن \(\lambda\) هو طول التمثيل الثنائي للعدد \(N\). أما الكلفة الحقيقية فتتحدد بعدد الأزواج المختزلة المختلفة التي تظهر أثناء الهبوط التكراري.
إذا رمزنا إلى عدد هذه الحالات المحفوظة بـ \(M\)، فإن زمن التنفيذ يكون \(O(M)\) بعد احتساب وصولات جدول التجزئة، كما يكون استهلاك الذاكرة \(O(M)\) أيضًا. عمليًا يبقى \(M\) صغيرًا، لأن كل خطوة جديدة غير مخزنة تستبدل المقياس الحالي بمقادير أصغر من الباقي الحالي، فيظهر انكماش من نوع إقليدي بدل انفجار توافقي.