Let \(s(n)\) be the sum of the proper divisors of \(n\):
$$s(n)=\sum_{\substack{d\mid n\\1\le d<n}} d.$$
Starting from \(a_0=n\), define an aliquot sequence by \(a_{k+1}=s(a_k)\). The problem asks for the smallest member of the longest cycle produced by this iteration, under the condition that every element of the cycle is at most \(10^6\). Thus we are searching the directed cycles of the map \(n\mapsto s(n)\) inside the bounded interval \([1,10^6]\).
A direct per-start factorization strategy would waste most of the work. The implementations instead precompute every value \(s(n)\) once, then analyze the resulting functional graph of outgoing edges.
Write \(N=10^6\) and \(f(n)=s(n)\). Each integer \(n\in[1,N]\) has exactly one successor \(f(n)\), although that successor may lie outside the interval. The full problem therefore becomes a cycle search in a directed graph with out-degree 1.
Every proper divisor \(d\) of \(m\) contributes exactly once to \(s(m)\). Instead of factoring each \(m\) separately, we distribute each possible divisor to all of its multiples. For a fixed \(d\), the affected numbers are \(2d,3d,\dots,\left\lfloor N/d\right\rfloor d\), so the sieve performs the updates
$$s(kd)\leftarrow s(kd)+d\qquad\text{for }k=2,3,\dots,\left\lfloor\frac{N}{d}\right\rfloor.$$
After all \(d\) have been processed, the array already contains the exact values of \(s(1),s(2),\dots,s(N)\). This is the real mathematical object used by the code: the aliquot map has been materialized as a lookup table.
The total number of updates is
$$\sum_{d=1}^{N}\left(\left\lfloor\frac{N}{d}\right\rfloor-1\right),$$
which is \(O(N\log N)\) by the harmonic-series estimate. That is dramatically smaller than refactoring every number from scratch, and it makes the later graph traversal cheap because each successor query becomes an \(O(1)\) array access.
Once the table is known, every start value generates a deterministic walk
$$n,\ f(n),\ f(f(n)),\ \dots.$$
For a walk that stays inside \([1,N]\), exactly one of the following eventually happens: the next value leaves the interval, the walk enters a region explored earlier, or the walk repeats a value already seen on the current path. The third case is the only one that produces a new bounded cycle.
This viewpoint matters because a graph with out-degree 1 cannot branch forward: from any starting value there is only one possible future. That is the invariant that makes the global marking step correct.
Suppose the current walk has recorded distinct in-range values
$$p_0,p_1,\dots,p_{m-1}.$$
If the next value is \(p_r\) for some \(r\), then the suffix
$$p_r,p_{r+1},\dots,p_{m-1}$$
is exactly the cycle. Its length is
$$\ell=m-r,$$
and the candidate answer from this cycle is
$$\min\{p_r,p_{r+1},\dots,p_{m-1}\}.$$
The prefix \(p_0,\dots,p_{r-1}\) is only a tail leading into that cycle. This is why the implementations keep, alongside the current path, a table recording the first position where each value on that path appeared.
After one walk stops, every in-range value on that walk can be marked as fully processed. The reason is structural: in a functional graph, starting again from any one of those values can only follow the same tail, reach the same cycle, leave the interval in the same way, or merge into a component that was already known. No new bounded cycle can be discovered through them.
That single invariant converts the second phase from repeated trial walks into an almost linear sweep: each in-range value is appended to an explicit path at most once before it becomes permanently classified.
A concrete example appears already at the smaller bound \(N=300\). The sieve gives
$$s(220)=1+2+4+5+10+11+20+22+44+55+110=284,$$
$$s(284)=1+2+4+71+142=220.$$
So the walk from 220 is
$$220\to 284\to 220.$$
The repeated value 220 first appeared at position 0, so the whole recorded path is the cycle. Its length is 2 and its smallest member is 220. This is exactly the kind of cycle extraction the implementations use at the full one-million bound as well.
The C++, Python, and Java implementations first build an array of proper-divisor sums for all values up to the limit. They then scan start values from 2 upward. If a start value has already been classified during an earlier walk, it is skipped immediately.
For each new start value, the implementation grows a current path and a position table for values on that path. The walk stops when the next value leaves \([1,N]\), reaches a globally processed value, or repeats inside the current path. In the repeat case, the repeated suffix yields one bounded cycle, from which the implementation computes the cycle length and its minimum member. The global best answer is updated by the rule: prefer the longer cycle, and on equal length prefer the smaller minimum element. After that, every value seen on the current path is marked as processed.
Self-loops, corresponding to perfect numbers, need no special branch in the implementation. They are simply cycles of length 1, and any longer cycle automatically beats them under the same update rule.
The sieve phase costs
$$\sum_{d=1}^{N}\left\lfloor\frac{N}{d}\right\rfloor=O(N\log N),$$
which dominates the running time. The path-following phase is \(O(N)\) after the sieve, because each in-range value is inserted into an explicit path at most once before it becomes globally processed. Therefore the overall time complexity is \(O(N\log N)\).
Memory usage is linear. The divisor-sum table and the global processed marker both require \(O(N)\) space, and the temporary path plus its position table are also bounded by \(O(N)\) in the worst case.
Sei \(s(n)\) die Summe der echten Teiler von \(n\):
$$s(n)=\sum_{\substack{d\mid n\\1\le d<n}} d.$$
Ausgehend von \(a_0=n\) definieren wir die Aliquot-Folge durch \(a_{k+1}=s(a_k)\). Gesucht ist das kleinste Element des längsten Zyklus dieser Iteration unter der Nebenbedingung, dass jedes Glied des Zyklus höchstens \(10^6\) ist. Wir suchen also in der Abbildung \(n\mapsto s(n)\) alle gerichteten Zyklen innerhalb des Intervalls \([1,10^6]\) und wählen den längsten aus.
Eine naive Strategie, für jeden Startwert immer wieder neu zu faktorisieren, würde denselben Aufwand ständig wiederholen. Die Implementierungen berechnen deshalb zunächst alle Werte \(s(n)\) in einem Zug und untersuchen danach den entstehenden funktionalen Graphen.
Schreibe \(N=10^6\) und \(f(n)=s(n)\). Jede Zahl \(n\in[1,N]\) besitzt genau einen Nachfolger \(f(n)\), auch wenn dieser Nachfolger außerhalb des Intervalls liegen kann. Damit wird das Problem zu einer Zyklensuche in einem gerichteten Graphen mit Ausgrad 1.
Jeder echte Teiler \(d\) von \(m\) trägt genau einmal zu \(s(m)\) bei. Anstatt jede Zahl einzeln zu faktorisieren, verteilt man jeden möglichen Teiler auf alle seine Vielfachen. Für festes \(d\) sind die betroffenen Zahlen \(2d,3d,\dots,\left\lfloor N/d\right\rfloor d\), also führt das Sieb die Aktualisierungen
$$s(kd)\leftarrow s(kd)+d\qquad\text{für }k=2,3,\dots,\left\lfloor\frac{N}{d}\right\rfloor$$
aus. Danach enthält das Feld bereits die exakten Werte von \(s(1),s(2),\dots,s(N)\). Genau dieses Objekt benutzt der Code später: die Aliquot-Abbildung liegt als direkter Nachschlagetisch vor.
Die Gesamtzahl der Updates ist
$$\sum_{d=1}^{N}\left(\left\lfloor\frac{N}{d}\right\rfloor-1\right),$$
also nach der harmonischen Abschätzung \(O(N\log N)\). Das ist wesentlich billiger, als jede Zahl separat zu zerlegen, und macht die spätere Graphenphase effizient, weil jeder Nachfolgerzugriff nur noch ein Array-Lookup ist.
Sobald die Tabelle feststeht, erzeugt jeder Startwert einen deterministischen Weg
$$n,\ f(n),\ f(f(n)),\ \dots.$$
Für einen Weg, der zunächst innerhalb von \([1,N]\) bleibt, tritt zwangsläufig einer von drei Fällen ein: Der nächste Wert verlässt das Intervall, der Weg läuft in einen bereits früher vollständig untersuchten Bereich, oder der Weg wiederholt einen Wert, der schon auf dem aktuellen Pfad lag. Nur der dritte Fall liefert einen neuen beschränkten Zyklus.
Gerade hier ist der Ausgrad-1-Charakter entscheidend. Nach vorn kann ein solcher Graph nicht verzweigen; von jedem Start aus gibt es genau eine Zukunft. Darauf beruht die Korrektheit des globalen Markierens.
Angenommen, der aktuelle Weg hat die paarweise verschiedenen Werte
$$p_0,p_1,\dots,p_{m-1}$$
gespeichert. Ist der nächste Wert gleich \(p_r\), dann ist der Suffix
$$p_r,p_{r+1},\dots,p_{m-1}$$
genau der Zyklus. Seine Länge ist
$$\ell=m-r,$$
und der Kandidat für die gesuchte Ausgabe ist
$$\min\{p_r,p_{r+1},\dots,p_{m-1}\}.$$
Das Präfix \(p_0,\dots,p_{r-1}\) ist nur ein Einlauf in diesen Zyklus. Deshalb halten die Implementierungen neben dem aktuellen Pfad auch eine Tabelle vor, die die erste Position jedes auf diesem Pfad gesehenen Wertes speichert.
Nachdem ein Weg beendet wurde, dürfen alle darin auftretenden In-Range-Werte dauerhaft als verarbeitet markiert werden. Der strukturelle Grund ist einfach: Startet man später noch einmal bei einem solchen Wert, dann folgt man nur demselben Schwanz, erreicht denselben Zyklus, verlässt das Intervall an derselben Stelle oder mündet in eine bereits bekannte Komponente. Ein neuer beschränkter Zyklus kann dort nicht mehr versteckt sein.
Diese Invariante macht die zweite Phase fast linear: Jeder In-Range-Wert wird höchstens einmal explizit an einen Pfad angehängt, bevor er endgültig klassifiziert ist.
Schon für die kleinere Schranke \(N=300\) sieht man das Verfahren klar. Das Sieb liefert
$$s(220)=1+2+4+5+10+11+20+22+44+55+110=284,$$
$$s(284)=1+2+4+71+142=220.$$
Damit lautet der Weg ab 220
$$220\to 284\to 220.$$
Der wiederholte Wert 220 erschien zuerst an Position 0, also ist der gesamte aufgezeichnete Pfad bereits der Zyklus. Seine Länge beträgt 2 und sein kleinstes Element ist 220. Genau so extrahieren die Implementierungen auch beim Grenzwert \(10^6\) ihre Zyklen.
Die C++-, Python- und Java-Implementierungen bauen zuerst ein Feld mit den Summen echter Teiler für alle Werte bis zur Grenze auf. Anschließend durchlaufen sie die Startwerte ab 2. Wenn ein Startwert schon bei einer früheren Verfolgung vollständig eingeordnet wurde, wird er sofort übersprungen.
Für jeden neuen Startwert wächst die Implementierung einen aktuellen Pfad sowie eine Positionstabelle für die Werte auf diesem Pfad. Der Lauf stoppt, sobald der nächste Wert \([1,N]\) verlässt, einen global verarbeiteten Wert erreicht oder sich innerhalb des aktuellen Pfads wiederholt. Im Wiederholungsfall liefert der wiederholte Suffix genau einen beschränkten Zyklus; daraus werden Zykluslänge und kleinstes Zykluselement bestimmt. Die beste Antwort wird mit der Regel aktualisiert: längerer Zyklus gewinnt, bei gleicher Länge gewinnt das kleinere Minimum. Danach werden alle Werte des aktuellen Pfads global als verarbeitet markiert.
Selbstschleifen, also perfekte Zahlen, brauchen keinen Sonderfall. Sie sind einfach Zyklen der Länge 1, und jeder längere Zyklus schlägt sie automatisch nach derselben Vergleichsregel.
Die Siebphase kostet
$$\sum_{d=1}^{N}\left\lfloor\frac{N}{d}\right\rfloor=O(N\log N),$$
und dominiert damit die Laufzeit. Die Pfadverfolgung ist danach \(O(N)\), weil jeder In-Range-Wert höchstens einmal explizit in einen Pfad eingetragen wird, bevor er global als verarbeitet gilt. Insgesamt ergibt sich also \(O(N\log N)\).
Der Speicherbedarf ist linear. Sowohl das Feld der Teilersummen als auch die globale Markierung benötigen \(O(N)\) Platz; der temporäre Pfad und seine Positionstabelle sind im schlimmsten Fall ebenfalls durch \(O(N)\) beschränkt.
\(s(n)\), \(n\) sayısının kendisi hariç pozitif bölenlerinin toplamı olsun:
$$s(n)=\sum_{\substack{d\mid n\\1\le d<n}} d.$$
\(a_0=n\) ile başlayıp \(a_{k+1}=s(a_k)\) tanımını yaptığımızda bir aliquot dizi elde ederiz. Soru, bu iterasyonun oluşturduğu döngüler arasında tüm elemanları \(10^6\)'yı aşmayan en uzun döngünün en küçük elemanını istemektedir. Başka bir deyişle, \(n\mapsto s(n)\) dönüşümünün \([1,10^6]\) aralığında kalan yönlü çevrimlerini inceliyoruz.
Her başlangıç için bölenleri tekrar tekrar hesaplayan kaba kuvvet yaklaşımı çok fazla işi boşa harcar. Uygulamalar bunun yerine önce bütün \(s(n)\) değerlerini tek seferde çıkarır, sonra ortaya çıkan fonksiyonel grafı dolaşır.
\(N=10^6\) ve \(f(n)=s(n)\) yazalım. \([1,N]\) aralığındaki her \(n\) tam olarak bir sonraki değere sahiptir; bu sonraki değer bazen aralığın dışına çıkabilir. Dolayısıyla problem, çıkış derecesi 1 olan yönlü bir graf üzerinde çevrim aramaya dönüşür.
\(m\)'nin her öz böleni \(d\), \(s(m)\)'ye tam bir kez katkı yapar. Her sayıyı ayrı ayrı çarpanlarına ayırmak yerine, her olası böleni bütün katlarına dağıtmak daha verimlidir. Sabit bir \(d\) için etkilenen sayılar \(2d,3d,\dots,\left\lfloor N/d\right\rfloor d\) olduğundan, elek şu güncellemeleri yapar:
$$s(kd)\leftarrow s(kd)+d\qquad\text{ }k=2,3,\dots,\left\lfloor\frac{N}{d}\right\rfloor.$$
Tüm \(d\) değerleri işlendiğinde dizide \(s(1),s(2),\dots,s(N)\) hazır durur. Kodun kullandığı asıl matematiksel nesne budur: aliquot dönüşümü doğrudan tabloya dökülmüş olur.
Toplam güncelleme sayısı
$$\sum_{d=1}^{N}\left(\left\lfloor\frac{N}{d}\right\rfloor-1\right)$$
kadardır ve harmonik seri tahminiyle \(O(N\log N)\) eder. Bu, her sayıyı baştan çarpanlara ayırmaktan çok daha ucuzdur; ayrıca sonraki aşamada her geçiş sadece bir dizi erişimine dönüşür.
Tablo hazır olunca her başlangıç değeri şu deterministik yürüyüşü üretir:
$$n,\ f(n),\ f(f(n)),\ \dots.$$
Bu yürüyüş \([1,N]\) içinde kaldığı sürece sonunda üç durumdan biri görülür: sıradaki değer aralık dışına çıkar, yürüyüş daha önce tamamen incelenmiş bir bölgeye girer ya da mevcut yol üzerinde zaten görülmüş bir değeri tekrar eder. Yeni bir sınırlı döngü yalnızca üçüncü durumda bulunur.
Buradaki temel yapı şudur: çıkış derecesi 1 olan bir graf ileriye doğru dallanmaz. Bir düğümden başladıktan sonra tek bir gelecek vardır. Küresel işaretlemenin doğruluğu bu değişmeze dayanır.
Mevcut yürüyüş boyunca birbirinden farklı şu değerlerin kaydedildiğini düşünelim:
$$p_0,p_1,\dots,p_{m-1}.$$
Sıradaki değer \(p_r\) çıkarsa, o zaman
$$p_r,p_{r+1},\dots,p_{m-1}$$
tam olarak döngüdür. Uzunluğu
$$\ell=m-r$$
olur; bu döngünün cevap adayı da
$$\min\{p_r,p_{r+1},\dots,p_{m-1}\}$$
değeridir. \(p_0,\dots,p_{r-1}\) kısmı sadece döngüye giren bir kuyruktur. Bu nedenle uygulamalar, mevcut yolun yanında her değerin bu yolda ilk görüldüğü konumu da saklar.
Bir yürüyüş bittiğinde, üzerinde görülen bütün aralık içi değerler kalıcı olarak işlenmiş sayılabilir. Bunun nedeni yapısaldır: bu düğümlerden birinden yeniden başlamak ancak aynı kuyruğu izler, aynı döngüye ulaşır, aynı biçimde aralık dışına çıkar ya da zaten bilinen bir bileşene bağlanır. Onların arkasında saklı başka bir sınırlı döngü yoktur.
Bu değişmez ikinci aşamayı neredeyse doğrusal hale getirir: her aralık içi değer, kalıcı biçimde sınıflandırılmadan önce açık bir yol listesine en fazla bir kez eklenir.
Mekanizma daha küçük \(N=300\) sınırında bile açıkça görülür. Elek şunları verir:
$$s(220)=1+2+4+5+10+11+20+22+44+55+110=284,$$
$$s(284)=1+2+4+71+142=220.$$
Dolayısıyla 220'den başlayan yürüyüş
$$220\to 284\to 220$$
olur. Tekrarlanan 220 değeri ilk kez 0. konumda göründüğü için, kaydedilmiş yolun tamamı döngüdür. Uzunluğu 2, en küçük elemanı 220'dir. Uygulamaların büyük sınırda yaptığı çıkarım da tam olarak budur.
C++, Python ve Java uygulamaları önce sınırdaki bütün değerler için öz bölen toplamı dizisini oluşturur. Sonra başlangıç değerlerini 2'den itibaren tararlar. Bir başlangıç daha önceki bir yürüyüş sırasında tamamen sınıflandırılmışsa hemen atlanır.
Yeni bir başlangıç için uygulama hem bir mevcut yol listesi hem de bu listedeki değerlerin konum tablosunu büyütür. Yürüyüş, sıradaki değer \([1,N]\) dışına çıktığında, küresel olarak işlenmiş bir değere ulaştığında ya da mevcut yol içinde tekrar ettiğinde durur. Tekrar durumunda tekrar eden sonek tek bir sınırlı döngü verir; uygulama buradan döngü uzunluğunu ve döngünün en küçük elemanını hesaplar. En iyi sonuç şu kuralla güncellenir: daha uzun döngü tercih edilir, eşitlikte ise daha küçük minimum seçilir. Ardından mevcut yolda görülen tüm değerler işlenmiş olarak işaretlenir.
Mükemmel sayılara karşılık gelen öz-döngüler için ayrı bir dal gerekmez. Bunlar sadece uzunluğu 1 olan döngülerdir; aynı karşılaştırma kuralı altında herhangi bir daha uzun döngü onları zaten geçer.
Elek aşamasının maliyeti
$$\sum_{d=1}^{N}\left\lfloor\frac{N}{d}\right\rfloor=O(N\log N)$$
olup toplam süreyi baskılar. Yol izleme aşaması ise elekten sonra \(O(N)\)'dir; çünkü her aralık içi değer, küresel olarak işlenmeden önce açık bir yola en fazla bir kez eklenir. Böylece toplam zaman karmaşıklığı \(O(N\log N)\) olur.
Bellek kullanımı doğrusaldır. Öz bölen toplamı tablosu ile küresel işaretleme dizisi \(O(N)\) alan ister; geçici yol ve onun konum tablosu da en kötü durumda yine \(O(N)\) ile sınırlıdır.
Sea \(s(n)\) la suma de los divisores propios de \(n\):
$$s(n)=\sum_{\substack{d\mid n\\1\le d<n}} d.$$
Partiendo de \(a_0=n\), definimos una sucesión alícuota mediante \(a_{k+1}=s(a_k)\). El problema pide el menor elemento del ciclo más largo producido por esta iteración, con la restricción de que todos los elementos del ciclo sean \(\le 10^6\). En otras palabras, buscamos los ciclos dirigidos de la aplicación \(n\mapsto s(n)\) que permanecen dentro de \([1,10^6]\).
Un enfoque ingenuo que factorizara cada número de nuevo para cada arranque repetiría muchísimo trabajo. Por eso las implementaciones calculan primero todos los valores \(s(n)\) y solo después recorren el grafo funcional resultante.
Escribamos \(N=10^6\) y \(f(n)=s(n)\). Cada entero \(n\in[1,N]\) tiene exactamente un sucesor \(f(n)\), aunque ese sucesor puede quedar fuera del intervalo. El problema completo pasa así a ser una búsqueda de ciclos en un grafo dirigido de grado de salida 1.
Cada divisor propio \(d\) de \(m\) aporta exactamente una vez a \(s(m)\). En lugar de factorizar cada \(m\) por separado, distribuimos cada posible divisor entre todos sus múltiplos. Para un \(d\) fijo, los números afectados son \(2d,3d,\dots,\left\lfloor N/d\right\rfloor d\), de modo que la criba realiza las actualizaciones
$$s(kd)\leftarrow s(kd)+d\qquad\text{para }k=2,3,\dots,\left\lfloor\frac{N}{d}\right\rfloor.$$
Cuando todos los \(d\) han sido procesados, el arreglo ya contiene los valores exactos de \(s(1),s(2),\dots,s(N)\). Ese es el objeto matemático central de la solución: el mapa alícuota queda materializado como una tabla.
El número total de actualizaciones es
$$\sum_{d=1}^{N}\left(\left\lfloor\frac{N}{d}\right\rfloor-1\right),$$
que vale \(O(N\log N)\) por la estimación armónica. Esto es mucho más barato que refactorizar todos los números uno por uno, y además convierte cada transición posterior en una consulta \(O(1)\) al arreglo.
Una vez conocida la tabla, cada valor inicial genera un recorrido determinista
$$n,\ f(n),\ f(f(n)),\ \dots.$$
Mientras el recorrido permanezca en \([1,N]\), solo pueden ocurrir tres cosas: el siguiente valor sale del intervalo, el recorrido entra en una zona ya estudiada antes, o reaparece un valor ya visto en el camino actual. Solo el tercer caso produce un ciclo nuevo completamente contenido en el rango permitido.
Este punto de vista es importante porque un grafo de salida 1 no puede ramificarse hacia delante. Desde cualquier vértice hay un único futuro posible. Esa es la invariante que justifica el marcado global.
Supongamos que el recorrido actual ha almacenado valores distintos
$$p_0,p_1,\dots,p_{m-1}.$$
Si el siguiente valor es \(p_r\), entonces el sufijo
$$p_r,p_{r+1},\dots,p_{m-1}$$
es exactamente el ciclo. Su longitud es
$$\ell=m-r,$$
y el candidato a respuesta que aporta ese ciclo es
$$\min\{p_r,p_{r+1},\dots,p_{m-1}\}.$$
El prefijo \(p_0,\dots,p_{r-1}\) es solo una cola que desemboca en el ciclo. Por eso las implementaciones guardan, junto al camino actual, una tabla con la primera posición en la que apareció cada valor de ese mismo camino.
Cuando un recorrido termina, todos los valores en rango que aparecieron en él pueden marcarse como ya procesados. La razón es estructural: si más tarde se vuelve a empezar desde cualquiera de ellos, el recorrido solo podrá seguir la misma cola, llegar al mismo ciclo, salir del intervalo de la misma forma o fusionarse con una componente que ya era conocida. No puede esconder un ciclo acotado diferente.
Esa invariante convierte la segunda fase en un barrido casi lineal: cada valor en rango entra en un camino explícito a lo sumo una vez antes de quedar clasificado de forma permanente.
El mecanismo se ve con claridad ya en la cota menor \(N=300\). La criba produce
$$s(220)=1+2+4+5+10+11+20+22+44+55+110=284,$$
$$s(284)=1+2+4+71+142=220.$$
Por tanto, el recorrido desde 220 es
$$220\to 284\to 220.$$
El valor repetido 220 apareció por primera vez en la posición 0, de modo que todo el camino registrado es el ciclo. Su longitud es 2 y su menor elemento es 220. Exactamente de este modo extraen las implementaciones los ciclos en la cota completa de un millón.
Las implementaciones en C++, Python y Java construyen primero un arreglo con la suma de divisores propios para todos los valores hasta el límite. Después recorren los valores iniciales desde 2 en adelante. Si un inicio ya quedó clasificado en una exploración anterior, se omite de inmediato.
Para cada nuevo inicio, la implementación mantiene un camino actual y una tabla de posiciones para los valores de ese camino. El recorrido se detiene cuando el siguiente valor sale de \([1,N]\), alcanza un valor ya procesado globalmente o se repite dentro del camino actual. En el caso de repetición, el sufijo repetido da un ciclo acotado; a partir de él se calculan la longitud del ciclo y su menor miembro. La mejor respuesta se actualiza con la regla: preferir el ciclo más largo y, en caso de empate, el menor mínimo. Después, todos los valores vistos en el camino actual se marcan como procesados.
Los bucles de longitud 1, correspondientes a números perfectos, no necesitan un tratamiento especial. Son simplemente ciclos de longitud 1 y cualquier ciclo más largo los supera automáticamente con la misma regla de comparación.
La fase de criba cuesta
$$\sum_{d=1}^{N}\left\lfloor\frac{N}{d}\right\rfloor=O(N\log N),$$
y domina el tiempo de ejecución. La fase de seguimiento de caminos es \(O(N)\) después de la criba, porque cada valor en rango se inserta en un camino explícito como mucho una vez antes de quedar marcado globalmente. Por lo tanto, la complejidad total es \(O(N\log N)\).
El uso de memoria es lineal. El arreglo de sumas de divisores y el marcador global requieren \(O(N)\), y el camino temporal junto con su tabla de posiciones también están acotados por \(O(N)\) en el peor caso.
设 \(s(n)\) 表示 \(n\) 的真因子和：
$$s(n)=\sum_{\substack{d\mid n\\1\le d<n}} d.$$
从 \(a_0=n\) 出发，定义迭代关系 \(a_{k+1}=s(a_k)\)，就得到一条 aliquot 序列。题目要求的是：在所有元素都不超过 \(10^6\) 的循环中，找出最长的那个，并返回该循环中的最小元素。也就是说，我们要研究映射 \(n\mapsto s(n)\) 在区间 \([1,10^6]\) 内形成的有向环。
如果对每个起点都重新分解因数，再一条条暴力追踪，会重复做大量相同工作。实现采用的正确思路是先一次性预计算全部 \(s(n)\)，再把问题视为函数图上的环检测。
记 \(N=10^6\)，并写 \(f(n)=s(n)\)。对于每个 \(n\in[1,N]\)，都有唯一的后继 \(f(n)\)，只是这个后继有时会跳出区间。于是整个问题可以重述为：在一个每个点出度都等于 1 的有向图里，寻找完全落在 \([1,N]\) 内的最长环。
如果 \(d\) 是 \(m\) 的真因子，那么它恰好向 \(s(m)\) 贡献一次。与其把每个 \(m\) 单独分解，不如把每个可能的因子一次性分发给它的所有倍数。对固定的 \(d\)，受影响的数是 \(2d,3d,\dots,\left\lfloor N/d\right\rfloor d\)，因此筛法执行的更新就是
$$s(kd)\leftarrow s(kd)+d\qquad\text{其中 }k=2,3,\dots,\left\lfloor\frac{N}{d}\right\rfloor.$$
当所有 \(d\) 都处理完之后，数组中就已经保存了 \(s(1),s(2),\dots,s(N)\) 的精确值。代码后续真正依赖的数学对象，就是这张被完全展开的“下一步去哪儿”的表。
总更新次数是
$$\sum_{d=1}^{N}\left(\left\lfloor\frac{N}{d}\right\rfloor-1\right),$$
利用调和级数估计可知它是 \(O(N\log N)\)。相比对每个整数单独做因数分解，这个代价小得多；同时也让后续每一次“走到下一个数”都变成了 \(O(1)\) 的数组访问。
一旦表格已知，每个起点都会产生唯一的一条轨道：
$$n,\ f(n),\ f(f(n)),\ \dots.$$
当这条轨道还停留在 \([1,N]\) 内时，最终只会发生三种情况之一：下一项跳出区间，轨道并入一个先前已经完整分析过的区域，或者当前轨道上出现了重复值。只有第三种情况才会产生一个新的、完全位于边界之内的循环。
这个观点的关键在于：出度为 1 的图向前不会分叉。从任意顶点出发，未来路径只有一条。这正是后面“全局标记已经处理过的点”为何正确的结构性原因。
设当前轨道中已经按顺序记录了互不相同的区间内数值
$$p_0,p_1,\dots,p_{m-1}.$$
如果下一项等于某个较早出现的 \(p_r\)，那么后缀
$$p_r,p_{r+1},\dots,p_{m-1}$$
就恰好是那个环。它的长度为
$$\ell=m-r,$$
而这个环对答案提供的候选值就是
$$\min\{p_r,p_{r+1},\dots,p_{m-1}\}.$$
前缀 \(p_0,\dots,p_{r-1}\) 只是通向环的一段尾巴，并不属于真正的友好链。因此，实现除了维护当前路径本身，还必须维护“某个值第一次出现在当前路径的哪个位置”这一位置表。
一条轨道结束之后，轨道上所有仍在区间内的值都可以永久标记为“已处理”。原因并不依赖经验，而是来自函数图结构：以后如果再从这些点中的任何一个重新出发，只会沿着同一条尾巴前进，到达同一个环，或者以同样方式离开区间，或者并入一个已经知道的连通部分。它们不可能再藏着另一个新的受限环。
这个不变式使第二阶段接近线性：每个区间内的值在被最终归类之前，最多只会被真正压入显式路径一次。
在较小的边界 \(N=300\) 下，这套机制已经能完整展示出来。筛法给出
$$s(220)=1+2+4+5+10+11+20+22+44+55+110=284,$$
$$s(284)=1+2+4+71+142=220.$$
因此从 220 出发的轨道就是
$$220\to 284\to 220.$$
重复出现的 220 第一次出现在位置 0，所以整个已记录路径就是一个环。它的长度是 2，最小元素是 220。完整的一百万范围搜索与此完全同构，只是规模更大而已。
C++、Python 和 Java 实现都会先建立一个数组，存放从 1 到上界的全部真因子和。之后它们按从 2 开始递增的顺序扫描每个起点。如果某个起点在更早的一次轨道追踪中已经被完整归类，就直接跳过。
对于新的起点，实现会同步维护两份临时状态：一条当前路径，以及当前路径上每个值第一次出现的位置表。只要下一项离开 \([1,N]\)、落到一个全局已处理的值上，或者在当前路径内部重复，追踪就停止。如果出现的是当前路径内部重复，那么重复后缀就给出一个受限环；实现据此计算环长与环上的最小元素。全局最优答案的更新规则是：优先选择更长的环；若长度相同，则选择最小元素更小的那个。最后，当前路径中出现过的所有值都会被整体标记为已处理。
对应完全数的自环不需要单独分支处理。它们只是长度为 1 的环，而任何更长的环都会在同一套比较规则下自然胜出。
筛法阶段的代价为
$$\sum_{d=1}^{N}\left\lfloor\frac{N}{d}\right\rfloor=O(N\log N),$$
这也是整体运行时间的主项。筛法之后，路径追踪阶段是 \(O(N)\) 的，因为每个区间内的值在被全局标记之前，最多只会进入显式路径一次。因此总时间复杂度为 \(O(N\log N)\)。
空间复杂度是线性的。真因子和数组与全局处理标记都需要 \(O(N)\) 空间；临时路径和它的位置表在最坏情况下也同样受 \(O(N)\) 约束。
Пусть \(s(n)\) обозначает сумму собственных делителей числа \(n\):
$$s(n)=\sum_{\substack{d\mid n\\1\le d<n}} d.$$
Начиная с \(a_0=n\), зададим аликвотную последовательность правилом \(a_{k+1}=s(a_k)\). Требуется найти наименьший элемент самого длинного цикла этой итерации при условии, что все элементы цикла не превосходят \(10^6\). Иначе говоря, нас интересуют ориентированные циклы отображения \(n\mapsto s(n)\), целиком лежащие внутри интервала \([1,10^6]\).
Наивный подход, при котором для каждого старта заново раскладываются на делители все встреченные числа, бессмысленно повторяет одну и ту же работу. Реальные реализации сначала вычисляют все значения \(s(n)\), а уже потом рассматривают получившийся функциональный граф.
Обозначим \(N=10^6\) и \(f(n)=s(n)\). У каждого числа \(n\in[1,N]\) есть ровно один следующий элемент \(f(n)\), хотя этот следующий элемент может выйти за пределы интервала. Поэтому задача сводится к поиску циклов в ориентированном графе, где исходящая степень каждой вершины равна 1.
Каждый собственный делитель \(d\) числа \(m\) вносит в \(s(m)\) ровно один вклад. Вместо отдельной факторизации каждого \(m\) выгоднее раздать каждый возможный делитель всем его кратным. Для фиксированного \(d\) затронуты числа \(2d,3d,\dots,\left\lfloor N/d\right\rfloor d\), поэтому решето выполняет обновления
$$s(kd)\leftarrow s(kd)+d\qquad\text{для }k=2,3,\dots,\left\lfloor\frac{N}{d}\right\rfloor.$$
После обработки всех \(d\) массив уже содержит точные значения \(s(1),s(2),\dots,s(N)\). Именно этот объект затем использует код: аликвотное отображение превращено в таблицу переходов.
Общее число обновлений равно
$$\sum_{d=1}^{N}\left(\left\lfloor\frac{N}{d}\right\rfloor-1\right),$$
то есть имеет порядок \(O(N\log N)\) по оценке через гармонический ряд. Это значительно дешевле, чем заново раскладывать каждое число, а также делает каждый последующий переход простым обращением к массиву за \(O(1)\).
Когда таблица построена, любой старт порождает детерминированную траекторию
$$n,\ f(n),\ f(f(n)),\ \dots.$$
Пока траектория остается в \([1,N]\), в конечном счете происходит ровно одно из трех: следующий элемент выходит из интервала, траектория попадает в область, уже полностью разобранную раньше, или повторяется значение, уже встречавшееся на текущем пути. Только третий случай дает новый ограниченный цикл.
Этот взгляд важен потому, что в графе с исходящей степенью 1 нельзя разветвиться вперед. Из каждой вершины существует единственное продолжение, и именно это делает корректным глобальное помечание уже разобранных значений.
Пусть на текущем пути записаны попарно различные значения
$$p_0,p_1,\dots,p_{m-1}.$$
Если следующий элемент равен \(p_r\), то суффикс
$$p_r,p_{r+1},\dots,p_{m-1}$$
и есть искомый цикл. Его длина равна
$$\ell=m-r,$$
а кандидат на ответ, связанный с этим циклом, равен
$$\min\{p_r,p_{r+1},\dots,p_{m-1}\}.$$
Префикс \(p_0,\dots,p_{r-1}\) является лишь хвостом, ведущим в цикл. Поэтому реализации хранят не только сам текущий путь, но и таблицу первой позиции каждого значения на этом пути.
После окончания одного прохода все встреченные на нем значения из диапазона можно навсегда считать обработанными. Причина чисто структурная: если потом запустить процесс снова из любого такого значения, он лишь пройдет по тому же хвосту, попадет в тот же цикл, выйдет из интервала тем же способом или сольется с уже известной компонентой. Новый ограниченный цикл там уже не обнаружится.
Эта инварианта делает вторую фазу почти линейной: каждое значение из диапазона добавляется в явный путь не более одного раза, после чего получает окончательную классификацию.
Даже при меньшей границе \(N=300\) механизм виден полностью. Решето дает
$$s(220)=1+2+4+5+10+11+20+22+44+55+110=284,$$
$$s(284)=1+2+4+71+142=220.$$
Значит, траектория из 220 равна
$$220\to 284\to 220.$$
Повторившееся значение 220 впервые встретилось в позиции 0, поэтому весь записанный путь и есть цикл. Его длина равна 2, а наименьший элемент равен 220. Именно так реализации извлекают циклы и при полном ограничении в один миллион.
Реализации на C++, Python и Java сначала строят массив сумм собственных делителей для всех значений до предела. Затем они просматривают стартовые значения, начиная с 2. Если старт уже был полностью классифицирован во время более раннего прохода, он сразу пропускается.
Для каждого нового старта реализация поддерживает текущий путь и таблицу позиций значений на этом пути. Проход заканчивается, когда следующий элемент выходит из \([1,N]\), попадает в глобально обработанное значение или повторяется внутри текущего пути. В случае повтора повторяющийся суффикс образует один ограниченный цикл; по нему вычисляются длина цикла и его минимальный элемент. Глобально лучший ответ обновляется по правилу: предпочесть более длинный цикл, а при равной длине предпочесть меньший минимум. После этого все значения, встреченные на текущем пути, помечаются как обработанные.
Самопетли, соответствующие совершенным числам, не требуют отдельной ветки логики. Это просто циклы длины 1, и любой более длинный цикл автоматически превосходит их по тому же правилу сравнения.
Фаза решета стоит
$$\sum_{d=1}^{N}\left\lfloor\frac{N}{d}\right\rfloor=O(N\log N),$$
и именно она задает основной порядок времени работы. Фаза проходов после решета имеет сложность \(O(N)\), потому что каждое значение из диапазона попадает в явный путь не более одного раза до глобального помечания. Следовательно, общая сложность равна \(O(N\log N)\).
Память линейна. Массив сумм делителей и глобальный массив пометок требуют \(O(N)\), а временный путь и его таблица позиций в худшем случае тоже ограничены величиной \(O(N)\).
لتكن \(s(n)\) مجموع القواسم الحقيقية للعدد \(n\):
$$s(n)=\sum_{\substack{d\mid n\\1\le d<n}} d.$$
إذا بدأنا من \(a_0=n\) وعرّفنا المتتالية بالعلاقة \(a_{k+1}=s(a_k)\)، نحصل على متتالية أليكوت. المطلوب هو أصغر عنصر في أطول دورة تنتجها هذه العملية، بشرط أن تكون جميع عناصر الدورة \(\le 10^6\). أي إننا نبحث عن الدورات الموجهة للدالة \(n\mapsto s(n)\) التي تبقى كل قيمها داخل المجال \([1,10^6]\).
الأسلوب الساذج الذي يعيد تحليل القواسم لكل بداية سيكرر المقدار نفسه من العمل مرات كثيرة. لذلك تحسب التطبيقات جميع القيم \(s(n)\) أولًا مرة واحدة، ثم تتعامل مع النتيجة على أنها رسم بياني دالي.
لنكتب \(N=10^6\) و\(f(n)=s(n)\). لكل عدد \(n\in[1,N]\) تابع وحيد هو \(f(n)\)، مع أن هذا التابع قد يقع خارج المجال. وهكذا تتحول المسألة إلى بحث عن دورات في رسم بياني موجه تكون درجة الخروج فيه لكل عقدة مساوية لـ 1.
كل قاسم حقيقي \(d\) للعدد \(m\) يضيف مساهمة واحدة فقط إلى \(s(m)\). بدلًا من تحليل كل \(m\) على حدة، نوزع كل قاسم محتمل على جميع مضاعفاته. عندما يكون \(d\) ثابتًا، فإن الأعداد المتأثرة هي \(2d,3d,\dots,\left\lfloor N/d\right\rfloor d\)، ولذلك ينفذ الغربال التحديثات
$$s(kd)\leftarrow s(kd)+d\qquad\text{لـ }k=2,3,\dots,\left\lfloor\frac{N}{d}\right\rfloor.$$
بعد الانتهاء من جميع قيم \(d\)، يصبح لدينا في المصفوفة القيم الدقيقة \(s(1),s(2),\dots,s(N)\). وهذا هو الكائن الرياضي الذي يعتمد عليه الحل فعلًا: خريطة أليكوت تتحول إلى جدول انتقالات مباشر.
عدد التحديثات الكلي هو
$$\sum_{d=1}^{N}\left(\left\lfloor\frac{N}{d}\right\rfloor-1\right),$$
وهو من الرتبة \(O(N\log N)\) بفضل تقدير السلسلة التوافقية. هذا أرخص بكثير من إعادة تحليل كل عدد على حدة، كما أنه يجعل كل انتقال لاحق مجرد وصول مباشر إلى عنصر في مصفوفة بزمن \(O(1)\).
بعد بناء الجدول، يولد كل عدد بداية مسارًا حتميًا:
$$n,\ f(n),\ f(f(n)),\ \dots.$$
وأثناء بقاء المسار داخل \([1,N]\)، فلا بد في النهاية من حدوث واحدة من ثلاث حالات: القيمة التالية تخرج من المجال، أو يدخل المسار منطقة سبق تحليلها بالكامل، أو تتكرر قيمة ظهرت من قبل على المسار الحالي نفسه. الحالة الثالثة وحدها هي التي تنتج دورة جديدة محصورة داخل الحد.
هذا المنظور مهم لأن الرسم البياني ذي درجة الخروج 1 لا يتشعب إلى الأمام. من كل عقدة يوجد مستقبل وحيد فقط، وهذا هو الثابت البنيوي الذي يجعل الوسم العام للقيم المعالجة صحيحًا.
افترض أن المسار الحالي سجّل القيم المختلفة التالية:
$$p_0,p_1,\dots,p_{m-1}.$$
إذا كانت القيمة التالية مساوية لـ \(p_r\)، فإن الذيل
$$p_r,p_{r+1},\dots,p_{m-1}$$
هو الدورة بالضبط. طولها يساوي
$$\ell=m-r,$$
والمرشح الذي تقدمه هذه الدورة للإجابة هو
$$\min\{p_r,p_{r+1},\dots,p_{m-1}\}.$$
أما المقدمة \(p_0,\dots,p_{r-1}\) فهي مجرد ذيل يقود إلى الدورة وليست جزءًا منها. لهذا تحتفظ التطبيقات، إلى جانب المسار الحالي، بجدول يحدد الموضع الأول الذي ظهرت فيه كل قيمة على ذلك المسار.
بعد انتهاء مسار واحد، يمكن اعتبار كل القيم الواقعة داخل المجال والتي ظهرت فيه قيَمًا معالجة نهائيًا. السبب بنيوي: إذا بدأنا مرة أخرى من أي قيمة منها فلن يحدث إلا أحد الأمور التالية: نسير في الذيل نفسه، أو نصل إلى الدورة نفسها، أو نخرج من المجال بالطريقة نفسها، أو نندمج في مكوّن كان معروفًا مسبقًا. لا يمكن أن تظهر من خلالها دورة جديدة مختلفة داخل المجال.
هذا الثابت يجعل المرحلة الثانية شبه خطية، لأن كل قيمة داخل المجال تُضاف إلى مسار صريح مرة واحدة على الأكثر قبل أن تُصنَّف نهائيًا.
حتى عند الحد الأصغر \(N=300\) تظهر الآلية كاملة. يعطي الغربال
$$s(220)=1+2+4+5+10+11+20+22+44+55+110=284,$$
$$s(284)=1+2+4+71+142=220.$$
إذن المسار المنطلق من 220 هو
$$220\to 284\to 220.$$
القيمة المكررة 220 ظهرت أول مرة عند الموضع 0، ولذلك فالمسار المسجّل كله هو الدورة. طولها 2 وأصغر عنصر فيها هو 220. بهذه الآلية نفسها تستخرج التطبيقات الدورات عند الحد الكامل \(10^6\).
تقوم تطبيقات C++ وPython وJava أولًا ببناء مصفوفة مجموع القواسم الحقيقية لجميع القيم حتى الحد. ثم تمر على قيم البداية ابتداءً من 2. فإذا كانت قيمة بداية ما قد صُنفت بالكامل أثناء مسار سابق، تُتجاوز مباشرة.
لكل بداية جديدة تحتفظ الخوارزمية بمسار حالي وبجدول لمواضع القيم داخل ذلك المسار. يتوقف السير عندما تخرج القيمة التالية من \([1,N]\)، أو تصل إلى قيمة موسومة عالميًا على أنها معالجة، أو تتكرر داخل المسار الحالي. في حالة التكرار يعطي الذيل المكرر دورة واحدة محصورة؛ ومنه تُحسب طول الدورة وأصغر قيمة فيها. ثم تُحدَّث أفضل إجابة وفق القاعدة التالية: تفضيل الدورة الأطول، وعند تساوي الطول تفضيل الأصغر حدًا أدنى. بعد ذلك تُوسم جميع القيم التي ظهرت على المسار الحالي على أنها معالجة.
الحلقات الذاتية الموافقة للأعداد الكاملة لا تحتاج إلى معالجة خاصة. فهي ببساطة دورات طولها 1، وأي دورة أطول منها تتغلب عليها تلقائيًا بالقانون نفسه.
تكلفة مرحلة الغربال هي
$$\sum_{d=1}^{N}\left\lfloor\frac{N}{d}\right\rfloor=O(N\log N),$$
وهي المسيطرة على زمن التنفيذ. أما مرحلة تتبع المسارات بعد الغربال فهي \(O(N)\)، لأن كل قيمة داخل المجال تُدرج في مسار صريح مرة واحدة على الأكثر قبل وسمها نهائيًا. لذلك يكون التعقيد الكلي \(O(N\log N)\).
استهلاك الذاكرة خطي. فجدول مجاميع القواسم وجدول الوسم العام يستهلكان \(O(N)\)، كما أن المسار المؤقت وجدول مواضعه محدودان أيضًا بـ \(O(N)\) في أسوأ الأحوال.