Problem Summary

Define the sequence

$$r_k=(kA)\bmod M,\qquad A=1504170715041707,\qquad M=4503599627370517,$$

with residues interpreted in $\{0,1,\dots,M-1\}$. An Eulercoin is a term that is smaller than every earlier term:

$$r_k<\min_{1\le j<k} r_j.$$

The goal is to sum all Eulercoins. A naive scan through all possible indices would be far too large, so the solution uses a two-phase argument: first collect the large record lows in index order, then recover the remaining small record lows from value order by using a modular inverse.

Mathematical Approach

The key fact is that multiplication by $A$ permutes the nonzero residues modulo $M$. That allows us to look at the same sequence from two complementary directions: by increasing index $k$, and by increasing value $v$.

Step 1: The sequence is a permutation of the nonzero residues

Because $\gcd(A,M)=1$, the congruence

$$kA\equiv \ell A \pmod M$$

implies $k\equiv \ell \pmod M$. Therefore the map $k\mapsto (kA)\bmod M$ is injective modulo $M$, and for $k=1,2,\dots,M-1$ it visits every nonzero residue exactly once.

So each integer $v\in\{1,2,\dots,M-1\}$ appears at one unique position in the sequence. This uniqueness is what makes the reverse phase possible.

Step 2: Recover the unique index of a value

Since $\gcd(A,M)=1$, there exists a modular inverse $A^{-1}\pmod M$. For any nonzero value $v$, the position where $v$ occurs is the unique solution of

$$kA\equiv v \pmod M,$$

namely

$$k(v)\equiv A^{-1}v \pmod M.$$

This means we do not have to wait for a small value to appear in a long forward simulation. We can compute directly where that value occurs.

Step 3: Characterize Eulercoins in value order

A value $v$ is an Eulercoin if and only if it appears before every smaller positive value. If $\mathcal{E}$ denotes the set of Eulercoins, then

$$v\in\mathcal{E}\iff k(v)<\min_{1\le u<v} k(u).$$

The forward implication is immediate: if some smaller value $u<v$ appeared earlier, then $v$ could not be a new record low. The converse is just as important: if every smaller value appears later, then all earlier sequence terms are larger than $v$, so $v$ really is a new minimum.

Thus the Eulercoins are exactly the record minima of the index sequence $k(1),k(2),k(3),\dots$ when values are scanned upward.

Step 4: Use a forward scan for the large Eulercoins

The implementations begin in index order. Starting from $r_1=A$, they update the sequence by one modular addition at a time:

$$r_{k+1}=\begin{cases} r_k+A,& r_k+A<M,\\ r_k+A-M,& r_k+A\ge M. \end{cases}$$

Whenever the new term is smaller than the current record low, it is an Eulercoin and is added to the sum. This efficiently captures the early Eulercoins, which still have large values.

The forward phase stops when the current Eulercoin drops below $20{,}000{,}000$. Let that last forward Eulercoin be $B$. Any later Eulercoin must be smaller than $B$, so from that point on only the values $1,2,\dots,B-1$ remain to be checked.

Step 5: Finish with a reverse scan on the remaining values

Now scan the values $v=1,2,\dots,B-1$. For each $v$, compute the unique position $k(v)\equiv A^{-1}v\pmod M$. Maintain the smallest index seen so far among all scanned values.

If the new index is smaller than that running minimum, then $v$ is an Eulercoin by the criterion from Step 3, so it must be added to the total. Otherwise some smaller value already appears earlier, and $v$ is not an Eulercoin.

This split is exact, not heuristic. The forward phase already found every Eulercoin with value at least $B$, and the reverse phase checks every positive value below $B$. The two sets are disjoint and together contain all Eulercoins.

Worked Example

With the actual constants, the first term is

$$r_1=A=1504170715041707.$$

The second term is

$$r_2=2A\bmod M=3008341430083414,$$

which is larger than $r_1$, so it is not an Eulercoin.

For $k=3$,

$$3A=4512512145125121=M+8912517754604,$$

hence

$$r_3=8912517754604.$$

Since

$$8912517754604<1504170715041707,$$

the third term is the second Eulercoin. The reverse viewpoint describes the same event differently: that value has a smaller index than every positive value below it, so it becomes a new record low exactly once.

How the Code Works

The C++, Python, and Java implementations all follow the same two-phase strategy. They begin with the modular sequence at $A$, keep track of the smallest value seen so far, and add each strict decrease to the running sum. That loop ends once the current Eulercoin falls below $20{,}000{,}000$.

Next they compute the modular inverse of $A$ modulo $M$ with the extended Euclidean algorithm. After that, they scan the remaining candidate values $1\le v<B$, convert each value into its unique sequence index with one modular multiplication, and add $v$ whenever that recovered index is a new minimum among all indices seen in the reverse scan.

The arithmetic details differ slightly by language, but the mathematics is identical. The C++ implementation uses a 128-bit intermediate product before reducing modulo $M$, Python relies on arbitrary-precision integers, and the Java implementation uses big-integer arithmetic for the modular product.

Complexity Analysis

Let $K_f$ be the number of forward iterations before the forward phase stops, and let $B$ be the last Eulercoin found there. The first phase costs $O(K_f)$, the second phase costs $O(B)$, and both phases use only constant extra memory. Therefore the total complexity is

$$O(K_f+B)$$

time with $O(1)$ additional space. For this problem that is vastly smaller than scanning the sequence all the way to $k=M-1$.

Footnotes and References

Problem page: Project Euler 700
Modular multiplicative inverse: Wikipedia - Modular multiplicative inverse
Extended Euclidean algorithm: Wikipedia - Extended Euclidean algorithm
Modular arithmetic: Wikipedia - Modular arithmetic
Complete residue system: Wikipedia - Complete residue system

Problemzusammenfassung

Betrachte die Folge

$$r_k=(kA)\bmod M,\qquad A=1504170715041707,\qquad M=4503599627370517,$$

wobei die Reste in $\{0,1,\dots,M-1\}$ liegen. Ein Eulercoin ist ein Folgenglied, das kleiner ist als alle vorherigen:

$$r_k<\min_{1\le j<k} r_j.$$

Gesucht ist die Summe aller Eulercoins. Eine naive Vorwärtssimulation über alle möglichen Indizes wäre viel zu groß, deshalb verwendet die Lösung ein Zweiphasenverfahren: zuerst werden die großen Rekordminima direkt in Indexreihenfolge gesammelt, danach werden die verbleibenden kleinen Werte über ein modulares Inverses in Wertereihenfolge rekonstruiert.

