For every starting integer \(1 \le n \lt 10^6\), repeatedly apply the Collatz map $$T(n)=\begin{cases}\dfrac{n}{2}, & n \equiv 0 \pmod{2},\\[4pt] 3n+1, & n \equiv 1 \pmod{2}.\end{cases}$$ The goal is to find which starting value produces the longest chain before reaching 1, counting both the starting value and the final 1 as terms of the chain.
The key difficulty is that the orbit of a small starting value can rise far above the search bound before it comes back down. That means the computation cannot be organized as a simple left-to-right table on the interval \(1,2,\dots,10^6-1\); it has to reuse information wherever different trajectories merge.
Write the Collatz orbit of \(n\) as $$n_0=n,\qquad n_{k+1}=T(n_k).$$ Define the chain length \(\lambda(n)\) to be the number of terms from \(n\) down to 1, inclusive. Then the basic recurrence is $$\lambda(1)=1,\qquad \lambda(n)=1+\lambda(T(n)) \quad (n \ge 2).$$ Everything in the implementations follows from using this recurrence efficiently.
The search is restricted to starting values below one million, but the recurrence itself lives on all positive integers visited by those starts. For example, the chain beginning at 13 is $$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1,$$ so even a small start immediately moves outside any tiny local neighborhood. The mathematical object being computed is therefore a directed functional graph on positive integers, where each \(n\) has exactly one outgoing edge to \(T(n)\).
If two starting values ever reach the same intermediate value \(m\), then everything after \(m\) is identical for both chains. So once \(\lambda(m)\) is known, there is no reason to recompute the tail below \(m\) again. The central invariant is simple: if \(n_a=n_b=m\), then the remaining suffix from that point onward is identical. In other words, the problem is not about storing whole chains; it is about storing chain lengths at merge points.
Suppose a forward walk starting from \(n\) produces distinct visited values $$n_0,\ n_1,\ n_2,\ \dots,\ n_{r-1},\ n_r,$$ and the first value already known in the memo table is \(n_r\). Then $$\lambda(n_{r-1})=\lambda(n_r)+1,$$ $$\lambda(n_{r-2})=\lambda(n_r)+2,$$ and in general $$\lambda(n_i)=\lambda(n_r)+(r-i)\qquad (0 \le i \lt r).$$ This is exactly why the implementations walk forward first, save the visited values on a stack, and then assign lengths while popping that stack in reverse order.
Starting from 13, the orbit is $$13,\ 40,\ 20,\ 10,\ 5,\ 16,\ 8,\ 4,\ 2,\ 1.$$ If the memo table already contains \(\lambda(1)=1\), reverse backfilling gives $$\lambda(2)=2,\ \lambda(4)=3,\ \lambda(8)=4,\ \lambda(16)=5,$$ $$\lambda(5)=6,\ \lambda(10)=7,\ \lambda(20)=8,\ \lambda(40)=9,\ \lambda(13)=10.$$ This matches the explicit length of the chain and also matches the checkpoint used by the C++ implementation.
Once \(\lambda(n)\) can be obtained quickly, the rest of the problem is a record search: $$\underset{1 \le n \lt 10^6}{\arg\max}\ \lambda(n).$$ The implementations scan the starting values in increasing order, compute each chain length with the memoized recurrence above, and keep the start that achieves the largest length seen so far. A smaller built-in checkpoint confirms that among starts below 20, the record holder is 18.
The computation begins from the only chain length known a priori: $$\lambda(1)=1.$$ A hash table or dictionary stores already computed lengths. This choice matters because trajectories may rise above the original search limit, so the memoized values are not restricted to a fixed contiguous array of small integers.
For each new start, the implementation repeatedly applies the Collatz rule until it reaches a value whose length has already been stored. Every unseen value on that path is pushed onto a temporary stack. Once a known value is reached, the code pops the stack and assigns each stored value with the recurrence \(\lambda(x)=1+\lambda(T(x))\). This avoids recursion, uses the recurrence exactly, and ensures that every stored value is written with its correct final chain length.
After each chain length is recovered, the implementation compares it with the current record and updates the best starting value only when a strictly longer chain is found. The C++, Python, and Java implementations all follow this same logic. The C++ and Java versions use 64-bit integer arithmetic for the orbit values, Python uses arbitrary-precision integers, and the C++ version also includes an explicit guard against overflow in the odd step.
Let \(L=10^6\) be the search bound, and let \(M\) be the number of distinct integers that appear in all trajectories started from \(1 \le n \lt L\) before they hit a memoized value. Because each newly discovered integer is inserted into the memo table once, pushed once, and popped once, the total expected running time is $$O(L+M),$$ where the expectation comes from constant-time average hash-table operations.
The memory usage is $$O(M),$$ not merely \(O(L)\), because the memo table also stores intermediate values above the search bound whenever a trajectory climbs that high. In practice this is still easily manageable for the Project Euler bound, and the memoized reuse of shared tails is what makes the search fast.
Für jede Startzahl \(1 \le n \lt 10^6\) wird die Collatz-Abbildung $$T(n)=\begin{cases}\dfrac{n}{2}, & n \equiv 0 \pmod{2},\\[4pt] 3n+1, & n \equiv 1 \pmod{2}.\end{cases}$$ wiederholt angewendet. Gesucht ist diejenige Startzahl, deren Folge vor dem Erreichen von 1 die größte Kettenlänge besitzt, wobei sowohl der Startwert als auch die abschließende 1 mitgezählt werden.
Die Schwierigkeit liegt darin, dass die Bahn einer kleinen Startzahl weit über die Grenze von einer Million hinaussteigen kann, bevor sie wieder fällt. Deshalb genügt keine einfache Tabelle nur über dem Suchintervall; man muss Informationen überall dort wiederverwenden, wo verschiedene Bahnen zusammenlaufen.
Schreibe die Collatz-Bahn von \(n\) als $$n_0=n,\qquad n_{k+1}=T(n_k).$$ Die Kettenlänge \(\lambda(n)\) sei die Anzahl der Terme von \(n\) bis 1 einschließlich. Dann gilt $$\lambda(1)=1,\qquad \lambda(n)=1+\lambda(T(n)) \quad (n \ge 2).$$ Die gesamte Lösung besteht darin, diese Rekurrenz effizient auszunutzen.
Die Suche ist auf Startwerte unter einer Million beschränkt, aber die Rekurrenz lebt auf allen positiven Zahlen, die von diesen Starts erreicht werden. Bereits für 13 erhält man $$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1.$$ Mathematisch arbeitet man also auf einem funktionalen Graphen der positiven ganzen Zahlen, in dem jeder Knoten genau eine ausgehende Kante zu \(T(n)\) besitzt.
Treffen zwei Startwerte irgendwann denselben Zwischenwert \(m\), dann ist der restliche Teil der Folge ab \(m\) identisch. Ist \(\lambda(m)\) einmal bekannt, darf dieser Suffix nie erneut vollständig berechnet werden. Der zentrale Gedanke lautet also: Wenn \(n_a=n_b=m\), dann ist der Rest der Bahn ab diesem Punkt derselbe. Gespeichert werden nicht ganze Folgen, sondern Längen an Zusammenführungspunkten.
Angenommen, der Vorwärtslauf von einem Start \(n\) besucht $$n_0,\ n_1,\ n_2,\ \dots,\ n_{r-1},\ n_r,$$ wobei \(n_r\) der erste bereits memoisiere Wert ist. Dann folgt unmittelbar $$\lambda(n_{r-1})=\lambda(n_r)+1,$$ $$\lambda(n_{r-2})=\lambda(n_r)+2,$$ und allgemein $$\lambda(n_i)=\lambda(n_r)+(r-i)\qquad (0 \le i \lt r).$$ Genau deshalb gehen die Implementierungen erst vorwärts, legen die besuchten Werte auf einen Stapel und füllen anschließend in umgekehrter Reihenfolge zurück.
Für 13 lautet die Bahn $$13,\ 40,\ 20,\ 10,\ 5,\ 16,\ 8,\ 4,\ 2,\ 1.$$ Wenn die Tabelle bereits \(\lambda(1)=1\) enthält, liefert das Rückwärts-Auffüllen $$\lambda(2)=2,\ \lambda(4)=3,\ \lambda(8)=4,\ \lambda(16)=5,$$ $$\lambda(5)=6,\ \lambda(10)=7,\ \lambda(20)=8,\ \lambda(40)=9,\ \lambda(13)=10.$$ Das stimmt mit der explizit gezählten Kettenlänge überein und entspricht auch dem Kontrolltest der C++-Version.
Sobald \(\lambda(n)\) schnell berechnet werden kann, bleibt nur noch eine Rekordsuche: $$\underset{1 \le n \lt 10^6}{\arg\max}\ \lambda(n).$$ Die Implementierungen prüfen die Startwerte in aufsteigender Reihenfolge, bestimmen jede Kettenlänge mit der memoisierten Rekurrenz und merken sich die Startzahl mit dem bisher größten Wert. Ein kleiner eingebauter Test bestätigt zusätzlich, dass unter 20 der Rekordhalter 18 ist.
Zu Beginn ist genau eine Länge sicher bekannt: $$\lambda(1)=1.$$ Eine Hashtabelle speichert alle bereits berechneten Werte. Das ist wichtig, weil die Bahnen über die Suchgrenze hinauswachsen können; die gespeicherten Zustände bilden also keine feste kleine Intervalltabelle.
Für jeden neuen Start folgt die Implementierung der Collatz-Regel, bis ein Wert erreicht wird, dessen Kettenlänge bereits bekannt ist. Alle zuvor unbekannten Werte werden auf einem temporären Stapel gesammelt. Danach wird der Stapel rückwärts geleert, und jedes Element erhält seine Länge über die Rekurrenz \(\lambda(x)=1+\lambda(T(x))\). So wird die Rekurrenz exakt umgesetzt, ohne Rekursion zu benötigen.
Nach jeder Berechnung wird die gefundene Länge mit dem bisherigen Rekord verglichen. Nur bei einer strikt größeren Länge wird die beste Startzahl ersetzt. Die C++-, Python- und Java-Implementierungen verwenden dasselbe Schema. C++ und Java arbeiten für Bahnwerte mit 64-Bit-Ganzzahlen, Python mit beliebig großen Ganzzahlen, und die C++-Version schützt den ungeraden Schritt zusätzlich vor Überlauf.
Sei \(L=10^6\) die Suchgrenze und \(M\) die Anzahl verschiedener Ganzzahlen, die in allen Bahnen von Startwerten \(1 \le n \lt L\) auftreten, bevor ein bereits memoisiertes Element erreicht wird. Da jede neu entdeckte Zahl genau einmal eingefügt, einmal auf den Stapel gelegt und einmal wieder entfernt wird, beträgt die erwartete Gesamtlaufzeit $$O(L+M),$$ wobei die Erwartung von den durchschnittlich konstanten Hashtabellenoperationen stammt.
Der Speicherbedarf ist $$O(M),$$ nicht bloß \(O(L)\), weil auch Zwischenwerte oberhalb der Suchgrenze gespeichert werden, sobald eine Bahn dorthin ansteigt. Für die Euler-Grenze bleibt das problemlos praktikabel; entscheidend ist die Wiederverwendung gemeinsamer Suffixe.
Her başlangıç değeri \(1 \le n \lt 10^6\) için Collatz dönüşümü $$T(n)=\begin{cases}\dfrac{n}{2}, & n \equiv 0 \pmod{2},\\[4pt] 3n+1, & n \equiv 1 \pmod{2}.\end{cases}$$ art arda uygulanır. Amaç, 1'e ulaşmadan önce en uzun zinciri veren başlangıç sayısını bulmaktır; zincir uzunluğu sayılırken hem başlangıç terimi hem de son terim olan 1 dahildir.
Asıl zorluk şudur: küçük bir başlangıç değeri bile inişe geçmeden önce bir milyon sınırının çok üstüne çıkabilir. Dolayısıyla hesaplama yalnızca \(1,2,\dots,10^6-1\) aralığında soldan sağa doldurulan basit bir tablo değildir; farklı yörüngelerin birleştiği yerlerde bilginin yeniden kullanılması gerekir.
\(n\)'in Collatz yörüngesini $$n_0=n,\qquad n_{k+1}=T(n_k)$$ biçiminde yazalım. \(\lambda(n)\), \(n\)'den başlayıp 1'e kadar gidilen terim sayısı olsun. O zaman temel bağıntı $$\lambda(1)=1,\qquad \lambda(n)=1+\lambda(T(n)) \quad (n \ge 2)$$ olur. Uygulamaların yaptığı her şey bu bağıntının verimli biçimde kullanılmasıdır.
Arama uzayı bir milyonun altındaki başlangıçlarla sınırlıdır, fakat bağıntının kendisi bu başlangıçların ziyaret ettiği bütün pozitif tam sayılar üzerinde yaşar. Örneğin 13 için zincir $$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$$ şeklindedir. Yani matematiksel olarak çalışılan nesne, her \(n\)'nin tam bir çıkış kenarıyla \(T(n)\)'ye bağlandığı pozitif tam sayılar üzerindeki fonksiyonel grafiktir.
İki farklı başlangıç bir noktada aynı ara değere \(m\) ulaşırsa, o andan sonraki kuyruk tamamen aynıdır. Bu yüzden \(\lambda(m)\) bir kez bilindiğinde, \(m\)'den aşağısını tekrar hesaplamak gereksizdir. Merkezdeki fikir şudur: Eğer \(n_a=n_b=m\) ise, bundan sonraki kuyruk aynıdır. Dolayısıyla saklanan şey tüm zincirler değil, birleşme noktalarındaki zincir uzunluklarıdır.
Diyelim ki bir başlangıç için ileri yürüyüş $$n_0,\ n_1,\ n_2,\ \dots,\ n_{r-1},\ n_r$$ değerlerini üretiyor ve memo tablosunda zaten bilinen ilk değer \(n_r\) oluyor. O zaman $$\lambda(n_{r-1})=\lambda(n_r)+1,$$ $$\lambda(n_{r-2})=\lambda(n_r)+2,$$ ve genel olarak $$\lambda(n_i)=\lambda(n_r)+(r-i)\qquad (0 \le i \lt r).$$ Kodun önce ileri gidip ziyaret edilen değerleri bir yığına koyması, sonra da bu yığını ters sırada boşaltması tam olarak bu formüle dayanır.
13'ten başlayan zincir $$13,\ 40,\ 20,\ 10,\ 5,\ 16,\ 8,\ 4,\ 2,\ 1$$ olur. Eğer tabloda zaten \(\lambda(1)=1\) varsa ters doldurma şu değerleri verir: $$\lambda(2)=2,\ \lambda(4)=3,\ \lambda(8)=4,\ \lambda(16)=5,$$ $$\lambda(5)=6,\ \lambda(10)=7,\ \lambda(20)=8,\ \lambda(40)=9,\ \lambda(13)=10.$$ Bu hem zincirin açık sayımıyla uyuşur hem de C++ uygulamasındaki küçük doğrulama kontrolüyle tam olarak aynıdır.
\(\lambda(n)\) hızlı biçimde bulunabildiğinde geriye yalnızca rekor araması kalır: $$\underset{1 \le n \lt 10^6}{\arg\max}\ \lambda(n).$$ Uygulamalar başlangıç değerlerini artan sırayla gezer, her zincir uzunluğunu yukarıdaki memoize bağıntıyla hesaplar ve o ana kadar görülen en büyük uzunluğu veren başlangıcı tutar. Ayrıca daha küçük bir kontrol olarak, 20'nin altındaki başlangıçlar arasında en uzun zincirin 18'den geldiği de doğrulanır.
Başlangıçta kesin olarak bilinen tek değer $$\lambda(1)=1$$ olduğundan memo yapısı bununla kurulur. Kullanılan yapı bir hash tablo ya da sözlüktür. Bu tercih önemlidir; çünkü zincirler arama sınırının üzerine çıkabildiği için saklanan değerler küçük ve bitişik bir diziye sıkışmaz.
Her yeni başlangıç için uygulama Collatz kuralını tekrarlayarak daha önce uzunluğu bilinmeyen değerleri bir yığında toplar. Uzunluğu bilinen bir değere ulaşıldığında, yığın ters sırada boşaltılır ve her değer için \(\lambda(x)=1+\lambda(T(x))\) bağıntısı kullanılır. Böylece özyineleme kullanılmadan tam matematiksel bağıntı uygulanmış olur.
Her zincir uzunluğu bulunduktan sonra mevcut rekorla karşılaştırılır; yalnızca daha uzun bir zincir bulunduğunda en iyi başlangıç değiştirilir. C++, Python ve Java uygulamalarının ortak mantığı budur. C++ ve Java yörünge değerleri için 64 bit tam sayı kullanır, Python ise keyfi büyüklükte tam sayılarla çalışır; C++ sürümünde tek sayı adımı için ayrıca taşma koruması da vardır.
\(L=10^6\) arama sınırı ve \(M\), \(1 \le n \lt L\) için başlatılan tüm zincirlerde memoize bir değere ulaşılmadan önce görülen farklı tam sayıların sayısı olsun. Her yeni değer tabloya bir kez eklenir, bir kez yığına konur ve bir kez yığından çıkarılır. Hash tablo işlemlerinin ortalama sabit zamanlı olduğu varsayımıyla toplam beklenen süre $$O(L+M)$$ olur.
Bellek kullanımı ise $$O(M)$$ düzeyindedir. Burada yalnızca başlangıç aralığındaki sayılar değil, zincirin daha yukarıda ziyaret ettiği ara değerler de saklandığı için salt \(O(L)\) demek doğru olmaz. Project Euler sınırında bu yaklaşım rahatlıkla uygulanabilir ve hızın ana nedeni ortak kuyrukların yeniden kullanılabilmesidir.
Para cada valor inicial \(1 \le n \lt 10^6\), se aplica repetidamente la transformación de Collatz $$T(n)=\begin{cases}\dfrac{n}{2}, & n \equiv 0 \pmod{2},\\[4pt] 3n+1, & n \equiv 1 \pmod{2}.\end{cases}$$ Hay que determinar qué valor inicial produce la cadena más larga antes de llegar a 1, contando tanto el valor inicial como el 1 final dentro de la longitud.
La dificultad real es que una trayectoria que empieza por debajo de un millón puede subir muy por encima de ese límite antes de descender. Por eso no basta una tabla lineal sobre el intervalo de búsqueda; la solución tiene que reutilizar información cada vez que dos trayectorias comparten el mismo sufijo.
Escribamos la órbita de Collatz de \(n\) como $$n_0=n,\qquad n_{k+1}=T(n_k).$$ Definimos \(\lambda(n)\) como el número de términos desde \(n\) hasta 1, inclusive. Entonces $$\lambda(1)=1,\qquad \lambda(n)=1+\lambda(T(n)) \quad (n \ge 2).$$ Toda la solución consiste en explotar esta recurrencia sin recalcular colas ya conocidas.
La búsqueda sólo considera valores iniciales menores que un millón, pero la recurrencia vive en todos los enteros positivos visitados por esas órbitas. Incluso el ejemplo clásico $$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$$ muestra que una trayectoria pequeña enseguida abandona cualquier vecindad corta. Matemáticamente, el problema se apoya en un grafo funcional sobre enteros positivos, donde cada \(n\) tiene exactamente una arista saliente hacia \(T(n)\).
Si dos trayectorias llegan al mismo valor intermedio \(m\), desde ese punto en adelante ambas siguen exactamente la misma cola. Una vez conocida \(\lambda(m)\), no hay razón para recomputar esa parte de nuevo. La idea central es ésta: si \(n_a=n_b=m\), entonces el resto de la cadena coincide a partir de \(m\). Por tanto, lo que se memoriza no son cadenas completas, sino longitudes en los puntos de convergencia.
Supongamos que el recorrido hacia adelante desde un inicio \(n\) visita $$n_0,\ n_1,\ n_2,\ \dots,\ n_{r-1},\ n_r,$$ y que \(n_r\) es el primer valor cuya longitud ya está almacenada. Entonces $$\lambda(n_{r-1})=\lambda(n_r)+1,$$ $$\lambda(n_{r-2})=\lambda(n_r)+2,$$ y, en general, $$\lambda(n_i)=\lambda(n_r)+(r-i)\qquad (0 \le i \lt r).$$ Ésta es exactamente la razón por la que las implementaciones avanzan primero, guardan los valores vistos en una pila y luego rellenan longitudes al desapilar en orden inverso.
La órbita de 13 es $$13,\ 40,\ 20,\ 10,\ 5,\ 16,\ 8,\ 4,\ 2,\ 1.$$ Si la tabla ya contiene \(\lambda(1)=1\), el rellenado inverso da $$\lambda(2)=2,\ \lambda(4)=3,\ \lambda(8)=4,\ \lambda(16)=5,$$ $$\lambda(5)=6,\ \lambda(10)=7,\ \lambda(20)=8,\ \lambda(40)=9,\ \lambda(13)=10.$$ Esto coincide con la longitud explícita de la cadena y también con la comprobación pequeña que aparece en la implementación de C++.
Una vez que \(\lambda(n)\) se obtiene rápido, el resto es una búsqueda de récord: $$\underset{1 \le n \lt 10^6}{\arg\max}\ \lambda(n).$$ Las implementaciones recorren los valores iniciales en orden creciente, calculan cada longitud con la recurrencia memorizada y conservan el inicio que ha producido la mayor longitud hasta ese momento. Como control adicional, también verifican que el mejor inicio por debajo de 20 es 18.
El cálculo arranca con la única longitud conocida de antemano: $$\lambda(1)=1.$$ Esa información se guarda en un diccionario o tabla hash. Esta elección es importante porque las trayectorias pueden superar el límite de búsqueda, así que los valores memorizados no están restringidos a un arreglo fijo de enteros pequeños consecutivos.
Para cada nuevo inicio, la implementación aplica la regla de Collatz hasta encontrar un valor cuya longitud ya está almacenada. Todos los valores inéditos de esa trayectoria se apilan temporalmente. Cuando aparece un valor conocido, la pila se vacía al revés y se asignan longitudes usando \(\lambda(x)=1+\lambda(T(x))\). Así se evita la recursión y se respeta exactamente la recurrencia matemática.
Después de recuperar una longitud, la implementación la compara con el récord actual y sólo actualiza el mejor inicio cuando encuentra una cadena estrictamente más larga. Las versiones en C++, Python y Java siguen esta misma lógica. C++ y Java usan enteros de 64 bits para los valores de la órbita, Python usa enteros de precisión arbitraria, y la versión en C++ añade además una protección explícita contra desbordamiento en el paso impar.
Sea \(L=10^6\) el límite de búsqueda y sea \(M\) el número de enteros distintos que aparecen en todas las trayectorias iniciadas con \(1 \le n \lt L\) antes de alcanzar un valor ya memorizado. Como cada entero nuevo se inserta una sola vez, se apila una sola vez y se desapila una sola vez, el tiempo total esperado es $$O(L+M),$$ donde la expectativa proviene del coste promedio constante de las operaciones sobre tablas hash.
La memoria es $$O(M),$$ y no simplemente \(O(L)\), porque la tabla también conserva valores intermedios mayores que el límite cuando una trayectoria asciende por encima de él. Para el límite de Project Euler esto sigue siendo muy manejable, y la reutilización de colas comunes es lo que vuelve práctico el método.
对于每个起始整数 \(1 \le n \lt 10^6\)，反复应用 Collatz 变换 $$T(n)=\begin{cases}\dfrac{n}{2}, & n \equiv 0 \pmod{2},\\[4pt] 3n+1, & n \equiv 1 \pmod{2}.\end{cases}$$ 题目要求找出哪一个起始值在到达 1 之前产生最长的链，并且链长同时计入起点和终点 1。
真正的难点在于：虽然搜索范围只限定在一百万以下的起始值，但某条轨道在下降之前可能会先冲到远高于这个界限的整数。因此，算法不能只在小区间上做顺序表填充，而必须在不同轨道合流时重用已经得到的信息。
把 \(n\) 的 Collatz 轨道写成 $$n_0=n,\qquad n_{k+1}=T(n_k).$$ 定义 \(\lambda(n)\) 为从 \(n\) 走到 1 的项数，且起点与终点都计入长度。于是有基本递推 $$\lambda(1)=1,\qquad \lambda(n)=1+\lambda(T(n)) \quad (n \ge 2).$$ 三种语言的实现本质上都在高效利用这个递推式。
搜索时只枚举 \(n \lt 10^6\) 的起点，但递推真正依赖的是这些起点沿途访问到的所有正整数。经典例子 13 的轨道就是 $$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1.$$ 这说明即使起点很小，轨道也可能很快跑到别的数量级。数学上更合适的对象是一个定义在正整数上的函数图，其中每个结点 \(n\) 都只有一条出边，指向 \(T(n)\)。
如果两个不同起点在某一步第一次汇合到同一个中间值 \(m\)，那么从 \(m\) 开始往后的尾部完全相同。于是只要 \(\lambda(m)\) 已知，就没有必要再把这段尾部重算一次。核心不变量可以直接表述为：若 \(n_a=n_b=m\)，那么从 \(m\) 开始的剩余轨道完全相同。因而真正需要缓存的不是整条链，而是这些合流点的链长。
设某个起点的前向遍历依次得到 $$n_0,\ n_1,\ n_2,\ \dots,\ n_{r-1},\ n_r,$$ 其中 \(n_r\) 是第一个已经在缓存中出现的值。由于它的链长已知，所以立刻有 $$\lambda(n_{r-1})=\lambda(n_r)+1,$$ $$\lambda(n_{r-2})=\lambda(n_r)+2,$$ 更一般地， $$\lambda(n_i)=\lambda(n_r)+(r-i)\qquad (0 \le i \lt r).$$ 这就是实现为什么先向前走、把未见过的值压入栈，再逆序弹栈回填长度的根本原因。
13 的整条轨道是 $$13,\ 40,\ 20,\ 10,\ 5,\ 16,\ 8,\ 4,\ 2,\ 1.$$ 如果缓存中起初只有 \(\lambda(1)=1\)，那么反向回填依次得到 $$\lambda(2)=2,\ \lambda(4)=3,\ \lambda(8)=4,\ \lambda(16)=5,$$ $$\lambda(5)=6,\ \lambda(10)=7,\ \lambda(20)=8,\ \lambda(40)=9,\ \lambda(13)=10.$$ 这既和逐项数出来的链长一致，也正好对应 C++ 实现中的一个小型校验。
一旦 \(\lambda(n)\) 可以快速得到，剩下的就是一个记录保持者搜索： $$\underset{1 \le n \lt 10^6}{\arg\max}\ \lambda(n).$$ 实现按起始值从小到大扫描，利用上述记忆化递推求出每个链长，并维护到目前为止最长链所对应的起点。代码里还有一个更小的检查：在 20 以下的起点中，最长链来自 18。
整个计算从唯一已知的长度开始： $$\lambda(1)=1.$$ 这个值被放入一个哈希表或字典中。之所以不用只覆盖小范围整数的定长数组，是因为轨道会越过原始搜索边界，缓存必须能够容纳这些更大的中间值。
对每个新的起点，程序不断应用 Collatz 规则，直到遇到一个长度已经缓存的值为止。沿途第一次见到的值都会暂时压入栈中。到达已知结点后，代码按相反顺序弹栈，并对每个结点应用 \(\lambda(x)=1+\lambda(T(x))\) 来写入正确长度。这样既避免了递归深度问题，又完全忠实于数学递推关系。
每算出一个起点的链长，程序就把它与当前记录比较；只有发现严格更长的链时，才会替换当前最优起点。C++、Python 和 Java 三个实现都遵循这一逻辑。C++ 与 Java 用 64 位整数保存轨道上的值，Python 使用任意精度整数，而 C++ 版本还对奇数步中的 \(3n+1\) 做了显式溢出保护。
记 \(L=10^6\) 为搜索上界，记 \(M\) 为所有起点 \(1 \le n \lt L\) 的轨道在撞上已缓存值之前所访问到的不同整数个数。每个新整数只会被插入缓存一次、压栈一次、弹栈一次，所以总的期望时间复杂度为 $$O(L+M),$$ 其中“期望”来自哈希表查找和插入的平均常数时间。
空间复杂度为 $$O(M),$$ 而不是简单的 \(O(L)\)。原因是缓存里除了起点区间内的值，还会保存轨道上升时碰到的、更大的中间整数。对于题目的范围，这个规模依然完全可控，而真正节省时间的关键正是公共尾部的复用。
Для каждого начального числа \(1 \le n \lt 10^6\) многократно применяется преобразование Коллатца $$T(n)=\begin{cases}\dfrac{n}{2}, & n \equiv 0 \pmod{2},\\[4pt] 3n+1, & n \equiv 1 \pmod{2}.\end{cases}$$ Нужно определить, какой старт даёт самую длинную цепочку до достижения 1, причём в длину входят и начальное значение, и конечная единица.
Главная трудность в том, что траектория маленького старта может значительно превысить миллион, прежде чем начнёт снижаться. Поэтому недостаточно просто заполнить таблицу на отрезке поиска; нужно переиспользовать уже найденные хвосты там, где разные орбиты сливаются.
Обозначим орбиту Коллатца числа \(n\) так: $$n_0=n,\qquad n_{k+1}=T(n_k).$$ Пусть \(\lambda(n)\) означает число членов от \(n\) до 1 включительно. Тогда выполняется базовая рекурсия $$\lambda(1)=1,\qquad \lambda(n)=1+\lambda(T(n)) \quad (n \ge 2).$$ Вся идея решения состоит в том, чтобы использовать эту формулу без повторного вычисления одинаковых хвостов.
Перебираются лишь старты меньше миллиона, но сама рекурсия относится ко всем положительным целым, которые посещают эти старты. Уже пример $$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$$ показывает, что траектория быстро выходит за рамки локального интервала. Математически удобно рассматривать функциональный граф на положительных целых числах, где из каждого \(n\) выходит ровно одно ребро к \(T(n)\).
Если две траектории когда-либо попадают в один и тот же промежуточный узел \(m\), то всё, что идёт после \(m\), у них совпадает. Значит, после вычисления \(\lambda(m)\) нет смысла заново проходить этот хвост. Центральный инвариант таков: если \(n_a=n_b=m\), то дальнейшая часть цепочки совпадает. Следовательно, хранить нужно не сами цепочки, а их длины в точках слияния.
Пусть при движении вперёд из некоторого старта получаются значения $$n_0,\ n_1,\ n_2,\ \dots,\ n_{r-1},\ n_r,$$ причём \(n_r\) - первое число, длина которого уже есть в мемо-таблице. Тогда сразу получаем $$\lambda(n_{r-1})=\lambda(n_r)+1,$$ $$\lambda(n_{r-2})=\lambda(n_r)+2,$$ и вообще $$\lambda(n_i)=\lambda(n_r)+(r-i)\qquad (0 \le i \lt r).$$ Именно поэтому реализации сначала идут вперёд, складывают новые значения в стек, а затем извлекают их в обратном порядке и восстанавливают длины.
Орбита числа 13 равна $$13,\ 40,\ 20,\ 10,\ 5,\ 16,\ 8,\ 4,\ 2,\ 1.$$ Если в таблице уже записано \(\lambda(1)=1\), то обратное заполнение даёт $$\lambda(2)=2,\ \lambda(4)=3,\ \lambda(8)=4,\ \lambda(16)=5,$$ $$\lambda(5)=6,\ \lambda(10)=7,\ \lambda(20)=8,\ \lambda(40)=9,\ \lambda(13)=10.$$ Это совпадает и с прямым подсчётом длины цепочки, и с маленькой проверкой, встроенной в реализацию на C++.
Когда \(\lambda(n)\) уже можно находить быстро, остаётся лишь поиск рекордсмена: $$\underset{1 \le n \lt 10^6}{\arg\max}\ \lambda(n).$$ Реализации просматривают стартовые значения по возрастанию, вычисляют каждую длину через мемоизированную рекурсию и запоминают старт с наибольшей длиной на текущий момент. Дополнительная небольшая проверка подтверждает, что среди стартов меньше 20 рекорд даёт 18.
В начале известна только одна длина: $$\lambda(1)=1.$$ Она помещается в хеш-таблицу. Такой выбор структуры данных принципиален, потому что траектории выходят за исходную границу поиска, и хранить значения только в компактном массиве малых индексов было бы неверно.
Для каждого нового старта реализация повторяет правило Коллатца, пока не встретит число с уже известной длиной. Все ранее невиданные значения складываются во временный стек. После этого стек извлекается в обратном порядке, и каждому элементу присваивается длина по правилу \(\lambda(x)=1+\lambda(T(x))\). Тем самым рекурсия реализуется точно, но без проблем глубины рекурсивного вызова.
После нахождения длины очередного старта она сравнивается с текущим максимумом; лучшая стартовая величина обновляется только при строго большем значении. Реализации на C++, Python и Java следуют одной и той же схеме. C++ и Java используют 64-битные целые для значений орбиты, Python - целые произвольной длины, а версия на C++ дополнительно проверяет нечётный шаг на возможное переполнение.
Пусть \(L=10^6\) - верхняя граница поиска, а \(M\) - число различных целых значений, которые встречаются во всех траекториях стартов \(1 \le n \lt L\) до попадания в уже мемоизированную вершину. Поскольку каждое новое значение вставляется в таблицу один раз, кладётся в стек один раз и извлекается один раз, суммарное ожидаемое время работы равно $$O(L+M),$$ где ожидание связано со средней константной стоимостью операций хеш-таблицы.
Память составляет $$O(M),$$ а не просто \(O(L)\), потому что таблица хранит и те промежуточные значения, которые лежат выше границы поиска. Для предела из задачи Project Euler это по-прежнему вполне комфортно, а решающую экономию времени даёт именно повторное использование общих хвостов.
لكل قيمة ابتدائية \(1 \le n \lt 10^6\)، نطبّق تحويل كولاتز $$T(n)=\begin{cases}\dfrac{n}{2}, & n \equiv 0 \pmod{2},\\[4pt] 3n+1, & n \equiv 1 \pmod{2}.\end{cases}$$ المطلوب هو تحديد أي قيمة ابتدائية تعطي أطول سلسلة قبل الوصول إلى 1، مع احتساب قيمة البداية والعدد 1 النهائي ضمن طول السلسلة.
الصعوبة الجوهرية أن مساراً يبدأ تحت المليون قد يرتفع إلى قيم أكبر بكثير من هذا الحد قبل أن يهبط من جديد. لذلك لا تكفي معالجة خطية على مجال البحث فقط؛ بل يجب إعادة استخدام المعلومات كلما التقت سلسلتان في ذيل مشترك.
لنكتب مدار كولاتز للعدد \(n\) على الصورة $$n_0=n,\qquad n_{k+1}=T(n_k).$$ ولنعرّف \(\lambda(n)\) بأنه عدد الحدود من \(n\) حتى 1 مع الشمول. عندئذٍ نحصل على العلاقة الأساسية $$\lambda(1)=1,\qquad \lambda(n)=1+\lambda(T(n)) \quad (n \ge 2).$$ كل ما تفعله التطبيقات المختلفة هو استغلال هذه العلاقة بكفاءة ومنع إعادة حساب الذيول نفسها مراراً.
البحث نفسه يمرّ على قيم ابتدائية أقل من مليون، لكن العلاقة التراجعية تعيش على جميع الأعداد الصحيحة الموجبة التي تزورها هذه المدارات. حتى المثال البسيط $$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$$ يبيّن أن سلسلة صغيرة قد تغادر المجال المحلي سريعاً. رياضياً نحن نتعامل مع رسم بياني دالي على الأعداد الموجبة، بحيث يملك كل عدد \(n\) ضلع خروج واحداً فقط نحو \(T(n)\).
إذا وصلت سلسلتان مختلفتان في لحظة ما إلى القيمة الوسيطة نفسها \(m\)، فإن كل ما يأتي بعد \(m\) يكون متطابقاً تماماً في السلسلتين. لذلك متى عُرفت \(\lambda(m)\) مرة واحدة فلا داعي لإعادة حساب الذيل أسفلها. الفكرة المركزية هي: إذا كان \(n_a=n_b=m\)، فإن بقية المسار بعد \(m\) تكون واحدة في الحالتين. إذن ما يُخزَّن ليس السلاسل الكاملة، بل أطوال السلاسل عند نقاط الاندماج.
لنفترض أن السير إلى الأمام من قيمة ابتدائية ما يعطي $$n_0,\ n_1,\ n_2,\ \dots,\ n_{r-1},\ n_r,$$ وأن \(n_r\) هو أول عدد طوله معروف مسبقاً في جدول التذكّر. عندها نحصل مباشرة على $$\lambda(n_{r-1})=\lambda(n_r)+1,$$ $$\lambda(n_{r-2})=\lambda(n_r)+2,$$ وبصورة عامة $$\lambda(n_i)=\lambda(n_r)+(r-i)\qquad (0 \le i \lt r).$$ ولهذا السبب بالضبط تمشي التطبيقات أولاً إلى الأمام، وتجمع القيم غير المعروفة في مكدّس، ثم تفرغ المكدّس بالعكس لإسناد الأطوال الصحيحة.
مدار العدد 13 هو $$13,\ 40,\ 20,\ 10,\ 5,\ 16,\ 8,\ 4,\ 2,\ 1.$$ إذا كان جدول التذكّر يحتوي في البداية على \(\lambda(1)=1\)، فإن التعبئة العكسية تعطي $$\lambda(2)=2,\ \lambda(4)=3,\ \lambda(8)=4,\ \lambda(16)=5,$$ $$\lambda(5)=6,\ \lambda(10)=7,\ \lambda(20)=8,\ \lambda(40)=9,\ \lambda(13)=10.$$ وهذا يطابق العد المباشر لطول السلسلة، كما يطابق أيضاً فحصاً صغيراً موجوداً في تنفيذ C++.
بمجرد أن يصبح حساب \(\lambda(n)\) سريعاً، لا يبقى سوى البحث عن صاحب الرقم القياسي: $$\underset{1 \le n \lt 10^6}{\arg\max}\ \lambda(n).$$ تمرّ التطبيقات على قيم البداية تصاعدياً، وتحسب طول كل سلسلة باستخدام العلاقة المذخّرة أعلاه، ثم تحتفظ بالبداية التي حققت أكبر طول حتى تلك اللحظة. كما يوجد فحص أصغر يؤكد أن أفضل بداية تحت 20 هي 18.
يبدأ الحساب من الحقيقة الوحيدة المعروفة مسبقاً: $$\lambda(1)=1.$$ وتوضع هذه القيمة في قاموس أو جدول hash. هذا الاختيار مهم لأن المدارات قد تتجاوز حدّ البحث، وبالتالي لا يمكن حصر القيم المخزنة في مصفوفة صغيرة ثابتة الفهارس.
لكل بداية جديدة، يكرّر التنفيذ قاعدة كولاتز حتى يصل إلى قيمة طولها مخزون مسبقاً. كل قيمة جديدة على الطريق تُدفَع إلى مكدّس مؤقت. وعندما تظهر قيمة معروفة، يُفرَّغ المكدّس بالعكس وتُسند الأطوال باستخدام العلاقة \(\lambda(x)=1+\lambda(T(x))\). وبهذا تُنفَّذ العلاقة الرياضية نفسها بدقة من غير اللجوء إلى الاستدعاء الذاتي العميق.
بعد حساب طول أي سلسلة، يُقارَن هذا الطول بالرقم القياسي الحالي، ولا تتغير أفضل بداية إلا إذا ظهرت سلسلة أطول على نحو صارم. هذا هو المنطق المشترك بين تطبيقات C++ وPython وJava. يستخدم C++ وJava أعداداً صحيحة ذات 64 بت لقيم المدار، بينما يستخدم Python أعداداً صحيحة غير محدودة الدقة، كما تضيف نسخة C++ حماية صريحة ضد الفيض في الخطوة الفردية.
لنرمز إلى حدّ البحث بـ \(L=10^6\)، ولتكن \(M\) عدد القيم الصحيحة المختلفة التي تظهر في جميع المدارات المنطلقة من \(1 \le n \lt L\) قبل أن تصطدم بقيمة مخزنة مسبقاً. بما أن كل قيمة جديدة تُدرج مرة واحدة فقط، وتُدفَع إلى المكدّس مرة واحدة، وتُسحب منه مرة واحدة، فإن زمن التنفيذ المتوقع الكلي هو $$O(L+M),$$ حيث تأتي كلمة "متوقع" من كون عمليات جدول hash ذات كلفة ثابتة في المتوسط.
أما الذاكرة فهي $$O(M),$$ وليست مجرد \(O(L)\)، لأن الجدول لا يخزّن فقط القيم داخل مجال البداية، بل أيضاً القيم الوسيطة الأكبر التي تبلغها السلاسل عند الصعود. ومع ذلك يبقى هذا عملياً جداً عند حد Project Euler، والسر الحقيقي في السرعة هو إعادة استخدام الذيول المشتركة.