Let \(P(m)\) denote the largest prime factor of \(m\). For nine consecutive integers define
$$S(n)=\sum_{j=0}^{8} P(n+j).$$
The task is to determine the maximum value of \(S(n)\) for starting points up to \(10^{16}\). A direct scan is hopeless: the search range is enormous, and each trial value of \(n\) would require factoring nine nearby integers. The implementations therefore do something more structured: they force several offsets to contain prescribed small factors, then check whether the remaining quotients are prime.
The central idea is to build arithmetic progressions in which the numbers \(n,n+1,\dots,n+8\) already have a favorable factorization pattern. If the large quotients are prime, then those quotients are automatically the largest prime factors we want to sum.
The search works modulo
$$M=16\cdot 9\cdot 5\cdot 7\cdot 11\cdot 13=720720.$$
First impose
$$n\equiv 5 \pmod 9,\qquad n\equiv 1 \pmod 5,\qquad n\equiv 3 \pmod 7.$$
Then \(n+4\) is divisible by \(9\), \(5\), and \(7\), so
$$315 \mid (n+4).$$
Next choose one of the two residues
$$n\equiv 1 \pmod{16}\qquad \text{or}\qquad n\equiv 7 \pmod{16}.$$
If \(n\equiv 1 \pmod{16}\), then the odd offsets satisfy
$$2\mid(n+1),\qquad 4\mid(n+3),\qquad 2\mid(n+5),\qquad 8\mid(n+7).$$
If \(n\equiv 7 \pmod{16}\), the powers of two are redistributed as
$$8\mid(n+1),\qquad 2\mid(n+3),\qquad 4\mid(n+5),\qquad 2\mid(n+7).$$
Because \(n\equiv 5 \pmod 9\), both \(n+1\) and \(n+7\) are also divisible by \(3\). So the odd offsets always receive the divisor multiset
$$\{6,4,2,24\},$$
although the exact placement of these four divisors depends on which of the two residues modulo \(16\) is chosen.
The construction also requires
$$n\equiv 1\text{ or }2 \pmod{11},\qquad n\equiv 1,2,3,\text{ or }4 \pmod{13}.$$
These choices ensure that none of the nine numbers \(n,n+1,\dots,n+8\) is divisible by \(11\) or \(13\): the corresponding residue intervals never hit \(0\) modulo those primes. Combining all independent choices gives
$$2\cdot 2\cdot 4=16$$
admissible residue classes modulo \(M\). The Chinese Remainder Theorem turns the congruences above into 16 explicit residues \(r\), and every candidate examined by the program satisfies
$$n\equiv r \pmod M$$
for one of those residues.
For one representative residue family the nine numbers take the form
$$n+j=d_j q_j,\qquad d=(1,6,1,4,315,2,1,24,1).$$
The mirrored family simply permutes the four odd-offset divisors from \((6,4,2,24)\) to \((24,2,4,6)\). In either case the small divisor \(d_j\) contains only primes from \(\{2,3,5,7\}\). If the quotient \(q_j\) is prime, then \(q_j\) is automatically larger than every prime dividing \(d_j\), so
$$P(n+j)=q_j=\frac{n+j}{d_j}.$$
Therefore, on a fully successful candidate, the target sum becomes a linear expression in \(n\). For the displayed family,
$$S(n)=n+\frac{n+1}{6}+(n+2)+\frac{n+3}{4}+\frac{n+4}{315}+\frac{n+5}{2}+(n+6)+\frac{n+7}{24}+(n+8).$$
The mirrored family has the same coefficient of \(n\), because it uses the same reciprocal multiset
$$\left\{1,\frac16,1,\frac14,\frac1{315},\frac12,1,\frac1{24},1\right\}.$$
This matters because the score increases as \(n\) increases, so once a residue class is fixed we only care about the nearest admissible candidates below the top of the range.
Let
$$N_0=M\left\lfloor\frac{10^{16}}{M}\right\rfloor.$$
For each admissible residue \(r\), the implementations examine candidates of the form
$$n=N_0+r-Mk,\qquad 0\le k<10^7.$$
This converts the original search over \(n\) into a one-dimensional scan over \(k\). Since every step decreases \(n\) by exactly \(M\), and the score is affine in \(n\) once the divisor pattern is fixed, smaller \(k\) means a better candidate inside the same residue class.
The sieve uses every prime \(p\) with
$$17\le p<10^8.$$
These are exactly the primes not already handled by the residue construction. Because \(p\nmid M\), the inverse \(M^{-1}\pmod p\) exists. For any offset \(j\), the condition that the quotient at that offset be divisible by \(p\) is equivalent to
$$N_0+r+j-Mk\equiv 0 \pmod p,$$
so the bad values of \(k\) lie in the arithmetic progression
$$k\equiv (N_0+r+j)M^{-1}\pmod p.$$
Thus each prime marks at most one residue class of \(k\) for each of the nine offsets. Unmarked indices are precisely the candidates for which none of the nine reduced quotients has a prime divisor between \(17\) and \(10^8-1\).
The largest reduced quotient is on the order of \(10^{16}\), so its square root is about \(10^8\). The smallest reduced quotient comes from dividing by \(315\), and
$$\sqrt{\frac{10^{16}}{315}}<10^8.$$
Hence every quotient checked by the program has square root below the sieve limit. If a positive quotient survives all prime divisors up to \(10^8\), it has no divisor up to its square root and must be prime. That turns the modular sieve into a full primality certificate for the reduced numbers.
The implementations contain a small verification example before the full search. Direct factorization gives
$$\begin{aligned} P(100)&=5,\quad P(101)=101,\quad P(102)=17,\quad P(103)=103,\\ P(104)&=13,\quad P(105)=7,\quad P(106)=53,\quad P(107)=107,\quad P(108)=3. \end{aligned}$$
Therefore
$$S(100)=5+101+17+103+13+7+53+107+3=409.$$
The same checkpoint scan also verifies that
$$\max_{2\le n\le 100} S(n)=417.$$
This example is small enough to check directly, and it confirms that the largest-prime-factor definition is being interpreted correctly before the residue-class sieve is run on the real bound.
The C++, Python, and Java implementations all use the same mathematical plan. First they build the 16 admissible residues produced by the CRT constraints. Next they generate all primes from \(17\) up to \(10^8-1\), and for each such prime they precompute the modular inverse of \(M\).
Each worker then processes one subset of the residue classes. For one residue class it allocates a byte array of length \(10^7\), one slot for each index \(k\). For every prime and every offset \(j=0,\dots,8\), it marks the arithmetic progression of indices that would make the corresponding reduced quotient divisible by that prime. After the marking phase, the unmarked indices are the surviving candidates.
Finally the implementation evaluates the quotient-based score for each surviving candidate and keeps the maximum over all residue classes. The Python entry point delegates to the same native search logic, while the Java version implements the same sieve-and-scan strategy directly.
Let \(B=10^8\) and \(K=10^7\). Building the prime table up to \(B\) costs \(O(B\log\log B)\) time and \(O(B)\) memory. For one residue class, the marking work is
$$O\!\left(9K\sum_{p<B}\frac1p\right)=O(K\log\log B),$$
followed by one linear scan of \(K\) flags. Since there are only 16 residue classes, the overall asymptotic cost is still \(O(B\log\log B+K\log\log B)\) up to a fixed constant factor. In practice the dominant memory cost is the prime sieve plus one \(K\)-sized marker array per worker thread.
Sei \(P(m)\) der größte Primfaktor von \(m\). Für neun aufeinanderfolgende Zahlen definieren wir
$$S(n)=\sum_{j=0}^{8} P(n+j).$$
Gesucht ist der maximale Wert von \(S(n)\) für Startwerte bis \(10^{16}\). Ein direkter Durchlauf ist ausgeschlossen: Der Suchraum ist riesig, und für jedes \(n\) müssten neun nahe Zahlen faktorisiert werden. Die Implementierungen erzwingen daher zuerst günstige Teilbarkeitsmuster und prüfen dann nur noch, ob die verbleibenden Quotienten prim sind.
Die Grundidee besteht darin, Restklassen zu konstruieren, in denen die Zahlen \(n,n+1,\dots,n+8\) bereits eine brauchbare Vorfaktorzerlegung besitzen. Sind die großen Quotienten prim, dann sind genau diese Quotienten die größten Primfaktoren, die summiert werden sollen.
Gearbeitet wird modulo
$$M=16\cdot 9\cdot 5\cdot 7\cdot 11\cdot 13=720720.$$
Zunächst werden die Kongruenzen
$$n\equiv 5 \pmod 9,\qquad n\equiv 1 \pmod 5,\qquad n\equiv 3 \pmod 7$$
vorgegeben. Dann ist \(n+4\) gleichzeitig durch \(9\), \(5\) und \(7\) teilbar, also
$$315 \mid (n+4).$$
Zusätzlich wählen wir
$$n\equiv 1 \pmod{16}\qquad \text{oder}\qquad n\equiv 7 \pmod{16}.$$
Im ersten Fall gilt
$$2\mid(n+1),\qquad 4\mid(n+3),\qquad 2\mid(n+5),\qquad 8\mid(n+7).$$
Im zweiten Fall verschieben sich die Zweierpotenzen zu
$$8\mid(n+1),\qquad 2\mid(n+3),\qquad 4\mid(n+5),\qquad 2\mid(n+7).$$
Wegen \(n\equiv 5 \pmod 9\) sind außerdem \(n+1\) und \(n+7\) durch \(3\) teilbar. Die ungeraden Offsets tragen damit immer die Teilermenge
$$\{6,4,2,24\},$$
wobei die genaue Zuordnung dieser vier Teiler von der gewählten Restklasse modulo \(16\) abhängt.
Zusätzlich verlangt die Konstruktion
$$n\equiv 1\text{ oder }2 \pmod{11},\qquad n\equiv 1,2,3,\text{ oder }4 \pmod{13}.$$
Damit ist garantiert, dass keine der neun Zahlen \(n,\dots,n+8\) durch \(11\) oder \(13\) teilbar ist: Die entsprechenden Restintervalle treffen nie \(0\) modulo diesen Primzahlen. Insgesamt entstehen dadurch
$$2\cdot 2\cdot 4=16$$
zulässige Restklassen modulo \(M\). Der chinesische Restsatz fasst die obigen Bedingungen zu 16 konkreten Resten \(r\) zusammen, und jeder geprüfte Kandidat erfüllt
$$n\equiv r \pmod M$$
für einen dieser Reste.
Für eine repräsentative Restklassenfamilie haben die neun Zahlen die Form
$$n+j=d_j q_j,\qquad d=(1,6,1,4,315,2,1,24,1).$$
Die gespiegelte Familie vertauscht nur die vier ungeraden Teiler von \((6,4,2,24)\) zu \((24,2,4,6)\). In beiden Fällen enthält \(d_j\) nur Primzahlen aus \(\{2,3,5,7\}\). Ist der Quotient \(q_j\) prim, dann ist er automatisch größer als jeder Primteiler von \(d_j\), also
$$P(n+j)=q_j=\frac{n+j}{d_j}.$$
Auf einem vollständig erfolgreichen Kandidaten wird die Zielfunktion damit zu einem linearen Ausdruck in \(n\). Für die angezeigte Familie lautet er
$$S(n)=n+\frac{n+1}{6}+(n+2)+\frac{n+3}{4}+\frac{n+4}{315}+\frac{n+5}{2}+(n+6)+\frac{n+7}{24}+(n+8).$$
Die gespiegelte Familie hat denselben Koeffizienten von \(n\), weil die Kehrwertmenge identisch bleibt:
$$\left\{1,\frac16,1,\frac14,\frac1{315},\frac12,1,\frac1{24},1\right\}.$$
Das ist wichtig, weil der Wert mit wachsendem \(n\) steigt. Hat man also eine Restklasse fixiert, sind nur die Kandidaten nahe an der oberen Schranke interessant.
Setze
$$N_0=M\left\lfloor\frac{10^{16}}{M}\right\rfloor.$$
Für jeden zulässigen Rest \(r\) untersuchen die Implementierungen Kandidaten der Form
$$n=N_0+r-Mk,\qquad 0\le k<10^7.$$
Damit wird die ursprüngliche Suche über \(n\) in einen eindimensionalen Scan über \(k\) umgewandelt. Jeder Schritt verringert \(n\) exakt um \(M\), und sobald das Teilbarkeitsmuster feststeht, ist der Wert affin in \(n\). Innerhalb derselben Restklasse ist daher kleineres \(k\) immer besser.
Gesiebt wird mit allen Primzahlen
$$17\le p<10^8.$$
Genau diese Primzahlen sind nicht schon durch die Restklassenkonstruktion behandelt. Da \(p\nmid M\), existiert das Inverse \(M^{-1}\pmod p\). Für ein Offset \(j\) ist die Bedingung, dass der zugehörige Quotient durch \(p\) teilbar ist, äquivalent zu
$$N_0+r+j-Mk\equiv 0 \pmod p,$$
also liegen die schlechten \(k\)-Werte in der arithmetischen Progression
$$k\equiv (N_0+r+j)M^{-1}\pmod p.$$
Jede Primzahl markiert somit für jedes der neun Offsets höchstens eine Restklasse von \(k\). Unmarkierte Indizes sind genau die Kandidaten, deren neun reduzierte Quotienten keinen Primteiler zwischen \(17\) und \(10^8-1\) besitzen.
Der größte reduzierte Quotient hat Größenordnung \(10^{16}\), also liegt seine Quadratwurzel bei etwa \(10^8\). Der kleinste reduzierte Quotient entsteht nach Division durch \(315\), und es gilt
$$\sqrt{\frac{10^{16}}{315}}<10^8.$$
Damit hat jeder vom Programm geprüfte Quotient eine Quadratwurzel unterhalb der Siebgrenze. Überlebt ein positiver Quotient alle Primteiler bis \(10^8\), so hat er keinen Teiler bis zu seiner Quadratwurzel und ist daher prim. Das modulare Sieb liefert also bereits einen vollständigen Primnachweis für die reduzierten Zahlen.
Vor der großen Suche führen die Implementierungen eine kleine Kontrolle durch. Direkte Faktorisierung ergibt
$$\begin{aligned} P(100)&=5,\quad P(101)=101,\quad P(102)=17,\quad P(103)=103,\\ P(104)&=13,\quad P(105)=7,\quad P(106)=53,\quad P(107)=107,\quad P(108)=3. \end{aligned}$$
Daher ist
$$S(100)=5+101+17+103+13+7+53+107+3=409.$$
Der gleiche Kontrolllauf bestätigt außerdem
$$\max_{2\le n\le 100} S(n)=417.$$
Dieses kleine Beispiel lässt sich vollständig von Hand oder mit kurzem Code überprüfen und bestätigt, dass die Definition des größten Primfaktors vor dem eigentlichen Restklassensieb korrekt umgesetzt ist.
Die C++-, Python- und Java-Implementierungen folgen alle demselben mathematischen Plan. Zuerst erzeugen sie die 16 zulässigen Reste aus den CRT-Bedingungen. Danach werden alle Primzahlen von \(17\) bis \(10^8-1\) erzeugt, und zu jeder dieser Primzahlen wird das Inverse von \(M\) modulo \(p\) vorab berechnet.
Anschließend bearbeitet jeder Worker eine Teilmenge der Restklassen. Für eine feste Restklasse hält er ein Byte-Feld der Länge \(10^7\), also einen Eintrag pro Index \(k\). Für jede Primzahl und jedes Offset \(j=0,\dots,8\) markiert die Implementierung die arithmetische Progression der Indizes, bei denen der entsprechende reduzierte Quotient durch diese Primzahl teilbar wäre. Nach dieser Markierungsphase bleiben genau die überlebenden Kandidaten übrig.
Zum Schluss wird für jeden überlebenden Kandidaten die auf Quotienten basierende Summe ausgewertet und das globale Maximum gespeichert. Der Python-Einstiegspunkt nutzt dabei dieselbe native Suchlogik wieder, während die Java-Version dieselbe Sieb-und-Scan-Strategie direkt implementiert.
Mit \(B=10^8\) und \(K=10^7\) kostet das Primzahlsieb bis \(B\) \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher. Für eine Restklasse beträgt die Markierungsarbeit
$$O\!\left(9K\sum_{p<B}\frac1p\right)=O(K\log\log B),$$
danach folgt ein linearer Durchlauf über \(K\) Marker. Da es nur 16 Restklassen gibt, bleibt die gesamte asymptotische Laufzeit bis auf einen festen Faktor \(16\) bei \(O(B\log\log B+K\log\log B)\). Praktisch wird der Speicher von dem großen Primzahlsieb und einem \(K\)-großen Markerfeld pro Worker-Thread dominiert.
\(P(m)\), \(m\) sayısının en büyük asal çarpanı olsun. Dokuz ardışık sayı için
$$S(n)=\sum_{j=0}^{8} P(n+j)$$
tanımını yapalım. Amaç, başlangıç noktası \(10^{16}\)'yı geçmeyen tüm pencereler için \(S(n)\)'nin en büyük değerini bulmaktır. Doğrudan tarama uygulanamaz; aralık aşırı büyüktür ve her aday için dokuz sayıyı çarpanlara ayırmak gerekir. Bu yüzden uygulama önce belirli küçük bölenleri zorlayan kalıntı sınıfları kurar, sonra geriye kalan bölümlerin asal olup olmadığını sınar.
Ana fikir, \(n,n+1,\dots,n+8\) bloğunda bazı konumların önceden bilinen küçük çarpanlara sahip olduğu aritmetik ilerlemeler kurmaktır. Büyük bölümler asal çıkarsa, toplamak istediğimiz en büyük asal çarpanlar doğrudan bu bölümler olur.
Çalışılan modül
$$M=16\cdot 9\cdot 5\cdot 7\cdot 11\cdot 13=720720$$
olur. Önce şu kongrüanslar seçilir:
$$n\equiv 5 \pmod 9,\qquad n\equiv 1 \pmod 5,\qquad n\equiv 3 \pmod 7.$$
Böylece \(n+4\), \(9\), \(5\) ve \(7\)'ye aynı anda bölünür; dolayısıyla
$$315 \mid (n+4).$$
Daha sonra
$$n\equiv 1 \pmod{16}\qquad \text{veya}\qquad n\equiv 7 \pmod{16}$$
seçilir. Birinci durumda
$$2\mid(n+1),\qquad 4\mid(n+3),\qquad 2\mid(n+5),\qquad 8\mid(n+7)$$
elde edilir. İkinci durumda ise iki kuvvetleri şu şekilde yer değiştirir:
$$8\mid(n+1),\qquad 2\mid(n+3),\qquad 4\mid(n+5),\qquad 2\mid(n+7).$$
Ayrıca \(n\equiv 5 \pmod 9\) olduğu için \(n+1\) ve \(n+7\) üçe de bölünür. Böylece tek ofsetlerde her zaman
$$\{6,4,2,24\}$$
bölen çokluğu oluşur; yalnızca bu dört sayının hangi ofsetlere denk geldiği, mod \(16\)'daki seçime göre değişir.
Yapı ayrıca
$$n\equiv 1\text{ veya }2 \pmod{11},\qquad n\equiv 1,2,3,\text{ veya }4 \pmod{13}$$
koşullarını da ister. Bu seçimler sayesinde \(n,n+1,\dots,n+8\) içindeki hiçbir sayı \(11\) ya da \(13\)'e bölünmez; çünkü dokuz terimlik artık aralığı bu iki modda \(0\) kalıntısına hiç uğramaz. Bağımsız seçimler toplamda
$$2\cdot 2\cdot 4=16$$
adet uygun kalıntı sınıfı verir. Çin Kalan Teoremi bunları mod \(M\) altında 16 somut kalıntıya \(r\) dönüştürür ve programın incelediği her aday
$$n\equiv r \pmod M$$
şeklindedir.
Temsilî bir kalıntı ailesinde dokuz sayı şu biçimi alır:
$$n+j=d_j q_j,\qquad d=(1,6,1,4,315,2,1,24,1).$$
Aynalanmış aile ise tek ofsetlerdeki \((6,4,2,24)\) düzenini \((24,2,4,6)\) olarak değiştirir. Her iki durumda da \(d_j\) yalnızca \(\{2,3,5,7\}\) kümesindeki küçük asalları içerir. Eğer bölüm \(q_j\) asal ise, \(d_j\)'yi bölen bütün asallardan daha büyük olur ve
$$P(n+j)=q_j=\frac{n+j}{d_j}$$
elde edilir. Bu nedenle tam başarılı bir adayda hedef toplam \(n\)'in doğrusal bir ifadesine dönüşür. Gösterilen aile için
$$S(n)=n+\frac{n+1}{6}+(n+2)+\frac{n+3}{4}+\frac{n+4}{315}+\frac{n+5}{2}+(n+6)+\frac{n+7}{24}+(n+8)$$
olur. Aynalanmış ailenin \(n\) katsayısı aynıdır; çünkü kullanılan ters katsayı çokluğu yine
$$\left\{1,\frac16,1,\frac14,\frac1{315},\frac12,1,\frac1{24},1\right\}$$
olur. Bu gözlem önemlidir: \(n\) büyüdükçe skor da büyür, dolayısıyla her kalıntı sınıfında üst sınıra en yakın adaylar daha değerlidir.
Şunu tanımlayalım:
$$N_0=M\left\lfloor\frac{10^{16}}{M}\right\rfloor.$$
Her uygun kalıntı \(r\) için uygulamalar
$$n=N_0+r-Mk,\qquad 0\le k<10^7$$
biçimindeki adayları inceler. Böylece başlangıçtaki \(n\) araması, tek boyutlu bir \(k\) taramasına dönüşür. Her adım \(n\)'yi tam olarak \(M\) kadar azaltır. Bölünebilme deseni sabitlenince skor \(n\)'in afin bir fonksiyonu olduğundan, aynı kalıntı sınıfında daha küçük \(k\) her zaman daha iyi aday demektir.
Süzgeçte
$$17\le p<10^8$$
şartını sağlayan tüm asallar kullanılır. Bunlar, kalıntı yapısı tarafından önceden ele alınmamış asallardır. \(p\nmid M\) olduğu için \(M^{-1}\pmod p\) vardır. Bir \(j\) ofseti için ilgili bölümün \(p\)'ye bölünmesi koşulu
$$N_0+r+j-Mk\equiv 0 \pmod p$$
ile eşdeğerdir; dolayısıyla kötü \(k\) değerleri
$$k\equiv (N_0+r+j)M^{-1}\pmod p$$
aritmetik ilerlemesine düşer. Böylece her asal, dokuz ofsetin her biri için en fazla bir \(k\) kalıntı sınıfını işaretler. İşaretlenmeyen indeksler, dokuz indirgenmiş bölümün hiçbirinin \(17\) ile \(10^8-1\) arasında bir asal böleni olmadığı adaylardır.
En büyük indirgenmiş bölüm yaklaşık \(10^{16}\) mertebesindedir; karekökü yaklaşık \(10^8\)'dir. En küçük indirgenmiş bölüm ise \(315\)'e bölünmüş halidir ve
$$\sqrt{\frac{10^{16}}{315}}<10^8$$
olur. Bu nedenle programın kontrol ettiği her bölümün karekökü süzgeç sınırının altındadır. Pozitif bir bölüm \(10^8\)'e kadar tüm asal bölenlerden kurtuluyorsa, kareköküne kadar hiçbir böleni yoktur ve asal olmak zorundadır. Yani modüler süzgeç, indirgenmiş sayılar için tam bir asallık belgesine dönüşür.
Uygulamalarda büyük aramadan önce küçük bir doğrulama bulunur. Doğrudan çarpanlara ayırma şu değerleri verir:
$$\begin{aligned} P(100)&=5,\quad P(101)=101,\quad P(102)=17,\quad P(103)=103,\\ P(104)&=13,\quad P(105)=7,\quad P(106)=53,\quad P(107)=107,\quad P(108)=3. \end{aligned}$$
Böylece
$$S(100)=5+101+17+103+13+7+53+107+3=409$$
elde edilir. Aynı küçük tarama ayrıca
$$\max_{2\le n\le 100} S(n)=417$$
sonucunu da doğrular. Bu örnek elle ya da kısa bir doğrulama koduyla kolayca kontrol edilebilir ve büyük aramaya geçmeden önce tanımın doğru uygulandığını gösterir.
C++, Python ve Java uygulamaları aynı matematiksel planı izler. Önce CRT koşullarından doğan 16 uygun kalıntı üretilir. Ardından \(17\)'den \(10^8-1\)'e kadar olan tüm asallar oluşturulur ve her asal için \(M\)'nin modüler tersi önceden hesaplanır.
Sonrasında her işçi, kalıntı sınıflarının bir alt kümesini işler. Tek bir kalıntı sınıfı için uzunluğu \(10^7\) olan bir bayt dizisi tutulur; bu dizide her hücre bir \(k\) indeksine karşılık gelir. Her asal ve her \(j=0,\dots,8\) ofseti için, o ofsetteki indirgenmiş bölümü bu asala bölünebilir yapan aritmetik ilerleme işaretlenir. İşaretleme bittikten sonra elde kalan indeksler hayatta kalan adaylardır.
Son aşamada, hayatta kalan her adayın bölüm temelli skoru hesaplanır ve tüm kalıntı sınıfları üzerinde maksimum alınır. Python girişi aynı yerel çözüm mantığını yeniden kullanır; Java sürümü ise aynı eleme-ve-tarama stratejisini doğrudan uygular.
\(B=10^8\) ve \(K=10^7\) olsun. \(B\)'ye kadar asal tablosu kurmak \(O(B\log\log B)\) zaman ve \(O(B)\) bellek ister. Tek bir kalıntı sınıfı için işaretleme maliyeti
$$O\!\left(9K\sum_{p<B}\frac1p\right)=O(K\log\log B)$$
olur; ardından bir adet \(O(K)\) uzunluklu doğrusal tarama gelir. Sadece 16 kalıntı sınıfı bulunduğu için toplam asimptotik maliyet sabit bir \(16\) katsayısı dışında yine \(O(B\log\log B+K\log\log B)\) biçimindedir. Pratikte belleği belirleyen ana unsurlar, büyük asal süzgeci ile işçi başına tutulan \(K\) boyutlu işaretleme dizisidir.
Sea \(P(m)\) el mayor factor primo de \(m\). Para nueve enteros consecutivos definimos
$$S(n)=\sum_{j=0}^{8} P(n+j).$$
La meta es hallar el valor máximo de \(S(n)\) cuando el punto inicial no supera \(10^{16}\). Un barrido directo es inviable: el rango es inmenso y cada candidato exigiría factorizar nueve enteros cercanos. Por eso la implementación impone primero ciertos divisores pequeños y después comprueba si los cocientes restantes son primos.
La idea central consiste en construir progresiones aritméticas en las que los números \(n,n+1,\dots,n+8\) ya tengan una estructura de factorización favorable. Si los cocientes grandes resultan primos, entonces esos mismos cocientes son exactamente los mayores factores primos que se desean sumar.
Se trabaja módulo
$$M=16\cdot 9\cdot 5\cdot 7\cdot 11\cdot 13=720720.$$
Primero se imponen las congruencias
$$n\equiv 5 \pmod 9,\qquad n\equiv 1 \pmod 5,\qquad n\equiv 3 \pmod 7.$$
Entonces \(n+4\) es divisible por \(9\), \(5\) y \(7\), así que
$$315 \mid (n+4).$$
Después se elige
$$n\equiv 1 \pmod{16}\qquad \text{o}\qquad n\equiv 7 \pmod{16}.$$
En el primer caso se obtiene
$$2\mid(n+1),\qquad 4\mid(n+3),\qquad 2\mid(n+5),\qquad 8\mid(n+7).$$
En el segundo caso las potencias de \(2\) se redistribuyen como
$$8\mid(n+1),\qquad 2\mid(n+3),\qquad 4\mid(n+5),\qquad 2\mid(n+7).$$
Además, como \(n\equiv 5 \pmod 9\), los términos \(n+1\) y \(n+7\) también son divisibles por \(3\). Por tanto, en los desplazamientos impares siempre aparece el multiconjunto de divisores
$$\{6,4,2,24\},$$
aunque su ubicación exacta depende de cuál de las dos clases módulo \(16\) se haya elegido.
La construcción también exige
$$n\equiv 1\text{ o }2 \pmod{11},\qquad n\equiv 1,2,3,\text{ o }4 \pmod{13}.$$
Con estas elecciones, ninguno de los nueve números \(n,n+1,\dots,n+8\) es divisible por \(11\) ni por \(13\): los intervalos de residuos correspondientes nunca alcanzan \(0\) módulo esos primos. Al combinar todas las opciones independientes aparecen
$$2\cdot 2\cdot 4=16$$
clases de residuos admisibles módulo \(M\). El Teorema Chino del Resto fusiona esas condiciones en 16 residuos concretos \(r\), y cada candidato examinado por el programa satisface
$$n\equiv r \pmod M.$$
Para una familia representativa de residuos, los nueve términos toman la forma
$$n+j=d_j q_j,\qquad d=(1,6,1,4,315,2,1,24,1).$$
La familia simétrica solo permuta los cuatro divisores de los desplazamientos impares, pasando de \((6,4,2,24)\) a \((24,2,4,6)\). En ambos casos \(d_j\) solo contiene primos de \(\{2,3,5,7\}\). Si \(q_j\) es primo, entonces es forzosamente mayor que cualquier primo que divida a \(d_j\), y por ello
$$P(n+j)=q_j=\frac{n+j}{d_j}.$$
Así, sobre un candidato completamente válido, la suma buscada se vuelve una expresión lineal en \(n\). Para la familia mostrada,
$$S(n)=n+\frac{n+1}{6}+(n+2)+\frac{n+3}{4}+\frac{n+4}{315}+\frac{n+5}{2}+(n+6)+\frac{n+7}{24}+(n+8).$$
La familia simétrica tiene el mismo coeficiente de \(n\), porque usa el mismo multiconjunto de recíprocos
$$\left\{1,\frac16,1,\frac14,\frac1{315},\frac12,1,\frac1{24},1\right\}.$$
Esto es importante: dentro de una misma clase de residuos, cuanto mayor sea \(n\), mayor será el valor de la suma.
Definimos
$$N_0=M\left\lfloor\frac{10^{16}}{M}\right\rfloor.$$
Para cada residuo admisible \(r\), las implementaciones estudian candidatos de la forma
$$n=N_0+r-Mk,\qquad 0\le k<10^7.$$
Esto transforma la búsqueda original sobre \(n\) en un recorrido unidimensional sobre \(k\). Cada incremento de \(k\) reduce \(n\) exactamente en \(M\), y una vez fijado el patrón de divisibilidad la puntuación es afín en \(n\). Por eso, dentro de una clase de residuos, los valores pequeños de \(k\) son los más prometedores.
El cribado usa todos los primos
$$17\le p<10^8.$$
Son precisamente los primos que no quedan ya controlados por la construcción de residuos. Como \(p\nmid M\), existe el inverso \(M^{-1}\pmod p\). Para un desplazamiento \(j\), pedir que el cociente correspondiente sea divisible por \(p\) equivale a exigir
$$N_0+r+j-Mk\equiv 0 \pmod p,$$
y por tanto los índices malos \(k\) forman la progresión aritmética
$$k\equiv (N_0+r+j)M^{-1}\pmod p.$$
Cada primo marca así, para cada uno de los nueve desplazamientos, a lo sumo una clase residual de \(k\). Los índices no marcados son exactamente los candidatos cuyos nueve cocientes reducidos no tienen divisores primos entre \(17\) y \(10^8-1\).
El mayor cociente reducido es del orden de \(10^{16}\), de modo que su raíz cuadrada es aproximadamente \(10^8\). El menor cociente reducido aparece tras dividir por \(315\), y
$$\sqrt{\frac{10^{16}}{315}}<10^8.$$
Así, todos los cocientes que maneja el programa tienen raíz cuadrada por debajo del límite del cribado. Si un cociente positivo sobrevive a todos los primos hasta \(10^8\), entonces no posee divisores hasta su raíz cuadrada y debe ser primo. El cribado modular funciona, por tanto, como un certificado completo de primalidad para los cocientes reducidos.
Antes de lanzar la búsqueda completa, las implementaciones incluyen un ejemplo pequeño de verificación. La factorización directa da
$$\begin{aligned} P(100)&=5,\quad P(101)=101,\quad P(102)=17,\quad P(103)=103,\\ P(104)&=13,\quad P(105)=7,\quad P(106)=53,\quad P(107)=107,\quad P(108)=3. \end{aligned}$$
Por consiguiente,
$$S(100)=5+101+17+103+13+7+53+107+3=409.$$
El mismo barrido de control también confirma que
$$\max_{2\le n\le 100} S(n)=417.$$
Es un ejemplo lo bastante pequeño como para verificarlo directamente, y sirve para asegurar que la definición del mayor factor primo está bien interpretada antes de entrar en la búsqueda grande con clases de residuos.
Las implementaciones en C++, Python y Java siguen el mismo plan matemático. Primero construyen los 16 residuos admisibles obtenidos por las condiciones CRT. Después generan todos los primos entre \(17\) y \(10^8-1\), y para cada uno precalculan el inverso modular de \(M\).
Cada trabajador procesa entonces un subconjunto independiente de clases de residuos. Para una clase fija mantiene un arreglo de bytes de longitud \(10^7\), una posición por cada índice \(k\). Para cada primo y cada desplazamiento \(j=0,\dots,8\), marca la progresión aritmética de índices que haría al cociente reducido correspondiente divisible por ese primo. Una vez terminada esa fase, los índices no marcados son los candidatos supervivientes.
Finalmente, la implementación evalúa la suma basada en cocientes para cada candidato superviviente y conserva el máximo global. La entrada de Python reutiliza la misma lógica nativa de búsqueda, mientras que la versión de Java implementa directamente la misma estrategia de cribado y escaneo.
Si escribimos \(B=10^8\) y \(K=10^7\), construir la tabla de primos hasta \(B\) cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria. Para una sola clase de residuos, el trabajo de marcado es
$$O\!\left(9K\sum_{p<B}\frac1p\right)=O(K\log\log B),$$
seguido de un recorrido lineal de \(K\) posiciones. Como solo existen 16 clases de residuos, el coste asintótico total sigue siendo \(O(B\log\log B+K\log\log B)\) salvo por un factor constante igual a 16. En la práctica, la memoria queda dominada por el gran cribado de primos y por un arreglo de marcadores de tamaño \(K\) por hilo de trabajo.
设 \(P(m)\) 表示整数 \(m\) 的最大素因子。对九个连续整数定义
$$S(n)=\sum_{j=0}^{8} P(n+j).$$
题目要求在起点不超过 \(10^{16}\) 的范围内求出 \(S(n)\) 的最大值。直接枚举完全不可行，因为搜索区间太大，而且每个候选 \(n\) 都要分解九个相邻整数。实现采用的思路不是逐点分解，而是先构造一批同余类，使窗口中的若干位置自带固定的小因子，然后只对剩余的大商做素性筛除。
核心思想是：把 \(n,n+1,\dots,n+8\) 放进一个精心设计的模结构里，让其中若干项的“小部分”先固定下来。如果剩余商都是素数，那么这些商自然就是各项的最大素因子，于是目标和就可以直接写成这些商的和。
程序在模
$$M=16\cdot 9\cdot 5\cdot 7\cdot 11\cdot 13=720720$$
的意义下工作。首先要求
$$n\equiv 5 \pmod 9,\qquad n\equiv 1 \pmod 5,\qquad n\equiv 3 \pmod 7.$$
这样一来，\(n+4\) 同时被 \(9\)、\(5\)、\(7\) 整除，因此
$$315 \mid (n+4).$$
然后再规定
$$n\equiv 1 \pmod{16}\qquad \text{或}\qquad n\equiv 7 \pmod{16}.$$
如果 \(n\equiv 1 \pmod{16}\)，那么
$$2\mid(n+1),\qquad 4\mid(n+3),\qquad 2\mid(n+5),\qquad 8\mid(n+7).$$
如果 \(n\equiv 7 \pmod{16}\)，那么二次幂的分布会变成
$$8\mid(n+1),\qquad 2\mid(n+3),\qquad 4\mid(n+5),\qquad 2\mid(n+7).$$
又因为 \(n\equiv 5 \pmod 9\)，所以 \(n+1\) 与 \(n+7\) 还会额外带一个因子 \(3\)。因此，四个奇数偏移位置总会得到同一个除数多重集合
$$\{6,4,2,24\},$$
只不过这四个值在不同偏移上的具体摆放，会随模 \(16\) 的选择而改变。
构造还附加了
$$n\equiv 1\text{ 或 }2 \pmod{11},\qquad n\equiv 1,2,3,\text{ 或 }4 \pmod{13}$$
这组条件。这样做的目的是让 \(n,n+1,\dots,n+8\) 这九个数里没有任何一个能被 \(11\) 或 \(13\) 整除，因为对应的九个连续余数区间不会碰到 \(0\)。把所有独立选择合并起来，一共得到
$$2\cdot 2\cdot 4=16$$
个合法的模 \(M\) 余数类。中国剩余定理把这些条件拼成 16 个具体余数 \(r\)，程序实际考察的每一个候选都满足
$$n\equiv r \pmod M.$$
对其中一类代表性的余数族，可以把九个数写成
$$n+j=d_j q_j,\qquad d=(1,6,1,4,315,2,1,24,1).$$
另一类镜像余数族只是在奇数偏移处把 \((6,4,2,24)\) 重新排列成 \((24,2,4,6)\)。无论哪一类，\(d_j\) 里都只含有 \(\{2,3,5,7\}\) 这些很小的素数。如果商 \(q_j\) 本身是素数，那么它一定大于 \(d_j\) 里的所有素因子，于是
$$P(n+j)=q_j=\frac{n+j}{d_j}.$$
这样一来，在完全成功的候选上，目标函数就变成 \(n\) 的一个线性表达式。对上面这类代表模式，有
$$S(n)=n+\frac{n+1}{6}+(n+2)+\frac{n+3}{4}+\frac{n+4}{315}+\frac{n+5}{2}+(n+6)+\frac{n+7}{24}+(n+8).$$
镜像族虽然奇数位置的除数顺序不同，但使用的倒数多重集合仍然是
$$\left\{1,\frac16,1,\frac14,\frac1{315},\frac12,1,\frac1{24},1\right\},$$
所以 \(n\) 的总系数完全相同。这一点很重要，因为它说明在同一个余数类里，\(n\) 越大，得到的分数就越大。
令
$$N_0=M\left\lfloor\frac{10^{16}}{M}\right\rfloor.$$
对每个合法余数 \(r\)，实现扫描的候选形式为
$$n=N_0+r-Mk,\qquad 0\le k<10^7.$$
这一步把原来对 \(n\) 的搜索改写成了对单个参数 \(k\) 的扫描。每增加 1 个 \(k\)，\(n\) 就精确减少一个 \(M\)。而当整除模式固定以后，得分对 \(n\) 是仿射的，因此同一个余数类里越靠近上界的候选越值得优先考虑。
程序使用所有满足
$$17\le p<10^8$$
的素数。这些正是没有被同余构造提前处理掉的素数。由于 \(p\nmid M\)，模 \(p\) 下的逆元 \(M^{-1}\) 一定存在。对任意偏移 \(j\)，若对应商被 \(p\) 整除，则等价于
$$N_0+r+j-Mk\equiv 0 \pmod p,$$
于是所有坏的 \(k\) 都落在同一个等差序列中：
$$k\equiv (N_0+r+j)M^{-1}\pmod p.$$
也就是说，对每个素数、每个偏移，程序只需标记一条模 \(p\) 的等差进程。没有被标记的 \(k\)，恰好对应于九个约化商都不含 \(17\) 到 \(10^8-1\) 之间素因子的候选。
最大的约化商量级约为 \(10^{16}\)，其平方根大约是 \(10^8\)。最小的约化商出现在除以 \(315\) 的位置，而且
$$\sqrt{\frac{10^{16}}{315}}<10^8.$$
因此，程序处理到的每一个约化商，其平方根都低于筛的上界。只要一个正商没有任何不超过 \(10^8\) 的素因子，它就不可能再有不超过自身平方根的因子，所以它必然是素数。换句话说，这里的模筛不仅是“排除小因子”，实际上已经足够完成素性判定。
在进入正式搜索之前，实现先做一个很小的校验例子。直接分解可得
$$\begin{aligned} P(100)&=5,\quad P(101)=101,\quad P(102)=17,\quad P(103)=103,\\ P(104)&=13,\quad P(105)=7,\quad P(106)=53,\quad P(107)=107,\quad P(108)=3. \end{aligned}$$
因此
$$S(100)=5+101+17+103+13+7+53+107+3=409.$$
同一段小范围检查还验证了
$$\max_{2\le n\le 100} S(n)=417.$$
这个例子规模很小，可以直接算出来，作用是先确认“最大素因子求和”的定义没有理解错误，然后再执行真正的大规模同余筛搜索。
C++、Python 和 Java 三个实现遵循同一套数学流程。第一步先构造出 CRT 条件对应的 16 个合法余数。第二步生成 \(17\) 到 \(10^8-1\) 之间的全部素数，并为每个素数预先算出 \(M\) 在该模数下的乘法逆元。
随后，每个工作线程负责若干个余数类。对某个固定余数类，它维护一个长度为 \(10^7\) 的字节数组，每个位置对应一个 \(k\)。对每个素数以及每个偏移 \(j=0,\dots,8\)，程序都会标记那条使相应约化商被该素数整除的等差数列。标记完成以后，没有被标记的位置就是幸存候选。
最后，实现对每个幸存候选计算基于商的得分，并在全部余数类上取最大值。Python 入口复用同样的原生搜索逻辑，而 Java 版本则直接实现同样的筛选与扫描过程。
记 \(B=10^8\)、\(K=10^7\)。建立到 \(B\) 为止的素数表需要 \(O(B\log\log B)\) 时间和 \(O(B)\) 空间。对单个余数类，标记工作量为
$$O\!\left(9K\sum_{p<B}\frac1p\right)=O(K\log\log B),$$
之后还要做一次 \(O(K)\) 的线性扫描。由于余数类只有 16 个，所以总的渐近复杂度仍然可以写成 \(O(B\log\log B+K\log\log B)\)，只差一个固定常数因子。实际内存主要消耗在大素数筛本身，以及每个工作线程维护的一份长度为 \(K\) 的标记数组上。
Пусть \(P(m)\) обозначает наибольший простой делитель числа \(m\). Для девяти последовательных чисел определим
$$S(n)=\sum_{j=0}^{8} P(n+j).$$
Требуется найти максимальное значение \(S(n)\) при начальных точках, не превосходящих \(10^{16}\). Прямой перебор невозможен: диапазон слишком велик, а для каждого кандидата пришлось бы факторизовать девять соседних чисел. Поэтому реализации сначала строят специальные классы вычетов, в которых несколько позиций уже имеют заранее известные малые множители, а затем проверяют простоту оставшихся больших частных.
Главная идея состоит в том, чтобы подобрать такие арифметические прогрессии, где числа \(n,n+1,\dots,n+8\) заранее обладают выгодной структурой разложения. Если оставшиеся частные оказываются простыми, то именно они и являются теми самыми наибольшими простыми делителями, которые надо суммировать.
Поиск ведется по модулю
$$M=16\cdot 9\cdot 5\cdot 7\cdot 11\cdot 13=720720.$$
Сначала задаются сравнения
$$n\equiv 5 \pmod 9,\qquad n\equiv 1 \pmod 5,\qquad n\equiv 3 \pmod 7.$$
Тогда число \(n+4\) делится одновременно на \(9\), \(5\) и \(7\), а значит
$$315 \mid (n+4).$$
Затем выбирается одно из двух условий
$$n\equiv 1 \pmod{16}\qquad \text{или}\qquad n\equiv 7 \pmod{16}.$$
В первом случае получаем
$$2\mid(n+1),\qquad 4\mid(n+3),\qquad 2\mid(n+5),\qquad 8\mid(n+7).$$
Во втором случае степени двойки перераспределяются так:
$$8\mid(n+1),\qquad 2\mid(n+3),\qquad 4\mid(n+5),\qquad 2\mid(n+7).$$
Поскольку \(n\equiv 5 \pmod 9\), числа \(n+1\) и \(n+7\) дополнительно делятся на \(3\). Поэтому на нечётных сдвигах всегда возникает один и тот же набор делителей
$$\{6,4,2,24\},$$
хотя конкретное расположение этих четырех значений зависит от выбора остатка по модулю \(16\).
Конструкция также требует
$$n\equiv 1\text{ или }2 \pmod{11},\qquad n\equiv 1,2,3,\text{ или }4 \pmod{13}.$$
Этим гарантируется, что ни одно из девяти чисел \(n,n+1,\dots,n+8\) не делится на \(11\) или \(13\): соответствующие интервалы вычетов не содержат нуля по этим модулям. Все независимые варианты вместе дают
$$2\cdot 2\cdot 4=16$$
допустимых классов вычетов по модулю \(M\). Китайская теорема об остатках собирает условия в 16 конкретных остатков \(r\), и каждый кандидат, который рассматривает программа, удовлетворяет
$$n\equiv r \pmod M.$$
Для одной представительной семьи классов вычетов девять чисел имеют вид
$$n+j=d_j q_j,\qquad d=(1,6,1,4,315,2,1,24,1).$$
Зеркальная семья просто переставляет четыре нечётных делителя, заменяя \((6,4,2,24)\) на \((24,2,4,6)\). В любом случае \(d_j\) содержит только простые числа из множества \(\{2,3,5,7\}\). Если частное \(q_j\) простое, то оно автоматически больше любого простого делителя числа \(d_j\), и потому
$$P(n+j)=q_j=\frac{n+j}{d_j}.$$
Следовательно, на полностью удачном кандидате целевая сумма превращается в линейное выражение по \(n\). Для показанной семьи получаем
$$S(n)=n+\frac{n+1}{6}+(n+2)+\frac{n+3}{4}+\frac{n+4}{315}+\frac{n+5}{2}+(n+6)+\frac{n+7}{24}+(n+8).$$
У зеркальной семьи тот же коэффициент при \(n\), потому что используется тот же набор обратных величин
$$\left\{1,\frac16,1,\frac14,\frac1{315},\frac12,1,\frac1{24},1\right\}.$$
Это важно: внутри одного класса вычетов большему \(n\) соответствует и большее значение суммы.
Положим
$$N_0=M\left\lfloor\frac{10^{16}}{M}\right\rfloor.$$
Для каждого допустимого остатка \(r\) реализации рассматривают кандидаты вида
$$n=N_0+r-Mk,\qquad 0\le k<10^7.$$
Так исходный поиск по \(n\) превращается в одномерное сканирование по \(k\). Каждый шаг уменьшает \(n\) ровно на \(M\), а когда шаблон делимости уже фиксирован, значение функции аффинно зависит от \(n\). Поэтому внутри одного класса вычетов меньшие \(k\) всегда предпочтительнее.
Сито использует все простые числа
$$17\le p<10^8.$$
Это как раз те простые, которые не были заранее обработаны через систему сравнений. Поскольку \(p\nmid M\), обратный элемент \(M^{-1}\pmod p\) существует. Для фиксированного сдвига \(j\) условие делимости соответствующего частного на \(p\) равносильно сравнению
$$N_0+r+j-Mk\equiv 0 \pmod p,$$
то есть плохие значения \(k\) образуют арифметическую прогрессию
$$k\equiv (N_0+r+j)M^{-1}\pmod p.$$
Иными словами, каждый простой \(p\) помечает не более одного класса вычетов по \(k\) для каждого из девяти сдвигов. Непомеченные индексы — это ровно те кандидаты, у которых ни одно из девяти редуцированных частных не имеет простого делителя между \(17\) и \(10^8-1\).
Наибольшее редуцированное частное имеет порядок \(10^{16}\), поэтому его квадратный корень имеет порядок \(10^8\). Наименьшее редуцированное частное получается после деления на \(315\), и
$$\sqrt{\frac{10^{16}}{315}}<10^8.$$
Следовательно, квадратный корень любого частного, которое проверяет программа, меньше границы сита. Если положительное частное не делится ни на один простой до \(10^8\), то у него нет делителей вплоть до собственного квадратного корня, а значит оно обязано быть простым. Тем самым модульное сито одновременно дает и полную проверку простоты редуцированных чисел.
Перед основным поиском реализации выполняют небольшой контрольный пример. Прямая факторизация дает
$$\begin{aligned} P(100)&=5,\quad P(101)=101,\quad P(102)=17,\quad P(103)=103,\\ P(104)&=13,\quad P(105)=7,\quad P(106)=53,\quad P(107)=107,\quad P(108)=3. \end{aligned}$$
Отсюда
$$S(100)=5+101+17+103+13+7+53+107+3=409.$$
Та же контрольная проверка подтверждает и равенство
$$\max_{2\le n\le 100} S(n)=417.$$
Этот пример достаточно мал, чтобы его можно было проверить напрямую, и он подтверждает корректную интерпретацию суммы наибольших простых делителей еще до запуска большого поиска по классам вычетов.
Реализации на C++, Python и Java следуют одному и тому же плану. Сначала они строят 16 допустимых остатков, возникающих из условий CRT. Затем генерируются все простые числа от \(17\) до \(10^8-1\), и для каждого такого простого заранее вычисляется обратный элемент для \(M\) по соответствующему модулю.
После этого каждый рабочий поток обрабатывает независимое подмножество классов вычетов. Для одного класса он держит байтовый массив длины \(10^7\), по одной позиции на каждый индекс \(k\). Для каждого простого и каждого сдвига \(j=0,\dots,8\) реализация помечает арифметическую прогрессию индексов, которая сделала бы соответствующее редуцированное частное делимым на этот простой. Когда фаза пометок завершена, непомеченные индексы и есть выжившие кандидаты.
Затем программа вычисляет для каждого выжившего кандидата сумму, построенную из редуцированных частных, и сохраняет глобальный максимум. Точка входа Python использует ту же нативную поисковую логику, а версия на Java напрямую реализует ту же схему ситового отбора и последующего прохода.
Пусть \(B=10^8\), \(K=10^7\). Построение таблицы простых чисел до \(B\) требует \(O(B\log\log B)\) времени и \(O(B)\) памяти. Для одного класса вычетов работа по пометке составляет
$$O\!\left(9K\sum_{p<B}\frac1p\right)=O(K\log\log B),$$
после чего выполняется линейный проход по \(K\) флагам. Так как классов вычетов всего 16, итоговая асимптотика остается \(O(B\log\log B+K\log\log B)\) с точностью до фиксированного множителя 16. На практике память в основном расходуется на большое простое сито и на один массив меток длины \(K\) для каждого рабочего потока.
لتكن \(P(m)\) أكبر قاسم أولي للعدد \(m\). ولتكن
$$S(n)=\sum_{j=0}^{8} P(n+j)$$
مجموع أكبر القواسم الأولية لتسعة أعداد متتالية تبدأ من \(n\). المطلوب هو إيجاد أكبر قيمة ممكنة لهذا المجموع عندما لا يتجاوز موضع البداية \(10^{16}\). الفحص المباشر غير عملي تمامًا، لأن المجال هائل ولكل قيمة مرشحة من \(n\) نحتاج إلى تحليل تسعة أعداد متقاربة إلى عواملها الأولية. لذلك تعتمد الحلول على بناء فئات بواقي تجعل بعض الحدود تحمل عوامل صغيرة ثابتة سلفًا، ثم تُختبر الأجزاء الكبيرة المتبقية بالغربلة.
الفكرة الأساسية هي تصميم متتاليات حسابية يكون فيها النمط العام لتحليل الأعداد \(n,n+1,\dots,n+8\) معروفًا مسبقًا. فإذا كانت الحصص الكبيرة المتبقية أعدادًا أولية، فإن هذه الحصص نفسها تصبح أكبر القواسم الأولية المطلوبة في المجموع.
يُجرى البحث modulo
$$M=16\cdot 9\cdot 5\cdot 7\cdot 11\cdot 13=720720.$$
أولًا نفرض الشروط
$$n\equiv 5 \pmod 9,\qquad n\equiv 1 \pmod 5,\qquad n\equiv 3 \pmod 7.$$
عندئذٍ يكون \(n+4\) قابلاً للقسمة على \(9\) و\(5\) و\(7\) معًا، وبالتالي
$$315 \mid (n+4).$$
ثم نختار أحد الشرطين
$$n \bmod 16 \in \{1,7\}.$$
في الحالة الأولى نحصل على
$$2\mid(n+1),\qquad 4\mid(n+3),\qquad 2\mid(n+5),\qquad 8\mid(n+7).$$
وفي الحالة الثانية تنتقل قوى العدد \(2\) لتصبح
$$8\mid(n+1),\qquad 2\mid(n+3),\qquad 4\mid(n+5),\qquad 2\mid(n+7).$$
وبما أن \(n\equiv 5 \pmod 9\)، فإن \(n+1\) و\(n+7\) يقبلان القسمة على \(3\) أيضًا. لهذا السبب تحمل الإزاحات الفردية دائمًا مجموعة القواسم
$$\{6,4,2,24\},$$
لكن توزيع هذه القيم الأربع على المواقع الفردية يتبدل بحسب الباقي المختار modulo \(16\).
تضيف البنية كذلك الشرطين
$$n \bmod 11 \in \{1,2\},\qquad n \bmod 13 \in \{1,2,3,4\}.$$
وهذا يضمن أن أي عدد من الأعداد التسعة \(n,n+1,\dots,n+8\) لا يكون قابلاً للقسمة على \(11\) أو \(13\)، لأن مقطع البواقي المتتالي لا يمر بالباقي \(0\) في هذين المعيارين. وعند جمع جميع الخيارات المستقلة نحصل على
$$2\cdot 2\cdot 4=16$$
فئة بواقي مسموحة modulo \(M\). ثم تجمع مبرهنة البواقي الصينية هذه الشروط في 16 باقيًا صريحًا \(r\)، ويحقق كل مرشح يفحصه البرنامج العلاقة
$$n\equiv r \pmod M.$$
في إحدى العائلات التمثيلية من فئات البواقي يمكن كتابة الحدود التسعة بالشكل
$$n+j=d_j q_j,\qquad d=(1,6,1,4,315,2,1,24,1).$$
أما العائلة المرآتية فتعيد ترتيب القواسم الفردية من \((6,4,2,24)\) إلى \((24,2,4,6)\) فقط. في كلتا الحالتين، يتكوّن \(d_j\) من الأعداد الأولية الصغيرة \(\{2,3,5,7\}\) فحسب. إذا كان \(q_j\) عددًا أوليًا، فهو بالضرورة أكبر من كل قاسم أولي يظهر داخل \(d_j\)، ومن ثم
$$P(n+j)=q_j=\frac{n+j}{d_j}.$$
وبذلك يصبح المجموع المطلوب، على أي مرشح ناجح بالكامل، تعبيرًا خطيًا في \(n\). وفي العائلة المعروضة يكون
$$S(n)=n+\frac{n+1}{6}+(n+2)+\frac{n+3}{4}+\frac{n+4}{315}+\frac{n+5}{2}+(n+6)+\frac{n+7}{24}+(n+8).$$
العائلة المرآتية تمتلك المعامل نفسه أمام \(n\)، لأنها تستخدم المجموعة نفسها من المقلوبات
$$\left\{1,\frac16,1,\frac14,\frac1{315},\frac12,1,\frac1{24},1\right\}.$$
وهذه ملاحظة مهمة: داخل فئة بواقي واحدة، كلما كان \(n\) أكبر كانت قيمة المجموع أكبر.
لنعرّف
$$N_0=M\left\lfloor\frac{10^{16}}{M}\right\rfloor.$$
ولكل باقي مسموح \(r\)، تفحص التطبيقات المرشحات من الصورة
$$n=N_0+r-Mk,\qquad 0\le k<10^7.$$
بهذا تتحول المسألة من بحث على \(n\) إلى مسح أحادي البعد على \(k\). كل زيادة بمقدار واحد في \(k\) تُنقص \(n\) بمقدار \(M\) بالضبط. وبعد تثبيت نمط القسمة يصبح المجموع دالة تآلفية في \(n\)، ولذلك تكون القيم الصغيرة لـ \(k\) هي الأفضل داخل الفئة نفسها.
يستخدم الغربال جميع الأعداد الأولية التي تحقق
$$17\le p<10^8.$$
وهذه هي الأعداد الأولية التي لم تُعالَج مسبقًا عن طريق شروط البواقي. ولأن \(p\nmid M\)، فإن المعكوس \(M^{-1}\pmod p\) موجود. إذا أردنا أن يكون خارج القسمة الموافق للإزاحة \(j\) قابلاً للقسمة على \(p\)، فهذا يكافئ الشرط
$$N_0+r+j-Mk\equiv 0 \pmod p,$$
ومن ثم تقع قيم \(k\) الممنوعة في متتالية حسابية واحدة:
$$k\equiv (N_0+r+j)M^{-1}\pmod p.$$
إذًا، لكل أولي ولكل إزاحة من الإزاحات التسع، نحتاج فقط إلى تعليم فئة بواقي واحدة من قيم \(k\). والقيم غير المعلّمة هي بالضبط المرشحات التي لا تملك فيها الحصص التسع المختزلة أي قاسم أولي بين \(17\) و\(10^8-1\).
أكبر خارج قسمة مختزل يقع في مرتبة \(10^{16}\)، ولذلك يكون جذره التربيعي في مرتبة \(10^8\). وأصغر خارج قسمة مختزل ينتج من القسمة على \(315\)، ولدينا
$$\sqrt{\frac{10^{16}}{315}}<10^8.$$
بالتالي فإن الجذر التربيعي لكل خارج قسمة يفحصه البرنامج يقع تحت حد الغربلة. فإذا نجا خارج قسمة موجب من جميع القواسم الأولية حتى \(10^8\)، فلا يمكن أن يملك قاسمًا حتى جذره التربيعي، ومن ثم يجب أن يكون أوليًا. وهذا يجعل الغربلة المعيارية كافية لإثبات أولية الأجزاء المختزلة نفسها.
قبل بدء البحث الكبير، تتضمن التطبيقات مثال تحقق صغيرًا. بالتحليل المباشر نحصل على
$$\begin{aligned} P(100)&=5,\quad P(101)=101,\quad P(102)=17,\quad P(103)=103,\\ P(104)&=13,\quad P(105)=7,\quad P(106)=53,\quad P(107)=107,\quad P(108)=3. \end{aligned}$$
ومن ثم
$$S(100)=5+101+17+103+13+7+53+107+3=409.$$
كما يؤكد مسح التحقق نفسه أن
$$\max_{2\le n\le 100} S(n)=417.$$
هذا المثال صغير بما يكفي ليُفحص مباشرة، وهو يثبت أن تفسير مجموع أكبر القواسم الأولية صحيح قبل الانتقال إلى الغربلة الكبيرة المبنية على فئات البواقي.
تنفذ الشيفرات المكتوبة بلغة C++ وPython وJava الخطة الرياضية نفسها. تبدأ أولًا ببناء فئات البواقي الست عشرة الناتجة من شروط CRT. ثم تُولِّد جميع الأعداد الأولية من \(17\) حتى \(10^8-1\)، وتحسب مسبقًا معكوس \(M\) modulo كل عدد أولي منها.
بعد ذلك يعالج كل عامل مجموعة مستقلة من فئات البواقي. وداخل فئة واحدة يحتفظ بمصفوفة بايت طولها \(10^7\)، تمثل كل خانة فيها قيمة واحدة من \(k\). ولكل أولي ولكل إزاحة \(j=0,\dots,8\)، يعلّم البرنامج المتتالية الحسابية لقيم \(k\) التي تجعل خارج القسمة المختزل الموافق قابلًا للقسمة على ذلك الأولي. وبعد انتهاء التعليم تبقى الخانات غير المعلّمة هي المرشحات الناجية.
أخيرًا تُحسَب الدرجة المبنية على الحصص لكل مرشح ناجٍ، ثم يؤخذ أكبر مقدار على جميع فئات البواقي. مدخل Python يعيد استخدام المنطق الأصلي نفسه، بينما تنفذ نسخة Java الإستراتيجية نفسها مباشرة: غربلة ثم مسح ثم اختيار أكبر قيمة.
إذا كتبنا \(B=10^8\) و\(K=10^7\)، فإن بناء جدول الأعداد الأولية حتى \(B\) يكلّف \(O(B\log\log B)\) زمنًا و\(O(B)\) ذاكرة. أما داخل فئة بواقي واحدة، فتكلفة التعليم هي
$$O\!\left(9K\sum_{p<B}\frac1p\right)=O(K\log\log B),$$
ثم يتبع ذلك مسح خطي لطول \(K\). وبما أن عدد فئات البواقي يساوي 16 فقط، تبقى الكلفة الإجمالية من رتبة \(O(B\log\log B+K\log\log B)\) حتى مع وجود عامل ثابت مقداره 16. عمليًا تهيمن على الذاكرة غربلة الأعداد الأولية الكبيرة، إضافة إلى مصفوفة تعليم بطول \(K\) لكل خيط عمل.