Mathematischer Ansatz

Der Kernpunkt ist, dass die Multiplikation mit $A$ die von Null verschiedenen Reste modulo $M$ permutiert. Dadurch kann man dieselbe Folge aus zwei Blickwinkeln untersuchen: nach wachsendem Index $k$ und nach wachsendem Wert $v$.

Schritt 1: Die Folge ist eine Permutation der Nichtnullreste

Weil $\gcd(A,M)=1$ gilt, folgt aus

$$kA\equiv \ell A \pmod M$$

bereits $k\equiv \ell \pmod M$. Also ist die Abbildung $k\mapsto (kA)\bmod M$ modulo $M$ injektiv und durchläuft für $k=1,2,\dots,M-1$ jeden von Null verschiedenen Rest genau einmal.

Damit besitzt jedes $v\in\{1,2,\dots,M-1\}$ genau eine Position in der Folge. Diese Eindeutigkeit ist die Grundlage der Rückwärtsphase.

Schritt 2: Den eindeutigen Index eines Werts zurückgewinnen

Da $\gcd(A,M)=1$, existiert ein modulares Inverses $A^{-1}\pmod M$. Für jeden Nichtnullwert $v$ hat die Kongruenz

$$kA\equiv v \pmod M$$

genau die Lösung

$$k(v)\equiv A^{-1}v \pmod M.$$

Dadurch muss man auf einen kleinen Wert nicht erst in einer langen Simulation warten. Man kann direkt berechnen, an welcher Stelle dieser Wert auftritt.

Schritt 3: Eulercoins in Wertereihenfolge charakterisieren

Ein Wert $v$ ist genau dann ein Eulercoin, wenn er vor jedem kleineren positiven Wert erscheint. Bezeichnet $\mathcal{E}$ die Menge der Eulercoins, so gilt

$$v\in\mathcal{E}\iff k(v)<\min_{1\le u<v} k(u).$$

Die Hinrichtung ist klar: Wenn ein kleinerer Wert $u<v$ früher auftauchte, könnte $v$ kein neues Rekordminimum sein. Umgekehrt gilt ebenso: Wenn alle kleineren Werte erst später erscheinen, dann sind alle früheren Folgenglieder größer als $v$, also ist $v$ tatsächlich ein neues Minimum.

Damit sind die Eulercoins genau die Rekordminima der Indexfolge $k(1),k(2),k(3),\dots$, wenn man die Werte aufsteigend durchsucht.

Schritt 4: Große Eulercoins per Vorwärtsscan einsammeln

Die Implementierungen beginnen trotzdem in Indexreihenfolge. Ausgehend von $r_1=A$ wird die Folge mit jeweils einer modularen Addition fortgesetzt:

$$r_{k+1}=\begin{cases} r_k+A,& r_k+A<M,\\ r_k+A-M,& r_k+A\ge M. \end{cases}$$

Immer wenn der neue Term kleiner als das bisherige Rekordminimum ist, liegt ein Eulercoin vor und wird zur Summe addiert. So werden die frühen Eulercoins mit noch großen Werten effizient gefunden.

Die Vorwärtsphase endet, sobald der aktuelle Eulercoin unter $20{,}000{,}000$ fällt. Sei $B$ dieser letzte vorwärts gefundene Eulercoin. Jeder spätere Eulercoin muss kleiner als $B$ sein, also bleiben nur noch die Werte $1,2,\dots,B-1$ zu prüfen.

Schritt 5: Die kleinen Werte per Rückwärtsscan vervollständigen

Nun werden die Werte $v=1,2,\dots,B-1$ durchlaufen. Für jeden Wert berechnet man die eindeutige Position $k(v)\equiv A^{-1}v\pmod M$ und merkt sich den kleinsten bislang gesehenen Index.

Ist der neue Index kleiner als dieses laufende Minimum, dann ist $v$ nach Schritt 3 ein Eulercoin und wird addiert. Andernfalls existiert bereits ein kleinerer Wert mit früherem Auftreten, also ist $v$ kein Eulercoin.

Diese Aufteilung ist exakt und keine Heuristik. Die Vorwärtsphase hat schon alle Eulercoins mit Wert mindestens $B$ gefunden, und die Rückwärtsphase prüft jeden positiven Wert unterhalb von $B$. Beide Mengen sind disjunkt und zusammen vollständig.

Durchgerechnetes Beispiel

Für die tatsächlichen Konstanten ist der erste Term

$$r_1=A=1504170715041707.$$

Der zweite Term ist

$$r_2=2A\bmod M=3008341430083414,$$

also größer als $r_1$ und damit kein Eulercoin.

Für $k=3$ gilt

$$3A=4512512145125121=M+8912517754604,$$

daher

$$r_3=8912517754604.$$

Weil

$$8912517754604<1504170715041707,$$

ist der dritte Term der zweite Eulercoin. Die Rückwärtsbetrachtung beschreibt dasselbe Ereignis so: Dieser Wert besitzt einen kleineren Index als jeder positive Wert darunter und wird daher genau einmal zu einem neuen Rekordminimum.

Wie der Code funktioniert

Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe Zweiphasenstrategie. Zuerst starten sie die modulare Folge bei $A$, merken sich das bisher kleinste Glied und addieren jede echte Abnahme zur laufenden Summe. Diese Schleife endet, sobald der aktuelle Eulercoin unter $20{,}000{,}000$ fällt.

Danach wird mit dem erweiterten Euklidischen Algorithmus das modulare Inverse von $A$ modulo $M$ berechnet. Anschließend werden die verbleibenden Kandidaten $1\le v<B$ durchsucht, jeder Wert wird mit einer modularen Multiplikation in seinen eindeutigen Folgenindex zurückübersetzt, und $v$ wird genau dann addiert, wenn dieser Index ein neues Minimum unter allen bisher in der Rückwärtsphase gesehenen Indizes ist.

Die arithmetischen Details unterscheiden sich leicht nach Sprache, die Mathematik aber nicht. Die C++-Implementierung benutzt ein 128-Bit-Zwischenprodukt vor der Reduktion modulo $M$, Python verwendet Ganzzahlen mit beliebiger Präzision, und die Java-Implementierung nutzt Big-Integer-Arithmetik für das modulare Produkt.

