For a positive integer \(n\), write its decimal digits as \(d_1,d_2,\dots,d_r\) and define the digit-factorial map
$$F(n)=\sum_{i=1}^{r} d_i!.$$
Starting from \(n\), we repeatedly apply \(F\). The resulting sequence eventually repeats, so each start produces a finite list of distinct terms followed by a return to a value seen earlier. The problem asks for the number of starting values with \(1 \le n < 10^6\) whose chain contains exactly 60 non-repeating terms.
The classic example is \(69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454\), so the distinct part has length 5. The implementations solve the full count by treating these chains as walks in a finite functional graph and memoizing the exact remaining length of every state they finish.
The central object is not a large search tree but a deterministic map: every integer has exactly one outgoing edge, namely \(n \mapsto F(n)\). That means every trajectory has the same shape: a tail leading into a cycle. The whole problem is therefore to compute, for each start below one million, how many distinct vertices appear before the first repeated one.
The ten digit factorials are fixed once and for all:
$$0!=1,\ 1!=1,\ 2!=2,\ 3!=6,\ 4!=24,\ 5!=120,\ 6!=720,\ 7!=5040,\ 8!=40320,\ 9!=362880.$$
So evaluating \(F(n)\) is just decimal digit extraction plus table lookup. Zeros matter: every zero digit contributes \(0!=1\), which is why numbers such as \(363600\) jump to \(1454\) rather than to a smaller value.
If \(1 \le n < 10^6\), then \(n\) has at most six digits, so its first image satisfies
$$F(n)\le 6\cdot 9! = 2{,}177{,}280.$$
After that, every term has at most seven digits, and therefore every later image satisfies
$$F(a_k)\le 7\cdot 9! = 2{,}540{,}160 \qquad (k\ge 1).$$
Thus every chain starting below one million enters the finite set \(\{1,2,\dots,2{,}540{,}160\}\) immediately and never leaves it. A deterministic walk inside a finite set must eventually revisit a value, so every chain has a well-defined tail and cycle.
For a starting value \(n\), write
$$a_0=n,\qquad a_{k+1}=F(a_k).$$
The chain length required by the problem is the number of distinct values before the first repetition:
$$\ell(n)=\min\{t\ge 1 : a_t \in \{a_0,a_1,\dots,a_{t-1}\}\}.$$
Suppose a fresh exploration sees distinct values \(a_0,a_1,\dots,a_{t-1}\) and then finds that the next value equals \(a_r\) for some \(0\le r<t\). Then \(a_r,a_{r+1},\dots,a_{t-1}\) form a cycle of length
$$c=t-r.$$
Every point already on that cycle has exactly \(c\) non-repeating terms ahead of it, while each point in the tail has to traverse the remaining tail plus the full cycle. Therefore
$$\ell(a_i)=c \quad (r\le i<t),\qquad \ell(a_i)=c+r-i \quad (0\le i<r).$$
These formulas are exactly what the implementations write into the memo table when a new cycle is discovered.
Often a new search does not have to discover a brand-new cycle. Instead it reaches a value whose chain length was already computed earlier. If the first known value is \(a_t=m\) and \(\ell(m)\) is already stored, then the current path \(a_0,\dots,a_{t-1}\) is still repetition-free; otherwise the walk would have terminated earlier. So each earlier point simply adds one extra step:
$$\ell(a_i)=\ell(m)+t-i \qquad (0\le i<t).$$
This recurrence is the key optimization. Many starting values flow into the same suffix, so once that suffix is solved once, every later chain can stop immediately when it reaches it.
For \(69\), the chain is
$$69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454.$$
Here the distinct segment is \((69,363600,1454,169,363601)\), and the next value repeats the entry at position \(r=2\). Thus \(t=5\), the cycle length is \(c=3\), and the formulas give
$$\ell(1454)=3,\qquad \ell(363600)=4,\qquad \ell(69)=5.$$
A second useful checkpoint is
$$78 \to 45360 \to 871 \to 45361 \to 871.$$
Now the repeat begins at \(r=2\) with \(t=4\), so \(c=2\). Hence
$$\ell(871)=2,\qquad \ell(45360)=3,\qquad \ell(78)=4.$$
These two examples show both ingredients of the method: detect where the cycle begins, then propagate exact lengths backward through the tail.
The C++, Python, and Java implementations all begin by storing the ten values \(0!,1!,\dots,9!\). That makes each application of \(F\) a short digit loop with constant-time table lookups instead of repeated factorial computation.
To evaluate a single chain, the implementation keeps two temporary structures for the current exploration: an ordered list of newly visited values and a hash structure recording where each of those values first appeared. At each step it computes the next value and checks two termination conditions.
If the new value already has a memoized length, the implementation walks backward through the ordered list and assigns lengths using \(\ell(a_i)=\ell(m)+t-i\). If the new value already appeared on the current path, the ordered list is split into tail and cycle, the cycle nodes receive the common cycle length, and the tail nodes receive increasing lengths as one moves backward. In both cases, once these memo entries are written, the length of the original start is immediately known.
The outer loop runs through every \(n\) with \(1 \le n < 10^6\), asks for \(\ell(n)\), and increments the answer when \(\ell(n)=60\). Because the memo table is shared across the entire sweep, many later starts terminate after only a few steps. The C++ and Python implementations also include small built-in checkpoints for the sample lengths \(69 \mapsto 5\) and \(78 \mapsto 4\) before performing the full count.
Once a chain enters the bounded region, every evaluation of \(F\) reads at most seven digits, so each transition is \(O(1)\) in practice. Let \(U\) be the number of distinct values that are actually discovered while processing all starts below one million. Because a value is fully expanded only the first time it is solved, the total work is \(O(10^6 + U)\) hash-table operations, or \(O((10^6+U)d)\) digit operations with \(d\le 7\).
The bound above gives \(U\le 2{,}540{,}160\), so the algorithm is effectively linear in a few million states. Memory usage is \(O(U)\) for the memoized chain lengths, plus temporary storage proportional to the length of the chain currently being explored.
Für eine positive ganze Zahl \(n\) seien ihre Dezimalziffern \(d_1,d_2,\dots,d_r\). Definiere dann die Ziffernfakultätsabbildung
$$F(n)=\sum_{i=1}^{r} d_i!.$$
Ausgehend von \(n\) wird \(F\) immer wieder angewendet. Die entstehende Folge wiederholt sich schließlich, also besteht jede Startfolge aus einem endlichen Abschnitt verschiedener Werte und einem späteren Rücksprung auf einen früher gesehenen Wert. Gesucht ist die Anzahl der Startwerte mit \(1 \le n < 10^6\), deren Kette genau 60 nicht wiederholte Terme besitzt.
Das Standardbeispiel ist \(69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454\); der unterschiedliche Teil hat also Länge 5. Die Implementierungen lösen die Gesamtaufgabe, indem sie diese Ketten als Wege in einem endlichen funktionalen Graphen behandeln und für jeden vollständig aufgelösten Zustand die exakte Restlänge zwischenspeichern.
Das zentrale Objekt ist kein großer Suchbaum, sondern eine deterministische Abbildung: Jede ganze Zahl hat genau eine ausgehende Kante, nämlich \(n \mapsto F(n)\). Deshalb hat jede Bahn dieselbe Form, nämlich einen Schwanz, der in einen Zyklus einmündet. Die gesamte Aufgabe besteht also darin, für jeden Startwert unter einer Million die Anzahl verschiedener Knoten vor der ersten Wiederholung zu bestimmen.
Die zehn Ziffernfakultäten sind fest:
$$0!=1,\ 1!=1,\ 2!=2,\ 3!=6,\ 4!=24,\ 5!=120,\ 6!=720,\ 7!=5040,\ 8!=40320,\ 9!=362880.$$
Damit ist die Auswertung von \(F(n)\) nur noch eine Dezimalzerlegung mit anschließendem Tabellenzugriff. Nullen sind wichtig: Jede Nullziffer trägt \(0!=1\) bei. Darum springt \(363600\) auf \(1454\) und nicht auf einen kleineren Wert.
Für \(1 \le n < 10^6\) hat \(n\) höchstens sechs Ziffern, also gilt für das erste Bild
$$F(n)\le 6\cdot 9! = 2{,}177{,}280.$$
Danach hat jeder weitere Term höchstens sieben Ziffern, also gilt für alle späteren Bilder
$$F(a_k)\le 7\cdot 9! = 2{,}540{,}160 \qquad (k\ge 1).$$
Jede Kette mit Start unter einer Million tritt also sofort in die endliche Menge \(\{1,2,\dots,2{,}540{,}160\}\) ein und verlässt sie nie wieder. Ein deterministischer Weg in einer endlichen Menge muss irgendwann einen Wert erneut treffen, daher besitzt jede Kette einen wohldefinierten Schwanz und einen wohldefinierten Zyklus.
Für einen Startwert \(n\) schreiben wir
$$a_0=n,\qquad a_{k+1}=F(a_k).$$
Die verlangte Kettenlänge ist die Zahl der verschiedenen Werte vor der ersten Wiederholung:
$$\ell(n)=\min\{t\ge 1 : a_t \in \{a_0,a_1,\dots,a_{t-1}\}\}.$$
Angenommen, eine frische Suche sieht die paarweise verschiedenen Werte \(a_0,a_1,\dots,a_{t-1}\) und stellt dann fest, dass der nächste Wert gleich \(a_r\) mit \(0\le r<t\) ist. Dann bilden \(a_r,a_{r+1},\dots,a_{t-1}\) einen Zyklus der Länge
$$c=t-r.$$
Jeder Punkt auf diesem Zyklus besitzt genau \(c\) nicht wiederholte Terme vor sich; jeder Punkt im Schwanz muss den verbleibenden Schwanz plus den ganzen Zyklus durchlaufen. Also gilt
$$\ell(a_i)=c \quad (r\le i<t),\qquad \ell(a_i)=c+r-i \quad (0\le i<r).$$
Genau diese Formeln tragen die Implementierungen in die Memo-Tabelle ein, wenn ein neuer Zyklus gefunden wird.
Oft entdeckt eine neue Suche keinen völlig neuen Zyklus, sondern erreicht einen Wert, dessen Kettenlänge bereits früher berechnet wurde. Wenn der erste bekannte Wert \(a_t=m\) ist und \(\ell(m)\) schon gespeichert wurde, dann ist der aktuelle Pfad \(a_0,\dots,a_{t-1}\) weiterhin wiederholungsfrei; sonst wäre die Suche früher beendet worden. Daher addiert jeder frühere Punkt einfach einen zusätzlichen Schritt:
$$\ell(a_i)=\ell(m)+t-i \qquad (0\le i<t).$$
Diese Rekurrenz ist die entscheidende Optimierung. Viele Startwerte laufen in denselben Suffix, und sobald dieser einmal gelöst ist, kann jede spätere Kette dort sofort anhalten.
Für \(69\) lautet die Kette
$$69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454.$$
Der unterschiedliche Abschnitt ist also \((69,363600,1454,169,363601)\), und der nächste Wert wiederholt den Eintrag an Position \(r=2\). Damit sind \(t=5\), die Zykluslänge \(c=3\), und die Formeln liefern
$$\ell(1454)=3,\qquad \ell(363600)=4,\qquad \ell(69)=5.$$
Ein zweiter nützlicher Prüfpunkt ist
$$78 \to 45360 \to 871 \to 45361 \to 871.$$
Hier beginnt die Wiederholung bei \(r=2\) mit \(t=4\), also ist \(c=2\). Damit folgt
$$\ell(871)=2,\qquad \ell(45360)=3,\qquad \ell(78)=4.$$
Diese beiden Beispiele zeigen die beiden Bausteine der Methode: erst den Zyklusanfang bestimmen, dann die exakten Längen rückwärts durch den Schwanz propagieren.
Die Implementierungen in C++, Python und Java speichern zunächst die zehn Werte \(0!,1!,\dots,9!\). Dadurch wird jede Auswertung von \(F\) zu einer kurzen Ziffernschleife mit konstantem Tabellenzugriff statt zu wiederholten Fakultätsrechnungen.
Für eine einzelne Kette hält die Implementierung zwei temporäre Strukturen: eine geordnete Liste der neu besuchten Werte und eine Hash-Struktur, die speichert, an welcher Position jeder dieser Werte zuerst erschien. In jedem Schritt wird der nächste Wert berechnet und anschließend werden zwei mögliche Abbruchbedingungen geprüft.
Ist der neue Wert bereits memoisiert, dann läuft die Implementierung die geordnete Liste rückwärts durch und weist Längen mittels \(\ell(a_i)=\ell(m)+t-i\) zu. Ist der neue Wert bereits auf dem aktuellen Pfad erschienen, dann wird die Liste in Schwanz und Zyklus aufgeteilt, die Zyklusknoten erhalten die gemeinsame Zykluslänge und die Schwanzknoten erhalten beim Rückwärtsgehen jeweils um 1 wachsende Werte. In beiden Fällen ist danach sofort die Länge des ursprünglichen Startwerts bekannt.
Die äußere Schleife geht alle \(n\) mit \(1 \le n < 10^6\) durch, berechnet \(\ell(n)\) und erhöht die Antwort genau dann, wenn \(\ell(n)=60\) gilt. Weil die Memo-Tabelle während des gesamten Durchlaufs geteilt wird, brechen viele spätere Starts schon nach wenigen Schritten ab. Die C++- und Python-Implementierungen enthalten vor der vollständigen Suche außerdem kleine eingebaute Prüfpunkte für die Beispielwerte \(69 \mapsto 5\) und \(78 \mapsto 4\).
Sobald eine Kette den beschränkten Bereich erreicht hat, liest jede Auswertung von \(F\) höchstens sieben Ziffern; ein einzelner Übergang ist also praktisch \(O(1)\). Sei \(U\) die Zahl der tatsächlich entdeckten verschiedenen Werte beim Verarbeiten aller Starts unter einer Million. Da ein Wert nur bei seiner ersten vollständigen Auflösung wirklich expandiert wird, beträgt der Gesamtaufwand \(O(10^6 + U)\) Hash-Operationen beziehungsweise \(O((10^6+U)d)\) Ziffernoperationen mit \(d\le 7\).
Aus der obigen Schranke folgt \(U\le 2{,}540{,}160\), also ist der Algorithmus effektiv linear in einigen Millionen Zuständen. Der Speicherverbrauch beträgt \(O(U)\) für die memoisierten Kettenlängen plus temporären Speicher in Größe der aktuell untersuchten Kette.
Pozitif bir \(n\) tamsayısının onluk basamakları \(d_1,d_2,\dots,d_r\) olsun. Basamak-faktöriyel dönüşümünü
$$F(n)=\sum_{i=1}^{r} d_i!$$
şeklinde tanımlayalım. \(n\)'den başlayıp bu fonksiyonu tekrar tekrar uyguladığımızda oluşan dizi sonunda mutlaka tekrar eder; dolayısıyla her başlangıç değeri, önce birbirinden farklı sonlu bir liste üretir, sonra daha önce görülmüş bir değere geri döner. Soru, \(1 \le n < 10^6\) için zinciri tam olarak 60 tekrarsız terim içeren başlangıç sayılarını saymaktır.
Klasik örnek \(69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454\) zinciridir; burada farklı terim sayısı 5'tir. Uygulamalar bu zincirleri sonlu bir fonksiyonel graf üzerindeki yürüyüşler olarak ele alır ve tamamı çözülmüş her durum için geri kalan tam zincir uzunluğunu önbelleğe alır.
Buradaki temel nesne büyük bir arama ağacı değil, deterministik bir dönüşümdür: her tam sayının tam bir çıkışı vardır, o da \(n \mapsto F(n)\) geçişidir. Bu yüzden her yörünge aynı biçimdedir; önce bir kuyruk, sonra bir döngü gelir. Dolayısıyla esas iş, bir milyonun altındaki her başlangıç için ilk tekrar gelmeden önce kaç farklı düğüm görüldüğünü hesaplamaktır.
On basamak faktöriyeli sabittir:
$$0!=1,\ 1!=1,\ 2!=2,\ 3!=6,\ 4!=24,\ 5!=120,\ 6!=720,\ 7!=5040,\ 8!=40320,\ 9!=362880.$$
Böylece \(F(n)\) hesaplamak yalnızca basamakları ayırıp bu tabloya bakmaktır. Sıfırlar önemlidir: her sıfır basamağı \(0!=1\) katkısı yapar. Bu yüzden \(363600\) değeri daha küçük bir sayıya değil, \(1454\)'e gider.
\(1 \le n < 10^6\) için \(n\) en fazla altı basamaklıdır; dolayısıyla ilk görüntü için
$$F(n)\le 6\cdot 9! = 2{,}177{,}280$$
elde edilir. Bundan sonraki her terim en fazla yedi basamaklı olduğundan, sonraki tüm görüntüler için
$$F(a_k)\le 7\cdot 9! = 2{,}540{,}160 \qquad (k\ge 1)$$
geçerlidir. Yani bir milyonun altındaki her başlangıç zinciri anında \(\{1,2,\dots,2{,}540{,}160\}\) sonlu kümesine girer ve artık dışına çıkmaz. Sonlu bir küme içindeki deterministik yürüyüş mutlaka bir değeri yeniden ziyaret eder; bu da her zincirin iyi tanımlı bir kuyruğu ve döngüsü olduğu anlamına gelir.
Bir başlangıç değeri \(n\) için
$$a_0=n,\qquad a_{k+1}=F(a_k)$$
yazalım. Soruda istenen zincir uzunluğu, ilk tekrar öncesindeki farklı değer sayısıdır:
$$\ell(n)=\min\{t\ge 1 : a_t \in \{a_0,a_1,\dots,a_{t-1}\}\}.$$
Diyelim ki yeni bir arama \(a_0,a_1,\dots,a_{t-1}\) farklı değerlerini görüyor ve sonra sonraki değerin \(a_r\) ile aynı olduğunu fark ediyor; burada \(0\le r<t\). O zaman \(a_r,a_{r+1},\dots,a_{t-1}\) uzunluğu
$$c=t-r$$
olan bir döngü oluşturur. Döngü üzerindeki her noktanın önünde tam \(c\) tekrarsız terim vardır; kuyruğun üzerindeki her nokta ise kalan kuyruğu ve tüm döngüyü geçmek zorundadır. Bu yüzden
$$\ell(a_i)=c \quad (r\le i<t),\qquad \ell(a_i)=c+r-i \quad (0\le i<r)$$
olur. Yeni bir döngü bulunduğunda uygulamaların önbelleğe yazdığı tam formül budur.
Çoğu zaman yeni bir arama yepyeni bir döngü bulmaz; bunun yerine uzunluğu daha önce hesaplanmış bir değere ulaşır. İlk bilinen değer \(a_t=m\) ve \(\ell(m)\) önceden saklanmışsa, mevcut yol \(a_0,\dots,a_{t-1}\) hâlâ tekrarsızdır; aksi halde arama daha önce biterdi. O hâlde önceki her nokta yalnızca bir ek adım daha taşır:
$$\ell(a_i)=\ell(m)+t-i \qquad (0\le i<t).$$
Asıl hız kazancı buradan gelir. Pek çok başlangıç aynı devam zincirine akar; o devam bir kez çözüldükten sonra sonraki zincirler oraya ulaşınca hemen durabilir.
\(69\) için zincir
$$69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454$$
şeklindedir. Farklı bölüm \((69,363600,1454,169,363601)\) olur ve sonraki değer \(r=2\) konumundaki girdiyi tekrarlar. Demek ki \(t=5\), döngü uzunluğu \(c=3\), dolayısıyla
$$\ell(1454)=3,\qquad \ell(363600)=4,\qquad \ell(69)=5.$$
İkinci yararlı kontrol örneği ise
$$78 \to 45360 \to 871 \to 45361 \to 871$$
zinciridir. Burada tekrar \(r=2\) noktasında ve \(t=4\) ile başlar; yani \(c=2\). Sonuç olarak
$$\ell(871)=2,\qquad \ell(45360)=3,\qquad \ell(78)=4.$$
Bu iki örnek yöntemin iki bileşenini açıkça gösterir: önce döngünün başladığı yeri bul, sonra tam uzunlukları kuyruk boyunca geriye doğru yay.
C++, Python ve Java uygulamalarının üçü de önce \(0!,1!,\dots,9!\) değerlerini saklar. Böylece \(F\)'nin her uygulanışı, tekrar tekrar faktöriyel almak yerine kısa bir basamak döngüsüne ve sabit zamanlı tablo erişimine dönüşür.
Tek bir zinciri değerlendirirken uygulama iki geçici yapı tutar: yeni ziyaret edilmiş değerlerin sıralı listesi ve bu değerlerin ilk kez hangi konumda görüldüğünü kaydeden bir hash yapısı. Her adımda yeni değer hesaplanır ve iki farklı bitiş koşulu kontrol edilir.
Eğer yeni değer zaten önbellekteyse, uygulama sıralı liste üzerinde geriye doğru yürür ve \(\ell(a_i)=\ell(m)+t-i\) formülüyle uzunlukları atar. Eğer yeni değer mevcut yol üzerinde daha önce görülmüşse, liste kuyruk ve döngü olarak ayrılır; döngü düğümlerine ortak döngü uzunluğu yazılır, kuyruk düğümlerine ise geriye gidildikçe birer artan değerler atanır. Her iki durumda da başlangıç sayısının uzunluğu hemen belirlenmiş olur.
Dış döngü \(1 \le n < 10^6\) aralığındaki tüm başlangıçları gezer, \(\ell(n)\) değerini ister ve yalnızca \(\ell(n)=60\) olduğunda cevabı artırır. Ön bellek tüm tarama boyunca paylaşıldığı için sonraki birçok başlangıç birkaç adım sonra durur. C++ ve Python uygulamaları tam sayımı başlatmadan önce \(69 \mapsto 5\) ve \(78 \mapsto 4\) örnekleri için küçük yerleşik kontroller de yapar.
Zincir sınırlı bölgeye girdikten sonra \(F\)'nin her uygulanışı en fazla yedi basamak okur; dolayısıyla tek bir geçiş pratikte \(O(1)\) maliyetlidir. \(U\), bir milyon altındaki tüm başlangıçlar işlenirken gerçekten keşfedilen farklı durum sayısı olsun. Bir durum yalnızca ilk kez tamamen çözüldüğünde genişletildiği için toplam iş \(O(10^6 + U)\) hash işlemi, ya da \(d\le 7\) olmak üzere \(O((10^6+U)d)\) basamak işlemi olur.
Yukarıdaki sınır \(U\le 2{,}540{,}160\) verdiğinden algoritma fiilen birkaç milyon durum üzerinde doğrusal çalışır. Bellek kullanımı, önbelleğe alınan zincir uzunlukları için \(O(U)\), ayrıca o anda incelenen zincirin uzunluğu kadar geçici depolamadır.
Sea \(n\) un entero positivo con cifras decimales \(d_1,d_2,\dots,d_r\). Definimos la aplicación factorial de dígitos por
$$F(n)=\sum_{i=1}^{r} d_i!.$$
Partiendo de \(n\), aplicamos \(F\) repetidamente. La sucesión resultante acaba repitiéndose, de modo que cada valor inicial produce primero una lista finita de términos distintos y después vuelve a un valor ya visto. La pregunta es cuántos valores iniciales con \(1 \le n < 10^6\) generan una cadena con exactamente 60 términos no repetidos.
El ejemplo clásico es \(69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454\), así que la parte distinta tiene longitud 5. Las implementaciones resuelven el recuento total tratando estas cadenas como recorridos en un grafo funcional finito y memorizando la longitud exacta que queda desde cada estado ya resuelto.
El objeto central no es un gran árbol de búsqueda, sino una aplicación determinista: cada entero tiene exactamente una arista saliente, la transición \(n \mapsto F(n)\). Por eso toda trayectoria tiene la misma forma: una cola que desemboca en un ciclo. Así, el problema consiste en calcular, para cada inicio menor que un millón, cuántos vértices distintos aparecen antes de la primera repetición.
Los diez factoriales de las cifras son constantes:
$$0!=1,\ 1!=1,\ 2!=2,\ 3!=6,\ 4!=24,\ 5!=120,\ 6!=720,\ 7!=5040,\ 8!=40320,\ 9!=362880.$$
Por tanto, evaluar \(F(n)\) es solo extraer cifras decimales y consultar una tabla. Los ceros importan: cada cifra 0 aporta \(0!=1\). Por eso \(363600\) salta a \(1454\) en lugar de ir a un valor menor.
Si \(1 \le n < 10^6\), entonces \(n\) tiene como máximo seis cifras, y su primera imagen cumple
$$F(n)\le 6\cdot 9! = 2{,}177{,}280.$$
Después de eso, cada término tiene como mucho siete cifras, así que toda imagen posterior satisface
$$F(a_k)\le 7\cdot 9! = 2{,}540{,}160 \qquad (k\ge 1).$$
En consecuencia, toda cadena que empieza por debajo de un millón entra inmediatamente en el conjunto finito \(\{1,2,\dots,2{,}540{,}160\}\) y nunca sale de él. Un recorrido determinista dentro de un conjunto finito debe revisitar algún valor, así que cada cadena tiene una cola y un ciclo bien definidos.
Para un valor inicial \(n\), escribimos
$$a_0=n,\qquad a_{k+1}=F(a_k).$$
La longitud de cadena pedida por el problema es el número de valores distintos antes de la primera repetición:
$$\ell(n)=\min\{t\ge 1 : a_t \in \{a_0,a_1,\dots,a_{t-1}\}\}.$$
Supongamos que una exploración nueva ve valores distintos \(a_0,a_1,\dots,a_{t-1}\) y luego descubre que el siguiente valor coincide con \(a_r\), con \(0\le r<t\). Entonces \(a_r,a_{r+1},\dots,a_{t-1}\) forman un ciclo de longitud
$$c=t-r.$$
Cada punto que ya está dentro del ciclo tiene exactamente \(c\) términos no repetidos por delante; cada punto de la cola debe recorrer la cola restante más el ciclo completo. Por eso
$$\ell(a_i)=c \quad (r\le i<t),\qquad \ell(a_i)=c+r-i \quad (0\le i<r).$$
Estas son exactamente las fórmulas que las implementaciones escriben en la tabla de memoización cuando descubren un ciclo nuevo.
Con frecuencia una exploración nueva no descubre un ciclo completamente nuevo, sino que alcanza un valor cuya longitud ya fue calculada antes. Si el primer valor conocido es \(a_t=m\) y \(\ell(m)\) ya está almacenada, entonces el camino actual \(a_0,\dots,a_{t-1}\) sigue libre de repeticiones; de lo contrario, la búsqueda habría terminado antes. Así, cada punto anterior añade simplemente un paso más:
$$\ell(a_i)=\ell(m)+t-i \qquad (0\le i<t).$$
Esa recurrencia es la optimización decisiva. Muchos valores iniciales desembocan en el mismo sufijo, y una vez resuelto ese sufijo, las cadenas posteriores pueden detenerse en cuanto lo alcanzan.
Para \(69\), la cadena es
$$69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454.$$
La parte distinta es \((69,363600,1454,169,363601)\), y el siguiente valor repite la entrada en la posición \(r=2\). Por tanto \(t=5\), la longitud del ciclo es \(c=3\), y las fórmulas dan
$$\ell(1454)=3,\qquad \ell(363600)=4,\qquad \ell(69)=5.$$
Un segundo punto de control útil es
$$78 \to 45360 \to 871 \to 45361 \to 871.$$
Aquí la repetición empieza en \(r=2\) con \(t=4\), de modo que \(c=2\). En consecuencia,
$$\ell(871)=2,\qquad \ell(45360)=3,\qquad \ell(78)=4.$$
Estos dos ejemplos muestran con claridad los dos pasos del método: localizar el comienzo del ciclo y propagar después las longitudes exactas hacia atrás por la cola.
Las implementaciones en C++, Python y Java empiezan guardando los diez valores \(0!,1!,\dots,9!\). Así, cada aplicación de \(F\) se convierte en un bucle corto sobre las cifras con accesos a tabla en tiempo constante, en lugar de recalcular factoriales una y otra vez.
Para evaluar una cadena concreta, la implementación mantiene dos estructuras temporales: una lista ordenada de los valores nuevos visitados durante la exploración y una estructura hash que registra en qué posición apareció cada uno por primera vez. En cada paso se calcula el siguiente valor y se comprueban dos condiciones de terminación posibles.
Si el valor nuevo ya tiene longitud memorizada, la implementación recorre la lista ordenada hacia atrás y asigna longitudes usando \(\ell(a_i)=\ell(m)+t-i\). Si el valor nuevo ya apareció en el camino actual, la lista se divide en cola y ciclo, los nodos del ciclo reciben la longitud común del ciclo y los nodos de la cola reciben valores crecientes al retroceder. En ambos casos, la longitud del inicio original queda determinada de inmediato.
El bucle exterior recorre todos los \(n\) con \(1 \le n < 10^6\), calcula \(\ell(n)\) e incrementa la respuesta exactamente cuando \(\ell(n)=60\). Como la tabla de memoización se comparte durante todo el barrido, muchos valores posteriores terminan tras muy pocos pasos. Las implementaciones en C++ y Python también incluyen pequeñas comprobaciones internas con las longitudes de ejemplo \(69 \mapsto 5\) y \(78 \mapsto 4\) antes del conteo completo.
Una vez que la cadena entra en la región acotada, cada evaluación de \(F\) lee como mucho siete cifras, así que una transición individual es \(O(1)\) en la práctica. Sea \(U\) el número de valores distintos que realmente se descubren al procesar todos los inicios menores que un millón. Como cada valor solo se expande por completo la primera vez que queda resuelto, el trabajo total es \(O(10^6 + U)\) operaciones de tabla hash, o \(O((10^6+U)d)\) operaciones sobre cifras con \(d\le 7\).
La cota anterior da \(U\le 2{,}540{,}160\), así que el algoritmo es esencialmente lineal en unos pocos millones de estados. El uso de memoria es \(O(U)\) para las longitudes memorizadas, más almacenamiento temporal proporcional a la longitud de la cadena que se está explorando en ese momento.
设正整数 \(n\) 的十进制数字为 \(d_1,d_2,\dots,d_r\)，定义数字阶乘映射
$$F(n)=\sum_{i=1}^{r} d_i!.$$
从 \(n\) 出发不断迭代 \(F\)，最终得到的序列一定会重复，因此每个起点都会先经过一段有限的、互不相同的值，然后回到某个先前出现过的值。题目要求统计满足 \(1 \le n < 10^6\) 且链中恰好有 60 个不重复项的起始值个数。
经典例子是 \(69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454\)，所以它的不重复部分长度为 5。三种实现的核心都不是暴力枚举所有轨迹，而是把这些链看成一个有限函数图中的路径，并把每个已经完全求解过的状态的剩余链长缓存下来。
这里的核心对象不是一棵庞大的搜索树，而是一个确定性的映射：每个整数只有一条出边，也就是 \(n \mapsto F(n)\)。因此每条轨迹都具有相同的结构，先是一段尾部，然后进入一个环。问题于是变成：对于每个小于一百万的起点，第一次重复出现之前一共会访问多少个不同的节点。
十个数字的阶乘值是固定的：
$$0!=1,\ 1!=1,\ 2!=2,\ 3!=6,\ 4!=24,\ 5!=120,\ 6!=720,\ 7!=5040,\ 8!=40320,\ 9!=362880.$$
因此计算 \(F(n)\) 只需要拆出十进制数字并查表。数字 0 不能忽略，因为每个 0 都贡献 \(0!=1\)。这正是为什么 \(363600\) 会跳到 \(1454\)，而不是落到一个更小的值。
若 \(1 \le n < 10^6\)，那么 \(n\) 最多只有六位，所以第一次映像满足
$$F(n)\le 6\cdot 9! = 2{,}177{,}280.$$
之后的每一项都至多有七位，因此后续所有映像都满足
$$F(a_k)\le 7\cdot 9! = 2{,}540{,}160 \qquad (k\ge 1).$$
也就是说，所有小于一百万的起点在第一步之后就进入了有限集合 \(\{1,2,\dots,2{,}540{,}160\}\)，而且之后不会离开。有限集合中的确定性迭代必然会再次遇到某个旧值，所以每条链都必然可以分解为“尾部 + 环”。
对起点 \(n\)，记
$$a_0=n,\qquad a_{k+1}=F(a_k).$$
题目要求的链长，就是第一次发生重复之前出现的不同值个数：
$$\ell(n)=\min\{t\ge 1 : a_t \in \{a_0,a_1,\dots,a_{t-1}\}\}.$$
设一次全新的搜索看到了互不相同的 \(a_0,a_1,\dots,a_{t-1}\)，接着发现下一项恰好等于某个 \(a_r\)，其中 \(0\le r<t\)。那么 \(a_r,a_{r+1},\dots,a_{t-1}\) 就构成了一个长度为
$$c=t-r$$
的环。环上的每个点从自身出发都会在走完这 \(c\) 个不同状态后第一次重复；而尾部上的每个点则必须先走完剩余尾部，再走完整个环。所以有
$$\ell(a_i)=c \quad (r\le i<t),\qquad \ell(a_i)=c+r-i \quad (0\le i<r).$$
一旦发现了一个新环，程序写入缓存的正是这组公式。
很多时候，新的搜索并不会遇到一个全新的环，而是先走到一个以前已经算出链长的值。若第一次遇到的已知值是 \(a_t=m\)，并且 \(\ell(m)\) 已经缓存，那么当前路径 \(a_0,\dots,a_{t-1}\) 仍然没有重复；否则搜索会更早结束。于是前面的每个点都只是在 \(\ell(m)\) 的基础上再多走若干步：
$$\ell(a_i)=\ell(m)+t-i \qquad (0\le i<t).$$
这就是速度提升的关键。许多不同的起点最终会流入同一个后缀，而这个后缀只要解过一次，后面的链一旦碰到它就可以立刻停止扩展。
对 \(69\)，链为
$$69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454.$$
因此不同部分是 \((69,363600,1454,169,363601)\)，下一项重复了位置 \(r=2\) 的值。于是 \(t=5\)，环长 \(c=3\)，从公式得到
$$\ell(1454)=3,\qquad \ell(363600)=4,\qquad \ell(69)=5.$$
另一个很有用的检查例子是
$$78 \to 45360 \to 871 \to 45361 \to 871.$$
这里重复从 \(r=2\) 开始，且 \(t=4\)，所以 \(c=2\)。因此
$$\ell(871)=2,\qquad \ell(45360)=3,\qquad \ell(78)=4.$$
这两个例子把方法的两步都展示得很清楚：先定位环的起点，再沿着尾部向后回填精确长度。
C++、Python 和 Java 实现都会先保存 \(0!,1!,\dots,9!\) 这十个值。这样每次计算 \(F\) 时，只需做一次很短的拆位循环和常数时间查表，而不用反复求阶乘。
在处理某个起点时，实现会维护两种临时信息：一份按访问顺序记录的新状态列表，以及一份记录这些状态第一次出现位置的哈希结构。每走一步，程序先计算下一个值，然后检查两种可能的终止情况。
如果新值已经有缓存好的链长，那么程序就沿着当前列表逆序回填，使用 \(\ell(a_i)=\ell(m)+t-i\) 给出每个状态的长度。如果新值已经在当前路径中出现过，那么列表就被分成尾部和环，环上的状态统一写入环长，尾部上的状态则在逆序回填时逐个加一。无论哪种情况，原始起点的链长都会立刻得到。
外层循环遍历所有满足 \(1 \le n < 10^6\) 的起点，求出 \(\ell(n)\)，并在 \(\ell(n)=60\) 时把答案加一。由于缓存表在整个扫描过程中共享，后面的很多起点只需走很少几步就会撞上已经求解过的后缀。C++ 和 Python 实现还会在完整统计之前，先做 \(69 \mapsto 5\) 与 \(78 \mapsto 4\) 这两个内置检查。
链一旦进入有界区域，每次计算 \(F\) 最多只需要读取七个数字，因此单次转移在实践中就是 \(O(1)\)。设 \(U\) 为处理所有小于一百万的起点时真正发现的不同状态数。由于每个状态只会在第一次被彻底求解时展开一次，总工作量是 \(O(10^6 + U)\) 次哈希操作，或者写成按数字处理的形式是 \(O((10^6+U)d)\)，其中 \(d\le 7\)。
上面的界给出 \(U\le 2{,}540{,}160\)，所以算法本质上是在几百万个状态上线性运行。内存复杂度为 \(O(U)\)，用于存储缓存好的链长，再加上与当前探索链长度成正比的临时存储。
Пусть десятичные цифры положительного числа \(n\) равны \(d_1,d_2,\dots,d_r\). Определим отображение суммы факториалов цифр формулой
$$F(n)=\sum_{i=1}^{r} d_i!.$$
Начиная с \(n\), мы многократно применяем \(F\). Полученная последовательность в конце концов обязана повториться, поэтому каждый старт сначала дает конечный список различных значений, а затем возвращается к уже встреченному значению. Нужно посчитать, сколько стартовых значений \(n\) с \(1 \le n < 10^6\) имеют цепочку ровно из 60 неповторяющихся членов.
Классический пример: \(69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454\); значит, длина различной части равна 5. Реализации решают полную задачу, рассматривая такие цепочки как обходы конечного функционального графа и запоминая точную оставшуюся длину для каждого уже полностью разобранного состояния.
Главный объект здесь не большое дерево перебора, а детерминированное отображение: у каждого целого числа есть ровно одно исходящее ребро, а именно переход \(n \mapsto F(n)\). Поэтому любая траектория имеет одну и ту же форму: сначала хвост, затем цикл. Значит, задача сводится к тому, чтобы для каждого старта меньше миллиона определить, сколько различных вершин будет посещено до первого повтора.
Десять факториалов цифр фиксированы:
$$0!=1,\ 1!=1,\ 2!=2,\ 3!=6,\ 4!=24,\ 5!=120,\ 6!=720,\ 7!=5040,\ 8!=40320,\ 9!=362880.$$
Поэтому вычисление \(F(n)\) сводится к извлечению десятичных цифр и просмотру таблицы. Нули принципиально важны: каждая цифра 0 дает вклад \(0!=1\). Именно поэтому \(363600\) переходит в \(1454\), а не в меньшее число.
Если \(1 \le n < 10^6\), то у \(n\) не более шести цифр, значит, для первого образа имеем
$$F(n)\le 6\cdot 9! = 2{,}177{,}280.$$
После этого каждый член имеет не более семи цифр, так что для всех последующих образов выполняется
$$F(a_k)\le 7\cdot 9! = 2{,}540{,}160 \qquad (k\ge 1).$$
Следовательно, каждая цепочка со стартом меньше миллиона уже после первого шага входит в конечное множество \(\{1,2,\dots,2{,}540{,}160\}\) и больше его не покидает. Детерминированное движение внутри конечного множества неизбежно приводит к повтору, а значит, у каждой цепочки существует корректное разложение на хвост и цикл.
Для стартового значения \(n\) положим
$$a_0=n,\qquad a_{k+1}=F(a_k).$$
Искомая длина цепочки — это число различных значений до первого повторения:
$$\ell(n)=\min\{t\ge 1 : a_t \in \{a_0,a_1,\dots,a_{t-1}\}\}.$$
Пусть при новой поисковой прогулке встретились попарно различные значения \(a_0,a_1,\dots,a_{t-1}\), а затем оказалось, что следующее значение совпадает с \(a_r\), где \(0\le r<t\). Тогда \(a_r,a_{r+1},\dots,a_{t-1}\) образуют цикл длины
$$c=t-r.$$
Каждая точка внутри цикла имеет ровно \(c\) неповторяющихся состояний до первого возврата, а каждая точка хвоста должна пройти остаток хвоста и весь цикл. Поэтому
$$\ell(a_i)=c \quad (r\le i<t),\qquad \ell(a_i)=c+r-i \quad (0\le i<r).$$
Именно эти формулы реализации записывают в таблицу мемоизации, когда обнаруживают новый цикл.
Нередко новая цепочка не открывает совершенно новый цикл, а приходит в значение, длина которого уже была вычислена раньше. Если первым известным значением является \(a_t=m\), а \(\ell(m)\) уже сохранено, то текущий путь \(a_0,\dots,a_{t-1}\) все еще не содержит повторов; иначе процесс остановился бы раньше. Поэтому для всех предыдущих вершин длины выражаются простой формулой
$$\ell(a_i)=\ell(m)+t-i \qquad (0\le i<t).$$
Это и есть главный источник ускорения. Очень многие стартовые значения сливаются в один и тот же хвост или цикл, и после первого решения этого суффикса все последующие проходы могут остановиться сразу при встрече с ним.
Для \(69\) получаем цепочку
$$69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454.$$
Различная часть здесь равна \((69,363600,1454,169,363601)\), а следующий член повторяет запись с индексом \(r=2\). Значит, \(t=5\), длина цикла \(c=3\), и формулы дают
$$\ell(1454)=3,\qquad \ell(363600)=4,\qquad \ell(69)=5.$$
Второй полезный контрольный пример таков:
$$78 \to 45360 \to 871 \to 45361 \to 871.$$
Здесь повтор начинается при \(r=2\), а \(t=4\), поэтому \(c=2\). Следовательно,
$$\ell(871)=2,\qquad \ell(45360)=3,\qquad \ell(78)=4.$$
Эти два примера наглядно показывают обе части метода: сначала найти место входа в цикл, затем распространить точные длины назад по хвосту.
Реализации на C++, Python и Java сначала сохраняют десять значений \(0!,1!,\dots,9!\). Благодаря этому каждое применение \(F\) превращается в короткий цикл по цифрам с доступом к таблице за константное время, а не в повторные вычисления факториалов.
Для одной цепочки реализация держит две временные структуры: упорядоченный список новых значений, встретившихся на текущем пути, и хеш-структуру, которая хранит позицию первого появления каждого из этих значений. На каждом шаге вычисляется следующий член, после чего проверяются два возможных условия остановки.
Если новое значение уже имеет мемоизированную длину, программа идет по списку назад и назначает длины по формуле \(\ell(a_i)=\ell(m)+t-i\). Если новое значение уже встречалось на текущем пути, список делится на хвост и цикл: вершины цикла получают общую длину цикла, а вершины хвоста при обратном проходе получают возрастающие значения. В обоих случаях длина исходного старта становится известной сразу.
Внешний цикл перебирает все \(n\) с \(1 \le n < 10^6\), вычисляет \(\ell(n)\) и увеличивает ответ только тогда, когда \(\ell(n)=60\). Поскольку таблица мемоизации общая для всего прохода, многие поздние старты завершаются уже через несколько шагов. Реализации на C++ и Python также выполняют перед полным запуском встроенные проверки \(69 \mapsto 5\) и \(78 \mapsto 4\).
После входа цепочки в ограниченную область каждое вычисление \(F\) читает не более семи цифр, так что один переход на практике имеет стоимость \(O(1)\). Пусть \(U\) — число различных состояний, реально обнаруженных при обработке всех стартов меньше миллиона. Так как каждое состояние полностью раскрывается только при первом решении, общий объем работы равен \(O(10^6 + U)\) хеш-операций, или \(O((10^6+U)d)\) операций над цифрами при \(d\le 7\).
Полученная выше граница дает \(U\le 2{,}540{,}160\), поэтому алгоритм фактически линеен по нескольким миллионам состояний. Память составляет \(O(U)\) для сохраненных длин цепочек, плюс временные структуры размера текущей исследуемой цепочки.
إذا كانت الأرقام العشرية للعدد الصحيح الموجب \(n\) هي \(d_1,d_2,\dots,d_r\)، فنعرّف دالة مجموع مضاريب الأرقام بالصيغة
$$F(n)=\sum_{i=1}^{r} d_i!.$$
بدءًا من \(n\)، نكرر تطبيق \(F\). لا بد أن تتكرر السلسلة في النهاية، ولذلك فإن كل قيمة ابتدائية تعطي أولًا قائمة منتهية من القيم المختلفة ثم تعود إلى قيمة شوهدت من قبل. المطلوب هو عدد القيم الابتدائية التي تحقق \(1 \le n < 10^6\) ويكون طول سلسلتها غير المتكررة مساويًا تمامًا لـ 60.
المثال الأشهر هو \(69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454\)، ولذلك فطول الجزء غير المتكرر يساوي 5. تعتمد الحلول البرمجية على النظر إلى هذه السلاسل بوصفها مسارات في رسم بياني دالي منتهٍ، ثم حفظ الطول المتبقي بدقة لكل حالة جرى حلها بالكامل.
العنصر المركزي هنا ليس شجرة بحث ضخمة، بل دالة حتمية: لكل عدد صحيح سهم خارج واحد فقط هو الانتقال \(n \mapsto F(n)\). لهذا السبب تأخذ كل مسيرة الشكل نفسه: ذيل ينتهي بدورة. وعليه فإن جوهر المسألة هو حساب عدد العقد المختلفة التي تُزار قبل أول تكرار لكل بداية أقل من مليون.
قيم مضروب الأرقام العشرة ثابتة:
$$0!=1,\ 1!=1,\ 2!=2,\ 3!=6,\ 4!=24,\ 5!=120,\ 6!=720,\ 7!=5040,\ 8!=40320,\ 9!=362880.$$
لذلك فإن حساب \(F(n)\) لا يحتاج إلا إلى استخراج الأرقام العشرية ثم الرجوع إلى هذا الجدول. والأصفار مهمة جدًا، لأن كل رقم 0 يضيف \(0!=1\). ولهذا ينتقل \(363600\) إلى \(1454\) بدلًا من أن ينتقل إلى قيمة أصغر.
إذا كان \(1 \le n < 10^6\)، فإن \(n\) يملك على الأكثر ست خانات، ومن ثم تحقق الصورة الأولى
$$F(n)\le 6\cdot 9! = 2{,}177{,}280.$$
وبعد ذلك تصبح كل قيمة في السلسلة ذات سبع خانات على الأكثر، ولذلك تحقق كل صورة لاحقة
$$F(a_k)\le 7\cdot 9! = 2{,}540{,}160 \qquad (k\ge 1).$$
أي إن كل سلسلة تبدأ بأقل من مليون تدخل مباشرة المجموعة المنتهية \(\{1,2,\dots,2{,}540{,}160\}\) ولا تغادرها بعد ذلك. والمسار الحتمي داخل مجموعة منتهية لا بد أن يزور قيمة سابقة من جديد، ولذلك فلكل سلسلة ذيل ودورة محددان تحديدًا دقيقًا.
للقيمة الابتدائية \(n\) نكتب
$$a_0=n,\qquad a_{k+1}=F(a_k).$$
وطول السلسلة المطلوب في المسألة هو عدد القيم المختلفة قبل أول تكرار:
$$\ell(n)=\min\{t\ge 1 : a_t \in \{a_0,a_1,\dots,a_{t-1}\}\}.$$
افترض أن بحثًا جديدًا رأى القيم المختلفة \(a_0,a_1,\dots,a_{t-1}\)، ثم وجد أن القيمة التالية تساوي \(a_r\) حيث \(0\le r<t\). عندئذ تشكل القيم \(a_r,a_{r+1},\dots,a_{t-1}\) دورة طولها
$$c=t-r.$$
كل نقطة داخل الدورة تملك بالضبط \(c\) قيم غير متكررة قبل العودة، أما كل نقطة في الذيل فيلزمها أن تعبر بقية الذيل ثم الدورة كاملة. لذلك نحصل على
$$\ell(a_i)=c \quad (r\le i<t),\qquad \ell(a_i)=c+r-i \quad (0\le i<r).$$
وهذه هي الصيغ نفسها التي تكتبها التطبيقات في جدول الحفظ عندما تكتشف دورة جديدة.
كثيرًا ما لا يكتشف البحث الجديد دورة جديدة كليًا، بل يصل إلى قيمة سبق حساب طول سلسلتها. فإذا كانت أول قيمة معلومة هي \(a_t=m\) وكان \(\ell(m)\) محفوظًا من قبل، فإن المسار الحالي \(a_0,\dots,a_{t-1}\) ما زال خاليًا من التكرار، وإلا لتوقفت العملية في وقت أبكر. ومن ثم فإن كل نقطة سابقة تضيف خطوة واحدة إضافية فقط:
$$\ell(a_i)=\ell(m)+t-i \qquad (0\le i<t).$$
هذه العلاقة هي أساس التسريع. فعدد كبير من القيم الابتدائية ينتهي إلى اللاحقة نفسها، وما إن تُحل تلك اللاحقة مرة واحدة حتى تستطيع السلاسل اللاحقة التوقف فور وصولها إليها.
بالنسبة إلى \(69\)، تكون السلسلة
$$69 \to 363600 \to 1454 \to 169 \to 363601 \to 1454.$$
إذن الجزء المختلف هو \((69,363600,1454,169,363601)\)، والقيمة التالية تكرر العنصر عند الموضع \(r=2\). ولذلك يكون \(t=5\)، وطول الدورة \(c=3\)، فنحصل على
$$\ell(1454)=3,\qquad \ell(363600)=4,\qquad \ell(69)=5.$$
ومثال تحقق آخر مفيد هو
$$78 \to 45360 \to 871 \to 45361 \to 871.$$
هنا يبدأ التكرار عند \(r=2\) ومع \(t=4\)، وبالتالي \(c=2\). ومن ثم
$$\ell(871)=2,\qquad \ell(45360)=3,\qquad \ell(78)=4.$$
يوضح هذان المثالان جزأي الطريقة بوضوح: تحديد موضع بداية الدورة أولًا، ثم نشر الأطوال الدقيقة رجوعًا عبر الذيل.
تبدأ تطبيقات C++ وPython وJava بحفظ القيم \(0!,1!,\dots,9!\). وهكذا يتحول كل تطبيق للدالة \(F\) إلى حلقة قصيرة على الأرقام مع وصول ثابت الزمن إلى جدول، بدلًا من إعادة حساب المضاريب مرارًا.
عند معالجة سلسلة واحدة تحتفظ التنفيذات ببنيتين مؤقتتين: قائمة مرتبة للقيم الجديدة التي زارتها السلسلة في المسار الحالي، وبنية تجزئة تسجل الموضع الذي ظهرت فيه كل قيمة أول مرة. في كل خطوة تُحسب القيمة التالية ثم يُفحص شرطان محتملان للتوقف.
إذا كانت القيمة الجديدة تملك طولًا محفوظًا مسبقًا، فإن التنفيذ يعود على القائمة إلى الخلف ويكتب الأطوال وفق العلاقة \(\ell(a_i)=\ell(m)+t-i\). وإذا كانت القيمة الجديدة قد ظهرت من قبل داخل المسار الحالي نفسه، فإن القائمة تنقسم إلى ذيل ودورة؛ فتعطى عقد الدورة طول الدورة المشترك، وتعطى عقد الذيل أطوالًا تزداد بمقدار 1 عند الرجوع إلى الخلف. وفي الحالتين يصبح طول البداية الأصلية معروفًا فورًا.
تمر الحلقة الخارجية على جميع \(n\) التي تحقق \(1 \le n < 10^6\)، وتحسب \(\ell(n)\)، وتزيد الجواب عندما يكون \(\ell(n)=60\). وبما أن جدول الحفظ مشترك طوال المسح كله، فإن عددًا كبيرًا من البدايات اللاحقة يتوقف بعد خطوات قليلة فقط. كما تحتوي نسختا C++ وPython على اختبارات داخلية صغيرة للقيمتين \(69 \mapsto 5\) و\(78 \mapsto 4\) قبل تنفيذ العد الكامل.
بعد دخول السلسلة إلى المنطقة المحدودة، لا يقرأ كل حساب لـ \(F\) أكثر من سبع خانات، ولذلك تكون كلفة الانتقال الواحد \(O(1)\) عمليًا. ولتكن \(U\) عدد الحالات المختلفة التي تُكتشف فعلًا عند معالجة جميع البدايات الأقل من مليون. وبما أن كل حالة لا تُوسَّع بالكامل إلا عند حلها لأول مرة، فإن العمل الكلي يساوي \(O(10^6 + U)\) من عمليات التجزئة، أو \(O((10^6+U)d)\) من عمليات معالجة الخانات حيث \(d\le 7\).
وتعطي الحدود السابقة \(U\le 2{,}540{,}160\)، ولذلك يكون الخوارزم فعليًا خطيًا في بضعة ملايين من الحالات. أما الذاكرة فتكلفتها \(O(U)\) لتخزين أطوال السلاسل المحفوظة، بالإضافة إلى تخزين مؤقت بحجم السلسلة الجاري استكشافها.