Let \(p_1=2,p_2=3,p_3=5,\dots\) be the primes in increasing order. For each \(i\ge 1\), define \(A_i\) as the smallest positive integer satisfying
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
The problem asks for the sum \(S(n)\) of all primes \(q \le n\) that divide at least one of these values \(A_i\). The sequence grows extremely fast, so the solution cannot build large integers naively. Instead, it extends the Chinese Remainder system one prime at a time and tracks only residues.
The entire method rests on viewing each \(A_i\) as one stage of an incremental Chinese Remainder Theorem construction.
For each stage \(i\), let
$$M_i=\prod_{k=1}^{i} p_k.$$
Because the moduli \(p_1,p_2,\dots,p_i\) are pairwise coprime, the Chinese Remainder Theorem gives a unique residue class modulo \(M_i\) satisfying
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
We may choose the least positive representative as \(A_i\). The first stage is immediate:
$$A_1=1,\qquad M_1=2.$$
So the problem becomes: as this CRT solution is extended from \(i\) to \(i+1\), which later primes ever divide the current representative?
Suppose \(q=p_j\) is the \(j\)-th prime. Once \(q\) has entered the system, every later term satisfies
$$A_i \equiv j \pmod{q}\qquad(i \ge j).$$
But \(j \lt p_j=q\), so this residue is never \(0\) modulo \(q\). Therefore \(q\) can divide some \(A_i\) only before its own congruence has been imposed, that is, only for stages \(i \lt j\).
This observation is crucial: at stage \(i\), it is enough to test only the primes \(p_{i+1},p_{i+2},\dots\). Any prime already built into the CRT system can no longer be a divisor.
Assume \(A_i\) is known modulo \(M_i\). Every number preserving the first \(i\) congruences has the form
$$A_i + M_i t,$$
for some integer \(t\). To create \(A_{i+1}\), we impose the new condition
$$A_{i+1} \equiv i+1 \pmod{p_{i+1}}.$$
Substituting \(A_{i+1}=A_i+M_i t\) gives
$$A_i + M_i t \equiv i+1 \pmod{p_{i+1}}.$$
Since \(p_{i+1}\) is a new prime, it is coprime to \(M_i\), so \(M_i\) has a modular inverse modulo \(p_{i+1}\). Hence
$$t \equiv (i+1-A_i)\,M_i^{-1} \pmod{p_{i+1}}.$$
This determines the next CRT state uniquely modulo \(M_{i+1}=M_i p_{i+1}\).
The values \(A_i\) become enormous, but divisibility by a prime \(q\) depends only on the residue \(A_i \bmod q\). So for every prime \(q \le n\), the implementation stores two running residues:
$$a_i(q)\equiv A_i \pmod{q},\qquad m_i(q)\equiv M_i \pmod{q}.$$
After computing the correction \(t\) from the previous step, these residues update by
$$a_{i+1}(q)\equiv a_i(q)+m_i(q)t \pmod{q},$$
$$m_{i+1}(q)\equiv m_i(q)\,p_{i+1} \pmod{q}.$$
Now the hit test is exact and cheap:
$$q \mid A_i \iff a_i(q)=0.$$
Each prime is marked at most once, so the final answer is simply the sum of all marked primes.
The checkpoint in the implementations is \(S(50)=69\). The first stages show why.
Start with
$$A_1=1.$$
No later prime divides \(1\).
For the next prime \(3\), solve
$$A_2=1+2t,\qquad 1+2t \equiv 2 \pmod{3},$$
so \(t \equiv 2 \pmod{3}\) and therefore
$$A_2=5.$$
This already gives a hit, because \(5\mid A_2\).
Next, extend to prime \(5\):
$$A_3=5+6t,\qquad 5+6t \equiv 3 \pmod{5}.$$
Since \(6 \equiv 1 \pmod{5}\), we get \(t \equiv 3\), so
$$A_3=23.$$
Thus \(23\mid A_3\), giving the second contributing prime.
For the next step,
$$A_4=23+30t,\qquad 23+30t \equiv 4 \pmod{7},$$
which yields
$$A_4=53.$$
This does not contribute to \(S(50)\) because \(53 \gt 50\). Continuing the same residue updates eventually reaches
$$A_{10}=5765999453,$$
and this value is divisible by \(41\). No other prime up to \(50\) ever hits, so
$$S(50)=5+23+41=69.$$
The C++, Python, and Java implementations first generate all primes up to the requested limit with a standard sieve. They then initialize the CRT state at the first prime, corresponding to \(A_1=1\) and \(M_1=2\).
From that point on, the implementation never needs the full huge integer \(A_i\). Instead, it keeps one array containing the current residue of the CRT solution modulo each prime up to the limit, and a second array containing the current residue of the running modulus \(M_i\) modulo those same primes.
At each stage, the implementation scans only the primes that have not yet entered the CRT system. If the stored residue is \(0\), that prime divides the current \(A_i\) and is marked for inclusion in the final sum. Then the code computes the unique correction factor \(t\) modulo the next prime using a modular inverse obtained from the extended Euclidean algorithm, and updates both residue arrays in parallel. After all stages, it adds the marked primes.
Let \(m=\pi(n)\), the number of primes up to \(n\). The sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. The main CRT process performs a triangular number of divisibility checks and residue updates, namely about
$$\sum_{i=1}^{m-1}(m-i)=\frac{m(m-1)}{2},$$
so the dominant cost is \(O(m^2)\) time. The stored prime list, the two residue arrays, and the hit markers together use \(O(m)\) additional memory.
Seien \(p_1=2,p_2=3,p_3=5,\dots\) die Primzahlen in aufsteigender Reihenfolge. Für jedes \(i\ge 1\) sei \(A_i\) die kleinste positive Zahl mit
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
Gesucht ist \(S(n)\), also die Summe aller Primzahlen \(q \le n\), die mindestens einen dieser Werte \(A_i\) teilen. Da die Folge sehr schnell wächst, kann man die Zahlen nicht direkt konstruieren. Die Lösung erweitert stattdessen das CRT-System Schritt für Schritt und verfolgt nur Restklassen.
Der Kern der Methode ist, jedes \(A_i\) als eine Stufe einer inkrementellen CRT-Konstruktion zu betrachten.
Für jede Stufe \(i\) definieren wir
$$M_i=\prod_{k=1}^{i} p_k.$$
Da die Moduli \(p_1,p_2,\dots,p_i\) paarweise teilerfremd sind, liefert der chinesische Restsatz genau eine Restklasse modulo \(M_i\), die
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i)$$
erfüllt. Als \(A_i\) wählen wir den kleinsten positiven Vertreter. Zu Beginn gilt sofort
$$A_1=1,\qquad M_1=2.$$
Die Aufgabe lautet also: Wenn man diese CRT-Lösung von \(i\) nach \(i+1\) erweitert, welche späteren Primzahlen teilen irgendwann den aktuellen Vertreter?
Sei \(q=p_j\) die \(j\)-te Primzahl. Sobald \(q\) in das System aufgenommen wurde, gilt für alle späteren Stufen
$$A_i \equiv j \pmod{q}\qquad(i \ge j).$$
Weil \(j \lt p_j=q\), ist dieser Rest niemals \(0\) modulo \(q\). Also kann \(q\) nur vor seiner eigenen Aufnahme ein Teiler sein, also nur in Stufen \(i \lt j\).
Das ist der entscheidende Filter: In Stufe \(i\) müssen nur die Primzahlen \(p_{i+1},p_{i+2},\dots\) getestet werden. Bereits eingebaute Primzahlen können nie wieder einen Treffer liefern.
Angenommen, \(A_i\) ist modulo \(M_i\) bekannt. Jede Zahl, die die ersten \(i\) Kongruenzen beibehält, hat die Form
$$A_i + M_i t,$$
mit einem ganzzahligen Parameter \(t\). Für \(A_{i+1}\) kommt die neue Bedingung hinzu
$$A_{i+1} \equiv i+1 \pmod{p_{i+1}}.$$
Mit \(A_{i+1}=A_i+M_i t\) erhält man
$$A_i + M_i t \equiv i+1 \pmod{p_{i+1}}.$$
Da \(p_{i+1}\) neu ist, ist es zu \(M_i\) teilerfremd, also besitzt \(M_i\) modulo \(p_{i+1}\) ein Inverses. Damit folgt
$$t \equiv (i+1-A_i)\,M_i^{-1} \pmod{p_{i+1}}.$$
Dieser Wert bestimmt den nächsten CRT-Zustand eindeutig modulo \(M_{i+1}=M_i p_{i+1}\).
Die Werte \(A_i\) werden riesig, aber die Teilbarkeit durch eine Primzahl \(q\) hängt nur von \(A_i \bmod q\) ab. Deshalb speichert die Implementierung für jede Primzahl \(q \le n\) zwei laufende Reste:
$$a_i(q)\equiv A_i \pmod{q},\qquad m_i(q)\equiv M_i \pmod{q}.$$
Nach Berechnung des Korrekturfaktors \(t\) werden diese Reste durch
$$a_{i+1}(q)\equiv a_i(q)+m_i(q)t \pmod{q},$$
$$m_{i+1}(q)\equiv m_i(q)\,p_{i+1} \pmod{q}$$
aktualisiert. Der Teilbarkeitstest wird dadurch zu
$$q \mid A_i \iff a_i(q)=0.$$
Jede Primzahl wird höchstens einmal markiert, und am Ende werden genau diese markierten Primzahlen summiert.
Der Kontrollwert der Implementierungen lautet \(S(50)=69\). Die ersten Stufen zeigen direkt, warum.
Man startet mit
$$A_1=1.$$
Keine spätere Primzahl teilt \(1\).
Für die nächste Primzahl \(3\) löst man
$$A_2=1+2t,\qquad 1+2t \equiv 2 \pmod{3},$$
also \(t \equiv 2 \pmod{3}\) und damit
$$A_2=5.$$
Damit entsteht bereits ein Treffer, denn \(5\mid A_2\).
Nun wird auf die Primzahl \(5\) erweitert:
$$A_3=5+6t,\qquad 5+6t \equiv 3 \pmod{5}.$$
Da \(6 \equiv 1 \pmod{5}\), folgt \(t \equiv 3\) und somit
$$A_3=23.$$
Also gilt auch \(23\mid A_3\).
Im nächsten Schritt
$$A_4=23+30t,\qquad 23+30t \equiv 4 \pmod{7},$$
erhält man
$$A_4=53.$$
Das trägt nicht zu \(S(50)\) bei, weil \(53 \gt 50\). Führt man dieselben Restklassen-Updates weiter, erhält man schließlich
$$A_{10}=5765999453,$$
und diese Zahl ist durch \(41\) teilbar. Weitere Treffer bis \(50\) gibt es nicht, also
$$S(50)=5+23+41=69.$$
Die C++-, Python- und Java-Implementierungen erzeugen zunächst alle Primzahlen bis zur Schranke mit einem Standard-Sieb. Danach initialisieren sie den CRT-Zustand beim ersten Primzahlmodul, also bei \(A_1=1\) und \(M_1=2\).
Anschließend wird die riesige Zahl \(A_i\) nie vollständig benötigt. Stattdessen speichert die Implementierung ein Array mit den aktuellen Resten der CRT-Lösung modulo jeder Primzahl bis zur Grenze und ein zweites Array mit den aktuellen Resten des laufenden Moduls \(M_i\) modulo denselben Primzahlen.
In jeder Stufe werden zuerst nur die Primzahlen betrachtet, die noch nicht in das CRT-System aufgenommen wurden. Steht dort der Rest \(0\), dann teilt die betreffende Primzahl den aktuellen Wert \(A_i\) und wird markiert. Danach berechnet der Code den eindeutigen Korrekturfaktor \(t\) modulo der nächsten Primzahl über ein modulares Inverses aus dem erweiterten euklidischen Algorithmus und aktualisiert beide Rest-Arrays parallel. Am Ende wird die Summe aller markierten Primzahlen ausgegeben.
Sei \(m=\pi(n)\) die Anzahl der Primzahlen bis \(n\). Das Sieb benötigt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Der eigentliche CRT-Prozess führt eine dreieckige Anzahl von Teilbarkeitstests und Rest-Updates aus, nämlich ungefähr
$$\sum_{i=1}^{m-1}(m-i)=\frac{m(m-1)}{2},$$
wodurch die dominierende Laufzeit \(O(m^2)\) ist. Die Primzahlliste, die beiden Rest-Arrays und die Markierungen benötigen zusammen \(O(m)\) zusätzlichen Speicher.
\(p_1=2,p_2=3,p_3=5,\dots\) artan asal dizisi olsun. Her \(i\ge 1\) için \(A_i\),
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i)$$
koşulunu sağlayan en küçük pozitif tam sayı olarak tanımlanır. Problem, bu \(A_i\) değerlerinden en az birini bölen tüm \(q \le n\) asallarının toplamı olan \(S(n)\)'yi istemektedir. Dizi çok hızlı büyüdüğü için sayıları doğrudan üretmek verimli değildir; çözüm, Çin Kalan Teoremi sistemini bir asal ekleyerek büyütür ve yalnızca artık sınıflarını takip eder.
Yöntemin temeli, her \(A_i\)'yi artımlı bir CRT inşasının bir aşaması olarak görmektir.
Her aşama için
$$M_i=\prod_{k=1}^{i} p_k$$
tanımını yapalım. Modüller \(p_1,p_2,\dots,p_i\) ikişerli aralarında asal olduğundan, Çin Kalan Teoremi
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i)$$
koşullarını sağlayan tek bir artık sınıfı verir; biz bunun en küçük pozitif temsilcisini \(A_i\) olarak seçeriz. İlk durum açıktır:
$$A_1=1,\qquad M_1=2.$$
Dolayısıyla soru şudur: Bu CRT çözümü \(i\)'den \(i+1\)'e genişlerken hangi sonraki asallar mevcut değeri böler?
\(q=p_j\) olsun. \(q\) sisteme girdikten sonra tüm sonraki aşamalarda
$$A_i \equiv j \pmod{q}\qquad(i \ge j)$$
olur. Fakat \(j \lt p_j=q\) olduğu için bu artık hiçbir zaman \(0\) değildir. Demek ki \(q\), ancak kendi kongruansı eklenmeden önce, yani yalnızca \(i \lt j\) iken, bazı \(A_i\) değerlerini bölebilir.
Bu gözlem ana sadeleştirmeyi sağlar: \(i\). aşamada sadece \(p_{i+1},p_{i+2},\dots\) asallarını test etmek yeterlidir. Sisteme zaten eklenmiş asallar bir daha bölen olamaz.
\(A_i\)'nin \(M_i\) modunda bilindiğini varsayalım. İlk \(i\) kongruansı koruyan her sayı
$$A_i + M_i t$$
şeklindedir. \(A_{i+1}\) için yeni koşul
$$A_{i+1} \equiv i+1 \pmod{p_{i+1}}$$
olduğundan, \(A_{i+1}=A_i+M_i t\) yazınca
$$A_i + M_i t \equiv i+1 \pmod{p_{i+1}}$$
elde edilir. \(p_{i+1}\), \(M_i\)'yi oluşturan asallardan farklı olduğu için \(\gcd(M_i,p_{i+1})=1\) ve \(M_i\)'nin modüler tersi vardır. Böylece
$$t \equiv (i+1-A_i)\,M_i^{-1} \pmod{p_{i+1}}$$
bulunur. Bu da sonraki CRT durumunu \(M_{i+1}=M_i p_{i+1}\) modunda tekil olarak belirler.
\(A_i\) sayıları çok hızlı büyür, fakat bir asal \(q\)'nun bölüp bölmediği yalnızca \(A_i \bmod q\)'ya bağlıdır. Bu yüzden uygulama her \(q \le n\) için iki çalışan artık tutar:
$$a_i(q)\equiv A_i \pmod{q},\qquad m_i(q)\equiv M_i \pmod{q}.$$
Önceki adımdaki düzeltme katsayısı \(t\) bulunduğunda güncelleme
$$a_{i+1}(q)\equiv a_i(q)+m_i(q)t \pmod{q},$$
$$m_{i+1}(q)\equiv m_i(q)\,p_{i+1} \pmod{q}$$
şeklindedir. Böylece bölünebilirlik testi tam ve ucuz hale gelir:
$$q \mid A_i \iff a_i(q)=0.$$
Her asal en fazla bir kez işaretlendiğinden, sonuç işaretli asalların toplamıdır.
Uygulamalardaki kontrol noktası \(S(50)=69\) değeridir. İlk aşamalar bunun nedenini açıkça gösterir.
Başlangıçta
$$A_1=1.$$
\(1\)'i bölen daha sonraki bir asal yoktur.
Sonraki asal \(3\) için
$$A_2=1+2t,\qquad 1+2t \equiv 2 \pmod{3}$$
çözülür. Buradan \(t \equiv 2 \pmod{3}\) ve dolayısıyla
$$A_2=5$$
elde edilir. Böylece ilk katkı gelir, çünkü \(5\mid A_2\).
Şimdi \(5\) modülünü ekleyelim:
$$A_3=5+6t,\qquad 5+6t \equiv 3 \pmod{5}.$$
\(6 \equiv 1 \pmod{5}\) olduğundan \(t \equiv 3\) ve
$$A_3=23$$
olur. Böylece \(23\mid A_3\) ile ikinci katkı da bulunur.
Bir sonraki adımda
$$A_4=23+30t,\qquad 23+30t \equiv 4 \pmod{7}$$
eşitliğinden
$$A_4=53$$
çıkar. Bu sayı \(50\)'den büyük olduğu için \(S(50)\)'ye katkı vermez. Aynı artık güncellemeleri sürdürülünce sonunda
$$A_{10}=5765999453$$
elde edilir ve bu sayı \(41\)'e tam bölünür. \(50\)'ye kadar başka hit olmadığı için
$$S(50)=5+23+41=69$$
sonucuna ulaşılır.
C++, Python ve Java uygulamaları önce standart bir elek ile sınıra kadar tüm asalları üretir. Ardından ilk asal için CRT durumunu, yani \(A_1=1\) ve \(M_1=2\) olacak şekilde başlatır.
Bundan sonra büyük \(A_i\) sayısını tam olarak tutmaya gerek kalmaz. Bunun yerine uygulama, sınıra kadar olan her asal için CRT çözümünün güncel artığını bir dizide ve çalışan modül \(M_i\)'nin o asala göre artığını ikinci bir dizide saklar.
Her aşamada önce henüz sisteme girmemiş asallar taranır. Saklanan artık \(0\) ise o asal mevcut \(A_i\)'yi bölüyor demektir ve toplam için işaretlenir. Sonra bir sonraki asal modülünde modüler ters yardımıyla tekil düzeltme katsayısı hesaplanır; bu ters, genişletilmiş Öklid algoritmasıyla bulunur. Son olarak iki artık dizisi paralel biçimde güncellenir ve süreç tamamlanınca işaretli asallar toplanır.
\(m=\pi(n)\) olsun; yani \(n\)'ye kadar kaç asal varsa o. Elek \(O(n\log\log n)\) zaman ve \(O(n)\) bellek ister. Ana CRT süreci yaklaşık
$$\sum_{i=1}^{m-1}(m-i)=\frac{m(m-1)}{2}$$
adet bölünebilirlik testi ve artık güncellemesi yapar; bu yüzden baskın zaman maliyeti \(O(m^2)\)'dir. Asal listesi, iki artık dizisi ve işaretleme dizisi birlikte \(O(m)\) ek bellek kullanır.
Sean \(p_1=2,p_2=3,p_3=5,\dots\) los números primos en orden creciente. Para cada \(i\ge 1\), se define \(A_i\) como el menor entero positivo que cumple
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
La tarea consiste en calcular \(S(n)\), la suma de todos los primos \(q \le n\) que dividen al menos uno de los valores \(A_i\). Como la secuencia crece con enorme rapidez, no es viable construir los enteros grandes de forma directa. La solución amplía el sistema CRT primo por primo y conserva solo residuos.
La idea central es interpretar cada \(A_i\) como una etapa de una construcción incremental del Teorema Chino del Resto.
Para cada etapa \(i\), definimos
$$M_i=\prod_{k=1}^{i} p_k.$$
Como los módulos \(p_1,p_2,\dots,p_i\) son coprimos dos a dos, el Teorema Chino del Resto da una única clase residual módulo \(M_i\) que satisface
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
Tomamos como \(A_i\) el representante positivo mínimo. El primer caso es inmediato:
$$A_1=1,\qquad M_1=2.$$
Así, el problema se convierte en la siguiente pregunta: al extender esta solución CRT desde \(i\) hasta \(i+1\), ¿qué primos posteriores llegan a dividir al representante actual?
Sea \(q=p_j\) el \(j\)-ésimo primo. Una vez que \(q\) entra en el sistema, todos los términos posteriores cumplen
$$A_i \equiv j \pmod{q}\qquad(i \ge j).$$
Pero \(j \lt p_j=q\), de modo que ese residuo nunca es \(0\) módulo \(q\). Por lo tanto, \(q\) solo puede dividir algún \(A_i\) antes de imponer su propia congruencia, es decir, únicamente cuando \(i \lt j\).
Esta observación elimina trabajo innecesario: en la etapa \(i\) basta comprobar los primos \(p_{i+1},p_{i+2},\dots\). Los primos ya fijados dentro del CRT no volverán a ser divisores.
Supongamos conocido \(A_i\) módulo \(M_i\). Todo número que preserve las primeras \(i\) congruencias tiene la forma
$$A_i + M_i t,$$
con \(t\) entero. Para construir \(A_{i+1}\), añadimos la nueva condición
$$A_{i+1} \equiv i+1 \pmod{p_{i+1}}.$$
Sustituyendo \(A_{i+1}=A_i+M_i t\), obtenemos
$$A_i + M_i t \equiv i+1 \pmod{p_{i+1}}.$$
Como \(p_{i+1}\) es un primo nuevo, es coprimo con \(M_i\), por lo que \(M_i\) tiene inverso modular módulo \(p_{i+1}\). Entonces
$$t \equiv (i+1-A_i)\,M_i^{-1} \pmod{p_{i+1}}.$$
Ese valor determina de manera única el siguiente estado CRT módulo \(M_{i+1}=M_i p_{i+1}\).
Los valores \(A_i\) se hacen gigantescos, pero la divisibilidad por un primo \(q\) depende únicamente del residuo \(A_i \bmod q\). Por eso la implementación guarda, para cada primo \(q \le n\), dos residuos dinámicos:
$$a_i(q)\equiv A_i \pmod{q},\qquad m_i(q)\equiv M_i \pmod{q}.$$
Una vez calculada la corrección \(t\), la actualización es
$$a_{i+1}(q)\equiv a_i(q)+m_i(q)t \pmod{q},$$
$$m_{i+1}(q)\equiv m_i(q)\,p_{i+1} \pmod{q}.$$
Así, el criterio de divisibilidad se vuelve exacto y barato:
$$q \mid A_i \iff a_i(q)=0.$$
Cada primo se marca a lo sumo una vez, y la respuesta final es la suma de los primos marcados.
El punto de control usado por las implementaciones es \(S(50)=69\). Las primeras etapas lo muestran con claridad.
Se empieza con
$$A_1=1.$$
Ningún primo posterior divide a \(1\).
Para el siguiente primo \(3\), resolvemos
$$A_2=1+2t,\qquad 1+2t \equiv 2 \pmod{3},$$
de donde \(t \equiv 2 \pmod{3}\) y por tanto
$$A_2=5.$$
Esto ya produce un acierto, porque \(5\mid A_2\).
Luego ampliamos hacia el primo \(5\):
$$A_3=5+6t,\qquad 5+6t \equiv 3 \pmod{5}.$$
Como \(6 \equiv 1 \pmod{5}\), se obtiene \(t \equiv 3\), así que
$$A_3=23.$$
Entonces \(23\mid A_3\), lo que aporta el segundo primo.
En el paso siguiente,
$$A_4=23+30t,\qquad 23+30t \equiv 4 \pmod{7},$$
y resulta
$$A_4=53.$$
Esto no contribuye a \(S(50)\) porque \(53 \gt 50\). Continuando el mismo proceso de residuos se llega finalmente a
$$A_{10}=5765999453,$$
que es divisible por \(41\). No aparece ningún otro primo \(\le 50\), de modo que
$$S(50)=5+23+41=69.$$
Las implementaciones en C++, Python y Java generan primero todos los primos hasta el límite con una criba estándar. Después inicializan el estado CRT en el primer primo, es decir, con \(A_1=1\) y \(M_1=2\).
A partir de ahí, la implementación nunca necesita materializar el entero enorme \(A_i\). En su lugar, mantiene un arreglo con el residuo actual de la solución CRT módulo cada primo hasta el límite y un segundo arreglo con el residuo actual del módulo acumulado \(M_i\) respecto a esos mismos primos.
En cada etapa se recorren únicamente los primos que todavía no han sido incorporados al sistema. Si el residuo guardado vale \(0\), entonces ese primo divide al valor actual \(A_i\) y se marca para la suma final. Después, el código calcula la corrección única \(t\) módulo el siguiente primo usando un inverso modular obtenido con el algoritmo extendido de Euclides, y actualiza ambos arreglos de residuos en paralelo. Al final, suma todos los primos marcados.
Sea \(m=\pi(n)\), el número de primos hasta \(n\). La criba cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. El proceso principal de CRT realiza un número triangular de comprobaciones y actualizaciones de residuos, aproximadamente
$$\sum_{i=1}^{m-1}(m-i)=\frac{m(m-1)}{2},$$
por lo que el coste dominante es \(O(m^2)\) tiempo. La lista de primos, los dos arreglos de residuos y las marcas usan en total \(O(m)\) memoria adicional.
设 \(p_1=2,p_2=3,p_3=5,\dots\) 为按升序排列的素数。对每个 \(i\ge 1\)，定义 \(A_i\) 为满足下列条件的最小正整数：
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
题目要求计算 \(S(n)\)：所有满足 \(q \le n\) 且能整除某个 \(A_i\) 的素数 \(q\) 的总和。由于这个序列增长极快，直接构造大整数完全不可取。有效做法是把中国剩余定理系统按素数逐步扩展，并且只维护各个模数下的余数。
整个思路的核心，是把每个 \(A_i\) 看成一次增量式中国剩余定理构造的当前状态。
对每个阶段 \(i\)，定义
$$M_i=\prod_{k=1}^{i} p_k.$$
因为模数 \(p_1,p_2,\dots,p_i\) 两两互素，中国剩余定理保证：模 \(M_i\) 意义下存在唯一一个剩余类，使得
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
我们把它的最小正代表记为 \(A_i\)。初始状态立即可得：
$$A_1=1,\qquad M_1=2.$$
因此问题可以重述为：当这个 CRT 解从第 \(i\) 步扩展到第 \(i+1\) 步时，哪些尚未加入的素数会整除当前代表值？
设 \(q=p_j\) 是第 \(j\) 个素数。一旦 \(q\) 自己的同余条件已经被加入系统，那么对所有后续阶段都有
$$A_i \equiv j \pmod{q}\qquad(i \ge j).$$
又因为 \(j \lt p_j=q\)，所以这个余数不可能是 \(0\)。这说明 \(q\) 只能在自己的同余条件加入之前整除某个 \(A_i\)，也就是只能发生在 \(i \lt j\) 的阶段。
这一步解释了算法为什么只检查“未来的素数”。在第 \(i\) 阶段，只需要测试 \(p_{i+1},p_{i+2},\dots\)。已经纳入 CRT 系统的素数不再可能成为新的因子。
假设 \(A_i\) 已知到模 \(M_i\) 的意义。所有保持前 \(i\) 个同余条件不变的整数都可以写成
$$A_i + M_i t,$$
其中 \(t\) 是整数。为了构造 \(A_{i+1}\)，我们还要加入新的条件
$$A_{i+1} \equiv i+1 \pmod{p_{i+1}}.$$
代入 \(A_{i+1}=A_i+M_i t\) 后得到
$$A_i + M_i t \equiv i+1 \pmod{p_{i+1}}.$$
由于 \(p_{i+1}\) 是新加入的素数，与 \(M_i\) 互素，所以 \(M_i\) 在模 \(p_{i+1}\) 下存在逆元。于是
$$t \equiv (i+1-A_i)\,M_i^{-1} \pmod{p_{i+1}}.$$
这个 \(t\) 唯一确定了下一步的 CRT 状态，模数变为 \(M_{i+1}=M_i p_{i+1}\)。
\(A_i\) 的真实数值会迅速变得极其庞大，但判断一个素数 \(q\) 是否整除 \(A_i\)，只需要知道 \(A_i \bmod q\)。因此，对每个 \(q \le n\)，实现都维护两个运行余数：
$$a_i(q)\equiv A_i \pmod{q},\qquad m_i(q)\equiv M_i \pmod{q}.$$
在求出上一步的修正量 \(t\) 之后，这两个量按如下方式更新：
$$a_{i+1}(q)\equiv a_i(q)+m_i(q)t \pmod{q},$$
$$m_{i+1}(q)\equiv m_i(q)\,p_{i+1} \pmod{q}.$$
于是整除判定就变成了一个精确且廉价的条件：
$$q \mid A_i \iff a_i(q)=0.$$
每个素数最多只会被标记一次，所以最终答案就是所有被标记素数的和。
实现中的校验点是 \(S(50)=69\)。前几步足以说明原因，而且这部分也很好地展示了公式如何工作。
起点是
$$A_1=1.$$
显然没有后续素数会整除 \(1\)。
加入下一个素数 \(3\) 时，我们求解
$$A_2=1+2t,\qquad 1+2t \equiv 2 \pmod{3}.$$
于是 \(t \equiv 2 \pmod{3}\)，得到
$$A_2=5.$$
这立刻产生一个命中，因为 \(5\mid A_2\)。
再加入素数 \(5\)：
$$A_3=5+6t,\qquad 5+6t \equiv 3 \pmod{5}.$$
由于 \(6 \equiv 1 \pmod{5}\)，所以 \(t \equiv 3\)，从而
$$A_3=23.$$
因此 \(23\mid A_3\)，第二个贡献素数出现。
下一步中，
$$A_4=23+30t,\qquad 23+30t \equiv 4 \pmod{7},$$
可得
$$A_4=53.$$
但 \(53 \gt 50\)，所以它不计入 \(S(50)\)。继续按同样的余数更新一直推进，可以得到
$$A_{10}=5765999453,$$
而这个数恰好能被 \(41\) 整除。到 \(50\) 为止再没有别的命中素数，因此
$$S(50)=5+23+41=69.$$
C++、Python 和 Java 实现都会先用标准筛法生成不超过上界的全部素数，然后把 CRT 的初始状态设为 \(A_1=1\)、\(M_1=2\)。
接下来，程序不再尝试保存巨大的完整整数 \(A_i\)。相反，它维护两个数组：第一个数组记录当前 CRT 解在每个素数模数下的余数，第二个数组记录当前累积模数 \(M_i\) 在这些素数模数下的余数。
在每一阶段，程序先扫描尚未进入 CRT 系统的素数。如果某个位置存储的当前余数为 \(0\)，就说明该素数整除了当前的 \(A_i\)，于是把它标记为需要加入最终总和。然后，程序利用扩展欧几里得算法求出下一个素数模数下所需的逆元，从而得到唯一的修正量 \(t\)，并对两个余数数组同时做并行更新。所有阶段结束后，把所有被标记的素数相加即可。
记 \(m=\pi(n)\)，即不超过 \(n\) 的素数个数。筛法部分需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间。主 CRT 过程执行的是一个三角形数量级的整除测试与余数更新，大约为
$$\sum_{i=1}^{m-1}(m-i)=\frac{m(m-1)}{2},$$
因此主导时间复杂度是 \(O(m^2)\)。素数表、两个余数数组以及命中标记一共只需要 \(O(m)\) 额外空间。
Пусть \(p_1=2,p_2=3,p_3=5,\dots\) — простые числа в возрастающем порядке. Для каждого \(i\ge 1\) определим \(A_i\) как наименьшее положительное число, удовлетворяющее условиям
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
Нужно вычислить \(S(n)\), то есть сумму всех простых \(q \le n\), которые делят хотя бы одно из чисел \(A_i\). Последовательность растет очень быстро, поэтому прямое построение больших значений не подходит. Эффективное решение поэтапно расширяет систему сравнений CRT и хранит только остатки.
Вся конструкция основана на том, что каждое \(A_i\) рассматривается как очередной этап инкрементального применения китайской теоремы об остатках.
Для каждого шага \(i\) введем
$$M_i=\prod_{k=1}^{i} p_k.$$
Так как модули \(p_1,p_2,\dots,p_i\) попарно взаимно просты, китайская теорема об остатках дает единственный класс по модулю \(M_i\), удовлетворяющий
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
В качестве \(A_i\) берем наименьшего положительного представителя. Начальное состояние сразу известно:
$$A_1=1,\qquad M_1=2.$$
Тем самым задача сводится к следующему вопросу: какие более поздние простые когда-либо делят текущий представитель, пока CRT-система расширяется от шага \(i\) к шагу \(i+1\)?
Пусть \(q=p_j\) — \(j\)-е простое число. После того как условие для \(q\) уже включено в систему, для всех последующих шагов выполняется
$$A_i \equiv j \pmod{q}\qquad(i \ge j).$$
Но \(j \lt p_j=q\), следовательно, этот остаток никогда не равен нулю. Значит, простое \(q\) может делить некоторое \(A_i\) только до того, как его собственное сравнение было добавлено, то есть лишь при \(i \lt j\).
Именно поэтому на шаге \(i\) достаточно проверять только простые \(p_{i+1},p_{i+2},\dots\). Уже встроенные в CRT простые не могут стать новыми делителями.
Предположим, что \(A_i\) известно по модулю \(M_i\). Любое число, сохраняющее первые \(i\) сравнения, имеет вид
$$A_i + M_i t,$$
где \(t\) — целое число. Чтобы получить \(A_{i+1}\), добавляем новое условие
$$A_{i+1} \equiv i+1 \pmod{p_{i+1}}.$$
Подставляя \(A_{i+1}=A_i+M_i t\), имеем
$$A_i + M_i t \equiv i+1 \pmod{p_{i+1}}.$$
Так как \(p_{i+1}\) — новый простой модуль, он взаимно прост с \(M_i\), а значит, \(M_i\) обратим по модулю \(p_{i+1}\). Поэтому
$$t \equiv (i+1-A_i)\,M_i^{-1} \pmod{p_{i+1}}.$$
Это однозначно определяет следующее CRT-состояние по модулю \(M_{i+1}=M_i p_{i+1}\).
Числа \(A_i\) быстро становятся огромными, но делимость на простой \(q\) зависит только от остатка \(A_i \bmod q\). Поэтому для каждого \(q \le n\) реализация хранит два текущих остатка:
$$a_i(q)\equiv A_i \pmod{q},\qquad m_i(q)\equiv M_i \pmod{q}.$$
После вычисления поправки \(t\) они обновляются так:
$$a_{i+1}(q)\equiv a_i(q)+m_i(q)t \pmod{q},$$
$$m_{i+1}(q)\equiv m_i(q)\,p_{i+1} \pmod{q}.$$
Тогда проверка делимости становится простой и точной:
$$q \mid A_i \iff a_i(q)=0.$$
Каждый простой отмечается не более одного раза, а ответом служит сумма всех отмеченных простых.
Проверочная точка в реализациях — это \(S(50)=69\). Уже первые этапы показывают, откуда берется это число.
Начинаем с
$$A_1=1.$$
Ни один более поздний простой не делит \(1\).
Для следующего простого \(3\) решаем
$$A_2=1+2t,\qquad 1+2t \equiv 2 \pmod{3},$$
откуда \(t \equiv 2 \pmod{3}\), следовательно
$$A_2=5.$$
Здесь сразу возникает первый вклад, потому что \(5\mid A_2\).
Далее добавляем модуль \(5\):
$$A_3=5+6t,\qquad 5+6t \equiv 3 \pmod{5}.$$
Так как \(6 \equiv 1 \pmod{5}\), получаем \(t \equiv 3\), и значит
$$A_3=23.$$
Следовательно, \(23\mid A_3\), и это второй учитываемый простой.
На следующем шаге
$$A_4=23+30t,\qquad 23+30t \equiv 4 \pmod{7},$$
что дает
$$A_4=53.$$
Число \(53\) не входит в \(S(50)\), потому что \(53 \gt 50\). Продолжая те же обновления остатков, приходим к значению
$$A_{10}=5765999453,$$
которое делится на \(41\). Других попаданий среди простых до \(50\) нет, поэтому
$$S(50)=5+23+41=69.$$
Реализации на C++, Python и Java сначала строят список всех простых до заданного предела с помощью стандартного решета. Затем они инициализируют CRT-состояние для первого простого, то есть \(A_1=1\) и \(M_1=2\).
После этого полное огромное число \(A_i\) уже не хранится. Вместо этого используется один массив текущих остатков CRT-решения по каждому простому до предела и второй массив текущих остатков накопленного модуля \(M_i\) по тем же простым.
На каждом шаге код сначала просматривает только те простые, которые еще не включены в CRT-систему. Если сохраненный остаток равен \(0\), значит соответствующий простой делит текущее \(A_i\), и его нужно отметить. Затем вычисляется единственная поправка \(t\) по следующему простому модулю; для этого используется модульный обратный, найденный расширенным алгоритмом Евклида. После этого оба массива остатков обновляются параллельно. В конце суммируются все отмеченные простые.
Обозначим через \(m=\pi(n)\) число простых, не превосходящих \(n\). Решето требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Основной CRT-процесс выполняет треугольное число проверок делимости и обновлений остатков, примерно
$$\sum_{i=1}^{m-1}(m-i)=\frac{m(m-1)}{2},$$
поэтому ведущая временная сложность равна \(O(m^2)\). Список простых, два массива остатков и массив отметок требуют \(O(m)\) дополнительной памяти.
لتكن \(p_1=2,p_2=3,p_3=5,\dots\) هي الأعداد الأولية بترتيب تصاعدي. ولكل \(i\ge 1\) نعرّف \(A_i\) بأنه أصغر عدد صحيح موجب يحقق
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
المطلوب هو حساب \(S(n)\)، أي مجموع جميع الأعداد الأولية \(q \le n\) التي تقسم واحدًا على الأقل من القيم \(A_i\). وبما أن هذه المتتالية تنمو بسرعة هائلة، فلا يمكن الاعتماد على بناء الأعداد الكبيرة مباشرة. لذلك يعتمد الحل على توسيع نظام مبرهنة البواقي الصينية تدريجيًا، مع الاحتفاظ بالبواقي فقط.
الفكرة الأساسية هي النظر إلى كل \(A_i\) على أنه مرحلة من بناء تزايدي باستخدام مبرهنة البواقي الصينية.
في كل مرحلة \(i\) نعرّف
$$M_i=\prod_{k=1}^{i} p_k.$$
ولأن الموديلات \(p_1,p_2,\dots,p_i\) أولية ومتمايزة فهي متباينة أوليًا اثنين اثنين، ولذلك تعطي مبرهنة البواقي الصينية فئة وحيدة بترديد \(M_i\) تحقق
$$A_i \equiv k \pmod{p_k}\qquad(1 \le k \le i).$$
ونختار \(A_i\) ليكون أصغر ممثل موجب لهذه الفئة. البداية مباشرة:
$$A_1=1,\qquad M_1=2.$$
وهكذا تصبح المسألة: أثناء توسيع هذا الحل من المرحلة \(i\) إلى المرحلة \(i+1\)، ما هي الأعداد الأولية اللاحقة التي قد تقسم القيمة الحالية؟
لنفرض أن \(q=p_j\) هو الأولي رقم \(j\). بعد أن يدخل \(q\) إلى النظام تصبح جميع القيم اللاحقة محققة للعلاقة
$$A_i \equiv j \pmod{q}\qquad(i \ge j).$$
وبما أن \(j \lt p_j=q\)، فلا يمكن أن يكون هذا الباقي مساويًا للصفر. إذن لا يمكن لـ \(q\) أن يقسم أي \(A_i\) إلا قبل إضافة شرطه الخاص، أي فقط عندما \(i \lt j\).
هذه الملاحظة تفسر البنية الأساسية للخوارزمية: في المرحلة \(i\) يكفي اختبار الأوليات \(p_{i+1},p_{i+2},\dots\) فقط. أما الأوليات التي دخلت بالفعل في نظام CRT فلن تصبح قواسم لاحقًا.
افترض أن \(A_i\) معروف بترديد \(M_i\). كل عدد يحافظ على أول \(i\) من التطابقات يمكن كتابته بالشكل
$$A_i + M_i t,$$
حيث \(t\) عدد صحيح. وللحصول على \(A_{i+1}\) نضيف الشرط الجديد
$$A_{i+1} \equiv i+1 \pmod{p_{i+1}}.$$
بالتعويض \(A_{i+1}=A_i+M_i t\) نحصل على
$$A_i + M_i t \equiv i+1 \pmod{p_{i+1}}.$$
ولأن \(p_{i+1}\) أولي جديد وغير موجود في حاصل ضرب \(M_i\)، فإن \(\gcd(M_i,p_{i+1})=1\)، وبالتالي يملك \(M_i\) معكوسًا ضربيًا بترديد \(p_{i+1}\). ومن هنا ينتج
$$t \equiv (i+1-A_i)\,M_i^{-1} \pmod{p_{i+1}}.$$
وهذا يحدد الحالة التالية تحديدًا وحيدًا بترديد \(M_{i+1}=M_i p_{i+1}\).
القيم \(A_i\) نفسها تصبح ضخمة جدًا، لكن قابلية القسمة على أولي \(q\) تعتمد فقط على \(A_i \bmod q\). لذلك تحتفظ الخوارزمية، لكل \(q \le n\)، بباقيين جاريين:
$$a_i(q)\equiv A_i \pmod{q},\qquad m_i(q)\equiv M_i \pmod{q}.$$
وبعد حساب معامل التصحيح \(t\)، يتم التحديث وفقًا للعلاقتين
$$a_{i+1}(q)\equiv a_i(q)+m_i(q)t \pmod{q},$$
$$m_{i+1}(q)\equiv m_i(q)\,p_{i+1} \pmod{q}.$$
عندئذ تصبح قاعدة الفحص دقيقة وبسيطة:
$$q \mid A_i \iff a_i(q)=0.$$
وكل أولي يُعلَّم مرة واحدة فقط، ثم يُجمع في النهاية إذا سبق أن ظهر كقاسم.
نقطة التحقق المستخدمة في التنفيذات هي \(S(50)=69\). ويمكن رؤية ذلك مباشرة من المراحل الأولى.
نبدأ من
$$A_1=1.$$
ولا يوجد أولي لاحق يقسم \(1\).
عند إضافة الأولي \(3\) نحل
$$A_2=1+2t,\qquad 1+2t \equiv 2 \pmod{3},$$
ومنها \(t \equiv 2 \pmod{3}\)، وبالتالي
$$A_2=5.$$
وهنا يظهر أول قاسم مساهم لأن \(5\mid A_2\).
ثم ننتقل إلى الأولي \(5\):
$$A_3=5+6t,\qquad 5+6t \equiv 3 \pmod{5}.$$
وبما أن \(6 \equiv 1 \pmod{5}\)، فإن \(t \equiv 3\)، ومن ثم
$$A_3=23.$$
إذن \(23\mid A_3\)، وهذا هو الأولي المساهم الثاني.
في الخطوة التالية،
$$A_4=23+30t,\qquad 23+30t \equiv 4 \pmod{7},$$
فنحصل على
$$A_4=53.$$
لكن \(53 \gt 50\)، لذلك لا يدخل في \(S(50)\). وعند متابعة التحديثات نفسها نصل في النهاية إلى
$$A_{10}=5765999453,$$
وهذا العدد يقبل القسمة على \(41\). ولا تظهر أي مساهمات أخرى حتى \(50\)، لذا
$$S(50)=5+23+41=69.$$
تبدأ التنفيذات في C++ وPython وJava بتوليد جميع الأعداد الأولية حتى الحد المطلوب باستخدام منخل قياسي. بعد ذلك تُهيَّأ حالة CRT الأولى بحيث يكون \(A_1=1\) و\(M_1=2\).
ومن تلك اللحظة فصاعدًا لا تحتاج التنفيذات إلى تخزين العدد الضخم \(A_i\) نفسه. بدلًا من ذلك، تُحتفَظ مصفوفة بباقي حل CRT الحالي بترديد كل أولي حتى الحد، وتُحتفَظ مصفوفة ثانية بباقي حاصل الضرب الجاري \(M_i\) بالنسبة إلى الأوليات نفسها.
في كل مرحلة، يفحص التنفيذ فقط الأوليات التي لم تدخل النظام بعد. إذا كان الباقي المخزَّن مساويًا للصفر، فهذا يعني أن ذلك الأولي يقسم القيمة الحالية \(A_i\)، فيُعلَّم ليُضاف لاحقًا إلى المجموع النهائي. ثم يُحسب معامل التصحيح الوحيد \(t\) بترديد الأولي التالي باستخدام معكوس ضربي يُستخرج عبر خوارزمية إقليدس الموسعة، وبعد ذلك تُحدَّث المصفوفتان معًا على نحو متوازٍ. وفي النهاية تُجمع جميع الأوليات التي تم تعليمها.
لنكتب \(m=\pi(n)\) لعدد الأوليات التي لا تتجاوز \(n\). يحتاج المنخل إلى زمن \(O(n\log\log n)\) وذاكرة \(O(n)\). أما عملية CRT الأساسية فتنفذ عددًا مثلثيًا من اختبارات القسمة وتحديثات البواقي، أي تقريبًا
$$\sum_{i=1}^{m-1}(m-i)=\frac{m(m-1)}{2},$$
ولذلك يكون التعقيد الزمني الغالب \(O(m^2)\). أما قائمة الأوليات ومصفوفتا البواقي وعلامات الإصابة فتستخدم معًا \(O(m)\) ذاكرة إضافية.