Komplexitätsanalyse

Sei $K_f$ die Anzahl der Vorwärtsschritte bis zum Abbruch der ersten Phase und $B$ der dort zuletzt gefundene Eulercoin. Die erste Phase kostet $O(K_f)$, die zweite $O(B)$, und beide benötigen nur konstanten Zusatzspeicher. Insgesamt ergibt sich also

$$O(K_f+B)$$

Zeit bei $O(1)$ zusätzlichem Speicher. Für dieses Problem ist das dramatisch kleiner als ein vollständiger Durchlauf bis $k=M-1$.

Fußnoten und Referenzen

Problemseite: Project Euler 700
Modulares Inverses: Wikipedia - Modular multiplicative inverse
Erweiterter Euklidischer Algorithmus: Wikipedia - Extended Euclidean algorithm
Modulare Arithmetik: Wikipedia - Modular arithmetic
Vollständiges Restsystem: Wikipedia - Complete residue system

Problem Özeti

Şu dizi tanımlanır:

$$r_k=(kA)\bmod M,\qquad A=1504170715041707,\qquad M=4503599627370517,$$

ve kalanlar $\{0,1,\dots,M-1\}$ kümesinden alınır. Bir Eulercoin, kendisinden önce gelen tüm terimlerden daha küçük olan terimdir:

$$r_k<\min_{1\le j<k} r_j.$$

İstenen şey tüm Eulercoin değerlerinin toplamıdır. Bunu doğrudan tüm indeksler boyunca taramak aşırı pahalı olacağı için çözüm iki fazlıdır: önce indeks uzayında büyük rekor düşüşleri toplar, sonra modüler ters sayesinde değer uzayında kalan küçük rekorları tamamlar.

Matematiksel Yaklaşım

Temel gözlem, $A$ ile çarpmanın modulo $M$ altında sıfır dışındaki tüm kalıntıları permüte etmesidir. Böylece aynı diziye iki farklı açıdan bakabiliriz: artan indeks $k$ yönünden ve artan değer $v$ yönünden.

Adım 1: Dizi sıfır dışındaki kalıntıların bir permütasyonudur

$\gcd(A,M)=1$ olduğu için

$$kA\equiv \ell A \pmod M$$

eşitliği doğrudan $k\equiv \ell \pmod M$ sonucunu verir. Yani $k\mapsto (kA)\bmod M$ dönüşümü modulo $M$ altında birebirdir ve $k=1,2,\dots,M-1$ iken sıfır dışındaki her kalıntıyı tam bir kez üretir.

Dolayısıyla $v\in\{1,2,\dots,M-1\}$ kümesindeki her değer dizide tam bir kez görünür. Ters fazın çalışmasını sağlayan şey bu teklik özelliğidir.

Adım 2: Bir değerin tek indeksini geri bul

$\gcd(A,M)=1$ olduğundan $A^{-1}\pmod M$ vardır. Sıfır dışındaki herhangi bir $v$ değeri için

$$kA\equiv v \pmod M$$

denkliğinin tek çözümü

$$k(v)\equiv A^{-1}v \pmod M$$

şeklindedir. Böylece küçük bir değerin dizide ne zaman ortaya çıkacağını beklememize gerek kalmaz; doğrudan hangi indekste oluştuğunu hesaplarız.

Adım 3: Eulercoin'leri değer sırasına göre karakterize et

Bir $v$ değeri tam ve ancak kendisinden küçük tüm pozitif değerlerden daha erken görünüyorsa Eulercoin olur. Eulercoin kümesini $\mathcal{E}$ ile gösterirsek

$$v\in\mathcal{E}\iff k(v)<\min_{1\le u<v} k(u).$$

Bunun bir yönü açıktır: eğer $u<v$ olan daha küçük bir değer daha önce görünmüşse, $v$ yeni bir rekor minimum olamaz. Tersi de doğrudur: kendisinden küçük tüm değerler daha sonra geliyorsa, $v$'den önce gelen her terim ondan büyüktür; o halde $v$ gerçekten yeni minimumdur.

Bu nedenle Eulercoin'ler, değerler artan sırada taranırken $k(1),k(2),k(3),\dots$ indeks dizisinin rekor minimumlarıdır.

Adım 4: Büyük Eulercoin'leri ileri taramayla yakala

Uygulamalar yine de işe indeks sırasından başlar. $r_1=A$ ile başlayıp diziyi birer modüler toplama ile ilerletirler:

$$r_{k+1}=\begin{cases} r_k+A,& r_k+A<M,\\ r_k+A-M,& r_k+A\ge M. \end{cases}$$

Yeni terim mevcut rekor minimumdan küçükse bu bir Eulercoin'dir ve toplama eklenir. Böylece değeri hâlâ büyük olan erken Eulercoin'ler verimli biçimde toplanır.

İleri faz, mevcut Eulercoin $20{,}000{,}000$'ın altına düştüğünde durur. Bu son ileri faz Eulercoin'ine $B$ diyelim. Daha sonra gelecek her Eulercoin mutlaka $B$'den küçük olacağından geriye yalnızca $1,2,\dots,B-1$ aralığı kalır.

Adım 5: Kalan küçük değerleri ters taramayla tamamla

Şimdi $v=1,2,\dots,B-1$ değerleri taranır. Her $v$ için tek konum $k(v)\equiv A^{-1}v\pmod M$ hesaplanır ve şimdiye kadar görülen en küçük indeks saklanır.

Eğer yeni indeks bu koşan minimumdan da küçükse, Adım 3'e göre $v$ bir Eulercoin'dir ve toplama eklenmelidir. Aksi halde daha küçük bir değer zaten daha erken görünmüştür; bu durumda $v$ Eulercoin değildir.

Bu bölme tamdır; sezgisel bir kesme değildir. İleri faz değeri en az $B$ olan tüm Eulercoin'leri bulmuştur, ters faz ise $B$'nin altındaki tüm pozitif değerleri sınar. İki küme çakışmaz ve birlikte tüm Eulercoin'leri verir.

Çözümlü Örnek

Gerçek sabitlerle ilk terim

$$r_1=A=1504170715041707.$$

İkinci terim

$$r_2=2A\bmod M=3008341430083414$$

olur; bu değer $r_1$'den büyük olduğu için Eulercoin değildir.

$k=3$ için

$$3A=4512512145125121=M+8912517754604,$$

dolayısıyla

$$r_3=8912517754604.$$

