For a prime \(p\), a verification consists of a prime \(q\) and coprime integers \(A \ge B > 0\) such that every prime less than \(q\) divides the product \(AB\), and either
$$p = A + B < q^2$$
or
$$p = A - B < q^2.$$
For each prime \(p\), define \(V(p)\) as the smallest possible value of \(A\) among all such verifications, and define
$$S(n)=\sum_{\substack{p < n\\ p\text{ prime}}} V(p).$$
The goal is to evaluate \(S(3800)\). A brute-force scan over all possible triples \((A,B,q)\) would waste almost all of its work, so the implementations reorganize the search around divisibility by the primes below \(q\).
The decisive simplification is that once the small primes below \(q\) are assigned to either \(A\) or \(B\), both branches \(p=A+B\) and \(p=A-B\) reduce to the same pair of congruences for \(A\). That turns the problem into a finite search over partitions of a squarefree product.
The definition only requires
$$p < q^2,$$
with \(q\) prime. If some verification works for a certain \(q\), then the same \(A\) and \(B\) also work for any smaller prime \(q'\) with \(p < q'^2\), because the divisibility requirement becomes weaker when fewer primes must divide \(AB\).
Therefore the minimum \(A\) must use the smallest prime satisfying \(q^2 > p\):
$$q=\min\{r \text{ prime}: r^2 > p\}.$$
So for each fixed prime \(p\), the value of \(q\) is determined immediately.
Let \(P\) be the product of all primes less than \(q\):
$$P=\prod_{r < q} r,$$
where the product runs over primes. Since \(AB\) is divisible by every prime below \(q\), we have
$$P \mid AB.$$
At the same time, the verification requires
$$\gcd(A,B)=1.$$
Because \(P\) is squarefree, every prime factor of \(P\) must divide exactly one of \(A\) and \(B\), never both. That means we can partition the primes below \(q\) into two disjoint groups and write
$$D \cdot E = P,\qquad \gcd(D,E)=1,$$
with
$$D \mid A,\qquad E \mid B.$$
Equivalently,
$$A=Dx,\qquad B=Ey$$
for some positive integers \(x\) and \(y\). Every divisor \(D \mid P\) corresponds to exactly one such partition, because \(E=P/D\).
Now fix one partition \(D \cdot E=P\).
In the sum branch \(p=A+B\), the condition \(E \mid B\) becomes
$$E \mid (p-A),$$
so \(A\) must satisfy
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
In the difference branch \(p=A-B\), we have \(B=A-p\), and the condition \(E \mid B\) again gives
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
Thus both branches share the same congruence core. Since \(\gcd(D,E)=1\), the Chinese Remainder Theorem gives a unique residue class modulo
$$P=DE.$$
If we write \(A=Dt\), then
$$Dt \equiv p \pmod E,$$
hence
$$t \equiv pD^{-1} \pmod E.$$
So one representative is
$$A_0=D\bigl(pD^{-1} \bmod E\bigr),\qquad 0 \le A_0 < P,$$
and every candidate for this partition has the form
$$A=A_0+kP,\qquad k \in \mathbb{Z}_{\ge 0}.$$
Suppose \(p=A+B\) with \(A \ge B > 0\). Then
$$B=p-A,$$
so positivity gives \(A < p\), and the ordering \(A \ge B\) gives
$$A \ge p-A \iff 2A \ge p.$$
Therefore the sum branch is exactly the interval
$$\left\lceil \frac{p}{2} \right\rceil \le A < p.$$
For a prime \(p\), coprimality is automatic here:
$$\gcd(A,B)=\gcd(A,p-A)=\gcd(A,p)=1,$$
because \(0 < A < p\). So for a fixed partition we only need the smallest number in the progression \(A_0+kP\) that lies in this interval.
Suppose instead that \(p=A-B\). Then
$$B=A-p,$$
and \(B > 0\) is equivalent to
$$A > p.$$
Now coprimality is no longer automatic. We have
$$\gcd(A,B)=\gcd(A,A-p)=\gcd(A,p),$$
so the condition \(\gcd(A,B)=1\) becomes
$$p \nmid A.$$
Hence, for the difference branch, we choose the smallest term of the arithmetic progression \(A_0+kP\) that is strictly larger than \(p\) and not divisible by \(p\).
This last check is simple because \(p\) is not one of the primes below \(q\), so
$$\gcd(p,P)=1.$$
Therefore, if the first term above \(p\) happens to be a multiple of \(p\), adding one more period \(P\) immediately moves to a non-multiple.
Each divisor \(D \mid P\) describes one allocation of the primes below \(q\) between \(A\) and \(B\). For that partition, the CRT gives one residue class modulo \(P\), and the two branches give at most two minimal admissible values of \(A\).
So the answer for one prime \(p\) is
$$V(p)=\min_{D \mid P}\Bigl(\min\bigl(A_{\mathrm{sum}}(D),A_{\mathrm{diff}}(D)\bigr)\Bigr),$$
ignoring any missing sum-branch candidate when the interval \([\lceil p/2\rceil,p)\) contains no term from that residue class. Finally,
$$S(n)=\sum_{\substack{p < n\\ p\text{ prime}}} V(p).$$
The smallest prime with \(q^2 > 11\) is \(q=5\), so
$$P=2 \cdot 3 = 6.$$
The divisors of \(P\) are \(1,2,3,6\). For each one, let \(E=6/D\) and solve
$$A \equiv 0 \pmod D,\qquad A \equiv 11 \pmod E.$$
This gives the following residue classes and candidates:
$$\begin{aligned} D=1&:&&A \equiv 5 \pmod 6,&& \text{sum: none},&& \text{difference: }17,\\ D=2&:&&A \equiv 2 \pmod 6,&& \text{sum: }8,&& \text{difference: }14,\\ D=3&:&&A \equiv 3 \pmod 6,&& \text{sum: }9,&& \text{difference: }15,\\ D=6&:&&A \equiv 0 \pmod 6,&& \text{sum: }6,&& \text{difference: }12. \end{aligned}$$
The global minimum is \(A=6\), achieved in the sum branch with \(B=5\). Therefore
$$V(11)=6.$$
The C++, Python, and Java implementations all follow the same workflow. They first generate the relevant prime lists, then determine for each prime \(p\) the smallest prime \(q\) with \(q^2 > p\).
For each distinct \(q\), the implementation caches the primes below \(q\), forms the product \(P\), enumerates all divisors \(D \mid P\), and precomputes the modular inverse needed for the CRT step. This is useful because many different primes \(p\) share the same \(q\), so the partition data does not need to be rebuilt every time.
When processing one prime \(p\), the implementation scans all partitions \(D \cdot E=P\). For each partition it constructs the residue \(A_0\), lifts it to the smallest admissible value in the sum branch, lifts it again to the smallest admissible value in the difference branch, and keeps the smaller valid result. The minimum over all partitions becomes \(V(p)\), and that value is added to the running total.
The same arithmetic reproduces the small checkpoints
$$S(10)=10,\qquad S(200)=7177,$$
which serve as a sanity check before evaluating the final target.
Let \(q(p)\) be the smallest prime with \(q(p)^2 > p\), and let \(k=\pi(q(p)-1)\) be the number of primes below \(q(p)\). Because \(P\) is squarefree, it has exactly
$$2^k$$
divisors. So after the partition table for that \(q\) has been prepared, evaluating one prime \(p\) costs \(O(2^k)\) congruence checks and arithmetic progression adjustments.
Prime generation itself is \(O(n\log\log n)\), while the cached partition tables are built once per distinct \(q\), not once per prime. For the actual target \(n=3800\), the largest needed \(q\) is \(67\), so the largest table uses the \(18\) primes below \(67\), giving
$$2^{18}=262144$$
partitions. That is the reason the method is practical: the search space is exponential in the number of small primes below \(q\), but that number stays modest in the required range.
Für eine Primzahl \(p\) besteht eine Verifikation aus einer Primzahl \(q\) und teilerfremden ganzen Zahlen \(A \ge B > 0\), so dass jedes Prim \(r < q\) das Produkt \(AB\) teilt und außerdem entweder
$$p = A + B < q^2$$
oder
$$p = A - B < q^2$$
gilt. Für jedes Prim \(p\) sei \(V(p)\) das kleinstmögliche \(A\), und gesucht ist
$$S(n)=\sum_{\substack{p < n\\ p\text{ prim}}} V(p).$$
Zu berechnen ist also \(S(3800)\). Eine naive Suche über alle Kandidaten \((A,B,q)\) wäre viel zu unstrukturiert; die Lösung ordnet das Problem stattdessen über die Primzahlen unterhalb von \(q\).
Die zentrale Beobachtung lautet: Sobald feststeht, welche kleinen Primzahlen unterhalb von \(q\) zu \(A\) und welche zu \(B\) gehören, werden sowohl der Summenfall \(p=A+B\) als auch der Differenzfall \(p=A-B\) zu demselben Kongruenzsystem für \(A\). Damit reduziert sich alles auf eine endliche Suche über Zerlegungen eines quadratfreien Produkts.
Die Definition verlangt nur
$$p < q^2,$$
wobei \(q\) prim sein muss. Funktioniert eine Verifikation für ein bestimmtes \(q\), dann funktioniert dasselbe Paar \(A,B\) auch für jedes kleinere Prim \(q'\) mit \(p < q'^2\), denn dann müssen weniger Primzahlen das Produkt \(AB\) teilen.
Folglich verwendet das minimale \(A\) immer das kleinste Prim mit \(q^2 > p\):
$$q=\min\{r \text{ prim}: r^2 > p\}.$$
Damit ist \(q\) für jedes feste \(p\) sofort eindeutig festgelegt.
Sei \(P\) das Produkt aller Primzahlen kleiner als \(q\):
$$P=\prod_{r < q} r,$$
wobei das Produkt über Primzahlen läuft. Da jede solche Primzahl das Produkt \(AB\) teilen muss, gilt
$$P \mid AB.$$
Zusätzlich ist vorgeschrieben, dass
$$\gcd(A,B)=1.$$
Weil \(P\) quadratfrei ist, kann jeder Primfaktor von \(P\) nur in genau einem der beiden Zahlen \(A\) oder \(B\) vorkommen. Also zerlegen wir die kleinen Primzahlen in zwei disjunkte Gruppen und schreiben
$$D \cdot E = P,\qquad \gcd(D,E)=1,$$
mit
$$D \mid A,\qquad E \mid B.$$
Äquivalent dazu gibt es positive ganze Zahlen \(x,y\) mit
$$A=Dx,\qquad B=Ey.$$
Jeder Teiler \(D \mid P\) beschreibt genau eine solche Aufteilung, denn stets ist \(E=P/D\).
Fixiere nun eine Zerlegung \(D \cdot E=P\).
Im Summenfall \(p=A+B\) folgt aus \(E \mid B\), dass
$$E \mid (p-A),$$
also
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
Im Differenzfall \(p=A-B\) gilt \(B=A-p\), und wieder ergibt \(E \mid B\) genau dieselben Kongruenzen:
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
Beide Zweige haben daher denselben arithmetischen Kern. Da \(\gcd(D,E)=1\), liefert der Chinesische Restsatz genau eine Restklasse modulo
$$P=DE.$$
Setzt man \(A=Dt\), dann folgt aus
$$Dt \equiv p \pmod E$$
die Kongruenz
$$t \equiv pD^{-1} \pmod E.$$
Damit erhält man einen Repräsentanten
$$A_0=D\bigl(pD^{-1} \bmod E\bigr),\qquad 0 \le A_0 < P,$$
und alle Kandidaten dieser Zerlegung haben die Form
$$A=A_0+kP,\qquad k \in \mathbb{Z}_{\ge 0}.$$
Angenommen \(p=A+B\) mit \(A \ge B > 0\). Dann ist
$$B=p-A,$$
also verlangt \(B > 0\) die Ungleichung \(A < p\). Aus \(A \ge B\) folgt
$$A \ge p-A \iff 2A \ge p.$$
Der Summenfall ist also äquivalent zu
$$\left\lceil \frac{p}{2} \right\rceil \le A < p.$$
Die Teilerfremdheit ist hier automatisch erfüllt, denn
$$\gcd(A,B)=\gcd(A,p-A)=\gcd(A,p)=1,$$
weil \(0 < A < p\) und \(p\) prim ist. Für eine feste Restklasse muss man also nur den kleinsten Wert \(A_0+kP\) in diesem Intervall finden.
Im Fall \(p=A-B\) gilt
$$B=A-p,$$
und damit ist \(B > 0\) genau gleichbedeutend mit
$$A > p.$$
Hier ist die Teilerfremdheit nicht automatisch. Man erhält
$$\gcd(A,B)=\gcd(A,A-p)=\gcd(A,p),$$
also ist \(\gcd(A,B)=1\) äquivalent zu
$$p \nmid A.$$
Im Differenzfall wählt man daher den kleinsten Term der arithmetischen Folge \(A_0+kP\), der strikt größer als \(p\) und kein Vielfaches von \(p\) ist.
Das funktioniert einfach, weil \(p\) nicht zu den Primzahlen unterhalb von \(q\) gehört und deshalb
$$\gcd(p,P)=1$$
gilt. Falls also der erste Kandidat oberhalb von \(p\) gerade durch \(p\) teilbar ist, genügt ein weiteres Hinzufügen von \(P\).
Jeder Teiler \(D \mid P\) entspricht einer möglichen Zuordnung der kleinen Primzahlen zu \(A\) und \(B\). Für diese Zerlegung liefert der CRT-Schritt eine Restklasse modulo \(P\), und daraus entstehen bis zu zwei kleinste zulässige Werte von \(A\), einer pro Zweig.
Also ist
$$V(p)=\min_{D \mid P}\Bigl(\min\bigl(A_{\mathrm{Summe}}(D),A_{\mathrm{Differenz}}(D)\bigr)\Bigr),$$
wobei ein fehlender Summenkandidat ignoriert wird, wenn das Intervall \([\lceil p/2\rceil,p)\) keinen Wert aus der Restklasse enthält. Schließlich gilt
$$S(n)=\sum_{\substack{p < n\\ p\text{ prim}}} V(p).$$
Das kleinste Prim mit \(q^2 > 11\) ist \(q=5\). Also
$$P=2 \cdot 3 = 6.$$
Die Teiler von \(P\) sind \(1,2,3,6\). Für jeden davon setzt man \(E=6/D\) und löst
$$A \equiv 0 \pmod D,\qquad A \equiv 11 \pmod E.$$
Es ergeben sich die folgenden Restklassen und Kandidaten:
$$\begin{aligned} D=1&:&&A \equiv 5 \pmod 6,&& \text{Summe: keiner},&& \text{Differenz: }17,\\ D=2&:&&A \equiv 2 \pmod 6,&& \text{Summe: }8,&& \text{Differenz: }14,\\ D=3&:&&A \equiv 3 \pmod 6,&& \text{Summe: }9,&& \text{Differenz: }15,\\ D=6&:&&A \equiv 0 \pmod 6,&& \text{Summe: }6,&& \text{Differenz: }12. \end{aligned}$$
Das Minimum ist \(A=6\), und zwar im Summenzweig mit \(B=5\). Daher
$$V(11)=6.$$
Die Implementierungen in C++, Python und Java folgen demselben Ablauf. Zuerst werden die benötigten Primzahlen erzeugt, danach wird für jedes Prim \(p\) das kleinste Prim \(q\) mit \(q^2 > p\) bestimmt.
Für jedes verschiedene \(q\) werden die Primzahlen unterhalb von \(q\), das Produkt \(P\), alle Teiler \(D \mid P\) und die für den CRT-Schritt benötigten modularen Inversen zwischengespeichert. Das lohnt sich, weil viele verschiedene Primzahlen \(p\) dasselbe \(q\) besitzen und somit dieselbe Partitionsstruktur wiederverwenden.
Bei der Verarbeitung eines konkreten \(p\) durchläuft die Implementierung alle Zerlegungen \(D \cdot E=P\). Für jede Zerlegung konstruiert sie den Rest \(A_0\), hebt ihn auf den kleinsten zulässigen Wert im Summenzweig an, wiederholt dasselbe für den Differenzzweig und behält den kleineren gültigen Kandidaten. Das Minimum über alle Zerlegungen ist \(V(p)\), und dieser Wert wird zur laufenden Summe addiert.
Die gleiche Arithmetik reproduziert die kleinen Kontrollwerte
$$S(10)=10,\qquad S(200)=7177,$$
bevor das endgültige Ziel ausgewertet wird.
Sei \(q(p)\) das kleinste Prim mit \(q(p)^2 > p\), und sei \(k=\pi(q(p)-1)\) die Anzahl der Primzahlen unterhalb von \(q(p)\). Weil \(P\) quadratfrei ist, besitzt es genau
$$2^k$$
Teiler. Nach dem Vorbereiten der Partitionsdaten für dieses \(q\) kostet ein einzelnes Prim \(p\) also \(O(2^k)\) Kongruenzprüfungen und Fortschaltungen in arithmetischen Folgen.
Das Erzeugen der Primzahlen kostet \(O(n\log\log n)\). Die Partitionsdaten werden dank Caching nur einmal pro verschiedenem \(q\) gebaut, nicht einmal pro Primzahl. Für das konkrete Ziel \(n=3800\) ist das größte benötigte \(q\) gleich \(67\); damit treten höchstens die \(18\) Primzahlen unterhalb von \(67\) auf, also
$$2^{18}=262144$$
Zerlegungen. Genau deshalb bleibt die Methode praktisch: exponentiell in der Anzahl kleiner Primzahlen unterhalb von \(q\), aber diese Anzahl bleibt im geforderten Bereich moderat.
Bir asal sayı \(p\) için doğrulama, bir asal \(q\) ve aralarında asal tamsayılar \(A \ge B > 0\) ile verilir. Koşullar şunlardır: \(q\)'dan küçük her asal sayı \(AB\) çarpımını bölmelidir ve ayrıca ya
$$p = A + B < q^2$$
ya da
$$p = A - B < q^2$$
olmalıdır. Her asal \(p\) için mümkün olan en küçük \(A\) değerine \(V(p)\) denir ve
$$S(n)=\sum_{\substack{p < n\\ p\text{ asal}}} V(p)$$
toplamı hesaplanır. Hedef değer \(S(3800)\)'dür. Tüm \((A,B,q)\) üçlülerini doğrudan denemek çok verimsiz olur; bu yüzden çözüm, \(q\)'dan küçük asalların \(A\) ve \(B\) arasında nasıl dağıldığına odaklanır.
Temel sadeleştirme şudur: \(q\)'dan küçük asalların hangilerinin \(A\)'yı, hangilerinin \(B\)'yi böldüğü belirlendikten sonra hem toplam dalı \(p=A+B\) hem de fark dalı \(p=A-B\), \(A\) için aynı kongruens sistemine indirgenir. Böylece problem, kare-kök içermeyen bir çarpımın tüm bölücü ayrımlarını tarayan sonlu bir aramaya dönüşür.
Tanım yalnızca
$$p < q^2$$
koşulunu ister ve \(q\) asal olmalıdır. Eğer bir doğrulama belirli bir \(q\) için çalışıyorsa, aynı \(A\) ve \(B\) değerleri \(p < q'^2\) sağlayan daha küçük herhangi bir asal \(q'\) için de çalışır; çünkü o zaman \(AB\)'nin bölmesi gereken asal sayılar daha azdır.
Bu nedenle en küçük \(A\), mutlaka \(q^2 > p\) koşulunu sağlayan en küçük asalla elde edilir:
$$q=\min\{r \text{ asal}: r^2 > p\}.$$
Dolayısıyla her sabit \(p\) için \(q\) baştan belirlenmiş olur.
\(P\), \(q\)'dan küçük tüm asalların çarpımı olsun:
$$P=\prod_{r < q} r,$$
burada çarpım yalnızca asallar üzerindedir. \(q\)'dan küçük her asal \(AB\)'yi böldüğüne göre
$$P \mid AB$$
elde edilir. Aynı zamanda doğrulamada
$$\gcd(A,B)=1$$
şartı da vardır. \(P\) kare-kök içermeyen bir sayı olduğundan, \(P\)'nin her asal çarpanı \(A\) ve \(B\)'den yalnızca birini bölebilir; ikisini birden bölemez.
Bu yüzden küçük asalları iki ayrık kümeye ayırıp
$$D \cdot E = P,\qquad \gcd(D,E)=1,$$
ve
$$D \mid A,\qquad E \mid B$$
şeklinde yazabiliriz. Başka bir deyişle, bazı pozitif tamsayılar \(x,y\) için
$$A=Dx,\qquad B=Ey$$
olur. \(P\) kare-kök içermediği için her \(D \mid P\) bölücüsü tam olarak bir böyle ayrımı temsil eder; karşı tarafta da \(E=P/D\) vardır.
Şimdi sabit bir \(D \cdot E=P\) ayrımı seçelim.
Toplam dalında \(p=A+B\) olduğundan ve \(E \mid B\) gerektiğinden
$$E \mid (p-A)$$
olur. Bu da
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E$$
kongruenslerini verir.
Fark dalında \(p=A-B\) ise \(B=A-p\) olur. Yine \(E \mid B\) şartı tam olarak aynı kongruensleri üretir:
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
Dolayısıyla iki dalın ortak cebirsel çekirdeği aynıdır. \(\gcd(D,E)=1\) olduğu için Çin Kalan Teoremi,
$$P=DE$$
modunda tek bir artık sınıfı verir.
\(A=Dt\) yazarsak
$$Dt \equiv p \pmod E$$
olur ve buradan
$$t \equiv pD^{-1} \pmod E$$
çıkar. Böylece bir temsilci
$$A_0=D\bigl(pD^{-1} \bmod E\bigr),\qquad 0 \le A_0 < P$$
şeklindedir ve bu ayrımdaki tüm adaylar
$$A=A_0+kP,\qquad k \in \mathbb{Z}_{\ge 0}$$
biçimindedir.
\(p=A+B\) ve \(A \ge B > 0\) olsun. O zaman
$$B=p-A$$
olduğundan \(B > 0\) şartı \(A < p\) demektir. Ayrıca \(A \ge B\) eşitsizliği
$$A \ge p-A \iff 2A \ge p$$
şeklindedir. Sonuç olarak toplam dalı tam olarak şu aralığa iner:
$$\left\lceil \frac{p}{2} \right\rceil \le A < p.$$
Bu dalda aralarında asallık otomatik gelir:
$$\gcd(A,B)=\gcd(A,p-A)=\gcd(A,p)=1,$$
çünkü \(0 < A < p\) ve \(p\) asaldır. Bu yüzden sabit bir artık sınıfı için yapılacak iş, \(A_0+kP\) dizisinde bu aralığa düşen en küçük terimi seçmektir.
\(p=A-B\) durumunda
$$B=A-p$$
olur ve \(B > 0\) şartı doğrudan
$$A > p$$
eşitsizliğini verir. Burada aralarında asallık otomatik değildir. Gerçekten,
$$\gcd(A,B)=\gcd(A,A-p)=\gcd(A,p),$$
dolayısıyla \(\gcd(A,B)=1\) şartı
$$p \nmid A$$
ile aynıdır. Bu nedenle fark dalında, \(A_0+kP\) artimetik dizisinde \(p\)'den büyük olan ve \(p\)'ye bölünmeyen en küçük terim seçilir.
Bu kontrol kolaydır çünkü \(p\), \(q\)'dan küçük asalların arasında değildir; dolayısıyla
$$\gcd(p,P)=1.$$
İlk uygun aday tesadüfen \(p\)'nin katıysa, bir kez daha \(P\) eklemek yeterlidir.
Her \(D \mid P\) bölücüsü, küçük asalların \(A\) ve \(B\) arasında farklı bir dağılımını temsil eder. Bu ayrım için CRT bir artık sınıfı verir; ardından toplam ve fark dalları en fazla iki adet en küçük geçerli \(A\) adayı üretir.
Dolayısıyla bir asal \(p\) için cevap
$$V(p)=\min_{D \mid P}\Bigl(\min\bigl(A_{\mathrm{toplam}}(D),A_{\mathrm{fark}}(D)\bigr)\Bigr)$$
şeklindedir. Toplam dalında, ilgili artık sınıfı \([\lceil p/2\rceil,p)\) aralığına hiç düşmüyorsa o aday yok sayılır. Son olarak
$$S(n)=\sum_{\substack{p < n\\ p\text{ asal}}} V(p)$$
elde edilir.
\(11\) için \(q^2 > 11\) sağlayan en küçük asal \(q=5\)'tir. Bu yüzden
$$P=2 \cdot 3 = 6.$$
\(P\)'nin bölenleri \(1,2,3,6\)'dır. Her biri için \(E=6/D\) alıp
$$A \equiv 0 \pmod D,\qquad A \equiv 11 \pmod E$$
kongruenslerini çözelim. Sonuçlar şöyledir:
$$\begin{aligned} D=1&:&&A \equiv 5 \pmod 6,&& \text{toplam: yok},&& \text{fark: }17,\\ D=2&:&&A \equiv 2 \pmod 6,&& \text{toplam: }8,&& \text{fark: }14,\\ D=3&:&&A \equiv 3 \pmod 6,&& \text{toplam: }9,&& \text{fark: }15,\\ D=6&:&&A \equiv 0 \pmod 6,&& \text{toplam: }6,&& \text{fark: }12. \end{aligned}$$
En küçük değer \(A=6\)'dır ve toplam dalında \(B=5\) ile gerçekleşir. Demek ki
$$V(11)=6.$$
C++, Python ve Java uygulamalarının hepsi aynı akışı izler. Önce gerekli asal listeleri üretilir, sonra her asal \(p\) için \(q^2 > p\) koşulunu sağlayan en küçük asal \(q\) bulunur.
Her farklı \(q\) değeri için, uygulama \(q\)'dan küçük asalları, bunların çarpımı \(P\)'yi, tüm \(D \mid P\) bölenlerini ve CRT adımı için gereken modüler tersleri önceden saklar. Bunun nedeni, birçok farklı \(p\) değerinin aynı \(q\)'yu paylaşmasıdır; böylece aynı partition verisi tekrar tekrar kurulmaz.
Tek bir asal \(p\) işlenirken tüm \(D \cdot E=P\) ayrımları taranır. Her ayrım için \(A_0\) artık sınıfı üretilir, bu sınıf toplam dalında en küçük geçerli değere yükseltilir, ardından fark dalı için de aynı işlem yapılır ve küçük olan geçerli aday korunur. Tüm ayrımların minimumu \(V(p)\) olur; daha sonra bu değer toplam birikene eklenir.
Aynı aritmetik, küçük doğrulama noktalarını da yeniden üretir:
$$S(10)=10,\qquad S(200)=7177.$$
\(q(p)\), \(q(p)^2 > p\) koşulunu sağlayan en küçük asal olsun ve \(k=\pi(q(p)-1)\), yani \(q(p)\)'dan küçük asal sayısı olsun. \(P\) kare-kök içermediğinden tam olarak
$$2^k$$
adet böleni vardır. Dolayısıyla o \(q\) için partition tablosu hazırlandıktan sonra tek bir asal \(p\)'yi değerlendirmek \(O(2^k)\) kadar kongruens ve artimetik dizi ayarlaması gerektirir.
Asal üretimi \(O(n\log\log n)\) maliyetindedir. Öte yandan partition tabloları her asal için değil, yalnızca her farklı \(q\) için bir kez oluşturulur. Gerçek hedef \(n=3800\) için gereken en büyük \(q\) değeri \(67\)'dir; dolayısıyla en büyük tabloda \(67\)'den küçük \(18\) asal bulunur ve bu da
$$2^{18}=262144$$
ayrım anlamına gelir. Yöntemin pratik olmasının nedeni budur: maliyet, \(q\)'dan küçük asal sayısına göre üstel olsa da bu sayı gerekli aralıkta küçük kalır.
Para un primo \(p\), una verificación está formada por un primo \(q\) y por enteros coprimos \(A \ge B > 0\) tales que todo primo menor que \(q\) divide al producto \(AB\), y además se cumple una de estas dos posibilidades:
$$p = A + B < q^2$$
o bien
$$p = A - B < q^2.$$
Para cada primo \(p\), se define \(V(p)\) como el menor valor posible de \(A\), y luego se calcula
$$S(n)=\sum_{\substack{p < n\\ p\text{ primo}}} V(p).$$
La meta es evaluar \(S(3800)\). Probar triples \((A,B,q)\) a ciegas sería ineficiente; la idea correcta es reorganizar la búsqueda según cómo se reparten los primos menores que \(q\) entre \(A\) y \(B\).
La observación clave es que, una vez decidido qué primos pequeños menores que \(q\) van a \(A\) y cuáles van a \(B\), tanto la rama de suma \(p=A+B\) como la rama de diferencia \(p=A-B\) conducen al mismo sistema de congruencias para \(A\). Así, el problema se reduce a recorrer todas las particiones de un producto libre de cuadrados.
La definición solo exige
$$p < q^2,$$
con \(q\) primo. Si una verificación funciona para cierto \(q\), entonces el mismo par \(A,B\) también funciona para cualquier primo menor \(q'\) que siga cumpliendo \(p < q'^2\), porque entonces la condición de divisibilidad sobre \(AB\) es más débil.
Por lo tanto, el mínimo \(A\) siempre aparece con el menor primo tal que \(q^2 > p\):
$$q=\min\{r \text{ primo}: r^2 > p\}.$$
Así, para cada primo fijo \(p\), el valor de \(q\) queda determinado de inmediato.
Sea \(P\) el producto de todos los primos menores que \(q\):
$$P=\prod_{r < q} r,$$
donde el producto recorre solo primos. Como cada uno de esos primos debe dividir a \(AB\), se obtiene
$$P \mid AB.$$
Además, la verificación exige
$$\gcd(A,B)=1.$$
Puesto que \(P\) es libre de cuadrados, cada primo que aparece en \(P\) debe dividir exactamente a uno de \(A\) o \(B\), pero no a ambos. Por eso podemos repartir los primos pequeños en dos grupos disjuntos y escribir
$$D \cdot E = P,\qquad \gcd(D,E)=1,$$
con
$$D \mid A,\qquad E \mid B.$$
Equivalente a eso, existen enteros positivos \(x,y\) tales que
$$A=Dx,\qquad B=Ey.$$
Cada divisor \(D \mid P\) codifica exactamente una partición, porque necesariamente \(E=P/D\).
Fijemos ahora una partición \(D \cdot E=P\).
En la rama de suma, \(p=A+B\). Como \(E \mid B\), se tiene
$$E \mid (p-A),$$
y por tanto
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
En la rama de diferencia, \(p=A-B\), es decir, \(B=A-p\). De nuevo, la condición \(E \mid B\) produce exactamente las mismas congruencias:
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
Por lo tanto, ambas ramas tienen el mismo núcleo aritmético. Como \(\gcd(D,E)=1\), el teorema chino del resto da una única clase residual módulo
$$P=DE.$$
Si escribimos \(A=Dt\), entonces
$$Dt \equiv p \pmod E,$$
lo que implica
$$t \equiv pD^{-1} \pmod E.$$
Un representante conveniente es
$$A_0=D\bigl(pD^{-1} \bmod E\bigr),\qquad 0 \le A_0 < P,$$
y todos los candidatos asociados a esta partición tienen la forma
$$A=A_0+kP,\qquad k \in \mathbb{Z}_{\ge 0}.$$
Supongamos \(p=A+B\) con \(A \ge B > 0\). Entonces
$$B=p-A,$$
así que la positividad da \(A < p\). Además, la condición \(A \ge B\) equivale a
$$A \ge p-A \iff 2A \ge p.$$
En consecuencia, la rama de suma se describe exactamente por
$$\left\lceil \frac{p}{2} \right\rceil \le A < p.$$
Aquí la coprimalidad es automática, porque
$$\gcd(A,B)=\gcd(A,p-A)=\gcd(A,p)=1,$$
ya que \(0 < A < p\) y \(p\) es primo. Así, para una clase residual fija basta encontrar el menor término \(A_0+kP\) que caiga dentro de ese intervalo.
Si \(p=A-B\), entonces
$$B=A-p,$$
y la condición \(B > 0\) equivale a
$$A > p.$$
En esta rama, la coprimalidad ya no es automática. En efecto,
$$\gcd(A,B)=\gcd(A,A-p)=\gcd(A,p),$$
de modo que \(\gcd(A,B)=1\) es lo mismo que exigir
$$p \nmid A.$$
Por tanto, en la rama de diferencia se toma el menor término de la progresión \(A_0+kP\) que sea estrictamente mayor que \(p\) y que no sea múltiplo de \(p\).
Esta comprobación es sencilla porque \(p\) no aparece entre los primos menores que \(q\), así que
$$\gcd(p,P)=1.$$
Si el primer candidato por encima de \(p\) resulta divisible por \(p\), basta sumar un período adicional \(P\).
Cada divisor \(D \mid P\) representa una distribución posible de los primos pequeños entre \(A\) y \(B\). Para esa distribución, el paso CRT produce una clase residual módulo \(P\), y luego las dos ramas producen hasta dos valores mínimos admisibles de \(A\).
Por ello, para un primo \(p\) se obtiene
$$V(p)=\min_{D \mid P}\Bigl(\min\bigl(A_{\mathrm{suma}}(D),A_{\mathrm{diferencia}}(D)\bigr)\Bigr),$$
ignorando la rama de suma cuando ningún término de la clase residual cae dentro de \([\lceil p/2\rceil,p)\). Finalmente,
$$S(n)=\sum_{\substack{p < n\\ p\text{ primo}}} V(p).$$
El menor primo con \(q^2 > 11\) es \(q=5\). Por tanto,
$$P=2 \cdot 3 = 6.$$
Los divisores de \(P\) son \(1,2,3,6\). Para cada uno, tomamos \(E=6/D\) y resolvemos
$$A \equiv 0 \pmod D,\qquad A \equiv 11 \pmod E.$$
Las clases residuales y sus mejores candidatos quedan así:
$$\begin{aligned} D=1&:&&A \equiv 5 \pmod 6,&& \text{suma: ninguna},&& \text{diferencia: }17,\\ D=2&:&&A \equiv 2 \pmod 6,&& \text{suma: }8,&& \text{diferencia: }14,\\ D=3&:&&A \equiv 3 \pmod 6,&& \text{suma: }9,&& \text{diferencia: }15,\\ D=6&:&&A \equiv 0 \pmod 6,&& \text{suma: }6,&& \text{diferencia: }12. \end{aligned}$$
El mínimo global es \(A=6\), logrado en la rama de suma con \(B=5\). Así,
$$V(11)=6.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Primero generan las listas de primos necesarias y, para cada primo \(p\), determinan el menor primo \(q\) tal que \(q^2 > p\).
Para cada valor distinto de \(q\), la implementación guarda en caché los primos menores que \(q\), el producto \(P\), todos los divisores \(D \mid P\) y la inversa modular necesaria para resolver el paso CRT. Esto evita reconstruir la misma información una y otra vez cuando varios valores de \(p\) comparten el mismo \(q\).
Al procesar un primo concreto \(p\), la implementación recorre todas las particiones \(D \cdot E=P\). Para cada una construye el residuo \(A_0\), lo eleva al menor representante válido en la rama de suma, repite la operación para la rama de diferencia y conserva el menor candidato válido. El mínimo sobre todas las particiones es \(V(p)\), y luego se añade a la suma acumulada.
La misma aritmética reproduce los puntos de control pequeños
$$S(10)=10,\qquad S(200)=7177,$$
antes de evaluar el objetivo final.
Sea \(q(p)\) el menor primo con \(q(p)^2 > p\), y sea \(k=\pi(q(p)-1)\) el número de primos menores que \(q(p)\). Como \(P\) es libre de cuadrados, tiene exactamente
$$2^k$$
divisores. Por tanto, una vez construida la tabla de particiones para ese \(q\), evaluar un primo \(p\) requiere \(O(2^k)\) comprobaciones de congruencias y ajustes dentro de progresiones aritméticas.
La generación de primos cuesta \(O(n\log\log n)\), mientras que las tablas de particiones se construyen una sola vez por cada \(q\) distinto, no una vez por cada primo. Para el objetivo \(n=3800\), el mayor valor necesario es \(q=67\); por ello, la tabla más grande usa los \(18\) primos menores que \(67\), es decir,
$$2^{18}=262144$$
particiones. Esa es la razón de que el método sea viable: el crecimiento es exponencial en el número de primos pequeños por debajo de \(q\), pero ese número sigue siendo moderado en el rango pedido.
对一个素数 \(p\)，所谓一次验证由一个素数 \(q\) 和两个互素整数 \(A \ge B > 0\) 组成，并满足：所有小于 \(q\) 的素数都整除乘积 \(AB\)，而且还要满足下面两种情形之一：
$$p = A + B < q^2$$
或者
$$p = A - B < q^2.$$
对每个素数 \(p\)，定义 \(V(p)\) 为所有验证中最小的 \(A\)。然后求和
$$S(n)=\sum_{\substack{p < n\\ p\text{ 为素数}}} V(p).$$
本题要求计算 \(S(3800)\)。如果直接枚举所有可能的 \((A,B,q)\)，大部分工作都会浪费在无效候选上。更好的做法是从“小于 \(q\) 的素数必须如何分配到 \(A\) 与 \(B\)”这一点出发重新组织搜索。
核心简化在于：一旦确定了小于 \(q\) 的每个素数究竟归到 \(A\) 一侧还是 \(B\) 一侧，无论讨论的是和式分支 \(p=A+B\) 还是差式分支 \(p=A-B\)，最后都会落到同一组关于 \(A\) 的同余条件上。于是问题被压缩成“枚举一个无平方因子乘积的所有因子划分”。
定义中只要求
$$p < q^2,$$
并且 \(q\) 本身必须是素数。如果某个验证对某个 \(q\) 已经成立，那么对任何更小但仍满足 \(p < q'^2\) 的素数 \(q'\)，同样的 \(A,B\) 也仍然成立，因为这时“\(AB\) 必须被哪些素数整除”的要求只会更弱，不会更强。
因此，得到最小 \(A\) 时，必然应该选取满足 \(q^2 > p\) 的最小素数：
$$q=\min\{r \text{ 为素数}: r^2 > p\}.$$
这样一来，对每个固定的素数 \(p\)，对应的 \(q\) 就已经完全确定了。
令 \(P\) 表示所有小于 \(q\) 的素数之积：
$$P=\prod_{r < q} r,$$
其中乘积只在素数上取。因为每个小于 \(q\) 的素数都必须整除 \(AB\)，所以有
$$P \mid AB.$$
另一方面，题目还要求
$$\gcd(A,B)=1.$$
由于 \(P\) 是平方因子自由的数，\(P\) 中的每个素因子只能出现在 \(A\) 或 \(B\) 的其中一边，不可能同时出现在两边。于是，小于 \(q\) 的素数可以被拆成两个互不相交的集合，并写成
$$D \cdot E = P,\qquad \gcd(D,E)=1,$$
同时满足
$$D \mid A,\qquad E \mid B.$$
换句话说，可以表示为
$$A=Dx,\qquad B=Ey,$$
其中 \(x,y\) 是正整数。因为 \(P\) 没有重复素因子，所以每个除数 \(D \mid P\) 都唯一对应一种素数分配方式，而另一侧自动就是 \(E=P/D\)。
现在固定一个划分 \(D \cdot E=P\)。
如果走和式分支 \(p=A+B\)，那么由 \(E \mid B\) 得到
$$E \mid (p-A),$$
于是 \(A\) 必须满足
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
如果走差式分支 \(p=A-B\)，这时 \(B=A-p\)，而 \(E \mid B\) 同样给出完全一样的同余条件：
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
这说明两条分支拥有相同的数论核心。由于 \(\gcd(D,E)=1\)，中国剩余定理保证模
$$P=DE$$
意义下存在唯一的剩余类。
若把 \(A\) 写成 \(A=Dt\)，则需要解
$$Dt \equiv p \pmod E,$$
也就是
$$t \equiv pD^{-1} \pmod E.$$
因此可以取一个代表元
$$A_0=D\bigl(pD^{-1} \bmod E\bigr),\qquad 0 \le A_0 < P,$$
并且该划分对应的所有候选值都写成
$$A=A_0+kP,\qquad k \in \mathbb{Z}_{\ge 0}.$$
设 \(p=A+B\) 且 \(A \ge B > 0\)。此时
$$B=p-A,$$
所以 \(B > 0\) 等价于 \(A < p\)。另一方面，\(A \ge B\) 等价于
$$A \ge p-A \iff 2A \ge p.$$
因此和式分支中的 \(A\) 恰好落在区间
$$\left\lceil \frac{p}{2} \right\rceil \le A < p.$$
在这个分支里，互素条件自动满足，因为
$$\gcd(A,B)=\gcd(A,p-A)=\gcd(A,p)=1,$$
这里用到了 \(0 < A < p\) 且 \(p\) 是素数。也就是说，对固定剩余类而言，只需要在等差数列 \(A_0+kP\) 中找到落入上面区间的最小项即可。
若 \(p=A-B\)，那么
$$B=A-p,$$
而 \(B > 0\) 正好等价于
$$A > p.$$
这一分支中，互素性不再自动成立。因为
$$\gcd(A,B)=\gcd(A,A-p)=\gcd(A,p),$$
所以题目中的 \(\gcd(A,B)=1\) 等价于
$$p \nmid A.$$
于是，差式分支需要从等差数列 \(A_0+kP\) 中取出“严格大于 \(p\)”且“不是 \(p\) 的倍数”的最小项。
这一步之所以简单，是因为素数 \(p\) 本身并不在“小于 \(q\) 的素数”之列，所以
$$\gcd(p,P)=1.$$
如果第一个超过 \(p\) 的候选值恰好能被 \(p\) 整除，那么再加一次周期 \(P\) 就一定能跳到一个非倍数位置。
每个除数 \(D \mid P\) 都对应一种把小素数分给 \(A\) 与 \(B\) 的方式。对这个划分，CRT 会给出模 \(P\) 的一个剩余类；然后和式分支与差式分支各自产生至多一个最小可行的 \(A\)。
因此，对某个素数 \(p\) 而言，答案就是
$$V(p)=\min_{D \mid P}\Bigl(\min\bigl(A_{\mathrm{sum}}(D),A_{\mathrm{diff}}(D)\bigr)\Bigr),$$
其中如果和式分支对应的剩余类在区间 \([\lceil p/2\rceil,p)\) 中没有出现，就忽略那个分支。最后再求
$$S(n)=\sum_{\substack{p < n\\ p\text{ 为素数}}} V(p).$$
满足 \(q^2 > 11\) 的最小素数是 \(q=5\)，所以
$$P=2 \cdot 3 = 6.$$
\(P\) 的除数为 \(1,2,3,6\)。对每个除数，令 \(E=6/D\)，并求解
$$A \equiv 0 \pmod D,\qquad A \equiv 11 \pmod E.$$
得到的剩余类与各分支中的最佳候选如下：
$$\begin{aligned} D=1&:&&A \equiv 5 \pmod 6,&& \text{和式: 无},&& \text{差式: }17,\\ D=2&:&&A \equiv 2 \pmod 6,&& \text{和式: }8,&& \text{差式: }14,\\ D=3&:&&A \equiv 3 \pmod 6,&& \text{和式: }9,&& \text{差式: }15,\\ D=6&:&&A \equiv 0 \pmod 6,&& \text{和式: }6,&& \text{差式: }12. \end{aligned}$$
全局最小值是 \(A=6\)，对应和式分支，此时 \(B=5\)。因此
$$V(11)=6.$$
C++、Python 和 Java 三个实现采用的是同一套流程。首先生成所需的素数表，然后对每个素数 \(p\) 找到满足 \(q^2 > p\) 的最小素数 \(q\)。
对于每个不同的 \(q\)，实现会缓存“小于 \(q\) 的素数列表”、乘积 \(P\)、所有除数 \(D \mid P\)，以及 CRT 步骤中所需的模逆。这样做的原因是：很多不同的 \(p\) 会共享同一个 \(q\)，因此不必重复构造同样的划分数据。
处理某个具体的素数 \(p\) 时，程序扫描全部划分 \(D \cdot E=P\)。对每个划分，它先构造剩余代表 \(A_0\)，再把这个剩余类提升到和式分支中的最小合法值，然后再提升到差式分支中的最小合法值，并保留其中较小的有效候选。遍历完成后，所有划分中的最小值就是 \(V(p)\)，再把它加入总和。
同样的算术流程还能复现两个小检查点：
$$S(10)=10,\qquad S(200)=7177,$$
这说明分支处理和同余计算是一致的。
设 \(q(p)\) 为满足 \(q(p)^2 > p\) 的最小素数，记 \(k=\pi(q(p)-1)\) 为严格小于 \(q(p)\) 的素数个数。因为 \(P\) 是平方因子自由的，所以它恰好有
$$2^k$$
个除数。于是，在该 \(q\) 的划分表准备完成之后，处理一个素数 \(p\) 的代价就是 \(O(2^k)\) 次同余检查与等差数列调整。
筛出素数本身需要 \(O(n\log\log n)\) 时间，而划分表只会对每个不同的 \(q\) 构建一次，不会对每个 \(p\) 都重建。对最终目标 \(n=3800\) 来说，最大的所需素数是 \(q=67\)。这时小于 \(67\) 的素数共有 \(18\) 个，因此最大的划分表大小为
$$2^{18}=262144.$$
这正是该方法可行的原因：复杂度确实随着“小于 \(q\) 的素数个数”呈指数增长，但在题目要求的范围内，这个数量仍然不大。
Для простого числа \(p\) проверка задаётся простым числом \(q\) и взаимно простыми целыми \(A \ge B > 0\) так, что каждое простое число меньше \(q\) делит произведение \(AB\), и при этом выполняется одно из двух условий:
$$p = A + B < q^2$$
или
$$p = A - B < q^2.$$
Для каждого простого \(p\) величина \(V(p)\) определяется как минимально возможное \(A\). Затем требуется вычислить
$$S(n)=\sum_{\substack{p < n\\ p\text{ простое}}} V(p).$$
Нужно найти \(S(3800)\). Полный перебор троек \((A,B,q)\) здесь неразумен, поэтому решение перестраивает задачу вокруг того, как простые числа меньше \(q\) распределяются между \(A\) и \(B\).
Главное упрощение состоит в том, что после фиксации распределения всех простых чисел меньше \(q\) между \(A\) и \(B\) обе ветви, \(p=A+B\) и \(p=A-B\), приводят к одной и той же системе сравнений для \(A\). Поэтому задача сводится к конечному перебору разбиений квадратсвободного произведения.
По определению нужно только, чтобы
$$p < q^2,$$
где \(q\) простое. Если некоторая проверка существует для данного \(q\), то те же самые \(A\) и \(B\) подходят и для любого меньшего простого \(q'\), если всё ещё верно \(p < q'^2\), потому что требование делимости \(AB\) становится слабее.
Следовательно, минимальное \(A\) достигается при наименьшем простом \(q\), для которого \(q^2 > p\):
$$q=\min\{r \text{ простое}: r^2 > p\}.$$
Значит, для каждого фиксированного простого \(p\) число \(q\) определяется однозначно.
Пусть \(P\) обозначает произведение всех простых чисел, меньших \(q\):
$$P=\prod_{r < q} r,$$
где произведение берётся по простым. Так как каждое такое простое должно делить \(AB\), имеем
$$P \mid AB.$$
Кроме того, по условию
$$\gcd(A,B)=1.$$
Так как \(P\) квадратсвободно, любой его простой делитель может принадлежать только одной из двух сторон: либо \(A\), либо \(B\), но не обеим сразу. Значит, можно разбить набор простых чисел меньше \(q\) на две непересекающиеся группы и записать
$$D \cdot E = P,\qquad \gcd(D,E)=1,$$
причём
$$D \mid A,\qquad E \mid B.$$
Эквивалентно этому существуют положительные целые \(x,y\), для которых
$$A=Dx,\qquad B=Ey.$$
Каждый делитель \(D \mid P\) задаёт ровно одно такое разбиение, поскольку другая часть автоматически равна \(E=P/D\).
Теперь зафиксируем одно разбиение \(D \cdot E=P\).
В ветви суммы \(p=A+B\) из условия \(E \mid B\) следует
$$E \mid (p-A),$$
то есть
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
В ветви разности \(p=A-B\) имеем \(B=A-p\), и условие \(E \mid B\) снова даёт те же сравнения:
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
Тем самым обе ветви имеют общий арифметический каркас. Поскольку \(\gcd(D,E)=1\), китайская теорема об остатках даёт единственный класс вычетов по модулю
$$P=DE.$$
Если записать \(A=Dt\), то нужно решить
$$Dt \equiv p \pmod E,$$
а значит
$$t \equiv pD^{-1} \pmod E.$$
Удобный представитель имеет вид
$$A_0=D\bigl(pD^{-1} \bmod E\bigr),\qquad 0 \le A_0 < P,$$
и все кандидаты для данного разбиения записываются как
$$A=A_0+kP,\qquad k \in \mathbb{Z}_{\ge 0}.$$
Пусть \(p=A+B\) и \(A \ge B > 0\). Тогда
$$B=p-A,$$
поэтому условие \(B > 0\) равносильно \(A < p\). Из неравенства \(A \ge B\) получаем
$$A \ge p-A \iff 2A \ge p.$$
Следовательно, в ветви суммы число \(A\) обязано лежать в интервале
$$\left\lceil \frac{p}{2} \right\rceil \le A < p.$$
Взаимная простота здесь выполняется автоматически, поскольку
$$\gcd(A,B)=\gcd(A,p-A)=\gcd(A,p)=1,$$
ведь \(0 < A < p\), а \(p\) простое. Значит, для фиксированного класса вычетов нужно лишь найти наименьший член прогрессии \(A_0+kP\), попадающий в этот интервал.
Если \(p=A-B\), то
$$B=A-p,$$
и условие \(B > 0\) равносильно
$$A > p.$$
Здесь взаимная простота уже не автоматическая. Имеем
$$\gcd(A,B)=\gcd(A,A-p)=\gcd(A,p),$$
поэтому условие \(\gcd(A,B)=1\) эквивалентно требованию
$$p \nmid A.$$
Значит, в ветви разности выбирается наименьший член прогрессии \(A_0+kP\), который строго больше \(p\) и не делится на \(p\).
Это легко проверять, потому что \(p\) не входит в список простых чисел меньше \(q\), следовательно
$$\gcd(p,P)=1.$$
Если первый кандидат выше \(p\) случайно кратен \(p\), достаточно прибавить ещё один период \(P\).
Каждый делитель \(D \mid P\) описывает один способ распределить маленькие простые числа между \(A\) и \(B\). Для такого разбиения шаг CRT даёт один класс по модулю \(P\), а затем две ветви дают не более двух минимальных допустимых значений \(A\).
Следовательно, для одного простого \(p\)
$$V(p)=\min_{D \mid P}\Bigl(\min\bigl(A_{\mathrm{sum}}(D),A_{\mathrm{diff}}(D)\bigr)\Bigr),$$
где ветвь суммы просто пропускается, если соответствующий класс вычетов не пересекает интервал \([\lceil p/2\rceil,p)\). После этого вычисляется
$$S(n)=\sum_{\substack{p < n\\ p\text{ простое}}} V(p).$$
Наименьшее простое число с условием \(q^2 > 11\) равно \(q=5\). Поэтому
$$P=2 \cdot 3 = 6.$$
Делители числа \(P\) таковы: \(1,2,3,6\). Для каждого из них кладём \(E=6/D\) и решаем
$$A \equiv 0 \pmod D,\qquad A \equiv 11 \pmod E.$$
Получаем следующие классы вычетов и лучшие кандидаты:
$$\begin{aligned} D=1&:&&A \equiv 5 \pmod 6,&& \text{сумма: нет},&& \text{разность: }17,\\ D=2&:&&A \equiv 2 \pmod 6,&& \text{сумма: }8,&& \text{разность: }14,\\ D=3&:&&A \equiv 3 \pmod 6,&& \text{сумма: }9,&& \text{разность: }15,\\ D=6&:&&A \equiv 0 \pmod 6,&& \text{сумма: }6,&& \text{разность: }12. \end{aligned}$$
Глобальный минимум равен \(A=6\), и он достигается в ветви суммы при \(B=5\). Значит,
$$V(11)=6.$$
Реализации на C++, Python и Java используют один и тот же алгоритм. Сначала они строят необходимые списки простых чисел, а затем для каждого простого \(p\) находят наименьшее простое \(q\), удовлетворяющее неравенству \(q^2 > p\).
Для каждого различного значения \(q\) программа кэширует простые числа меньше \(q\), произведение \(P\), все делители \(D \mid P\) и модульные обратные, нужные для CRT-шага. Это важно, потому что многие разные простые \(p\) имеют одно и то же \(q\), а значит можно переиспользовать уже подготовленные данные о разбиениях.
Когда обрабатывается конкретное простое \(p\), программа перебирает все разбиения \(D \cdot E=P\). Для каждого из них она строит остаток \(A_0\), поднимает его до наименьшего допустимого значения в ветви суммы, затем до наименьшего допустимого значения в ветви разности и сохраняет меньший корректный кандидат. Минимум по всем разбиениям и есть \(V(p)\), после чего он добавляется к общей сумме.
Та же арифметика воспроизводит малые контрольные значения
$$S(10)=10,\qquad S(200)=7177,$$
что служит проверкой правильности перед финальным вычислением.
Обозначим через \(q(p)\) наименьшее простое число, для которого \(q(p)^2 > p\), а через \(k=\pi(q(p)-1)\) число простых меньше \(q(p)\). Поскольку \(P\) квадратсвободно, у него ровно
$$2^k$$
делителей. Значит, после подготовки таблицы разбиений для данного \(q\) обработка одного простого \(p\) требует \(O(2^k)\) проверок сравнений и переходов по арифметическим прогрессиям.
Построение таблицы простых чисел занимает \(O(n\log\log n)\). Кэширование означает, что таблицы разбиений создаются один раз для каждого различного \(q\), а не заново для каждого простого. Для целевого значения \(n=3800\) максимальное нужное \(q\) равно \(67\), поэтому самый большой набор использует \(18\) простых чисел меньше \(67\), то есть
$$2^{18}=262144$$
разбиений. Именно это и делает метод практичным: стоимость экспоненциальна по числу маленьких простых под \(q\), но само это число в нужном диапазоне остаётся умеренным.
لكل عدد أولي \(p\)، تتكوّن عملية التحقق من عدد أولي \(q\) وعددين صحيحين متباينين نسبيًا \(A \ge B > 0\)، بحيث إن كل عدد أولي أصغر من \(q\) يقسم حاصل الضرب \(AB\)، ومع ذلك يجب أن تتحقق إحدى الحالتين الآتيتين:
$$p = A + B < q^2$$
أو
$$p = A - B < q^2.$$
لكل أولي \(p\)، نعرّف \(V(p)\) بأنه أصغر قيمة ممكنة لـ \(A\) بين جميع هذه التحققات، ثم نحسب
$$S(n)=\sum_{\substack{p < n\\ p\text{ prime}}} V(p).$$
المطلوب هو إيجاد \(S(3800)\). الفحص المباشر لجميع الثلاثيات \((A,B,q)\) غير عملي، لذلك يُعاد تنظيم المسألة انطلاقًا من طريقة توزيع الأعداد الأولية الأصغر من \(q\) بين \(A\) و\(B\).
الفكرة الحاسمة هي أن تحديد الجهة التي يذهب إليها كل عدد أولي أصغر من \(q\) يجعل فرع الجمع \(p=A+B\) وفرع الطرح \(p=A-B\) يقودان في النهاية إلى نفس نظام التطابقات الخاص بـ \(A\). وهكذا تتحول المسألة إلى بحث منتهٍ على جميع تقسيمات حاصل ضرب خالٍ من المربعات.
التعريف لا يطلب إلا أن
$$p < q^2,$$
مع كون \(q\) عددًا أوليًا. إذا وُجد تحقق ما لقيمة معيّنة من \(q\)، فإن الزوج نفسه \(A,B\) يصلح أيضًا لأي أولي أصغر \(q'\) ما دام الشرط \(p < q'^2\) لا يزال صحيحًا، لأن شرط القسمة على \(AB\) يصبح أضعف حين نقلل مجموعة الأعداد الأولية المطلوبة.
لهذا السبب، فإن أصغر قيمة ممكنة لـ \(A\) تظهر عند أصغر عدد أولي يحقق \(q^2 > p\):
$$q=\min\{r \text{ prime}: r^2 > p\}.$$
إذن، لكل عدد أولي ثابت \(p\)، تصبح قيمة \(q\) محددة سلفًا.
لنرمز بـ \(P\) إلى حاصل ضرب جميع الأعداد الأولية الأصغر من \(q\):
$$P=\prod_{r < q} r,$$
حيث يؤخذ الضرب على الأعداد الأولية فقط. بما أن كل أولي أصغر من \(q\) يجب أن يقسم \(AB\)، فهذا يعني
$$P \mid AB.$$
وفي الوقت نفسه يشترط التحقق أن
$$\gcd(A,B)=1.$$
ولأن \(P\) عدد خالٍ من العوامل المربعة، فإن كل عامل أولي فيه لا بد أن يذهب إلى \(A\) أو إلى \(B\)، ولكن ليس إلى الاثنين معًا. لذلك يمكن تقسيم الأعداد الأولية الأصغر من \(q\) إلى مجموعتين منفصلتين وكتابة
$$D \cdot E = P,\qquad \gcd(D,E)=1,$$
مع
$$D \mid A,\qquad E \mid B.$$
وبصورة مكافئة توجد أعداد صحيحة موجبة \(x,y\) بحيث
$$A=Dx,\qquad B=Ey.$$
كل قاسم \(D \mid P\) يحدّد تقسيمًا واحدًا فقط، لأن الطرف الآخر يكون تلقائيًا \(E=P/D\).
لنثبت الآن تقسيمًا واحدًا \(D \cdot E=P\).
في فرع الجمع \(p=A+B\)، ومن الشرط \(E \mid B\)، نحصل على
$$E \mid (p-A),$$
ومن ثم
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
وفي فرع الطرح \(p=A-B\)، لدينا \(B=A-p\)، والشرط \(E \mid B\) يعطي بالضبط نفس التطابقات:
$$A \equiv 0 \pmod D,\qquad A \equiv p \pmod E.$$
إذن فالقلب الحسابي في الحالتين واحد. وبما أن \(\gcd(D,E)=1\)، فإن مبرهنة الباقي الصيني تعطي فئة بواقي وحيدة بترديد
$$P=DE.$$
إذا كتبنا \(A=Dt\)، فعلينا حل
$$Dt \equiv p \pmod E,$$
أي
$$t \equiv pD^{-1} \pmod E.$$
ومن ثم يمكن اختيار ممثل على الصورة
$$A_0=D\bigl(pD^{-1} \bmod E\bigr),\qquad 0 \le A_0 < P,$$
وجميع القيم المرشحة لهذا التقسيم تكون من الشكل
$$A=A_0+kP,\qquad k \in \mathbb{Z}_{\ge 0}.$$
إذا كان \(p=A+B\) مع \(A \ge B > 0\)، فإن
$$B=p-A,$$
ولذلك يكون الشرط \(B > 0\) مكافئًا لـ \(A < p\). كما أن \(A \ge B\) تعطي
$$A \ge p-A \iff 2A \ge p.$$
إذن فرع الجمع يكافئ تمامًا الفترة
$$\left\lceil \frac{p}{2} \right\rceil \le A < p.$$
وفي هذا الفرع تكون الأولية النسبية تلقائية، لأن
$$\gcd(A,B)=\gcd(A,p-A)=\gcd(A,p)=1,$$
ما دام \(0 < A < p\) و\(p\) أوليًا. لذلك يكفي، لفئة البواقي المعطاة، أن نأخذ أصغر عنصر من المتتالية \(A_0+kP\) يقع داخل هذه الفترة.
إذا كان \(p=A-B\)، فلدينا
$$B=A-p,$$
والشرط \(B > 0\) يصبح ببساطة
$$A > p.$$
هنا لا تكون الأولية النسبية تلقائية. بالفعل،
$$\gcd(A,B)=\gcd(A,A-p)=\gcd(A,p),$$
ومن ثم فإن \(\gcd(A,B)=1\) تكافئ الشرط
$$p \nmid A.$$
لذلك في فرع الطرح نختار أصغر عنصر من المتتالية \(A_0+kP\) يكون أكبر من \(p\) ولا يقبل القسمة على \(p\).
هذا سهل لأن \(p\) ليس من بين الأعداد الأولية الأصغر من \(q\)، وبالتالي
$$\gcd(p,P)=1.$$
فإذا كان أول عنصر بعد \(p\) مضاعفًا لـ \(p\)، فإن إضافة دورة واحدة أخرى مقدارها \(P\) تكفي لتجاوز هذا التعارض.
كل قاسم \(D \mid P\) يصف طريقة معينة لتوزيع الأعداد الأولية الصغيرة بين \(A\) و\(B\). لهذا التقسيم تعطي خطوة CRT فئة بواقي واحدة بترديد \(P\)، ثم ينتج من فرعي الجمع والطرح ما لا يزيد على قيمتين صغريين صالحين لـ \(A\).
لذلك نحصل، لكل أولي \(p\)، على الصيغة
$$V(p)=\min_{D \mid P}\Bigl(\min\bigl(A_{\mathrm{sum}}(D),A_{\mathrm{diff}}(D)\bigr)\Bigr),$$
مع تجاهل فرع الجمع إذا لم يقع أي عنصر من فئة البواقي داخل الفترة \([\lceil p/2\rceil,p)\). وبعد ذلك نحسب
$$S(n)=\sum_{\substack{p < n\\ p\text{ prime}}} V(p).$$
أصغر عدد أولي يحقق \(q^2 > 11\) هو \(q=5\)، ومن ثم
$$P=2 \cdot 3 = 6.$$
قواسم \(P\) هي \(1,2,3,6\). لكل واحد منها نأخذ \(E=6/D\) ونحل
$$A \equiv 0 \pmod D,\qquad A \equiv 11 \pmod E.$$
فتكون فئات البواقي وأفضل المرشحين كما يلي:
$$\begin{aligned} D=1&:&&A \equiv 5 \pmod 6,&& \text{sum: none},&& \text{diff: }17,\\ D=2&:&&A \equiv 2 \pmod 6,&& \text{sum: }8,&& \text{diff: }14,\\ D=3&:&&A \equiv 3 \pmod 6,&& \text{sum: }9,&& \text{diff: }15,\\ D=6&:&&A \equiv 0 \pmod 6,&& \text{sum: }6,&& \text{diff: }12. \end{aligned}$$
أصغر قيمة كلية هي \(A=6\)، وتتحقق في فرع الجمع مع \(B=5\). لذلك
$$V(11)=6.$$
التنفيذات في C++ وPython وJava تتبع الخطة نفسها. تبدأ أولًا بتوليد قوائم الأعداد الأولية اللازمة، ثم تحدد لكل أولي \(p\) أصغر أولي \(q\) يحقق \(q^2 > p\).
لكل قيمة مختلفة من \(q\)، تحفظ الشيفرة في الذاكرة قائمة الأعداد الأولية الأصغر من \(q\)، والجداء \(P\)، وجميع القواسم \(D \mid P\)، والمعكوسات المعيارية اللازمة لخطوة CRT. السبب هو أن عددًا كبيرًا من قيم \(p\) المختلفة يشترك في نفس \(q\)، وبالتالي يمكن إعادة استخدام بيانات التقسيم نفسها.
عند معالجة أولي معيّن \(p\)، تُفحص جميع التقسيمات \(D \cdot E=P\). لكل تقسيم تُبنى البقية \(A_0\)، ثم تُرفع إلى أصغر قيمة صالحة في فرع الجمع، وبعد ذلك إلى أصغر قيمة صالحة في فرع الطرح، ويُحتفظ بالأصغر بين المرشحين الصحيحين. أصغر قيمة بين جميع التقسيمات هي \(V(p)\)، ثم تضاف إلى المجموع الكلي.
والحساب نفسه يعيد إنتاج نقطتي الفحص الصغيرتين
$$S(10)=10,\qquad S(200)=7177,$$
وهو ما يوفر فحصًا معقولًا قبل حساب النتيجة النهائية.
لنرمز بـ \(q(p)\) إلى أصغر أولي يحقق \(q(p)^2 > p\)، ولنرمز بـ \(k=\pi(q(p)-1)\) إلى عدد الأعداد الأولية الأصغر من \(q(p)\). بما أن \(P\) خالٍ من المربعات، فهو يملك بالضبط
$$2^k$$
قاسمًا. ولذلك، بعد إعداد جدول التقسيمات الخاص بهذا \(q\)، تصبح كلفة معالجة أولي واحد \(p\) من رتبة \(O(2^k)\) من اختبارات التطابقات والتحركات على المتتاليات الحسابية.
أما توليد الأعداد الأولية نفسه فيأخذ \(O(n\log\log n)\)، بينما تُبنى جداول التقسيم مرة واحدة لكل قيمة مختلفة من \(q\)، لا مرة لكل عدد أولي. بالنسبة إلى الهدف الفعلي \(n=3800\)، فإن أكبر قيمة مطلوبة هي \(q=67\)، وعندها يوجد \(18\) عددًا أوليًا أصغر من \(67\)، أي أن أكبر جدول يحتوي على
$$2^{18}=262144$$
تقسيمًا. وهذا هو سبب بقاء الطريقة عملية: النمو أسي في عدد الأعداد الأولية الصغيرة تحت \(q\)، لكن هذا العدد يظل محدودًا في المجال المطلوب.