Define \(S(N)\) as the sum of all integers \(m\le N\) such that \(m\) is squarefree and every prime divisor \(p\mid m\) satisfies
$$p-1\mid m+3.$$
The target value is \(N=10^{12}\), so testing every integer up to \(N\) is infeasible. Useful checkpoints are
$$S(100)=32,\qquad S(10^6)=22868117.$$
The implementations therefore convert the prime-divisor conditions into modular constraints and search only inside branches that remain arithmetically possible.
The search is organized around the factorization of \(m\). Instead of scanning all integers, we explicitly choose some large prime factors, deduce a congruence for the missing part, and only enumerate that remainder when the resulting arithmetic progression is sparse enough.
The definition already requires
$$m\ \text{to be squarefree}.$$
Two further observations are crucial.
If \(m=q\) is prime, then the only nontrivial condition is
$$q-1\mid q+3,$$
so \(q-1\mid 4\). Hence the prime solutions are exactly
$$q\in\{2,3,5\}.$$
The value \(1\) is also valid vacuously because it has no prime divisors.
Next, a composite solution cannot be even. If \(2\mid m\) and some odd prime \(p\mid m\), then \(m+3\) is odd, while \(p-1\) is an even number greater than \(1\), so \(p-1\nmid m+3\). Therefore every composite solution is an odd squarefree product of distinct odd primes.
Choose a descending set of prime factors
$$\mathcal{L}=\{\ell_1\gt \ell_2\gt \cdots \gt \ell_k\ge 7\}$$
that we want to treat explicitly, and write
$$Q=\prod_{\ell\in\mathcal{L}}\ell,\qquad m=Q\,u.$$
The remaining factor \(u\) must then be odd, squarefree, and have all of its prime factors strictly smaller than the smallest selected prime \(\ell_k\).
For every \(\ell\in\mathcal{L}\), the original condition gives
$$\ell-1\mid Q\,u+3.$$
Since \(\ell\equiv 1\pmod{\ell-1}\), the selected factor \(\ell\) disappears modulo \(\ell-1\):
$$Q\equiv \frac{Q}{\ell}\pmod{\ell-1}.$$
So each selected prime yields one linear congruence for the unknown remainder factor:
$$u\cdot \frac{Q}{\ell}\equiv -3\pmod{\ell-1}.$$
Once the large prime factors are fixed, the rest of the problem has become a congruence problem in one variable.
A congruence of the form
$$a\,u\equiv -3\pmod n$$
has a solution only when
$$\gcd(a,n)\mid 3.$$
If that divisibility fails, the entire search branch is impossible and can be discarded immediately.
Otherwise, writing
$$d=\gcd(a,n),$$
we divide through by \(d\) and obtain
$$\frac{a}{d}\,u\equiv -\frac{3}{d}\pmod{\frac{n}{d}}.$$
Now the coefficient is invertible modulo \(n/d\), so this determines a unique residue class for \(u\) modulo \(n/d\).
Repeating the same reduction for every selected prime produces several residue classes, and the implementations merge them with the generalized Chinese Remainder Theorem. Either they are inconsistent, in which case the branch dies, or they collapse to a single progression
$$u\equiv r\pmod M.$$
After the congruence merge, all candidates have the form
$$u=r+tM,\qquad t\ge 0.$$
They must satisfy the obvious size bound
$$u\le \left\lfloor\frac{N}{Q}\right\rfloor.$$
There is also a sharper structural bound: because \(u\) is squarefree and may use each odd prime below \(\ell_k\) at most once,
$$u\le \prod_{\substack{q\lt \ell_k\\ q\ \text{odd prime}}} q.$$
Hence the real search interval is
$$u\le U=\min\left(\left\lfloor\frac{N}{Q}\right\rfloor,\ \prod_{\substack{q\lt \ell_k\\ q\ \text{odd prime}}} q\right).$$
If the arithmetic progression contributes only a modest number of terms up to \(U\), the implementations enumerate those terms directly. Each candidate remainder is then checked to be odd and squarefree, factored only with primes below \(\ell_k\), combined with the selected large primes, and finally tested against the original condition for every prime factor of the completed \(m\).
If the progression is still too dense, the search does not enumerate yet. Instead it selects one more large prime factor, appends it to \(\mathcal{L}\), and repeats the congruence-merging step. This branch-and-bound recursion shifts work from brute-force scanning into modular pruning.
The trivial valid values are
$$1,\ 2,\ 3,\ 5.$$
Now look at the branch where the only selected large prime is \(7\). Then \(Q=7\), and the congruence coming from \(7-1=6\) is
$$u\cdot 1\equiv -3\equiv 3\pmod 6,$$
so
$$u\equiv 3\pmod 6.$$
Also
$$u\le \left\lfloor\frac{100}{7}\right\rfloor=14.$$
Because the remaining prime factors must be smaller than \(7\), the only candidates in this progression are
$$u=3,\ 9.$$
The value \(9\) is rejected because it is not squarefree. The value \(3\) gives
$$m=7\cdot 3=21,$$
and indeed
$$21+3=24$$
is divisible by both \(2\) and \(6\), corresponding to the prime divisors \(3\) and \(7\).
For the next possible largest prime, \(11\), the congruence becomes \(u\equiv 7\pmod{10}\), so the only candidate below \(100/11\) is \(u=7\), which gives \(m=77\). That value satisfies the congruence forced by \(11\), but it fails the full condition for the smaller prime \(7\), because \(77+3=80\) is not divisible by \(6\). No larger branch produces a valid composite below \(100\).
Therefore the full list up to \(100\) is
$$1,\ 2,\ 3,\ 5,\ 21,$$
and hence
$$S(100)=1+2+3+5+21=32.$$
The C++, Python, and Java implementations all follow the same number-theoretic decomposition. They generate primes up to about \(\sqrt{N}\), insert the trivial values \(1,2,3,5\), and then recurse over descending sets of selected odd primes \(\ge 7\).
For each recursive branch, the implementation turns the selected-prime constraints into linear congruences, applies the gcd solvability test, and merges the surviving residue classes with generalized CRT. If the combined modulus already exceeds the remaining numeric search interval, only the smallest nonnegative solution can still matter, so the search range is effectively clamped there.
Next it estimates how many terms of the progression remain below the current bound. A branch is enumerated directly only when that estimate is around \(10^4\) terms or fewer; otherwise another large prime is appended and the recursion continues, which usually increases the modulus and decreases the candidate density.
Every enumerated remainder is factored with the branch-specific bound, checked for oddness and squarefreeness, combined with the selected primes, and then verified again against the original condition for every prime divisor. A set of accepted values removes duplicates that can arise from overlapping branches. The Python implementation is only a thin wrapper around the compiled search and parses the final numeric output.
Let \(N\) be the search limit. Building the prime table up to \(\sqrt{N}\) costs \(O(\sqrt{N}\log\log\sqrt{N})\) time and \(O(\sqrt{N})\) memory. After that, there is no clean closed form for the total running time because the recursion is highly data-dependent: each branch either dies early due to incompatible congruences or produces an arithmetic progression whose size is roughly \(U/M\) before final factoring and verification.
The implementation only enumerates a branch once that quantity is small, so most of the practical speed comes from modular pruning rather than from raw trial division. For one enumerated candidate, the remaining factor is checked by bounded trial division using primes below the current threshold, and the completed value is then validated against all of its distinct prime divisors. Memory usage is dominated by the prime list, the set of accepted values, and the recursion stack. In practice the admissible numbers are sparse enough that this strategy is fast for the target limit.
Definiere \(S(N)\) als die Summe aller ganzen Zahlen \(m\le N\), für die \(m\) quadratfrei ist und jeder Primteiler \(p\mid m\) die Bedingung
$$p-1\mid m+3$$
erfüllt. Der Zielwert ist \(N=10^{12}\), daher ist ein Test aller Zahlen bis \(N\) unmöglich. Nützliche Kontrollwerte sind
$$S(100)=32,\qquad S(10^6)=22868117.$$
Die Implementierungen übersetzen die Bedingungen an die Primteiler deshalb in modulare Nebenbedingungen und durchsuchen nur noch diejenigen Äste, die arithmetisch überhaupt möglich bleiben.
Die Suche wird über die Primfaktorzerlegung von \(m\) organisiert. Anstatt alle Zahlen zu testen, wählt man einige große Primfaktoren explizit aus, leitet für den fehlenden Restfaktor Kongruenzen her und enumeriert diesen Rest nur dann direkt, wenn die entstehende arithmetische Folge hinreichend dünn ist.
Bereits aus der Definition folgt
$$m\ \text{ist quadratfrei}.$$
Dazu kommen zwei weitere wichtige Beobachtungen.
Ist \(m=q\) prim, dann lautet die einzige nichttriviale Bedingung
$$q-1\mid q+3,$$
also \(q-1\mid 4\). Damit bleiben genau die Primzahlen
$$q\in\{2,3,5\}.$$
Außerdem ist \(1\) trivial gültig, weil es keine Primteiler besitzt.
Ferner kann eine zusammengesetzte Lösung nicht gerade sein. Gilt \(2\mid m\) und zugleich \(p\mid m\) für eine ungerade Primzahl \(p\), dann ist \(m+3\) ungerade, während \(p-1\) eine gerade Zahl größer als \(1\) ist. Also kann \(p-1\) \(m+3\) nicht teilen. Folglich ist jede zusammengesetzte Lösung ein ungerades quadratfreies Produkt verschiedener ungerader Primzahlen.
Wähle eine streng fallende Menge von Primfaktoren
$$\mathcal{L}=\{\ell_1\gt \ell_2\gt \cdots \gt \ell_k\ge 7\}$$
die explizit behandelt werden soll, und schreibe
$$Q=\prod_{\ell\in\mathcal{L}}\ell,\qquad m=Q\,u.$$
Dann muss der verbleibende Faktor \(u\) ungerade und quadratfrei sein, und alle seine Primfaktoren müssen strikt kleiner als die kleinste ausgewählte Primzahl \(\ell_k\) sein.
Für jedes \(\ell\in\mathcal{L}\) liefert die ursprüngliche Bedingung
$$\ell-1\mid Q\,u+3.$$
Da \(\ell\equiv 1\pmod{\ell-1}\) gilt, verschwindet der Faktor \(\ell\) modulo \(\ell-1\):
$$Q\equiv \frac{Q}{\ell}\pmod{\ell-1}.$$
Somit erzeugt jede ausgewählte Primzahl genau eine lineare Kongruenz für den unbekannten Restfaktor:
$$u\cdot \frac{Q}{\ell}\equiv -3\pmod{\ell-1}.$$
Sobald die großen Primfaktoren feststehen, ist der verbleibende Teil des Problems also ein Kongruenzproblem in einer Variablen.
Eine Kongruenz der Form
$$a\,u\equiv -3\pmod n$$
ist nur dann lösbar, wenn
$$\gcd(a,n)\mid 3.$$
Falls diese Teilbarkeit nicht gilt, kann der gesamte Suchast sofort verworfen werden.
Schreibt man
$$d=\gcd(a,n),$$
so erhält man nach Division durch \(d\)
$$\frac{a}{d}\,u\equiv -\frac{3}{d}\pmod{\frac{n}{d}}.$$
Jetzt ist der Koeffizient modulo \(n/d\) invertierbar, und damit ist eine eindeutige Restklasse für \(u\) modulo \(n/d\) bestimmt.
Wiederholt man diese Reduktion für alle ausgewählten Primzahlen, entstehen mehrere Restklassen, die von den Implementierungen mit dem verallgemeinerten chinesischen Restsatz zusammengeführt werden. Entweder sind sie widersprüchlich, dann stirbt der Ast, oder sie fallen zu einer einzigen Progression zusammen:
$$u\equiv r\pmod M.$$
Nach dem Zusammenführen haben alle Kandidaten die Form
$$u=r+tM,\qquad t\ge 0.$$
Zusätzlich gilt die offensichtliche Größenbeschränkung
$$u\le \left\lfloor\frac{N}{Q}\right\rfloor.$$
Es gibt aber auch eine schärfere strukturelle Schranke: Weil \(u\) quadratfrei ist und jede ungerade Primzahl unterhalb von \(\ell_k\) höchstens einmal verwenden darf, gilt
$$u\le \prod_{\substack{q\lt \ell_k\\ q\ \text{ungerade Primzahl}}} q.$$
Die tatsächliche Suchgrenze lautet daher
$$u\le U=\min\left(\left\lfloor\frac{N}{Q}\right\rfloor,\ \prod_{\substack{q\lt \ell_k\\ q\ \text{ungerade Primzahl}}} q\right).$$
Erzeugt die arithmetische Folge bis \(U\) nur noch relativ wenige Werte, enumerieren die Implementierungen diese direkt. Jeder Kandidat wird dann darauf geprüft, ungerade und quadratfrei zu sein, nur mit Primzahlen unterhalb von \(\ell_k\) faktorisiert, mit den ausgewählten großen Primzahlen zusammengesetzt und anschließend nochmals gegen die ursprüngliche Bedingung für alle Primteiler des vollständigen \(m\) getestet.
Ist die Folge noch zu dicht, wird noch nicht enumeriert. Stattdessen wird eine weitere große Primzahl ausgewählt, an \(\mathcal{L}\) angehängt und der Kongruenzschritt wiederholt. Diese Branch-and-Bound-Rekursion verschiebt Arbeit von roher Enumeration in modulare Ausdünnung.
Die trivial gültigen Werte sind
$$1,\ 2,\ 3,\ 5.$$
Betrachte nun den Ast, in dem die einzige ausgewählte große Primzahl \(7\) ist. Dann ist \(Q=7\), und die Kongruenz aus \(7-1=6\) lautet
$$u\cdot 1\equiv -3\equiv 3\pmod 6,$$
also
$$u\equiv 3\pmod 6.$$
Außerdem gilt
$$u\le \left\lfloor\frac{100}{7}\right\rfloor=14.$$
Da die verbleibenden Primfaktoren kleiner als \(7\) sein müssen, kommen in dieser Progression nur
$$u=3,\ 9$$
in Frage. Der Wert \(9\) fällt weg, weil er nicht quadratfrei ist. Der Wert \(3\) liefert
$$m=7\cdot 3=21,$$
und tatsächlich ist
$$21+3=24$$
sowohl durch \(2\) als auch durch \(6\) teilbar, passend zu den Primteilern \(3\) und \(7\).
Für die nächste mögliche größte Primzahl \(11\) wird die Kongruenz zu \(u\equiv 7\pmod{10}\). Unterhalb von \(100/11\) bleibt dann nur \(u=7\), also \(m=77\). Dieser Wert erfüllt zwar die Bedingung für \(11\), scheitert aber an der kleineren Primzahl \(7\), denn \(77+3=80\) ist nicht durch \(6\) teilbar. Kein größerer Ast erzeugt eine weitere gültige zusammengesetzte Zahl unter \(100\).
Die vollständige Liste bis \(100\) lautet also
$$1,\ 2,\ 3,\ 5,\ 21,$$
und damit
$$S(100)=1+2+3+5+21=32.$$
Die C++-, Python- und Java-Implementierungen folgen derselben zahlentheoretischen Zerlegung. Sie erzeugen Primzahlen bis ungefähr \(\sqrt{N}\), fügen die trivialen Werte \(1,2,3,5\) ein und durchlaufen dann rekursiv fallende Mengen ausgewählter ungerader Primzahlen \(\ge 7\).
Für jeden Rekursionsast wandelt die Implementierung die Bedingungen der ausgewählten Primzahlen in lineare Kongruenzen um, führt den ggT-Lösbarkeitstest durch und vereinigt die verbleibenden Restklassen mit dem verallgemeinerten chinesischen Restsatz. Überschreitet der kombinierte Modulus bereits den verbleibenden numerischen Suchbereich, kann nur noch die kleinste nichtnegative Lösung relevant sein; an dieser Stelle wird der Bereich daher effektiv begrenzt.
Anschließend wird abgeschätzt, wie viele Glieder der Progression noch unterhalb der aktuellen Schranke liegen. Direkt enumeriert wird nur dann, wenn diese Schätzung bei ungefähr \(10^4\) Werten oder weniger liegt; andernfalls wird noch eine weitere große Primzahl angehängt und die Rekursion fortgesetzt, was den Modulus meist vergrößert und die Kandidatendichte verkleinert.
Jeder enumerierte Restfaktor wird mit der jeweiligen Schranke faktorisiert, auf Ungeradheit und Quadratfreiheit geprüft, mit den ausgewählten Primzahlen kombiniert und danach nochmals gegen die ursprüngliche Teilbarkeitsbedingung für jeden Primteiler getestet. Eine Menge akzeptierter Werte entfernt Duplikate, die aus überlappenden Rekursionsästen entstehen können. Die Python-Implementierung ist dabei nur eine dünne Hülle um die kompilierte Suche und extrahiert den numerischen Endwert.
Sei \(N\) die Suchgrenze. Das Erzeugen der Primtabelle bis \(\sqrt{N}\) kostet \(O(\sqrt{N}\log\log\sqrt{N})\) Zeit und \(O(\sqrt{N})\) Speicher. Danach gibt es keine einfache geschlossene Formel für die Gesamtlaufzeit, weil die Rekursion stark datenabhängig ist: Jeder Ast stirbt entweder früh wegen widersprüchlicher Kongruenzen oder führt auf eine arithmetische Folge mit ungefähr \(U/M\) Kandidaten vor der abschließenden Faktorisierung und Verifikation.
Enumeriert wird ein Ast erst dann, wenn diese Anzahl klein genug ist; der praktische Geschwindigkeitsgewinn stammt also vor allem aus modularer Ausdünnung und nicht aus roher Probeteilung. Für einen einzelnen Kandidaten wird der Restfaktor mit Primzahlen unterhalb der aktuellen Schranke per begrenzter Probeteilung geprüft, und der vervollständigte Wert wird anschließend gegen alle seine verschiedenen Primteiler validiert. Der Speicherbedarf wird von der Primtabelle, der Menge akzeptierter Werte und dem Rekursionsstack dominiert. In der Praxis sind die zulässigen Zahlen so dünn verteilt, dass diese Strategie für die Zielgrenze effizient ist.
\(S(N)\), \(m\le N\) olan ve hem kare-çarpansız olan hem de her asal böleni \(p\mid m\) için
$$p-1\mid m+3$$
koşulunu sağlayan tüm sayıların toplamıdır. Hedef değer \(N=10^{12}\) olduğundan, \(1\)'den \(N\)'ye kadar her sayıyı tek tek test etmek mümkün değildir. Yararlı kontrol değerleri şunlardır:
$$S(100)=32,\qquad S(10^6)=22868117.$$
Bu yüzden implementasyonlar asal bölen koşullarını modüler kısıtlara çevirir ve yalnızca aritmetik olarak mümkün kalan dalları tarar.
Arama, \(m\)'nin asal çarpanlarına göre düzenlenir. Tüm sayıları taramak yerine bazı büyük asal çarpanları açıkça seçer, geriye kalan çarpan için kongruensler çıkarır ve bu kalan kısmı ancak ortaya çıkan aritmetik dizi yeterince seyrekse doğrudan sayarız.
Tanım gereği
$$m\ \text{kare-çarpansızdır}.$$
Bunun yanında iki önemli sonuç daha vardır.
Eğer \(m=q\) asal ise tek anlamlı koşul
$$q-1\mid q+3$$
olur. Bu da \(q-1\mid 4\) demektir; dolayısıyla asal çözümler yalnızca
$$q\in\{2,3,5\}$$
olabilir. Ayrıca \(1\), asal böleni olmadığı için boşluktan dolayı geçerlidir.
Ayrıca bileşik bir çözüm çift olamaz. Eğer \(2\mid m\) ve aynı anda tek bir asal \(p\mid m\) ise, \(m+3\) tek olur; fakat \(p-1\), \(1\)'den büyük çift bir sayıdır. O halde \(p-1\), \(m+3\)'ü bölemez. Demek ki her bileşik çözüm, farklı tek asalların çarpımı olan tek bir kare-çarpansız sayıdır.
Açıkça ele almak istediğimiz, azalan sırada bir asal kümesi seçelim:
$$\mathcal{L}=\{\ell_1\gt \ell_2\gt \cdots \gt \ell_k\ge 7\}.$$
Bunların çarpımını
$$Q=\prod_{\ell\in\mathcal{L}}\ell,\qquad m=Q\,u$$
şeklinde yazalım. Böylece geriye kalan \(u\), tek ve kare-çarpansız olmalı; ayrıca tüm asal bölenleri seçilen en küçük asal \(\ell_k\)'den küçük olmalıdır.
Her \(\ell\in\mathcal{L}\) için özgün koşul
$$\ell-1\mid Q\,u+3$$
verir. \(\ell\equiv 1\pmod{\ell-1}\) olduğundan, \(Q\) içindeki \(\ell\) çarpanı mod \(\ell-1\)'de kaybolur:
$$Q\equiv \frac{Q}{\ell}\pmod{\ell-1}.$$
Böylece seçilen her asal, bilinmeyen kalan çarpan için bir doğrusal kongruens üretir:
$$u\cdot \frac{Q}{\ell}\equiv -3\pmod{\ell-1}.$$
Büyük asal çarpanlar sabitlenince, problemin geri kalanı tek değişkenli bir kongruens problemine dönüşür.
Şu biçimde bir kongruens düşünelim:
$$a\,u\equiv -3\pmod n.$$
Bunun çözülebilmesi için
$$\gcd(a,n)\mid 3$$
olması gerekir. Bu bölünebilme sağlanmıyorsa o arama dalı hemen elenir.
Şimdi
$$d=\gcd(a,n)$$
olsun. O zaman \(d\) ile sadeleştirip
$$\frac{a}{d}\,u\equiv -\frac{3}{d}\pmod{\frac{n}{d}}$$
yazarız. Artık katsayı, \(n/d\) modunda terslenebilir olduğundan, bu ifade \(u\) için tek bir kalıntı sınıfı belirler.
Aynı işlem tüm seçilen asallar için yapıldığında birden fazla kalıntı sınıfı elde ederiz. Implementasyonlar bunları genelleştirilmiş Çin Kalan Teoremi ile birleştirir. Sonuç ya çelişkilidir ve dal kapanır, ya da tek bir ilerlemeye iner:
$$u\equiv r\pmod M.$$
Kongruensler birleştirildikten sonra tüm adaylar
$$u=r+tM,\qquad t\ge 0$$
biçimindedir. Ayrıca açık boyut sınırı
$$u\le \left\lfloor\frac{N}{Q}\right\rfloor$$
vardır.
Daha da güçlü bir yapısal sınır vardır: \(u\) kare-çarpansızdır ve \(\ell_k\)'den küçük her tek asalı en fazla bir kez kullanabilir. Bu nedenle
$$u\le \prod_{\substack{q\lt \ell_k\\ q\ \text{tek asal}}} q.$$
Gerçek arama üst sınırı böylece
$$u\le U=\min\left(\left\lfloor\frac{N}{Q}\right\rfloor,\ \prod_{\substack{q\lt \ell_k\\ q\ \text{tek asal}}} q\right)$$
olur. Eğer aritmetik dizi \(U\)'ya kadar yalnızca makul sayıda terim içeriyorsa implementasyon bu terimleri doğrudan dener. Her aday kalan çarpan için tek olma ve kare-çarpansızlık kontrol edilir, yalnızca \(\ell_k\)'den küçük asallarla çarpanlara ayrılır, seçilen büyük asallarla birleştirilir ve sonra oluşan tam \(m\) için özgün koşul tüm asal bölenler üzerinde tekrar doğrulanır.
Eğer dizi hâlâ çok yoğunsa henüz doğrudan tarama yapılmaz. Bunun yerine yeni bir büyük asal seçilir, \(\mathcal{L}\)'ye eklenir ve kongruens birleştirme adımı tekrarlanır. Bu dal-budala yaklaşımı işi kaba taramadan modüler elemeye kaydırır.
Önce trivyal geçerli değerler
$$1,\ 2,\ 3,\ 5$$
gelir.
Şimdi yalnızca \(7\)'nin seçilmiş büyük asal olduğu dala bakalım. Bu durumda \(Q=7\) olur ve \(7-1=6\)'dan gelen kongruens
$$u\cdot 1\equiv -3\equiv 3\pmod 6$$
olur; yani
$$u\equiv 3\pmod 6.$$
Ayrıca
$$u\le \left\lfloor\frac{100}{7}\right\rfloor=14.$$
Kalan asal bölenlerin \(7\)'den küçük olması gerektiği için bu ilerlemedeki adaylar yalnızca
$$u=3,\ 9$$
olur. \(9\), kare-çarpansız olmadığı için elenir. \(3\) ise
$$m=7\cdot 3=21$$
verir ve gerçekten
$$21+3=24$$
hem \(2\)'ye hem de \(6\)'ya bölünür; bunlar sırasıyla \(3\) ve \(7\) asal bölenlerine karşılık gelir.
Bir sonraki olası en büyük asal \(11\) için kongruens \(u\equiv 7\pmod{10}\) olur. \(100/11\)'in altında tek aday \(u=7\)'dir ve bu da \(m=77\) verir. Bu sayı \(11\)'in dayattığı koşulu geçse de daha küçük asal \(7\) için başarısız olur; çünkü \(77+3=80\), \(6\)'ya bölünmez. Daha büyük hiçbir dal \(100\)'ün altında yeni bir bileşik çözüm üretmez.
Dolayısıyla \(100\)'e kadar tam liste
$$1,\ 2,\ 3,\ 5,\ 21$$
olur ve
$$S(100)=1+2+3+5+21=32.$$
C++, Python ve Java implementasyonları aynı sayılar kuramı ayrışımını izler. Yaklaşık \(\sqrt{N}\)'ye kadar asalları üretir, trivyal değerler \(1,2,3,5\)'i ekler ve sonra \(\ge 7\) olan seçilmiş tek asalların azalan kümeleri üzerinde özyinelemeli ilerler.
Her özyinelemeli dal için implementasyon, seçilmiş asalların koşullarını doğrusal kongruenslere çevirir, EBOB tabanlı çözülebilirlik testini uygular ve kalan kalıntı sınıflarını genelleştirilmiş Çin Kalan Teoremi ile birleştirir. Eğer birleşik modül artık kalan sayısal arama aralığını aşmışsa yalnızca en küçük negatif olmayan çözüm anlamlı olabilir; bu noktada aralık fiilen sıkıştırılır.
Sonraki adımda, bu ilerlemenin mevcut üst sınır altında kaç terim ürettiği tahmin edilir. Bu sayı yaklaşık \(10^4\) ya da daha az ise dal doğrudan taranır; değilse yeni bir büyük asal eklenir ve özyineleme sürer. Bu genellikle modülü büyütür ve aday yoğunluğunu azaltır.
Doğrudan taranan her kalan değer, ilgili dalın sınırına göre çarpanlara ayrılır, tek ve kare-çarpansız olup olmadığı denetlenir, seçilmiş asallarla birleştirilir ve sonra özgün bölünebilme koşulu tüm asal bölenler için yeniden test edilir. Örtüşen dallardan gelebilecek tekrarları kaldırmak için kabul edilen değerler bir kümede tutulur. Python implementasyonu ise yalnızca derlenmiş aramayı çağıran ve son sayısal çıktıyı ayrıştıran ince bir katmandır.
\(N\) arama sınırı olsun. \(\sqrt{N}\)'ye kadar asal tablosu kurmak \(O(\sqrt{N}\log\log\sqrt{N})\) zaman ve \(O(\sqrt{N})\) bellek ister. Bundan sonraki toplam çalışma için temiz bir kapalı form yoktur; çünkü özyineleme veriye çok bağlıdır: her dal ya çelişkili kongruensler nedeniyle erken ölür ya da son faktörleme ve doğrulamadan önce yaklaşık \(U/M\) kadar aday içeren bir aritmetik ilerleme üretir.
Implementasyon bir dalı ancak bu miktar küçük olduğunda doğrudan tarar; dolayısıyla pratik hızın büyük kısmı kaba deneme bölmesinden değil, modüler budamadan gelir. Taranan tek bir aday için kalan çarpan, mevcut eşik altındaki asallarla sınırlı deneme bölmesiyle kontrol edilir; sonra tamamlanmış sayı, farklı asal bölenlerinin tümüne göre doğrulanır. Bellek kullanımı asal listesi, kabul edilen değerler kümesi ve özyineleme yığını tarafından belirlenir. Uygulamada geçerli sayıların çok seyrek olması bu stratejiyi hedef sınır için yeterince hızlı kılar.
Definimos \(S(N)\) como la suma de todos los enteros \(m\le N\) tales que \(m\) es libre de cuadrados y todo primo divisor \(p\mid m\) satisface
$$p-1\mid m+3.$$
El objetivo real es \(N=10^{12}\), así que no se puede comprobar cada entero hasta \(N\). Dos valores de control útiles son
$$S(100)=32,\qquad S(10^6)=22868117.$$
Por eso las implementaciones convierten las condiciones sobre los primos divisores en restricciones modulares y solo exploran ramas que siguen siendo aritméticamente posibles.
La búsqueda se organiza a partir de la factorización prima de \(m\). En lugar de recorrer todos los enteros, se fijan explícitamente algunos primos grandes, se deduce una congruencia para el factor que falta y ese resto solo se enumera cuando la progresión aritmética resultante ya es lo bastante dispersa.
La definición ya exige que
$$m\ \text{sea libre de cuadrados}.$$
Además hay dos observaciones decisivas.
Si \(m=q\) es primo, la única condición no trivial es
$$q-1\mid q+3,$$
de modo que \(q-1\mid 4\). Por tanto, las soluciones primas son exactamente
$$q\in\{2,3,5\}.$$
El valor \(1\) también es válido de forma vacía, porque no tiene divisores primos.
Además, una solución compuesta no puede ser par. Si \(2\mid m\) y algún primo impar \(p\mid m\), entonces \(m+3\) es impar, mientras que \(p-1\) es un número par mayor que \(1\). Así, \(p-1\) no puede dividir a \(m+3\). En consecuencia, toda solución compuesta es un producto impar, libre de cuadrados, de primos impares distintos.
Escogemos un conjunto decreciente de factores primos
$$\mathcal{L}=\{\ell_1\gt \ell_2\gt \cdots \gt \ell_k\ge 7\}$$
que queremos tratar de forma explícita, y escribimos
$$Q=\prod_{\ell\in\mathcal{L}}\ell,\qquad m=Q\,u.$$
Entonces el factor restante \(u\) debe ser impar, libre de cuadrados y con todos sus divisores primos estrictamente menores que el menor primo elegido \(\ell_k\).
Para cada \(\ell\in\mathcal{L}\), la condición original da
$$\ell-1\mid Q\,u+3.$$
Como \(\ell\equiv 1\pmod{\ell-1}\), el factor \(\ell\) desaparece módulo \(\ell-1\):
$$Q\equiv \frac{Q}{\ell}\pmod{\ell-1}.$$
Así, cada primo elegido produce una congruencia lineal para el factor restante:
$$u\cdot \frac{Q}{\ell}\equiv -3\pmod{\ell-1}.$$
Una vez fijados los primos grandes, el resto del problema se convierte en un problema de congruencias con una sola variable.
Una congruencia de la forma
$$a\,u\equiv -3\pmod n$$
solo tiene solución si
$$\gcd(a,n)\mid 3.$$
Si esa divisibilidad falla, toda la rama se descarta de inmediato.
Escribiendo
$$d=\gcd(a,n),$$
podemos dividir por \(d\) y obtener
$$\frac{a}{d}\,u\equiv -\frac{3}{d}\pmod{\frac{n}{d}}.$$
Ahora el coeficiente es invertible módulo \(n/d\), de modo que la congruencia determina una clase residual única para \(u\) módulo \(n/d\).
Repitiendo esta reducción para todos los primos elegidos se obtienen varias clases residuales, y las implementaciones las combinan mediante el Teorema Chino del Resto generalizado. O bien son incompatibles y la rama muere, o bien colapsan en una sola progresión:
$$u\equiv r\pmod M.$$
Tras combinar las congruencias, todos los candidatos tienen la forma
$$u=r+tM,\qquad t\ge 0.$$
Además deben satisfacer la cota obvia
$$u\le \left\lfloor\frac{N}{Q}\right\rfloor.$$
Hay también una cota estructural más fuerte: como \(u\) es libre de cuadrados y puede usar cada primo impar menor que \(\ell_k\) a lo sumo una vez, se tiene
$$u\le \prod_{\substack{q\lt \ell_k\\ q\ \text{primo impar}}} q.$$
Por tanto, el límite real de búsqueda es
$$u\le U=\min\left(\left\lfloor\frac{N}{Q}\right\rfloor,\ \prod_{\substack{q\lt \ell_k\\ q\ \text{primo impar}}} q\right).$$
Si la progresión aritmética aporta solo un número moderado de términos hasta \(U\), las implementaciones los enumeran directamente. Luego cada candidato se comprueba para verificar que es impar y libre de cuadrados, se factoriza usando solo primos menores que \(\ell_k\), se combina con los primos grandes elegidos y al final se vuelve a validar la condición original para todos los divisores primos del \(m\) completo.
Si la progresión sigue siendo demasiado densa, todavía no se enumera. En su lugar se añade otro primo grande a \(\mathcal{L}\) y se repite el paso de fusión de congruencias. Esta recursión de tipo branch-and-bound traslada trabajo desde la exploración bruta hacia la poda modular.
Los valores triviales válidos son
$$1,\ 2,\ 3,\ 5.$$
Consideremos ahora la rama en la que el único primo grande elegido es \(7\). Entonces \(Q=7\), y la congruencia procedente de \(7-1=6\) es
$$u\cdot 1\equiv -3\equiv 3\pmod 6,$$
es decir,
$$u\equiv 3\pmod 6.$$
Además,
$$u\le \left\lfloor\frac{100}{7}\right\rfloor=14.$$
Como los factores primos restantes deben ser menores que \(7\), los únicos candidatos en esa progresión son
$$u=3,\ 9.$$
El valor \(9\) se rechaza porque no es libre de cuadrados. El valor \(3\) produce
$$m=7\cdot 3=21,$$
y de hecho
$$21+3=24$$
es divisible por \(2\) y por \(6\), correspondientes a los divisores primos \(3\) y \(7\).
Para el siguiente posible primo máximo, \(11\), la congruencia pasa a ser \(u\equiv 7\pmod{10}\). Por debajo de \(100/11\) solo aparece \(u=7\), que da \(m=77\). Ese valor satisface la congruencia impuesta por \(11\), pero falla la condición completa para el primo menor \(7\), porque \(77+3=80\) no es divisible por \(6\). Ninguna rama mayor produce otra solución compuesta por debajo de \(100\).
Por tanto, la lista completa hasta \(100\) es
$$1,\ 2,\ 3,\ 5,\ 21,$$
y así
$$S(100)=1+2+3+5+21=32.$$
Las implementaciones en C++, Python y Java siguen la misma descomposición de teoría de números. Generan primos hasta aproximadamente \(\sqrt{N}\), insertan los valores triviales \(1,2,3,5\) y luego recorren de forma recursiva conjuntos decrecientes de primos impares elegidos, todos ellos \(\ge 7\).
En cada rama recursiva, la implementación transforma las restricciones de los primos elegidos en congruencias lineales, aplica la prueba de solvencia basada en el mcd y combina las clases residuales supervivientes mediante CRT generalizado. Si el módulo combinado ya supera el intervalo numérico restante, solo puede importar la solución no negativa más pequeña, así que el rango de búsqueda queda efectivamente acotado en ese punto.
Después se estima cuántos términos de la progresión quedan por debajo de la cota actual. Una rama solo se enumera directamente cuando esa estimación es del orden de \(10^4\) términos o menos; en caso contrario se añade otro primo grande y la recursión continúa, lo que normalmente aumenta el módulo y reduce la densidad de candidatos.
Cada resto enumerado se factoriza con la cota propia de la rama, se comprueba que sea impar y libre de cuadrados, se combina con los primos elegidos y luego se valida de nuevo la condición original para todos los divisores primos. Un conjunto de valores aceptados elimina duplicados que pueden aparecer por ramas solapadas. La implementación en Python es solo un envoltorio ligero alrededor de la búsqueda compilada y extrae el resultado numérico final.
Sea \(N\) el límite de búsqueda. Construir la tabla de primos hasta \(\sqrt{N}\) cuesta \(O(\sqrt{N}\log\log\sqrt{N})\) tiempo y \(O(\sqrt{N})\) memoria. Después no hay una forma cerrada sencilla para el tiempo total, porque la recursión depende mucho de los datos: cada rama muere pronto por congruencias incompatibles o produce una progresión aritmética de tamaño aproximado \(U/M\) antes de la factorización y verificación final.
La implementación solo enumera una rama cuando esa cantidad ya es pequeña; por eso, en la práctica, la mayor parte de la velocidad proviene de la poda modular y no de la división por prueba bruta. Para un candidato enumerado, el factor restante se comprueba mediante división por prueba acotada usando primos por debajo del umbral actual, y luego el valor completo se valida contra todos sus divisores primos distintos. La memoria está dominada por la lista de primos, el conjunto de valores aceptados y la pila de recursión. En la práctica los números válidos son lo bastante escasos como para que esta estrategia resulte eficiente en el límite objetivo.
定义 \(S(N)\) 为所有满足下列条件的整数 \(m\le N\) 的总和：\(m\) 是无平方因子的，并且对每一个素因子 \(p\mid m\) 都有
$$p-1\mid m+3.$$
真实目标是 \(N=10^{12}\)，因此不可能把 \(1\) 到 \(N\) 的每个整数都逐个检查。两个很有用的校验值是
$$S(100)=32,\qquad S(10^6)=22868117.$$
因此，程序并不是对所有整数做暴力判断，而是把“每个素因子带来的条件”改写成模约束，只在仍然可能成立的搜索分支里继续向下探索。
整个搜索围绕 \(m\) 的素因子分解来组织。核心思路不是枚举所有 \(m\)，而是先显式固定一部分较大的素因子，再由这些素因子推出剩余部分必须满足的同余条件，只有当对应的等差数列已经足够稀疏时，才真正去枚举剩余因子。
题目定义已经直接要求
$$m\ \text{必须是无平方因子的}.$$
除此之外，还有两个非常重要的推论。
如果 \(m=q\) 本身是素数，那么唯一非平凡的条件就是
$$q-1\mid q+3.$$
这等价于 \(q-1\mid 4\)，因此素数解只能是
$$q\in\{2,3,5\}.$$
另外，\(1\) 也天然合法，因为它没有任何素因子需要检查。
第二个结论是：合数解不可能是偶数。原因是，如果 \(2\mid m\) 且还有某个奇素数 \(p\mid m\)，那么 \(m+3\) 是奇数，而 \(p-1\) 是一个大于 \(1\) 的偶数，不可能整除奇数 \(m+3\)。所以所有合数解都必须是由互不相同的奇素数组成的奇数无平方因子乘积。
设我们显式选出一组按降序排列的大素因子
$$\mathcal{L}=\{\ell_1\gt \ell_2\gt \cdots \gt \ell_k\ge 7\},$$
并记它们的乘积为
$$Q=\prod_{\ell\in\mathcal{L}}\ell,\qquad m=Q\,u.$$
这样一来，剩余因子 \(u\) 必须满足三个条件：它是奇数，它本身也必须无平方因子，而且它的所有素因子都必须严格小于所选素因子中最小的那个 \(\ell_k\)。
对每个 \(\ell\in\mathcal{L}\)，原始条件给出
$$\ell-1\mid Q\,u+3.$$
由于 \(\ell\equiv 1\pmod{\ell-1}\)，所以在模 \(\ell-1\) 的意义下，\(Q\) 中这一份 \(\ell\) 可以被消掉：
$$Q\equiv \frac{Q}{\ell}\pmod{\ell-1}.$$
因此，每一个被选中的大素因子都会给 \(u\) 带来一个线性同余：
$$u\cdot \frac{Q}{\ell}\equiv -3\pmod{\ell-1}.$$
这一步很关键，因为一旦大素因子固定，剩下的问题就从“寻找所有可能的乘积”变成了“在某个同余类里寻找合适的 \(u\)”。
考虑一般形式
$$a\,u\equiv -3\pmod n$$
的同余。它并不是总有解的。必要且充分的可解条件是
$$\gcd(a,n)\mid 3.$$
一旦这个整除关系不成立，当前整条搜索分支就可以立刻剪掉，因为根本不可能存在满足条件的 \(u\)。
若令
$$d=\gcd(a,n),$$
那么把同余整体除以 \(d\) 后可得
$$\frac{a}{d}\,u\equiv -\frac{3}{d}\pmod{\frac{n}{d}}.$$
这时新的系数与模数互素，因此它在模 \(n/d\) 下有乘法逆元，于是就能把 \(u\) 唯一地确定到某个剩余类里。
对所有选中的大素因子都做这件事，就会得到若干个关于 \(u\) 的剩余类。程序再用广义中国剩余定理把它们合并起来。结果只有两种：
$$u\equiv r\pmod M$$
这样的单一等差条件成立，或者这些条件彼此矛盾，整个分支直接结束。
同余条件合并后，所有候选 \(u\) 都具有形式
$$u=r+tM,\qquad t\ge 0.$$
它们首先要满足显然的大小约束
$$u\le \left\lfloor\frac{N}{Q}\right\rfloor.$$
但程序还会再加一个更强的结构性上界。因为 \(u\) 必须无平方因子，而且每个小于 \(\ell_k\) 的奇素数最多只能在 \(u\) 中出现一次，所以有
$$u\le \prod_{\substack{q\lt \ell_k\\ q\ \text{为奇素数}}} q.$$
于是实际搜索上界写成
$$u\le U=\min\left(\left\lfloor\frac{N}{Q}\right\rfloor,\ \prod_{\substack{q\lt \ell_k\\ q\ \text{为奇素数}}} q\right).$$
如果这条等差数列在 \(U\) 以内只剩下不多的项，程序就直接枚举这些 \(u\)。对每个候选 \(u\)，程序会检查它是否为奇数、是否无平方因子、它的素因子是否都落在当前分支允许的范围内，然后把它与已经选中的大素因子重新拼成完整的 \(m\)，最后再对 \(m\) 的每个素因子完整验证原始条件。
如果这条数列仍然太密，程序就暂时不枚举，而是继续再选入一个更小的大素因子，把新的约束继续并入同余系统。这样做的效果是：与其在一个很长的数列上暴力筛选，不如不断增强模约束，让候选自然变得稀少。
先看最简单的合法值：
$$1,\ 2,\ 3,\ 5.$$
接着考虑“唯一选中的大素因子是 \(7\)”这一分支。这时 \(Q=7\)，而来自 \(7-1=6\) 的条件是
$$u\cdot 1\equiv -3\equiv 3\pmod 6,$$
也就是
$$u\equiv 3\pmod 6.$$
同时还有大小限制
$$u\le \left\lfloor\frac{100}{7}\right\rfloor=14.$$
由于剩余素因子必须都小于 \(7\)，这个分支里可能出现的候选只有
$$u=3,\ 9.$$
其中 \(9\) 不是无平方因子，所以立即排除。\(u=3\) 对应
$$m=7\cdot 3=21.$$
而且确实有
$$21+3=24,$$
它同时被 \(2\) 和 \(6\) 整除，分别对应素因子 \(3\) 与 \(7\) 的要求，所以 \(21\) 是合法解。
再看下一个可能的最大素因子 \(11\)。此时同余条件变成 \(u\equiv 7\pmod{10}\)。在 \(100/11\) 以下，唯一候选是 \(u=7\)，于是得到 \(m=77\)。这个数虽然满足由素因子 \(11\) 推出的同余条件，但它对更小的素因子 \(7\) 不成立，因为 \(77+3=80\) 不能被 \(6\) 整除。所以这个分支最终也失败。
继续往上看，更大的分支都不会在 \(100\) 以下再产生新的合数解。于是完整列表就是
$$1,\ 2,\ 3,\ 5,\ 21,$$
从而
$$S(100)=1+2+3+5+21=32.$$
C++、Python 和 Java 实现遵循的是同一套数论分解。它们先生成大约到 \(\sqrt{N}\) 为止的素数，加入平凡合法值 \(1,2,3,5\)，然后在所有按降序排列、且元素都不小于 \(7\) 的“大素因子集合”上做递归搜索。
对于每个递归分支，程序先把已选大素因子的限制改写成线性同余，做一次基于最大公约数的可解性判断，再用广义中国剩余定理把这些剩余类合并起来。如果合并后的模数已经超过当前剩余的数值搜索范围，那么实际上只有最小的非负解还可能有意义，所以实现会在这里把搜索范围等效地截断。
随后程序会估计这条等差数列在当前上界内还剩多少项。只有当这个数量大约不超过 \(10^4\) 时，才会直接枚举；否则就继续向分支里加入一个新的大素因子，让模数进一步变大、候选进一步变稀。
每个真正枚举到的剩余因子都会在当前分支的阈值下做试除分解，检查它是否为奇数、是否无平方因子，然后与已选大素因子合并成完整的 \(m\)，并再次对 \(m\) 的所有素因子验证原始整除条件。由于同一个整数可能从不同的递归路径到达，程序还会用集合去重。Python 实现本身只是一个很薄的包装层：它调用编译后的搜索程序，再把最后的数值结果提取出来。
设搜索上界为 \(N\)。构造到 \(\sqrt{N}\) 为止的素数表需要 \(O(\sqrt{N}\log\log\sqrt{N})\) 时间和 \(O(\sqrt{N})\) 空间。之后的总运行时间并没有简单的闭式，因为递归过程高度依赖数据：每个分支要么因为同余条件彼此冲突而很早结束，要么形成一条在最终试除与验证前大约有 \(U/M\) 个候选的等差数列。
实现只会在这个数量已经足够小时才真正枚举，所以实际速度主要来自模约束带来的剪枝，而不是来自大规模的试除。对于一个被枚举的候选，剩余因子只需要用当前阈值以下的素数做有界试除，随后完整的 \(m\) 再针对其所有不同素因子做最终验证。内存主要消耗在素数表、已接受结果的集合以及递归栈上。由于真正合法的整数非常稀疏，这一策略在目标规模下是可行且高效的。
Определим \(S(N)\) как сумму всех целых чисел \(m\le N\), для которых \(m\) свободно от квадратов, а каждый простой делитель \(p\mid m\) удовлетворяет условию
$$p-1\mid m+3.$$
Целевое значение равно \(N=10^{12}\), поэтому проверить все числа до \(N\) напрямую невозможно. Полезные контрольные значения таковы:
$$S(100)=32,\qquad S(10^6)=22868117.$$
Поэтому реализации переписывают условия на простые делители в виде модульных ограничений и продолжают поиск только по тем ветвям, которые остаются арифметически возможными.
Поиск организован вокруг разложения \(m\) на простые множители. Вместо полного перебора выбираются некоторые большие простые множители, из них выводится конгруэнция для недостающей части, а оставшийся множитель перечисляется напрямую только тогда, когда получающаяся арифметическая прогрессия уже достаточно разрежена.
Из определения сразу следует, что
$$m\ \text{должно быть бесквадратным}.$$
Кроме того, важны еще два наблюдения.
Если \(m=q\) — простое число, то единственное нетривиальное условие имеет вид
$$q-1\mid q+3,$$
то есть \(q-1\mid 4\). Следовательно, простые решения — это только
$$q\in\{2,3,5\}.$$
Число \(1\) тоже подходит тривиально, потому что у него нет простых делителей.
Далее, составное решение не может быть четным. Если \(2\mid m\) и одновременно некоторый нечетный простой \(p\mid m\), то \(m+3\) нечетно, а \(p-1\) — четное число больше \(1\). Значит, \(p-1\) не может делить \(m+3\). Итак, любое составное решение представляет собой нечетное бесквадратное произведение различных нечетных простых.
Выберем убывающий набор простых множителей
$$\mathcal{L}=\{\ell_1\gt \ell_2\gt \cdots \gt \ell_k\ge 7\}$$
которые будем отслеживать явно, и запишем
$$Q=\prod_{\ell\in\mathcal{L}}\ell,\qquad m=Q\,u.$$
Тогда оставшийся множитель \(u\) обязан быть нечетным, бесквадратным, а все его простые делители должны быть строго меньше наименьшего выбранного простого \(\ell_k\).
Для каждого \(\ell\in\mathcal{L}\) исходное условие дает
$$\ell-1\mid Q\,u+3.$$
Поскольку \(\ell\equiv 1\pmod{\ell-1}\), множитель \(\ell\) исчезает по модулю \(\ell-1\):
$$Q\equiv \frac{Q}{\ell}\pmod{\ell-1}.$$
Поэтому каждый выбранный простой задает линейную конгруэнцию для неизвестного остаточного множителя:
$$u\cdot \frac{Q}{\ell}\equiv -3\pmod{\ell-1}.$$
Как только большие простые множители зафиксированы, оставшаяся часть задачи превращается в задачу о конгруэнциях по одной переменной.
Конгруэнция вида
$$a\,u\equiv -3\pmod n$$
разрешима только в случае
$$\gcd(a,n)\mid 3.$$
Если эта делимость не выполняется, всю ветвь поиска можно немедленно отбросить.
Пусть
$$d=\gcd(a,n).$$
Тогда, разделив конгруэнцию на \(d\), получаем
$$\frac{a}{d}\,u\equiv -\frac{3}{d}\pmod{\frac{n}{d}}.$$
Теперь коэффициент взаимно прост с модулем \(n/d\), поэтому он обратим, и тем самым определяется единственный класс вычетов для \(u\) по модулю \(n/d\).
Проделав такую редукцию для всех выбранных простых, мы получаем несколько классов вычетов. Реализации объединяют их с помощью обобщенной китайской теоремы об остатках. В результате либо система оказывается несовместной и ветвь завершается, либо все условия сводятся к одной прогрессии
$$u\equiv r\pmod M.$$
После объединения конгруэнций все кандидаты имеют вид
$$u=r+tM,\qquad t\ge 0.$$
Они обязаны удовлетворять очевидному ограничению размера
$$u\le \left\lfloor\frac{N}{Q}\right\rfloor.$$
Есть и более сильная структурная оценка: поскольку \(u\) бесквадратно и может содержать каждый нечетный простой меньше \(\ell_k\) не более одного раза, имеем
$$u\le \prod_{\substack{q\lt \ell_k\\ q\ \text{нечетный простой}}} q.$$
Значит, реальная верхняя граница поиска равна
$$u\le U=\min\left(\left\lfloor\frac{N}{Q}\right\rfloor,\ \prod_{\substack{q\lt \ell_k\\ q\ \text{нечетный простой}}} q\right).$$
Если в этой арифметической прогрессии до \(U\) остается лишь умеренное число членов, реализации перечисляют их напрямую. Каждый такой кандидат проверяется на нечетность и бесквадратность, факторизуется только простыми меньше \(\ell_k\), соединяется с выбранными большими простыми и затем окончательно тестируется по исходному условию для всех простых делителей полного числа \(m\).
Если же прогрессия все еще слишком плотная, прямое перечисление откладывается. Вместо этого выбирается еще один большой простой множитель, добавляется в \(\mathcal{L}\), и процедура построения конгруэнций повторяется. Такая рекурсия branch-and-bound переносит основную работу из грубого перебора в модульное отсечение.
Тривиально допустимые значения таковы:
$$1,\ 2,\ 3,\ 5.$$
Рассмотрим ветвь, в которой единственным выбранным большим простым является \(7\). Тогда \(Q=7\), а конгруэнция, идущая от \(7-1=6\), имеет вид
$$u\cdot 1\equiv -3\equiv 3\pmod 6,$$
то есть
$$u\equiv 3\pmod 6.$$
Дополнительно
$$u\le \left\lfloor\frac{100}{7}\right\rfloor=14.$$
Так как оставшиеся простые множители должны быть меньше \(7\), в этой прогрессии остаются только кандидаты
$$u=3,\ 9.$$
Число \(9\) отбрасывается, потому что не является бесквадратным. Значение \(3\) дает
$$m=7\cdot 3=21,$$
и действительно
$$21+3=24$$
делится и на \(2\), и на \(6\), что соответствует простым делителям \(3\) и \(7\).
Для следующего возможного максимального простого, \(11\), получаем конгруэнцию \(u\equiv 7\pmod{10}\). Ниже \(100/11\) остается только \(u=7\), то есть \(m=77\). Это число проходит условие, навязанное простым \(11\), но проваливает полную проверку для меньшего простого \(7\), поскольку \(77+3=80\) не делится на \(6\). Никакая более крупная ветвь не дает нового составного решения ниже \(100\).
Следовательно, полный список до \(100\) равен
$$1,\ 2,\ 3,\ 5,\ 21,$$
а значит
$$S(100)=1+2+3+5+21=32.$$
Реализации на C++, Python и Java следуют одной и той же арифметической схеме. Сначала они строят список простых до примерно \(\sqrt{N}\), добавляют тривиальные значения \(1,2,3,5\), а затем рекурсивно обходят убывающие наборы выбранных нечетных простых \(\ge 7\).
Для каждой рекурсивной ветви реализация преобразует ограничения от выбранных простых в линейные конгруэнции, применяет проверку разрешимости через НОД и объединяет выжившие классы вычетов обобщенной китайской теоремой об остатках. Если объединенный модуль уже больше оставшегося числового диапазона поиска, то существенной может быть только наименьшая неотрицательная точка, поэтому диапазон фактически зажимается уже на этом этапе.
Далее оценивается, сколько членов прогрессии еще остается ниже текущей границы. Ветвь перечисляется напрямую только тогда, когда эта оценка имеет порядок \(10^4\) членов или меньше; иначе добавляется еще один большой простой и рекурсия продолжается, что обычно увеличивает модуль и уменьшает плотность кандидатов.
Каждый перечисленный остаточный множитель факторизуется с ограничением, заданным ветвью, проверяется на нечетность и бесквадратность, соединяется с выбранными простыми и затем снова валидируется по исходному условию для каждого простого делителя. Множество принятых значений удаляет дубликаты, которые могут появляться из пересекающихся ветвей. Python-реализация здесь является лишь тонкой оболочкой над скомпилированным поиском и извлекает итоговый числовой ответ.
Пусть \(N\) — верхняя граница поиска. Построение таблицы простых до \(\sqrt{N}\) требует \(O(\sqrt{N}\log\log\sqrt{N})\) времени и \(O(\sqrt{N})\) памяти. После этого для полной трудоемкости уже нет простой закрытой формулы, поскольку рекурсия сильно зависит от данных: каждая ветвь либо быстро обрывается из-за несовместимых конгруэнций, либо порождает арифметическую прогрессию размера примерно \(U/M\) до окончательной факторизации и проверки.
Ветка перечисляется напрямую лишь тогда, когда это число уже мало, поэтому основная практическая эффективность достигается за счет модульного отсечения, а не за счет грубой пробной делимости. Для одного перечисленного кандидата остаточный множитель проверяется ограниченной пробной делимостью простыми ниже текущего порога, а затем полное значение валидируется по всем своим различным простым делителям. Память в основном занимают список простых, множество принятых значений и стек рекурсии. На практике допустимых чисел достаточно мало, чтобы эта стратегия хорошо работала на целевом пределе.
نعرّف \(S(N)\) على أنه مجموع جميع الأعداد الصحيحة \(m\le N\) التي تكون خالية من المربعات، ويحقق كل عامل أولي \(p\mid m\) فيها الشرط
$$p-1\mid m+3.$$
القيمة المستهدفة هي \(N=10^{12}\)، ولذلك لا يمكن فحص كل عدد حتى هذا الحد مباشرة. ومن القيم المرجعية المفيدة
$$S(100)=32,\qquad S(10^6)=22868117.$$
لهذا السبب تحوّل التطبيقات الشروط المفروضة من العوامل الأولية إلى قيود معيارية، ثم تتابع البحث فقط في الفروع التي تبقى ممكنة حسابيًا.
ينظم البحث بالاعتماد على تحليل \(m\) إلى عوامله الأولية. والفكرة ليست تعداد جميع الأعداد، بل اختيار بعض العوامل الأولية الكبيرة صراحةً، ثم اشتقاق توافقات على العامل المتبقي، وعدم تعداد ذلك الجزء المتبقي إلا عندما تصبح المتتالية الحسابية الناتجة متناثرة بما يكفي.
من تعريف المسألة نحصل مباشرة على أن
$$m\ \text{is squarefree}.$$
وهناك بعد ذلك نتيجتان مهمتان جدًا.
إذا كان \(m=q\) عددًا أوليًا، فإن الشرط غير البديهي الوحيد هو
$$q-1\mid q+3.$$
وهذا يعني أن \(q-1\mid 4\)، ومن ثم فإن الحلول الأولية الوحيدة هي
$$q\in\{2,3,5\}.$$
كما أن العدد \(1\) صحيح بصورة بديهية لأنه لا يملك أي عوامل أولية أصلًا.
والنتيجة الثانية أن أي حل مركب لا يمكن أن يكون زوجيًا. فإذا كان \(2\mid m\) وكان هناك أيضًا أولي فردي \(p\mid m\)، فإن \(m+3\) يكون فرديًا، في حين أن \(p-1\) عدد زوجي أكبر من \(1\). لذلك يستحيل أن يقسم \(p-1\) العدد \(m+3\). وبالتالي فإن كل حل مركب هو حاصل ضرب فردي خالٍ من المربعات لعوامل أولية فردية مختلفة.
نختار مجموعة متناقصة من العوامل الأولية
$$\mathcal{L}=\{\ell_1\gt \ell_2\gt \cdots \gt \ell_k\ge 7\}$$
نريد معالجتها صراحةً، ثم نكتب
$$Q=\prod_{\ell\in\mathcal{L}}\ell,\qquad m=Q\,u.$$
عندئذٍ يجب أن يكون العامل المتبقي \(u\) فرديًا، وخاليًا من المربعات، وجميع عوامله الأولية أصغر بدقة من أصغر أولي مختار وهو \(\ell_k\).
ولكل \(\ell\in\mathcal{L}\) يعطي الشرط الأصلي
$$\ell-1\mid Q\,u+3.$$
وبما أن \(\ell\equiv 1\pmod{\ell-1}\)، فإن العامل \(\ell\) يختفي عند الاختزال بترديد \(\ell-1\):
$$Q\equiv \frac{Q}{\ell}\pmod{\ell-1}.$$
لذلك ينتج من كل أولي مختار توافق خطي في العامل المتبقي:
$$u\cdot \frac{Q}{\ell}\equiv -3\pmod{\ell-1}.$$
وبمجرد تثبيت العوامل الأولية الكبيرة، يتحول ما تبقى من المسألة إلى مسألة توافقات في متغير واحد.
التوافق من الشكل
$$a\,u\equiv -3\pmod n$$
لا يملك حلًا إلا إذا تحقق الشرط
$$\gcd(a,n)\mid 3.$$
فإن فشلت هذه القابلية للقسمة، أمكن حذف الفرع كاملًا فورًا لأنه غير ممكن أساسًا.
إذا وضعنا
$$d=\gcd(a,n),$$
فإن القسمة على \(d\) تعطينا
$$\frac{a}{d}\,u\equiv -\frac{3}{d}\pmod{\frac{n}{d}}.$$
وهنا يصبح المعامل قابلًا للعكس بترديد \(n/d\)، ومن ثم يحدد هذا التوافق فئة بواقي وحيدة لـ \(u\) بترديد \(n/d\).
وعند تكرار ذلك لكل أولي مختار نحصل على عدة فئات بواقي. ثم تجمعها التطبيقات باستخدام مبرهنة البواقي الصينية المعممة. والنتيجة إما أن تكون تناقضًا فينتهي الفرع، أو أن تختزل جميع الشروط إلى متتالية واحدة:
$$u\equiv r\pmod M.$$
بعد جمع التوافقات، يصبح كل مرشح على الصورة
$$u=r+tM,\qquad t\ge 0.$$
ولا بد أن يحقق أيضًا القيد الحجمي الواضح
$$u\le \left\lfloor\frac{N}{Q}\right\rfloor.$$
لكن يوجد أيضًا حد بنيوي أقوى: بما أن \(u\) خالٍ من المربعات، ولا يستطيع استخدام أي أولي فردي أصغر من \(\ell_k\) أكثر من مرة واحدة، فإن
$$u\le \prod_{\substack{q\lt \ell_k\\ q\ \text{odd prime}}} q.$$
ومن ثم تصبح حدود البحث الحقيقية
$$u\le U=\min\left(\left\lfloor\frac{N}{Q}\right\rfloor,\ \prod_{\substack{q\lt \ell_k\\ q\ \text{odd prime}}} q\right).$$
إذا كانت هذه المتتالية الحسابية لا تعطي إلا عددًا معتدلًا من الحدود حتى \(U\)، فإن التطبيقات تعدّها مباشرة. وكل قيمة مرشحة لـ \(u\) تُفحص للتأكد من كونها فردية وخالية من المربعات، ثم تُحلل فقط بواسطة الأعداد الأولية الأصغر من \(\ell_k\)، ثم تُدمج مع العوامل الكبيرة المختارة، وأخيرًا يُعاد التحقق من الشرط الأصلي على جميع العوامل الأولية للعدد الكامل \(m\).
أما إذا بقيت المتتالية كثيفة جدًا، فلا يبدأ التعداد بعد. بدلًا من ذلك يُضاف عامل أولي كبير آخر إلى \(\mathcal{L}\)، ثم يعاد بناء التوافقات من جديد. هذا الأسلوب من نوع branch-and-bound ينقل الجهد من المسح الخام إلى التضييق المعياري.
القيم الصحيحة البديهية هي
$$1,\ 2,\ 3,\ 5.$$
لننظر الآن إلى الفرع الذي يكون فيه الأولي الكبير المختار الوحيد هو \(7\). عندئذٍ \(Q=7\)، والتوافق الناتج من \(7-1=6\) هو
$$u\cdot 1\equiv -3\equiv 3\pmod 6,$$
أي
$$u\equiv 3\pmod 6.$$
ولدينا أيضًا
$$u\le \left\lfloor\frac{100}{7}\right\rfloor=14.$$
وبما أن العوامل الأولية المتبقية يجب أن تكون أصغر من \(7\)، فإن المرشحين الوحيدين في هذه المتتالية هما
$$u=3,\ 9.$$
تُرفض القيمة \(9\) لأنها ليست خالية من المربعات. أما \(u=3\) فتعطي
$$m=7\cdot 3=21,$$
وبالفعل فإن
$$21+3=24$$
يقبل القسمة على \(2\) وعلى \(6\)، الموافقين للعاملين الأوليين \(3\) و\(7\).
وبالنسبة إلى الأولي الأكبر التالي الممكن وهو \(11\)، يصبح التوافق \(u\equiv 7\pmod{10}\). وتحت الحد \(100/11\) يبقى المرشح الوحيد \(u=7\)، وهو يعطي \(m=77\). هذا العدد يحقق التوافق المفروض من \(11\)، لكنه يفشل عند التحقق الكامل للعامل الأصغر \(7\)، لأن \(77+3=80\) غير قابل للقسمة على \(6\). ولا ينتج أي فرع أكبر من ذلك حلًا مركبًا جديدًا أصغر من \(100\).
إذن القائمة الكاملة حتى \(100\) هي
$$1,\ 2,\ 3,\ 5,\ 21,$$
ومن ثم
$$S(100)=1+2+3+5+21=32.$$
تتبع تطبيقات C++ وPython وJava نفس هذا التفكيك العددي. فهي تولد الأعداد الأولية حتى نحو \(\sqrt{N}\)، ثم تضيف القيم البديهية \(1,2,3,5\)، وبعد ذلك تنتقل عوديًا بين مجموعات متناقصة من الأعداد الأولية الفردية المختارة التي لا تقل عن \(7\).
في كل فرع عودي، يحول التنفيذ الشروط المفروضة من العوامل الأولية المختارة إلى توافقات خطية، ثم يطبق اختبار القابلية للحل المعتمد على القاسم المشترك الأكبر، ثم يجمع فئات البواقي الباقية بمبرهنة البواقي الصينية المعممة. وإذا صار المودول الموحّد أكبر من المجال العددي المتبقي للبحث، فإن أصغر حل غير سالب فقط هو الذي قد يبقى ذا معنى، ولذلك يُحكم المجال فعليًا عند هذه النقطة.
بعد ذلك يقدّر التنفيذ عدد حدود المتتالية الواقعة تحت السقف الحالي. ولا يعدد الفرع مباشرة إلا إذا كان هذا العدد في حدود \(10^4\) قيمة أو أقل؛ وإلا أضيف أولي كبير آخر واستمرت العودية، وهذا يؤدي عادةً إلى تكبير المودول وتقليل كثافة المرشحين.
كل عامل متبقٍ يُعدَّد فعليًا يُحلل ضمن الحد الخاص بذلك الفرع، ويُفحص للتأكد من كونه فرديًا وخاليًا من المربعات، ثم يُدمج مع العوامل المختارة، وبعد ذلك يعاد التحقق من الشرط الأصلي على كل عامل أولي. وتستعمل مجموعة من القيم المقبولة لإزالة التكرارات التي قد تظهر من فروع متداخلة. أما تنفيذ Python فهو مجرد غلاف خفيف حول البحث المترجم، ويستخرج في النهاية القيمة العددية النهائية.
إذا كانت \(N\) هي حد البحث، فإن بناء جدول الأعداد الأولية حتى \(\sqrt{N}\) يكلف \(O(\sqrt{N}\log\log\sqrt{N})\) زمنًا و\(O(\sqrt{N})\) ذاكرة. بعد ذلك لا توجد صيغة مغلقة بسيطة للزمن الكلي، لأن العودية تعتمد بشدة على البيانات: فكل فرع إما أن ينتهي مبكرًا بسبب توافقات غير متسقة، أو ينتج متتالية حسابية حجمها التقريبي \(U/M\) قبل مرحلة التحليل والتحقق النهائيين.
ولا يبدأ التنفيذ التعداد المباشر إلا عندما تصبح هذه الكمية صغيرة، ولذلك تأتي معظم السرعة العملية من التضييق المعياري لا من القسمة التجريبية الخام. أما المرشح الذي يُعدّد فعلًا فيُفحص عامله المتبقي بواسطة قسمة تجريبية محدودة باستخدام الأعداد الأولية الأصغر من العتبة الحالية، ثم تُراجع القيمة الكاملة بالنسبة إلى جميع عواملها الأولية المختلفة. ويهيمن على الذاكرة جدول الأعداد الأولية، ومجموعة القيم المقبولة، ومكدس العودية. وبما أن الأعداد الصحيحة المقبولة متباعدة جدًا في الواقع، فإن هذه الإستراتيجية فعالة عند الحد المطلوب.