Şimdi

$$8912517754604<1504170715041707$$

olduğundan üçüncü terim ikinci Eulercoin olur. Değer uzayındaki bakış aynı olayı şöyle açıklar: bu değerin indeksi, kendisinden küçük her pozitif değerin indeksinden küçüktür; bu yüzden tam o noktada yeni rekor minimum oluşur.

Kod Nasıl Çalışır

C++, Python ve Java uygulamalarının üçü de aynı iki fazlı düzeni izler. Önce modüler diziyi $A$ değerinde başlatırlar, şimdiye kadarki en küçük terimi izlerler ve her yeni sıkı düşüşü toplama eklerler. Bu döngü, mevcut Eulercoin $20{,}000{,}000$'ın altına inince biter.

Daha sonra genişletilmiş Öklid algoritması ile $A$'nın modulo $M$'ye göre çarpımsal tersi hesaplanır. Ardından $1\le v<B$ aralığındaki aday değerler taranır, her biri tek dizin konumuna modüler çarpma ile çevrilir ve sadece bu geri kazanılmış indeks şimdiye kadarki en küçük indeks olduğunda $v$ toplama eklenir.

Aritmetik ayrıntılar dillere göre biraz değişir, fakat matematik aynıdır. C++ sürümü modulo işleminden önce 128 bitlik ara çarpım kullanır, Python keyfi büyüklükte tamsayılara dayanır, Java sürümü ise modüler çarpım için büyük tamsayı aritmetiği kullanır.

Karmaşıklık Analizi

$K_f$ ilk fazın kaç ileri adım sürdüğünü, $B$ de bu fazda bulunan son Eulercoin'i göstersin. Birinci faz $O(K_f)$, ikinci faz $O(B)$ zaman alır ve her ikisi de sabit ek bellek kullanır. Dolayısıyla toplam karmaşıklık

$$O(K_f+B)$$

zaman ve $O(1)$ ek alan olur. Bu, diziyi $k=M-1$'e kadar körlemesine taramaktan çok daha küçüktür.

Dipnotlar ve Kaynaklar

Problem sayfası: Project Euler 700
Modüler çarpımsal ters: Wikipedia - Modular multiplicative inverse
Genişletilmiş Öklid algoritması: Wikipedia - Extended Euclidean algorithm
Modüler aritmetik: Wikipedia - Modular arithmetic
Tam kalıntı sistemi: Wikipedia - Complete residue system

Resumen del Problema

Se define la sucesión

$$r_k=(kA)\bmod M,\qquad A=1504170715041707,\qquad M=4503599627370517,$$

donde los residuos se toman en $\{0,1,\dots,M-1\}$. Un Eulercoin es un término que es menor que todos los anteriores:

$$r_k<\min_{1\le j<k} r_j.$$

La tarea consiste en sumar todos los Eulercoins. Un recorrido ingenuo por todos los índices posibles sería demasiado grande, así que la solución usa dos fases: primero recoge los mínimos récord grandes en orden de índice y después reconstruye los mínimos récord pequeños en orden de valor mediante un inverso modular.

Enfoque Matemático

La observación decisiva es que multiplicar por $A$ permuta los residuos no nulos módulo $M$. Eso permite estudiar la misma sucesión desde dos direcciones complementarias: por índice creciente $k$ y por valor creciente $v$.

Paso 1: La sucesión es una permutación de los residuos no nulos

Como $\gcd(A,M)=1$, la congruencia

$$kA\equiv \ell A \pmod M$$

implica $k\equiv \ell \pmod M$. Por tanto, la aplicación $k\mapsto (kA)\bmod M$ es inyectiva módulo $M$ y, para $k=1,2,\dots,M-1$, recorre cada residuo no nulo exactamente una vez.

Así, cada entero $v\in\{1,2,\dots,M-1\}$ aparece en una posición única de la sucesión. Esa unicidad es la base de la fase inversa.

Paso 2: Recuperar el índice único de un valor

Dado que $\gcd(A,M)=1$, existe el inverso modular $A^{-1}\pmod M$. Para cualquier valor no nulo $v$, la posición en la que aparece es la solución única de

$$kA\equiv v \pmod M,$$

es decir,

$$k(v)\equiv A^{-1}v \pmod M.$$

Por eso no hace falta esperar a que un valor pequeño aparezca en una simulación larguísima: se puede calcular directamente en qué índice ocurre.

Paso 3: Caracterizar los Eulercoins por orden de valor

Un valor $v$ es un Eulercoin si y solo si aparece antes que cualquier valor positivo menor. Si $\mathcal{E}$ denota el conjunto de los Eulercoins, entonces

$$v\in\mathcal{E}\iff k(v)<\min_{1\le u<v} k(u).$$

Una dirección es inmediata: si un valor menor $u<v$ ya apareció antes, entonces $v$ no puede ser un nuevo mínimo récord. La recíproca también vale: si todos los valores menores aparecen después, entonces todos los términos anteriores son mayores que $v$, así que $v$ sí es un nuevo mínimo.

En consecuencia, los Eulercoins son exactamente los mínimos récord de la sucesión de índices $k(1),k(2),k(3),\dots$ cuando se recorren los valores en orden ascendente.

Paso 4: Encontrar los Eulercoins grandes con un barrido directo

Las implementaciones comienzan de todos modos por orden de índice. Partiendo de $r_1=A$, avanzan la sucesión con una sola suma modular en cada paso:

$$r_{k+1}=\begin{cases} r_k+A,& r_k+A<M,\\ r_k+A-M,& r_k+A\ge M. \end{cases}$$

Cada vez que el nuevo término queda por debajo del mínimo récord actual, ese término es un Eulercoin y se añade a la suma. Así se capturan de forma eficiente los Eulercoins tempranos, que todavía tienen valores grandes.

La fase directa se detiene cuando el Eulercoin actual baja de $20{,}000{,}000$. Si llamamos $B$ a ese último Eulercoin hallado en la fase directa, entonces cualquier Eulercoin posterior tiene que ser menor que $B$, por lo que solo quedan por revisar los valores $1,2,\dots,B-1$.

Paso 5: Completar los valores pequeños con un barrido inverso

Ahora se recorren los valores $v=1,2,\dots,B-1$. Para cada uno se calcula la posición única $k(v)\equiv A^{-1}v\pmod M$ y se mantiene el menor índice visto hasta ese momento.

Si el nuevo índice es menor que ese mínimo acumulado, entonces $v$ es un Eulercoin por el criterio del Paso 3 y debe sumarse. En caso contrario, ya existe un valor más pequeño que aparece antes, así que $v$ no es un Eulercoin.

Esta división es exacta, no heurística. La fase directa ya encontró todos los Eulercoins con valor al menos $B$, y la fase inversa comprueba todos los valores positivos menores que $B$. Ambos conjuntos son disjuntos y juntos cubren todos los Eulercoins.

Ejemplo Desarrollado

Con las constantes reales, el primer término es

$$r_1=A=1504170715041707.$$

El segundo término vale

$$r_2=2A\bmod M=3008341430083414,$$

que es mayor que $r_1$, por lo que no es un Eulercoin.

Para $k=3$,

$$3A=4512512145125121=M+8912517754604,$$

y por tanto

$$r_3=8912517754604.$$

Como

$$8912517754604<1504170715041707,$$

el tercer término es el segundo Eulercoin. La visión inversa describe exactamente lo mismo: ese valor tiene un índice menor que cualquier valor positivo inferior, y por eso se convierte en un nuevo mínimo récord.

Cómo Funciona el Código

Las implementaciones en C++, Python y Java siguen el mismo plan de dos fases. Primero inicializan la sucesión modular en $A$, mantienen el menor valor visto hasta el momento y añaden a la suma cada descenso estricto. Ese bucle termina cuando el Eulercoin actual cae por debajo de $20{,}000{,}000$.

Después calculan el inverso modular de $A$ módulo $M$ mediante el algoritmo extendido de Euclides. A continuación recorren los candidatos restantes $1\le v<B$, convierten cada valor en su índice único con una multiplicación modular y suman $v$ solamente cuando ese índice recuperado es un nuevo mínimo entre todos los índices vistos en la fase inversa.

Los detalles aritméticos cambian ligeramente según el lenguaje, pero la matemática es la misma. La implementación en C++ usa un producto intermedio de 128 bits antes de reducir módulo $M$, Python aprovecha enteros de precisión arbitraria y la implementación en Java emplea aritmética de enteros grandes para el producto modular.

Análisis de Complejidad

Sea $K_f$ el número de iteraciones de la fase directa y sea $B$ el último Eulercoin encontrado allí. La primera fase cuesta $O(K_f)$, la segunda cuesta $O(B)$, y ambas usan memoria extra constante. En consecuencia, la complejidad total es

$$O(K_f+B)$$

en tiempo y $O(1)$ en espacio adicional. Para este problema eso es muchísimo menor que recorrer la sucesión hasta $k=M-1$.

Notas y Referencias

Página del problema: Project Euler 700
Inverso multiplicativo modular: Wikipedia - Modular multiplicative inverse
Algoritmo extendido de Euclides: Wikipedia - Extended Euclidean algorithm
Aritmética modular: Wikipedia - Modular arithmetic
Sistema completo de residuos: Wikipedia - Complete residue system

问题概述

定义数列

$$r_k=(kA)\bmod M,\qquad A=1504170715041707,\qquad M=4503599627370517,$$

其中余数取自 $\{0,1,\dots,M-1\}$。如果某一项严格小于它之前出现过的所有项，那么这一项就是一个 Eulercoin：

$$r_k<\min_{1\le j<k} r_j.$$

题目要求把所有 Eulercoin 相加。直接按索引一路枚举到极大范围显然不可行，因此实现采用两阶段思路：先在索引顺序上收集较大的纪录最小值，再借助模逆元在数值顺序上补齐剩余的较小纪录最小值。

数学方法

最关键的事实是：因为 $A$ 与 $M$ 互素，所以乘以 $A$ 会把模 $M$ 的所有非零剩余重新排列一遍。于是同一个问题可以从两个互补角度来观察：一个是按索引 $k$ 增长来扫描，另一个是按取值 $v$ 增长来扫描。

步骤 1：该数列会遍历所有非零剩余一次且仅一次

由于 $\gcd(A,M)=1$，如果有

$$kA\equiv \ell A \pmod M,$$

那么必然推出 $k\equiv \ell \pmod M$。这说明映射 $k\mapsto (kA)\bmod M$ 在模 $M$ 意义下是单射，因此当 $k=1,2,\dots,M-1$ 时，它恰好枚举出每一个非零剩余。

换句话说，任意 $v\in\{1,2,\dots,M-1\}$ 都会在数列中出现，而且只出现一次。后面的反向阶段之所以成立，正是因为这个位置是唯一的。

步骤 2：由数值反推出它唯一对应的索引

既然 $\gcd(A,M)=1$，就存在模逆元 $A^{-1}\pmod M$。因此对于任意非零值 $v$，方程

$$kA\equiv v \pmod M$$

有唯一解

$$k(v)\equiv A^{-1}v \pmod M.$$

这意味着我们不必在一条极长的前向模拟中等待某个小值出现，而是可以直接算出这个值会在第几个位置出现。

步骤 3：按数值顺序刻画 Eulercoin

一个值 $v$ 是 Eulercoin，当且仅当它出现得比所有更小的正值都更早。若用 $\mathcal{E}$ 表示 Eulercoin 的集合，那么

$$v\in\mathcal{E}\iff k(v)<\min_{1\le u<v} k(u).$$

必要性很直接：如果某个更小的值 $u<v$ 已经更早出现，那么 $v$ 就不可能成为新的严格最小值。充分性同样成立：如果所有更小的正值都要在更后面才出现，那么在 $v$ 出现之前出现过的所有值都比它大，所以它必然是新的纪录最小值。

因此，随着 $v=1,2,3,\dots$ 递增扫描时，Eulercoin 正好对应于索引序列 $k(1),k(2),k(3),\dots$ 的纪录最小值。

步骤 4：先用前向扫描收集较大的 Eulercoin

实现仍然从索引顺序开始。以 $r_1=A$ 为起点，每一步只做一次模加法：

$$r_{k+1}=\begin{cases} r_k+A,& r_k+A<M,\\ r_k+A-M,& r_k+A\ge M. \end{cases}$$

每当新得到的项严格小于当前最小值，它就是一个新的 Eulercoin，需要加入总和。这一阶段可以高效地抓住前面那些数值仍然很大的 Eulercoin。

当前向阶段把纪录最小值降到 $20{,}000{,}000$ 以下时就停止。设这一阶段最后得到的 Eulercoin 为 $B$。那么之后出现的 Eulercoin 必然都小于 $B$，于是剩余候选值只可能落在 $1,2,\dots,B-1$ 之中。

步骤 5：再用反向数值扫描补齐较小的 Eulercoin

接下来按 $v=1,2,\dots,B-1$ 扫描所有剩余候选值。对每个 $v$，利用 $k(v)\equiv A^{-1}v\pmod M$ 算出它在数列中的唯一位置，并维护到目前为止见过的最小索引。

如果新的索引比这个运行中的最小索引还小，那么根据步骤 3，$v$ 就是一个 Eulercoin，应当加入总和。反之，如果它的索引没有刷新这个最小值，那么一定已经存在某个更小的值更早出现过，所以 $v$ 不是 Eulercoin。

这个切分是精确的，不是经验性的近似。前向阶段已经找到了所有取值不小于 $B$ 的 Eulercoin，而反向阶段逐一检查所有小于 $B$ 的正值。两部分互不重叠，合在一起刚好覆盖全部 Eulercoin。

例题演算

使用题目中的实际常数时，第一项为

$$r_1=A=1504170715041707.$$

第二项是

$$r_2=2A\bmod M=3008341430083414,$$

它大于 $r_1$，因此不是 Eulercoin。

当 $k=3$ 时，

$$3A=4512512145125121=M+8912517754604,$$

所以

$$r_3=8912517754604.$$

由于

$$8912517754604<1504170715041707,$$

第三项就是第二个 Eulercoin。从反向角度看，这个值之所以会成为新的纪录最小值，是因为它对应的索引比所有更小正值的索引都更靠前。

代码如何工作

C++、Python 和 Java 三个实现都遵循同样的两阶段方案。首先，它们把数列初始化为 $A$，维护当前为止最小的项，并在每次出现严格下降时把该值加入累计和。这个循环会在当前 Eulercoin 下降到 $20{,}000{,}000$ 以下时结束。

随后，程序利用扩展欧几里得算法求出 $A$ 关于模 $M$ 的逆元。再之后，程序枚举剩余候选值 $1\le v<B$，用一次模乘把每个值转换成它唯一对应的索引；只有当这个索引刷新了反向扫描阶段当前最小索引时，该值才会被加入总和。

不同语言在整数运算细节上略有差异，但数学结构完全相同。C++ 实现用 128 位中间乘积再取模，Python 依赖任意精度整数，而 Java 实现则用大整数完成模乘。

复杂度分析

设前向阶段执行了 $K_f$ 次迭代，且该阶段最后一个 Eulercoin 为 $B$。那么第一阶段复杂度是 $O(K_f)$，第二阶段复杂度是 $O(B)$，额外空间在两阶段中都保持常数级。因此总复杂度为

$$O(K_f+B)$$

时间和 $O(1)$ 额外空间。相比把索引一直枚举到 $M-1$，这个代价小得多。

注释与参考资料

题目页面：Project Euler 700
模乘法逆元：Wikipedia - Modular multiplicative inverse
扩展欧几里得算法：Wikipedia - Extended Euclidean algorithm
模运算：Wikipedia - Modular arithmetic
完全剩余系：Wikipedia - Complete residue system

Краткое описание задачи

Рассматривается последовательность

$$r_k=(kA)\bmod M,\qquad A=1504170715041707,\qquad M=4503599627370517,$$

где остатки берутся из $\{0,1,\dots,M-1\}$. Значение называется Eulercoin, если оно строго меньше всех предыдущих членов:

$$r_k<\min_{1\le j<k} r_j.$$

Нужно найти сумму всех Eulercoin. Полный прямой перебор по индексам был бы слишком велик, поэтому решение делит задачу на две части: сначала собирает большие рекордные минимумы в прямом порядке по индексам, а затем восстанавливает оставшиеся малые рекордные минимумы в порядке значений с помощью модульного обратного элемента.

Математический подход

Ключевое наблюдение состоит в том, что умножение на $A$ переставляет все ненулевые вычеты по модулю $M$. Поэтому одну и ту же последовательность удобно рассматривать с двух сторон: по возрастанию индекса $k$ и по возрастанию значения $v$.

Шаг 1: Последовательность является перестановкой ненулевых вычетов

Так как $\gcd(A,M)=1$, из сравнения

$$kA\equiv \ell A \pmod M$$

следует $k\equiv \ell \pmod M$. Значит, отображение $k\mapsto (kA)\bmod M$ инъективно по модулю $M$, и при $k=1,2,\dots,M-1$ оно проходит каждый ненулевой вычет ровно один раз.

Следовательно, каждое число $v\in\{1,2,\dots,M-1\}$ встречается в последовательности в одной-единственной позиции. Именно эта однозначность делает возможной обратную фазу.

Шаг 2: Восстановить единственный индекс по значению

Поскольку $\gcd(A,M)=1$, существует обратный элемент $A^{-1}\pmod M$. Поэтому для любого ненулевого значения $v$ у сравнения

$$kA\equiv v \pmod M$$

есть единственное решение

$$k(v)\equiv A^{-1}v \pmod M.$$

Итак, ждать появления малого значения в очень длинной прямой симуляции не нужно: можно сразу вычислить, на каком индексе это значение стоит.

Шаг 3: Критерий Eulercoin в порядке значений

Значение $v$ является Eulercoin тогда и только тогда, когда оно появляется раньше любого меньшего положительного значения. Если через $\mathcal{E}$ обозначить множество Eulercoin, то

$$v\in\mathcal{E}\iff k(v)<\min_{1\le u<v} k(u).$$

Необходимость очевидна: если некоторое меньшее значение $u<v$ уже встретилось раньше, то $v$ не может быть новым рекордным минимумом. Обратное утверждение тоже верно: если все меньшие значения появляются позже, то каждый более ранний член последовательности больше $v$, следовательно $v$ действительно является новым минимумом.

Значит, Eulercoin — это в точности рекордные минимумы последовательности индексов $k(1),k(2),k(3),\dots$, если сканировать значения по возрастанию.

Шаг 4: Собрать большие Eulercoin прямым проходом

Тем не менее реализации начинают с прямого прохода по индексам. Начиная с $r_1=A$, они переходят к следующему члену одной модульной прибавкой:

$$r_{k+1}=\begin{cases} r_k+A,& r_k+A<M,\\ r_k+A-M,& r_k+A\ge M. \end{cases}$$

Каждый раз, когда новый член оказывается меньше текущего рекордного минимума, найден Eulercoin, и его значение добавляется к сумме. Так удобно собрать ранние Eulercoin, которые еще достаточно велики по величине.

Прямая фаза останавливается, когда текущий Eulercoin становится меньше $20{,}000{,}000$. Обозначим последний найденный в этой фазе Eulercoin через $B$. Любой более поздний Eulercoin обязан быть меньше $B$, так что после этого остаются только значения $1,2,\dots,B-1$.

Шаг 5: Достроить малые значения обратным проходом

Теперь перебираются значения $v=1,2,\dots,B-1$. Для каждого вычисляется его единственная позиция $k(v)\equiv A^{-1}v\pmod M$, а также поддерживается минимальный индекс среди всех уже просмотренных значений.

Если новый индекс меньше этого текущего минимума, то по критерию из шага 3 значение $v$ является Eulercoin и должно быть добавлено. Иначе уже существует меньшее значение, которое появляется раньше, и $v$ Eulercoin не является.

Такое разделение является точным, а не эвристическим. Прямая фаза уже нашла все Eulercoin со значением не меньше $B$, а обратная фаза проверяет все положительные значения ниже $B$. Эти два множества не пересекаются и вместе дают полный ответ.

Разобранный пример

С реальными константами первый член равен

$$r_1=A=1504170715041707.$$

Второй член равен

$$r_2=2A\bmod M=3008341430083414,$$

то есть он больше, чем $r_1$, и потому не является Eulercoin.

Для $k=3$ получаем

$$3A=4512512145125121=M+8912517754604,$$

следовательно,

$$r_3=8912517754604.$$

Так как

$$8912517754604<1504170715041707,$$

третий член является вторым Eulercoin. С точки зрения обратного критерия происходит то же самое: этот value имеет индекс меньше, чем любой положительный value ниже него, и именно поэтому становится новым рекордным минимумом.

Как работает код

Реализации на C++, Python и Java используют один и тот же двухфазный план. Сначала они инициализируют последовательность значением $A$, поддерживают текущий наименьший встретившийся член и добавляют к сумме каждое строгое уменьшение. Этот цикл заканчивается, когда текущий Eulercoin падает ниже $20{,}000{,}000$.

Затем вычисляется обратный элемент к $A$ по модулю $M$ с помощью расширенного алгоритма Евклида. После этого программы перебирают оставшиеся кандидаты $1\le v<B$, переводят каждое значение в его единственный индекс с помощью модульного умножения и добавляют $v$ только тогда, когда восстановленный индекс оказывается новым минимумом среди всех индексов, увиденных в обратной фазе.

Технические детали арифметики немного различаются по языкам, но математическая схема одна и та же. В C++ используется промежуточное произведение шириной 128 бит перед взятием по модулю, Python опирается на целые числа произвольной длины, а Java использует арифметику больших целых для модульного произведения.

Анализ сложности

Пусть $K_f$ — число итераций прямой фазы, а $B$ — последний Eulercoin, найденный в ней. Тогда первая фаза стоит $O(K_f)$, вторая — $O(B)$, и обе используют только постоянный дополнительный объём памяти. Следовательно, общая сложность равна

$$O(K_f+B)$$

по времени и $O(1)$ по памяти. Для данной задачи это несравнимо лучше, чем прямой просмотр последовательности вплоть до $k=M-1$.

Примечания и ссылки

Страница задачи: Project Euler 700
Модульный обратный элемент: Wikipedia - Modular multiplicative inverse
Расширенный алгоритм Евклида: Wikipedia - Extended Euclidean algorithm
Модульная арифметика: Wikipedia - Modular arithmetic
Полная система вычетов: Wikipedia - Complete residue system

ملخص المسألة

تُعرَّف المتتالية

$$r_k=(kA)\bmod M,\qquad A=1504170715041707,\qquad M=4503599627370517,$$

بحيث تؤخذ البواقي من المجموعة $\{0,1,\dots,M-1\}$. وتُسمّى القيمة Eulercoin إذا كانت أصغر من كل القيم التي سبقتها:

$$r_k<\min_{1\le j<k} r_j.$$

المطلوب هو إيجاد مجموع جميع قيم Eulercoin. المسح المباشر على كل الفهارس الممكنة سيكون هائلًا جدًا، لذلك تعتمد الفكرة على مرحلتين: أولًا جمع القيم الدنيا القياسية الكبيرة في ترتيب الفهارس، ثم استرجاع القيم الدنيا القياسية الصغيرة المتبقية في ترتيب القيم باستخدام المعكوس الضربي المعياري.

المنهج الرياضي

الفكرة الحاسمة هي أن الضرب في $A$ يعيد ترتيب جميع البواقي غير الصفرية بترديد $M$. وهذا يسمح بدراسة المتتالية نفسها من زاويتين متكاملتين: بترتيب الفهرس $k$ وبترتيب القيمة $v$.

الخطوة 1: المتتالية تبديل لجميع البواقي غير الصفرية

بما أن $\gcd(A,M)=1$، فإن العلاقة

$$kA\equiv \ell A \pmod M$$

تؤدي مباشرة إلى $k\equiv \ell \pmod M$. لذلك يكون التحويل $k\mapsto (kA)\bmod M$ أحاديًا بترديد $M$، ومع $k=1,2,\dots,M-1$ فإنه يمر على كل باقي غير صفري مرة واحدة بالضبط.

إذن كل عدد $v\in\{1,2,\dots,M-1\}$ يظهر في المتتالية في موضع وحيد فقط. وهذه الفرادة هي ما يجعل المرحلة العكسية ممكنة.

الخطوة 2: استرجاع الفهرس الوحيد انطلاقًا من القيمة

بما أن $\gcd(A,M)=1$، يوجد معكوس ضربي $A^{-1}\pmod M$. ولذلك فإن الموضع الذي تظهر فيه أي قيمة غير صفرية $v$ هو الحل الوحيد للمعادلة

$$kA\equiv v \pmod M,$$

أي

$$k(v)\equiv A^{-1}v \pmod M.$$

وهكذا لا نحتاج إلى انتظار ظهور قيمة صغيرة داخل محاكاة أمامية طويلة جدًا؛ بل نستطيع حساب موضع ظهورها مباشرة.

الخطوة 3: توصيف Eulercoin بحسب ترتيب القيم

تكون القيمة $v$ Eulercoin إذا وفقط إذا ظهرت قبل كل قيمة موجبة أصغر منها. وإذا رمزنا لمجموعة قيم Eulercoin بالرمز $\mathcal{E}$، فإن

$$v\in\mathcal{E}\iff k(v)<\min_{1\le u<v} k(u).$$

أحد الاتجاهين واضح: إذا ظهرت قيمة أصغر $u<v$ قبلها، فلا يمكن أن تكون $v$ حدًا أدنى جديدًا. والاتجاه العكسي صحيح أيضًا: إذا كانت كل القيم الأصغر تظهر لاحقًا، فكل القيم السابقة على $v$ أكبر منها، وبالتالي تكون $v$ حدًا أدنى جديدًا فعلًا.

إذن قيم Eulercoin هي بالضبط القيم التي تصنع أرقامًا دنيا قياسية في متتالية الفهارس $k(1),k(2),k(3),\dots$ عندما نمسح القيم تصاعديًا.

الخطوة 4: جمع القيم الكبيرة بمسح أمامي

تبدأ التطبيقات مع ذلك بترتيب الفهارس. انطلاقًا من $r_1=A$، يتم تحديث المتتالية بجمع معياري واحد في كل خطوة:

$$r_{k+1}=\begin{cases} r_k+A,& r_k+A<M,\\ r_k+A-M,& r_k+A\ge M. \end{cases}$$

كلما كانت القيمة الجديدة أصغر من أصغر قيمة سابقة، فهي Eulercoin وتُضاف إلى المجموع. وبهذا نلتقط سريعًا قيم Eulercoin المبكرة التي ما تزال كبيرة نسبيًا.

تتوقف المرحلة الأمامية عندما تهبط قيمة Eulercoin الحالية تحت $20{,}000{,}000$. ولنسمِّ آخر Eulercoin وُجد في هذه المرحلة بالرمز $B$. عندئذٍ لا يمكن لأي Eulercoin لاحق أن يكون أكبر من أو مساويًا لـ $B$، وبالتالي تبقى فقط القيم $1,2,\dots,B-1$ للفحص.

الخطوة 5: إكمال القيم الصغيرة بمسح عكسي

الآن نمر على القيم $v=1,2,\dots,B-1$. ولكل قيمة نحسب موضعها الوحيد $k(v)\equiv A^{-1}v\pmod M$، ونحافظ على أصغر فهرس شوهد حتى تلك اللحظة.

إذا كان الفهرس الجديد أصغر من هذا الحد الأدنى الجاري، فإن $v$ تكون Eulercoin وفقًا لمعيار الخطوة 3 ويجب إضافتها. أما إذا لم يكسر هذا الفهرس الحد الأدنى الجاري، فهذا يعني أن هناك قيمة أصغر ظهرت قبله، وبالتالي ليست $v$ Eulercoin.

هذا التقسيم دقيق تمامًا وليس مجرد حيلة تقريبية. فالمرحلة الأمامية تكون قد جمعت جميع قيم Eulercoin التي لا تقل عن $B$، بينما تفحص المرحلة العكسية كل القيم الموجبة الأصغر من $B$. والمجموعتان منفصلتان معًا وتغطيان كل Eulercoin.

مثال محلول

باستخدام الثوابت الفعلية، يكون الحد الأول

$$r_1=A=1504170715041707.$$

أما الحد الثاني فهو

$$r_2=2A\bmod M=3008341430083414,$$

وهو أكبر من $r_1$، لذلك ليس Eulercoin.

وعند $k=3$ نحصل على

$$3A=4512512145125121=M+8912517754604,$$

ومن ثم

$$r_3=8912517754604.$$

وبما أن

$$8912517754604<1504170715041707,$$

فإن الحد الثالث هو ثاني Eulercoin. ومن زاوية الفحص العكسي، فهذه القيمة تمتلك فهرسًا أصغر من فهارس كل القيم الموجبة الأصغر منها، ولهذا تظهر كحد أدنى قياسي جديد.

كيف تعمل الشيفرة

تتبع تطبيقات C++ وPython وJava الخطة نفسها ذات المرحلتين. فهي تبدأ المتتالية عند $A$، وتحتفظ بأصغر قيمة شوهدت حتى اللحظة، وتضيف كل انخفاض صارم إلى المجموع التراكمي. وتنتهي هذه الحلقة عندما تصبح قيمة Eulercoin الحالية أصغر من $20{,}000{,}000$.

بعد ذلك تُحسب القيمة العكسية الضربية لـ $A$ بترديد $M$ بواسطة خوارزمية إقليدس الموسعة. ثم تُمسح القيم المرشحة المتبقية $1\le v<B$، وتُحوَّل كل قيمة إلى فهرسها الوحيد بعملية ضرب معيارية واحدة، ولا تُضاف $v$ إلا عندما يكون هذا الفهرس المستعاد أصغر من كل فهرس سبق رؤيته في المرحلة العكسية.

قد تختلف تفاصيل الحساب العددي قليلًا من لغة إلى أخرى، لكن البنية الرياضية واحدة. فتنفيذ C++ يستخدم حاصل ضرب وسيطًا بعرض 128 بت قبل الاختزال بترديد $M$، وPython تعتمد على الأعداد الصحيحة ذات الدقة غير المحدودة، أما Java فتستخدم حساب الأعداد الصحيحة الكبيرة في الضرب المعياري.

تحليل التعقيد

إذا رمزنا بعدد خطوات المرحلة الأمامية بالرمز $K_f$، ورمزنا لآخر Eulercoin يظهر فيها بالرمز $B$، فإن كلفة المرحلة الأولى هي $O(K_f)$، وكلفة المرحلة الثانية هي $O(B)$، بينما تبقى الذاكرة الإضافية ثابتة في المرحلتين. لذلك يكون التعقيد الكلي

$$O(K_f+B)$$

زمنًا مع $O(1)$ مساحة إضافية. وهذا أصغر بكثير من تتبع المتتالية مباشرة حتى $k=M-1$.

حواشٍ ومراجع

صفحة المسألة: Project Euler 700
المعكوس الضربي المعياري: Wikipedia - Modular multiplicative inverse
خوارزمية إقليدس الموسعة: Wikipedia - Extended Euclidean algorithm
الحساب المعياري: Wikipedia - Modular arithmetic
نظام البواقي الكامل: Wikipedia - Complete residue system