We want the sum of all primes \(p \lt L\) such that deleting the last decimal digit of \(p\) leaves a strong right-truncatable Harshad number. In the local solution files the default bound is \(L = 10^{14}\).
Let \(s(n)\) denote the sum of the decimal digits of \(n\). A positive integer \(n\) is a Harshad number if
$$s(n)\mid n.$$
It is strong if
$$\frac{n}{s(n)}$$
is prime. It is right-truncatable if every non-empty decimal prefix is Harshad. Writing \(n=\overline{d_1d_2\cdots d_k}\), each prefix \(\overline{d_1d_2\cdots d_i}\) for \(1 \le i \le k\) must satisfy the Harshad divisibility condition.
Every candidate answer prime has a unique decomposition
$$p = 10h + d,\qquad d = p \bmod 10,\qquad h=\left\lfloor\frac{p}{10}\right\rfloor.$$
The problem therefore reduces to generating exactly those prefixes \(h\) that are strong and right-truncatable Harshad numbers, then checking whether one more digit turns them into a prime below \(L\).
A brute-force approach would iterate over primes \(p \lt L\), remove the last digit, and test the whole prefix chain. The repository code does the opposite: it constructs only valid Harshad prefixes and never explores arbitrary integers.
All one-digit numbers \(1,\dots,9\) are Harshad because for a single decimal digit we have \(s(n)=n\), hence \(n/s(n)=1\). These values are the roots of the search tree.
Suppose the current node is a Harshad number \(n\) with digit sum \(s=s(n)\). Appending a digit \(d\in\{0,1,\dots,9\}\) gives
$$n' = 10n + d,\qquad s(n') = s + d.$$
The child is useful only if it is Harshad, namely
$$10n + d \equiv 0 \pmod{s+d}.$$
This test is exactly what the DFS applies before recursing. Because every child is created from an already valid Harshad parent, right-truncatability is automatic by induction: each visited node has a Harshad parent chain all the way back to a one-digit root.
Whenever a visited prefix \(n \ge 10\) is Harshad, the code computes
$$q=\frac{n}{s(n)}.$$
If \(q\) is prime, then \(n\) is strong. This is the decisive filter, because a final answer prime must come from a strong prefix. One-digit prefixes are excluded from this stage in the code since they would only produce \(q=1\), which is not prime.
For any prime \(p \gt 10\), the last digit cannot be even and cannot be \(5\). Therefore every strong prefix \(h\) produces at most four relevant prime candidates:
$$p = 10h + d,\qquad d \in \{1,3,7,9\}.$$
The implementations test each such \(p\) for the two remaining conditions: \(p \lt L\) and \(p\) is prime.
If both hold, \(p\) is added to the total. This characterization is complete and duplicate-free, because decimal truncation is unique: every valid prime determines exactly one prefix \(h=\lfloor p/10 \rfloor\).
If \(p=10h+d \lt L\), then necessarily
$$h \le \left\lfloor\frac{L-1}{10}\right\rfloor.$$
The C++ solution stores this value in harshad_limit. Any Harshad number larger than this can never be the prefix of a valid answer, so exploring beyond it is pointless.
The recursive stop test in the code is slightly sharper. If
$$n \gt \left\lfloor\frac{\left\lfloor(L-1)/10\right\rfloor}{10}\right\rfloor,$$
then every child \(10n+d\) already exceeds harshad_limit. The current node may still produce final primes \(10n+d\), but it cannot produce deeper Harshad prefixes that will later matter.
Take \(n=18\). Its digit sum is \(s(18)=9\), and \(18/9=2\), so \(18\) is a strong Harshad number. Since \(1\) and \(18\) are both Harshad, it is also right-truncatable.
The only possible prime endings are
$$181,\ 183,\ 187,\ 189.$$
Among these, \(181\) is prime, \(183\) and \(189\) are divisible by \(3\), and \(187=11\cdot 17\). Hence \(181\) is one of the required primes.
The local C++ program also validates the sample checkpoint
$$\sum_{p \lt 10^4} p = 90619,$$
and then cross-checks the optimized solver against a brute-force routine at \(L=10^6\). Those checks are consistent with the derivation above.
The three local implementations use the same core state: the current prefix \(n\) and its digit sum \(s(n)\). Carrying the digit sum forward via \(s(n')=s(n)+d\) makes each tree transition constant time instead of recomputing all decimal digits from scratch.
The C++ file exposes solve(limit), optional argument parsing with --limit=..., and a --skip-checkpoints flag. Its DFS function dfs_harshad returns the sum contributed by one subtree. For primality it first removes small prime divisors up to \(37\), then runs deterministic Miller-Rabin with bases
$$\{2,3,5,7,11,13,17\}.$$
To avoid overflow in modular multiplication, C++ uses __uint128_t.
The Python file implements the same recurrence and the same Miller-Rabin base set, but accumulates the answer in a nonlocal variable inside dfs. The Java file mirrors the same DFS structure in dfsHarshad and delegates modular exponentiation to BigInteger.modPow. Mathematically all three versions are identical.
Let \(H(L)\) be the number of right-truncatable Harshad prefixes actually visited, and let \(S(L)\) be the number of those prefixes that are strong. The DFS work per visited node is \(O(1)\): one digit-sum update and one divisibility test for each appended digit.
Each strong prefix triggers at most four primality tests, so a precise description is
$$O\bigl(H(L) + 4S(L)\,T_{\mathrm{prime}}\bigr),$$
where \(T_{\mathrm{prime}}\) is the cost of one Miller-Rabin test in the 64-bit range used here. Since \(S(L)\le H(L)\), this is often summarized as
$$O\bigl(H(L)\,T_{\mathrm{prime}}\bigr).$$
The recursion depth is the number of decimal digits of the largest explored prefix, so the auxiliary stack space is \(O(\log_{10} L)\). This is far smaller than scanning all integers or all primes below \(L\).
Gesucht ist die Summe aller Primzahlen \(p \lt L\), bei denen nach dem Entfernen der letzten Dezimalziffer eine starke rechts-trunkierbare Harshad-Zahl übrig bleibt. In den lokalen Lösungsdateien ist standardmäßig \(L = 10^{14}\).
Sei \(s(n)\) die Summe der Dezimalziffern von \(n\). Eine positive ganze Zahl \(n\) ist eine Harshad-Zahl, wenn
$$s(n)\mid n.$$
Sie heißt stark, wenn
$$\frac{n}{s(n)}$$
eine Primzahl ist. Sie heißt rechts-trunkierbar, wenn jedes nichtleere Dezimalpräfix ebenfalls Harshad ist. Schreibt man \(n=\overline{d_1d_2\cdots d_k}\), dann muss jedes Präfix \(\overline{d_1d_2\cdots d_i}\) für \(1 \le i \le k\) die Harshad-Bedingung erfüllen.
Jede gesuchte Primzahl besitzt die eindeutige Darstellung
$$p = 10h + d,\qquad d = p \bmod 10,\qquad h=\left\lfloor\frac{p}{10}\right\rfloor.$$
Das Problem reduziert sich also darauf, genau die Präfixe \(h\) zu erzeugen, die stark und rechts-trunkierbar sind, und dann zu testen, ob eine weitere Ziffer daraus eine Primzahl unter \(L\) macht.
Eine brute-forceartige Lösung würde alle Primzahlen \(p \lt L\) prüfen, die letzte Ziffer entfernen und anschließend die gesamte Präfixkette testen. Der Code im Repository macht genau das Gegenteil: Er konstruiert nur gültige Harshad-Präfixe und besucht nie beliebige ganze Zahlen.
Alle einstelligen Zahlen \(1,\dots,9\) sind Harshad, weil für eine einzelne Ziffer \(s(n)=n\) gilt. Diese Werte sind die Wurzeln des Suchbaums.
Sei \(n\) ein aktueller Harshad-Knoten mit Ziffernsumme \(s=s(n)\). Hängt man eine Ziffer \(d\in\{0,1,\dots,9\}\) an, so entsteht
$$n' = 10n + d,\qquad s(n') = s + d.$$
Der Nachfolger ist nur dann interessant, wenn er wieder Harshad ist, also wenn
$$10n + d \equiv 0 \pmod{s+d}.$$
Genau diesen Test führt die Tiefensuche vor dem rekursiven Abstieg aus. Weil jeder Kindknoten nur aus einem bereits gültigen Harshad-Elternknoten erzeugt wird, ist die Rechts-Trunkierbarkeit per Induktion automatisch erfüllt.
Sobald ein besuchtes Präfix \(n \ge 10\) Harshad ist, berechnet der Code
$$q=\frac{n}{s(n)}.$$
Ist \(q\) prim, dann ist \(n\) stark. Das ist der entscheidende Filter, denn jede gesuchte Endprimzahl muss aus einem starken Präfix entstehen. Einstellige Präfixe werden hierbei bewusst nicht berücksichtigt, weil dort nur \(q=1\) herauskäme und \(1\) nicht prim ist.
Für jede Primzahl \(p \gt 10\) darf die letzte Ziffer weder gerade noch \(5\) sein. Deshalb erzeugt jedes starke Präfix \(h\) höchstens vier relevante Kandidaten:
$$p = 10h + d,\qquad d \in \{1,3,7,9\}.$$
Die Implementierungen prüfen dann nur noch die beiden Bedingungen: \(p \lt L\) und \(p\) ist prim.
Sind beide erfüllt, wird \(p\) zur Summe addiert. Diese Beschreibung ist vollständig und zählt nichts doppelt, weil die Dezimaltrunkierung eindeutig ist: Jede gültige Primzahl bestimmt genau ein Präfix \(h=\lfloor p/10 \rfloor\).
Aus \(p=10h+d \lt L\) folgt notwendig
$$h \le \left\lfloor\frac{L-1}{10}\right\rfloor.$$
Die C++-Lösung speichert diesen Wert in harshad_limit. Jede Harshad-Zahl oberhalb dieser Grenze kann kein Präfix einer zulässigen Antwort mehr sein.
Der Abbruchtest der Rekursion ist sogar etwas schärfer. Gilt
$$n \gt \left\lfloor\frac{\left\lfloor(L-1)/10\right\rfloor}{10}\right\rfloor,$$
dann liegt bereits jedes Kind \(10n+d\) über harshad_limit. Der aktuelle Knoten kann also noch Endprimzahlen erzeugen, aber keine tieferen Harshad-Präfixe mehr, die später relevant würden.
Betrachte \(n=18\). Es gilt \(s(18)=9\) und \(18/9=2\), also ist \(18\) eine starke Harshad-Zahl. Da sowohl \(1\) als auch \(18\) Harshad sind, ist \(18\) außerdem rechts-trunkierbar.
Als mögliche Primendungen kommen nur
$$181,\ 183,\ 187,\ 189$$
in Frage. Davon ist \(181\) prim, \(183\) und \(189\) sind durch \(3\) teilbar, und \(187=11\cdot 17\). Also ist \(181\) eine der gesuchten Primzahlen.
Das lokale C++-Programm überprüft zusätzlich den Beispielwert
$$\sum_{p \lt 10^4} p = 90619,$$
und vergleicht den optimierten Algorithmus anschließend für \(L=10^6\) mit einer brute-forceartigen Referenz. Diese Tests bestätigen die obige Herleitung.
Alle drei lokalen Implementierungen tragen denselben Zustandsvektor durch die DFS: das aktuelle Präfix \(n\) und seine Ziffernsumme \(s(n)\). Durch die Fortführung per \(s(n')=s(n)+d\) kostet ein Baumschritt nur konstante Zeit; ein erneutes Durchlaufen aller Ziffern wäre unnötig teuer.
Die C++-Datei bietet solve(limit), Kommandozeilenargumente der Form --limit=... und die Option --skip-checkpoints. Ihre Funktion dfs_harshad liefert die Summe eines Teilbaums zurück. Für Primzahltests entfernt C++ zunächst kleine Teiler bis \(37\) und benutzt danach deterministisches Miller-Rabin mit den Basen
$$\{2,3,5,7,11,13,17\}.$$
Um Überläufe bei modularer Multiplikation zu vermeiden, wird __uint128_t eingesetzt.
Die Python-Datei verwendet dieselbe Rekurrenz und dieselbe Miller-Rabin-Basenmenge, sammelt das Ergebnis aber in einer nonlocal-Variablen innerhalb von dfs. Die Java-Datei spiegelt dieselbe Baumstruktur in dfsHarshad und delegiert die modulare Potenzierung an BigInteger.modPow. Mathematisch implementieren alle drei Dateien denselben Algorithmus.
Sei \(H(L)\) die Anzahl der tatsächlich besuchten rechts-trunkierbaren Harshad-Präfixe und \(S(L)\) die Anzahl der starken Präfixe darunter. Pro besuchtm Knoten ist die Arbeit \(O(1)\): Ziffernsumme fortschreiben und Teilbarkeit testen.
Jedes starke Präfix löst höchstens vier Primzahltests aus. Daher ist eine präzise Laufzeitbeschreibung
$$O\bigl(H(L) + 4S(L)\,T_{\mathrm{prime}}\bigr),$$
wobei \(T_{\mathrm{prime}}\) die Kosten eines Miller-Rabin-Tests im hier relevanten 64-Bit-Bereich sind. Da \(S(L)\le H(L)\), fasst man dies oft zu
$$O\bigl(H(L)\,T_{\mathrm{prime}}\bigr)$$
zusammen. Die Rekursionstiefe entspricht der Dezimalstellenzahl des größten untersuchten Präfixes, also beträgt der zusätzliche Stackbedarf \(O(\log_{10} L)\). Das ist deutlich kleiner als ein vollständiger Scan aller Zahlen oder Primzahlen unter \(L\).
Amaç, \(p \lt L\) olan tüm asal sayılar arasında, son basamağı silindiğinde geriye güçlü ve sağdan kırpılabilir bir Harshad sayısı kalanların toplamını bulmaktır. Yerel çözüm dosyalarında varsayılan sınır \(L = 10^{14}\) olarak alınır.
\(s(n)\), \(n\) sayısının ondalık rakamları toplamı olsun. Pozitif bir tam sayı \(n\),
$$s(n)\mid n$$
ise Harshad sayısıdır. Eğer
$$\frac{n}{s(n)}$$
asal ise güçlü Harshad denir. Bir sayı, boş olmayan her ondalık öneki de Harshad ise sağdan kırpılabilir olarak adlandırılır. \(n=\overline{d_1d_2\cdots d_k}\) yazımında, \(1 \le i \le k\) için her \(\overline{d_1d_2\cdots d_i}\) öneki Harshad koşulunu sağlamalıdır.
Her uygun asal sayı için tekil ayrışım
$$p = 10h + d,\qquad d = p \bmod 10,\qquad h=\left\lfloor\frac{p}{10}\right\rfloor$$
vardır. Dolayısıyla problem, yalnızca güçlü ve sağdan kırpılabilir Harshad öneklerini üretip bir ek basamağın bunları \(L\)'den küçük bir asala dönüştürüp dönüştürmediğini sınamaya indirgenir.
Naif çözüm, \(L\)'den küçük tüm asalları tarar, son basamağı atar ve ardından tüm önek zincirini kontrol ederdi. Depodaki kod bunun tersini yapar: sadece geçerli Harshad öneklerini kurar ve keyfi tam sayıları hiç dolaşmaz.
Tek basamaklı \(1,\dots,9\) sayıları Harshad'dır; çünkü tek basamaklı bir sayı için \(s(n)=n\) olur. Bu yüzden arama ağacının kökleri bunlardır.
Mevcut düğüm \(n\) ve rakam toplamı \(s=s(n)\) olsun. Sonuna \(d\in\{0,1,\dots,9\}\) rakamını ekleyince
$$n' = 10n + d,\qquad s(n') = s + d$$
elde edilir. Çocuk düğüm ancak yeniden Harshad ise anlamlıdır; yani
$$10n + d \equiv 0 \pmod{s+d}.$$
DFS tam olarak bu testi geçerse aşağı iner. Her çocuk zaten Harshad bir ebeveynden üretildiği için sağdan kırpılabilirlik tümevarımla otomatik olarak sağlanır.
Ziyaret edilen bir Harshad öneki \(n \ge 10\) olduğunda kod
$$q=\frac{n}{s(n)}$$
değerini hesaplar. Eğer \(q\) asalsa, \(n\) güçlüdür. Bu ana filtredir; çünkü aranan her son asal, güçlü bir önekten gelmek zorundadır. Tek basamaklı önekler burada dışlanır; çünkü onlar için \(q=1\) olur ve \(1\) asal değildir.
\(p \gt 10\) olan bir asalın son basamağı ne çift olabilir ne de \(5\) olabilir. Bu yüzden her güçlü önek \(h\) en fazla dört anlamlı aday üretir:
$$p = 10h + d,\qquad d \in \{1,3,7,9\}.$$
Uygulamalar daha sonra şu iki koşulu test eder: \(p \lt L\) ve \(p\) asaldır.
İkisi de doğruysa \(p\) toplam cevaba eklenir. Bu tanım eksiksizdir ve çift sayım üretmez; çünkü ondalık tabanda son basamağı atınca ortaya çıkan önek tektir.
\(p=10h+d \lt L\) ise zorunlu olarak
$$h \le \left\lfloor\frac{L-1}{10}\right\rfloor$$
olmalıdır. C++ çözümü bu değeri harshad_limit değişkeninde tutar. Bu sınırın üstündeki bir Harshad sayısı artık geçerli bir cevabın öneki olamaz.
Koddaki durma koşulu biraz daha sıkıdır. Eğer
$$n \gt \left\lfloor\frac{\left\lfloor(L-1)/10\right\rfloor}{10}\right\rfloor,$$
ise her çocuk \(10n+d\) zaten harshad_limit'i aşar. Mevcut düğüm son asal adaylarını hâlâ üretebilir, fakat daha derin Harshad önekleri artık işlevsizdir.
\(n=18\) alalım. \(s(18)=9\) ve \(18/9=2\) olduğundan \(18\) güçlü bir Harshad sayısıdır. Ayrıca \(1\) ve \(18\) Harshad olduğundan sağdan kırpılabilirlik koşulu da sağlanır.
Asal son basamakla oluşabilecek tek adaylar
$$181,\ 183,\ 187,\ 189$$
şeklindedir. Bunlardan \(181\) asaldır; \(183\) ve \(189\) sayıları \(3\)'e bölünür, \(187=11\cdot 17\) olduğundan asal değildir. Dolayısıyla \(181\) aranan sayılardan biridir.
Yerel C++ programı ayrıca örnek kontrolü
$$\sum_{p \lt 10^4} p = 90619$$
değerini doğrular ve sonra \(L=10^6\) için optimize çözümü kaba kuvvet yordamıyla karşılaştırır. Bu kontroller, türetilen yaklaşımın doğru uygulandığını gösterir.
Üç yerel uygulama da DFS boyunca aynı durumu taşır: mevcut önek \(n\) ve onun rakam toplamı \(s(n)\). \(s(n')=s(n)+d\) güncellemesi sayesinde her ağaç geçişi sabit maliyetlidir; aksi halde her seferinde tüm basamakları yeniden toplamak gerekirdi.
C++ dosyası solve(limit) fonksiyonunu, --limit=... biçiminde komut satırı argümanlarını ve --skip-checkpoints seçeneğini içerir. dfs_harshad bir alt ağacın ürettiği toplamı döndürür. Asallık denetiminde önce \(37\)'ye kadar küçük asal bölenler elenir, sonra sabit
$$\{2,3,5,7,11,13,17\}$$
tabanlarıyla deterministik Miller-Rabin uygulanır. Taşmayı önlemek için modüler çarpımda __uint128_t kullanılır.
Python dosyası aynı yinelemeyi ve aynı Miller-Rabin tabanlarını kullanır, ancak sonucu dfs içindeki nonlocal bir değişkende toplar. Java dosyası aynı DFS ağacını dfsHarshad içinde tekrarlar ve modüler üs alma işini BigInteger.modPow'a bırakır. Matematiksel olarak üçü de aynı algoritmadır.
\(H(L)\), gerçekten ziyaret edilen sağdan kırpılabilir Harshad öneklerinin sayısı; \(S(L)\) ise bunların içindeki güçlü öneklerin sayısı olsun. Her ziyaret edilen düğüm için iş yükü \(O(1)\)'dir: rakam toplamını güncellemek ve bölünebilirlik testini yapmak.
Her güçlü önek en fazla dört asallık testi tetikler. Bu nedenle daha ayrıntılı çalışma süresi
$$O\bigl(H(L) + 4S(L)\,T_{\mathrm{prime}}\bigr)$$
şeklindedir; burada \(T_{\mathrm{prime}}\), kullanılan 64 bitlik aralıkta bir Miller-Rabin testinin maliyetidir. \(S(L)\le H(L)\) olduğundan bu ifade çoğu zaman
$$O\bigl(H(L)\,T_{\mathrm{prime}}\bigr)$$
diye özetlenir. Özyineleme derinliği, incelenen en büyük önekin basamak sayısı kadar olduğundan ek yığın belleği \(O(\log_{10} L)\) olur. Bu, \(L\)'den küçük tüm sayıları ya da tüm asalları taramaktan çok daha küçüktür.
Buscamos la suma de todos los primos \(p \lt L\) tales que, al borrar su última cifra decimal, queda un número Harshad fuerte truncable por la derecha. En los archivos de solución locales el límite por defecto es \(L = 10^{14}\).
Sea \(s(n)\) la suma de las cifras decimales de \(n\). Un entero positivo \(n\) es Harshad si
$$s(n)\mid n.$$
Se llama fuerte cuando
$$\frac{n}{s(n)}$$
es primo. Se llama truncable por la derecha cuando todo prefijo decimal no vacío también es Harshad. Si \(n=\overline{d_1d_2\cdots d_k}\), cada prefijo \(\overline{d_1d_2\cdots d_i}\) con \(1 \le i \le k\) debe satisfacer la divisibilidad Harshad.
Cada primo válido admite la descomposición única
$$p = 10h + d,\qquad d = p \bmod 10,\qquad h=\left\lfloor\frac{p}{10}\right\rfloor.$$
Por tanto, el problema consiste en generar exactamente los prefijos \(h\) que son Harshad fuertes y truncables por la derecha, y después comprobar si una cifra adicional los convierte en un primo menor que \(L\).
Una solución ingenua recorrería los primos \(p \lt L\), eliminaría la última cifra y comprobaría toda la cadena de prefijos. El código del repositorio hace lo contrario: construye solo prefijos Harshad válidos y nunca explora enteros arbitrarios.
Todos los números de una cifra \(1,\dots,9\) son Harshad porque para una sola cifra se cumple \(s(n)=n\). Esos valores forman las raíces del árbol de búsqueda.
Supongamos que el nodo actual es un Harshad \(n\) con suma de cifras \(s=s(n)\). Si añadimos una cifra \(d\in\{0,1,\dots,9\}\), obtenemos
$$n' = 10n + d,\qquad s(n') = s + d.$$
El hijo solo es útil si vuelve a ser Harshad, es decir, si
$$10n + d \equiv 0 \pmod{s+d}.$$
Ese es exactamente el filtro que la DFS aplica antes de recursar. Como cada hijo nace de un padre que ya era Harshad, la propiedad de truncabilidad por la derecha queda garantizada por inducción.
Cuando un prefijo visitado \(n \ge 10\) es Harshad, el programa calcula
$$q=\frac{n}{s(n)}.$$
Si \(q\) es primo, entonces \(n\) es fuerte. Este es el filtro clave, porque cualquier primo válido debe provenir de un prefijo fuerte. Los prefijos de una sola cifra se excluyen en esta etapa, ya que producirían \(q=1\) y \(1\) no es primo.
Si \(p \gt 10\) es primo, su última cifra no puede ser par ni \(5\). Por ello, cada prefijo fuerte \(h\) genera como máximo cuatro candidatos relevantes:
$$p = 10h + d,\qquad d \in \{1,3,7,9\}.$$
Las implementaciones comprueban entonces las dos condiciones restantes: \(p \lt L\) y que \(p\) sea primo.
Si ambas se cumplen, \(p\) se añade a la suma. Esta descripción es completa y no cuenta duplicados, porque la truncación decimal determina un único prefijo \(h=\lfloor p/10 \rfloor\).
De \(p=10h+d \lt L\) se deduce necesariamente
$$h \le \left\lfloor\frac{L-1}{10}\right\rfloor.$$
La solución en C++ guarda este valor en harshad_limit. Cualquier Harshad mayor que esa cota ya no puede ser prefijo de una respuesta válida.
La condición de parada en el código es un poco más ajustada. Si
$$n \gt \left\lfloor\frac{\left\lfloor(L-1)/10\right\rfloor}{10}\right\rfloor,$$
entonces cada hijo \(10n+d\) ya supera harshad_limit. El nodo actual todavía puede producir primos finales, pero ya no puede producir prefijos Harshad más profundos que luego resulten útiles.
Tomemos \(n=18\). Se cumple \(s(18)=9\) y \(18/9=2\), así que \(18\) es un Harshad fuerte. Además, como \(1\) y \(18\) son Harshad, el número también es truncable por la derecha.
Las únicas extensiones compatibles con una terminación prima son
$$181,\ 183,\ 187,\ 189.$$
De ellas, \(181\) es primo; \(183\) y \(189\) son divisibles por \(3\), y \(187=11\cdot 17\). Por tanto, \(181\) es uno de los primos pedidos.
El programa local en C++ también valida el punto de control
$$\sum_{p \lt 10^4} p = 90619,$$
y luego compara el algoritmo optimizado con una rutina de fuerza bruta para \(L=10^6\). Ambas comprobaciones coinciden con la derivación matemática.
Las tres implementaciones locales mantienen el mismo estado en la DFS: el prefijo actual \(n\) y su suma de cifras \(s(n)\). Propagar la suma mediante \(s(n')=s(n)+d\) hace que cada transición del árbol tenga coste constante; recalcularla desde cero en cada llamada sería innecesario.
El archivo en C++ ofrece solve(limit), acepta argumentos de la forma --limit=... y permite omitir verificaciones con --skip-checkpoints. Su función dfs_harshad devuelve la suma aportada por un subárbol. Para la primalidad, C++ descarta primero divisores primos pequeños hasta \(37\) y después aplica Miller-Rabin determinista con las bases
$$\{2,3,5,7,11,13,17\}.$$
La multiplicación modular segura se implementa con __uint128_t.
El archivo en Python usa la misma recurrencia y el mismo conjunto de bases, pero acumula la respuesta en una variable nonlocal dentro de dfs. El archivo en Java reproduce el mismo árbol de búsqueda en dfsHarshad y delega la exponenciación modular en BigInteger.modPow. Matemáticamente, los tres programas son equivalentes.
Sea \(H(L)\) el número de prefijos Harshad truncables por la derecha realmente visitados, y \(S(L)\) el número de esos prefijos que además son fuertes. El trabajo por nodo visitado es \(O(1)\): actualizar la suma de cifras y comprobar divisibilidad.
Cada prefijo fuerte dispara como máximo cuatro pruebas de primalidad. Por eso una descripción precisa es
$$O\bigl(H(L) + 4S(L)\,T_{\mathrm{prime}}\bigr),$$
donde \(T_{\mathrm{prime}}\) es el coste de una prueba de Miller-Rabin en el rango de 64 bits usado aquí. Como \(S(L)\le H(L)\), a menudo se resume como
$$O\bigl(H(L)\,T_{\mathrm{prime}}\bigr).$$
La profundidad de la recursión coincide con el número de cifras del prefijo más grande explorado, de modo que el espacio adicional en pila es \(O(\log_{10} L)\). En la práctica esto es muchísimo menor que examinar todos los enteros o todos los primos menores que \(L\).
我们要求所有满足 \(p \lt L\) 的素数 \(p\) 之和，并且删去 \(p\) 的最后一个十进制数字后，剩下的前缀必须是一个强右截 Harshad 数。本仓库的本地解法默认使用 \(L = 10^{14}\)。
记 \(s(n)\) 为 \(n\) 的十进制数位和。若正整数 \(n\) 满足
$$s(n)\mid n,$$
则称 \(n\) 为 Harshad 数。若
$$\frac{n}{s(n)}$$
仍然是素数，则称它为强 Harshad 数。若 \(n\) 的每个非空十进制前缀也都是 Harshad 数，则称它为右截 Harshad 数。把 \(n\) 写成 \(n=\overline{d_1d_2\cdots d_k}\) 时，所有前缀 \(\overline{d_1d_2\cdots d_i}\)（其中 \(1 \le i \le k\)）都必须满足 Harshad 条件。
每个合法素数都可以唯一写成
$$p = 10h + d,\qquad d = p \bmod 10,\qquad h=\left\lfloor\frac{p}{10}\right\rfloor.$$
因此，本题等价于先生成所有既强又右截的 Harshad 前缀 \(h\)，再检查再补上一位后是否能得到小于 \(L\) 的素数。
朴素做法是遍历所有 \(p \lt L\) 的素数，删去最后一位，再检查整条前缀链。仓库代码采取了相反的方向：它只构造合法的 Harshad 前缀，从不遍历任意整数。
所有一位数 \(1,\dots,9\) 都是 Harshad 数，因为对一位数有 \(s(n)=n\)。因此这些数就是搜索树的根节点。
设当前节点是 Harshad 数 \(n\)，其数位和为 \(s=s(n)\)。在末尾追加一个数字 \(d\in\{0,1,\dots,9\}\) 后得到
$$n' = 10n + d,\qquad s(n') = s + d.$$
只有当新节点仍是 Harshad 数时才值得继续，也就是必须满足
$$10n + d \equiv 0 \pmod{s+d}.$$
DFS 在递归前正是执行这个判定。由于每个孩子都来自已经合法的 Harshad 父节点，所以右截性质通过归纳自动成立。
当访问到某个 \(n \ge 10\) 的 Harshad 前缀时，代码会计算
$$q=\frac{n}{s(n)}.$$
若 \(q\) 为素数，则 \(n\) 是强 Harshad 数。这是关键过滤条件，因为任何最终答案都必须来自一个强前缀。代码特意排除一位前缀，因为那时 \(q=1\)，而 \(1\) 不是素数。
若 \(p \gt 10\) 是素数，则最后一位既不可能是偶数，也不可能是 \(5\)。因此每个强前缀 \(h\) 最多只会生成四个有意义的候选：
$$p = 10h + d,\qquad d \in \{1,3,7,9\}.$$
实现随后检查剩余两条条件：\(p \lt L\)，并且 \(p\) 是素数。
若同时满足，就把 \(p\) 加入总和。这个描述既完整又不会重复计数，因为十进制去尾得到的前缀 \(h=\lfloor p/10 \rfloor\) 是唯一的。
由 \(p=10h+d \lt L\) 可知必然有
$$h \le \left\lfloor\frac{L-1}{10}\right\rfloor.$$
C++ 实现把这个上界存入 harshad_limit。任何大于此值的 Harshad 数都不可能再作为合法答案的前缀。
代码中的停止条件还更紧一些。如果
$$n \gt \left\lfloor\frac{\left\lfloor(L-1)/10\right\rfloor}{10}\right\rfloor,$$
那么所有孩子 \(10n+d\) 都已经超过 harshad_limit。此时当前节点仍可能直接产生最终素数，但不可能再产生更深层、仍有用的 Harshad 前缀。
取 \(n=18\)。有 \(s(18)=9\)，且 \(18/9=2\)，所以 \(18\) 是强 Harshad 数。由于 \(1\) 和 \(18\) 都是 Harshad 数，它也满足右截性质。
满足素数结尾条件的扩展只有
$$181,\ 183,\ 187,\ 189.$$
其中 \(181\) 是素数；\(183\) 与 \(189\) 都能被 \(3\) 整除，而 \(187=11\cdot 17\)。因此 \(181\) 就是题目要求的素数之一。
本地 C++ 程序还验证了样例检查点
$$\sum_{p \lt 10^4} p = 90619,$$
并在 \(L=10^6\) 时将优化算法与暴力校验程序进行对比。这些结果与上面的推导完全一致。
三种本地语言实现都维护同样的 DFS 状态：当前前缀 \(n\) 与它的数位和 \(s(n)\)。通过公式 \(s(n')=s(n)+d\) 递推数位和，就能让每次树扩展保持常数代价；否则每次都要重新扫描所有十进制位。
C++ 文件提供 solve(limit)，支持 --limit=... 参数，并允许用 --skip-checkpoints 跳过校验。其 dfs_harshad 返回一个子树贡献的总和。素性判定时，先试除到 \(37\) 为止的小素数，再使用固定底数
$$\{2,3,5,7,11,13,17\}$$
执行确定性的 Miller-Rabin。为了安全进行模乘，C++ 版本使用了 __uint128_t。
Python 文件使用相同的递推和相同的 Miller-Rabin 底数集合，但在 dfs 内通过 nonlocal 变量累计答案。Java 文件则在 dfsHarshad 中复现同样的搜索树，并把模幂运算交给 BigInteger.modPow。三份实现的数学逻辑完全一致。
设 \(H(L)\) 为实际访问到的右截 Harshad 前缀数量，\(S(L)\) 为其中强前缀的数量。每个被访问节点的基础工作都是 \(O(1)\)：更新数位和并检查整除关系。
每个强前缀最多触发四次素性测试，因此更精确的时间复杂度可写为
$$O\bigl(H(L) + 4S(L)\,T_{\mathrm{prime}}\bigr),$$
其中 \(T_{\mathrm{prime}}\) 表示当前 64 位范围内一次 Miller-Rabin 测试的成本。由于 \(S(L)\le H(L)\)，通常也可简写成
$$O\bigl(H(L)\,T_{\mathrm{prime}}\bigr).$$
递归深度等于所探索最大前缀的十进制位数，因此额外栈空间是 \(O(\log_{10} L)\)。与遍历所有小于 \(L\) 的整数或素数相比，这个规模要小得多。
Нужно найти сумму всех простых чисел \(p \lt L\), для которых после удаления последней десятичной цифры остается сильное правоусекаемое число Харшада. В локальных файлах решений по умолчанию используется \(L = 10^{14}\).
Пусть \(s(n)\) обозначает сумму десятичных цифр числа \(n\). Положительное целое \(n\) является числом Харшада, если
$$s(n)\mid n.$$
Оно называется сильным, если
$$\frac{n}{s(n)}$$
является простым. Оно называется правоусекаемым, если каждый его непустой десятичный префикс тоже является числом Харшада. Если \(n=\overline{d_1d_2\cdots d_k}\), то каждый префикс \(\overline{d_1d_2\cdots d_i}\) при \(1 \le i \le k\) обязан удовлетворять условию Харшада.
Каждый допустимый простой имеет единственное представление
$$p = 10h + d,\qquad d = p \bmod 10,\qquad h=\left\lfloor\frac{p}{10}\right\rfloor.$$
Следовательно, задача сводится к тому, чтобы породить все префиксы \(h\), которые одновременно сильные и правоусекаемые, а затем проверить, превращает ли добавление одной цифры такой префикс в простой меньше \(L\).
Наивный подход перебирал бы все простые \(p \lt L\), отбрасывал последнюю цифру и затем проверял всю цепочку префиксов. Код из репозитория делает наоборот: он строит только допустимые Harshad-префиксы и никогда не рассматривает произвольные целые числа.
Все однозначные числа \(1,\dots,9\) являются числами Харшада, потому что для одной цифры выполняется \(s(n)=n\). Именно они служат корнями дерева поиска.
Пусть текущий узел равен \(n\), а сумма его цифр равна \(s=s(n)\). При дописывании цифры \(d\in\{0,1,\dots,9\}\) получаем
$$n' = 10n + d,\qquad s(n') = s + d.$$
Потомок полезен только тогда, когда он снова является числом Харшада, то есть когда
$$10n + d \equiv 0 \pmod{s+d}.$$
Именно этот фильтр DFS проверяет перед рекурсией. Поскольку каждый ребенок строится из уже корректного Harshad-родителя, свойство правоусекаемости обеспечивается индуктивно автоматически.
Как только посещенный префикс \(n \ge 10\) оказывается числом Харшада, программа вычисляет
$$q=\frac{n}{s(n)}.$$
Если \(q\) простое, то \(n\) является сильным. Это главный фильтр, потому что любой подходящий конечный простой обязан происходить из сильного префикса. Однозначные префиксы здесь специально исключаются: для них получилось бы \(q=1\), а \(1\) не является простым.
Если \(p \gt 10\) простое, то его последняя цифра не может быть четной и не может быть равна \(5\). Поэтому каждый сильный префикс \(h\) дает не более четырех содержательных кандидатов:
$$p = 10h + d,\qquad d \in \{1,3,7,9\}.$$
Далее реализации проверяют два оставшихся условия: \(p \lt L\) и простоту числа \(p\).
Если оба выполнены, \(p\) добавляется в сумму. Это описание полно и не приводит к двойному счету, потому что десятичное усечение определяет единственный префикс \(h=\lfloor p/10 \rfloor\).
Из условия \(p=10h+d \lt L\) обязательно следует
$$h \le \left\lfloor\frac{L-1}{10}\right\rfloor.$$
В версии на C++ эта величина хранится в переменной harshad_limit. Любое число Харшада выше этого порога уже не может быть префиксом допустимого ответа.
Условие остановки в коде немного сильнее. Если
$$n \gt \left\lfloor\frac{\left\lfloor(L-1)/10\right\rfloor}{10}\right\rfloor,$$
то каждый потомок \(10n+d\) уже больше harshad_limit. Текущий узел еще может породить конечные простые, но более глубокие Harshad-префиксы уже не принесут пользы.
Возьмем \(n=18\). Тогда \(s(18)=9\) и \(18/9=2\), следовательно, \(18\) является сильным числом Харшада. Поскольку \(1\) и \(18\) оба являются числами Харшада, \(18\) также правоусекаемо.
Единственные возможные окончания, совместимые с простотой, таковы:
$$181,\ 183,\ 187,\ 189.$$
Из них \(181\) простое; \(183\) и \(189\) делятся на \(3\), а \(187=11\cdot 17\). Значит, \(181\) является одним из искомых простых чисел.
Локальная программа на C++ дополнительно проверяет контрольное значение
$$\sum_{p \lt 10^4} p = 90619,$$
а затем сравнивает оптимизированный поиск с грубой проверкой при \(L=10^6\). Эти тесты полностью согласуются с описанной конструкцией.
Во всех трех локальных версиях DFS хранит одно и то же состояние: текущий префикс \(n\) и сумму его цифр \(s(n)\). Передача суммы цифр по формуле \(s(n')=s(n)+d\) делает переход по ребру дерева константным по времени; иначе пришлось бы каждый раз заново суммировать все цифры.
Файл на C++ предоставляет solve(limit), поддерживает аргументы вида --limit=... и флаг --skip-checkpoints. Функция dfs_harshad возвращает вклад одного поддерева. Для проверки простоты C++ сначала удаляет малые делители до \(37\), а затем запускает детерминированный Miller-Rabin по основаниям
$$\{2,3,5,7,11,13,17\}.$$
Чтобы избежать переполнения при модульном умножении, используется __uint128_t.
Файл на Python использует ту же рекуррентную формулу и тот же набор оснований Miller-Rabin, но накапливает ответ в переменной nonlocal внутри dfs. Файл на Java повторяет ту же структуру дерева в dfsHarshad и поручает модульное возведение в степень методу BigInteger.modPow. С математической точки зрения все три реализации эквивалентны.
Пусть \(H(L)\) обозначает число реально посещенных правоусекаемых Harshad-префиксов, а \(S(L)\) — число сильных префиксов среди них. Базовая работа на один посещенный узел равна \(O(1)\): обновить сумму цифр и проверить делимость.
Каждый сильный префикс запускает не более четырех тестов простоты. Поэтому точнее всего время описывается как
$$O\bigl(H(L) + 4S(L)\,T_{\mathrm{prime}}\bigr),$$
где \(T_{\mathrm{prime}}\) — стоимость одного теста Miller-Rabin в используемом здесь 64-битном диапазоне. Так как \(S(L)\le H(L)\), это часто сокращают до
$$O\bigl(H(L)\,T_{\mathrm{prime}}\bigr).$$
Глубина рекурсии равна числу десятичных цифр у максимального исследуемого префикса, значит дополнительная память стека имеет порядок \(O(\log_{10} L)\). На практике это на порядки меньше, чем полный перебор всех чисел или всех простых ниже \(L\).
نريد حساب مجموع جميع الأعداد الأولية \(p \lt L\) التي يؤدي حذف آخر رقم عشري منها إلى بادئة تمثل عدد Harshad قويًا وقابلًا للاقتطاع من اليمين. في ملفات الحل المحلية المستعملة هنا يكون الحد الافتراضي \(L = 10^{14}\).
لنرمز بـ \(s(n)\) إلى مجموع الأرقام العشرية للعدد \(n\). يكون العدد الصحيح الموجب \(n\) عدد Harshad إذا تحقق
$$s(n)\mid n.$$
ويكون قويًا إذا كان
$$\frac{n}{s(n)}$$
عددًا أوليًا. ويكون قابلًا للاقتطاع من اليمين إذا كانت كل بادئة عشرية غير فارغة له أيضًا عدد Harshad. فإذا كتبنا \(n=\overline{d_1d_2\cdots d_k}\)، وجب أن تحقق كل بادئة \(\overline{d_1d_2\cdots d_i}\) حيث \(1 \le i \le k\) شرط Harshad.
كل عدد أولي صالح يملك التمثيل الفريد
$$p = 10h + d,\qquad d = p \bmod 10,\qquad h=\left\lfloor\frac{p}{10}\right\rfloor.$$
ولهذا تتحول المسألة إلى توليد كل البوادئ \(h\) التي تكون قوية وقابلة للاقتطاع من اليمين، ثم فحص ما إذا كانت إضافة رقم واحد في النهاية تحولها إلى عدد أولي أصغر من \(L\).
الطريقة الساذجة كانت ستفحص كل عدد أولي \(p \lt L\)، ثم تحذف آخر رقم منه، ثم تتحقق من كامل سلسلة البوادئ. كود المستودع يسير في الاتجاه المعاكس تمامًا: فهو يبني فقط بوادئ Harshad الصحيحة، ولا يستكشف أعدادًا صحيحة عشوائية.
كل عدد أحادي الرقم من \(1\) إلى \(9\) هو Harshad لأن \(s(n)=n\) في هذه الحالة. لذلك تشكل هذه القيم جذور شجرة البحث.
لنفترض أن العقدة الحالية هي \(n\) ومجموع أرقامها \(s=s(n)\). عند إلحاق رقم \(d\in\{0,1,\dots,9\}\) نحصل على
$$n' = 10n + d,\qquad s(n') = s + d.$$
ولا يكون الابن مفيدًا إلا إذا بقي عدد Harshad، أي إذا تحقق
$$10n + d \equiv 0 \pmod{s+d}.$$
هذا هو الاختبار الذي تطبقه DFS قبل النزول العودي. وبما أن كل ابن يُنتج من أب صحيح من نوع Harshad، فإن خاصية الاقتطاع من اليمين تصبح مضمونة بالاستقراء.
عندما تصل الخوارزمية إلى بادئة Harshad تحقق \(n \ge 10\)، تحسب القيمة
$$q=\frac{n}{s(n)}.$$
فإذا كان \(q\) أوليًا كانت البادئة \(n\) قوية. وهذا هو المرشح الحاسم، لأن كل عدد أولي مطلوب في النهاية لا بد أن يأتي من بادئة قوية. أما البوادئ الأحادية فتُستبعد في هذه المرحلة، لأن الناتج سيكون \(q=1\)، و\(1\) ليس عددًا أوليًا.
إذا كان \(p \gt 10\) عددًا أوليًا، فلا يمكن أن يكون رقمه الأخير زوجيًا ولا \(5\). لذلك فإن كل بادئة قوية \(h\) تولد في أقصى الأحوال أربعة مرشحين مهمين:
$$p = 10h + d,\qquad d \in \{1,3,7,9\}.$$
بعد ذلك تفحص التطبيقات الشرطين المتبقيين: أن يكون \(p \lt L\) وأن يكون \(p\) أوليًا.
فإن تحققا أضيف \(p\) إلى المجموع. وهذا الوصف كامل ولا ينتج تكرارًا في العد، لأن اقتطاع الرقم الأخير في النظام العشري يحدد بادئة واحدة فقط هي \(h=\lfloor p/10 \rfloor\).
من العلاقة \(p=10h+d \lt L\) نحصل بالضرورة على
$$h \le \left\lfloor\frac{L-1}{10}\right\rfloor.$$
نسخة C++ تخزن هذه القيمة في المتغير harshad_limit. وكل عدد Harshad أكبر من هذا الحد لا يمكن أن يبقى بادئة لجواب صحيح.
شرط التوقف في الكود أدق قليلًا. فإذا كان
$$n \gt \left\lfloor\frac{\left\lfloor(L-1)/10\right\rfloor}{10}\right\rfloor,$$
فإن كل ابن من الشكل \(10n+d\) سيكون أكبر من harshad_limit. عندئذ قد تنتج العقدة الحالية أعدادًا أولية نهائية مباشرة، لكنها لن تنتج بوادئ Harshad أعمق لها فائدة لاحقة.
لنأخذ \(n=18\). لدينا \(s(18)=9\) و\(18/9=2\)، ولذلك فإن \(18\) عدد Harshad قوي. وبما أن \(1\) و\(18\) كلاهما Harshad، فهو أيضًا قابل للاقتطاع من اليمين.
النهايات الوحيدة المناسبة للأولية هي
$$181,\ 183,\ 187,\ 189.$$
من بينها \(181\) أولي، بينما \(183\) و\(189\) يقبلان القسمة على \(3\)، و\(187=11\cdot 17\). إذن \(181\) واحد من الأعداد المطلوبة.
وتتحقق نسخة C++ المحلية أيضًا من نقطة الفحص
$$\sum_{p \lt 10^4} p = 90619,$$
ثم تقارن الحل المحسن بحل brute force عند \(L=10^6\). وهذه الفحوص تتطابق مع الاشتقاق الرياضي المعروض هنا.
تحمل إصدارات اللغات الثلاث الحالة نفسها داخل DFS: البادئة الحالية \(n\) ومجموع أرقامها \(s(n)\). وتمرير مجموع الأرقام بالعلاقة \(s(n')=s(n)+d\) يجعل الانتقال بين العقد ذا كلفة ثابتة؛ أما إعادة حساب مجموع الأرقام من الصفر في كل مرة فكانت ستزيد العمل بلا داع.
يوفر ملف C++ الدالة solve(limit)، ويدعم وسيطات من شكل --limit=...، ويتيح تعطيل نقاط الفحص عبر --skip-checkpoints. الدالة dfs_harshad تعيد مجموع ما يساهم به فرع واحد من الشجرة. وفي اختبار الأولية تستبعد نسخة C++ أولًا القواسم الأولية الصغيرة حتى \(37\)، ثم تطبق Miller-Rabin الحتمي على القواعد
$$\{2,3,5,7,11,13,17\}.$$
ولكي يبقى الضرب المعياري آمنًا من تجاوز السعة تستخدم النوع __uint128_t.
ملف Python يستعمل العلاقة نفسها ومجموعة القواعد نفسها، لكنه يجمع النتيجة في متغير nonlocal داخل dfs. أما ملف Java فيحافظ على شجرة DFS نفسها داخل dfsHarshad ويفوض حساب القوى المعيارية إلى BigInteger.modPow. من الناحية الرياضية، الملفات الثلاثة تنفذ الخوارزمية نفسها.
لنرمز بـ \(H(L)\) إلى عدد بوادئ Harshad القابلة للاقتطاع من اليمين التي تُزار فعليًا، وبـ \(S(L)\) إلى عدد البوادئ القوية بينها. العمل الأساسي عند كل عقدة مزارة هو \(O(1)\): تحديث مجموع الأرقام وفحص القابلية للقسمة.
كل بادئة قوية تطلق في أقصى تقدير أربع اختبارات أولية، ولذلك يمكن وصف الزمن بدقة على الصورة
$$O\bigl(H(L) + 4S(L)\,T_{\mathrm{prime}}\bigr),$$
حيث \(T_{\mathrm{prime}}\) هي كلفة اختبار Miller-Rabin واحد في مجال الأعداد ذي 64 بت المستعمل هنا. وبما أن \(S(L)\le H(L)\)، فيمكن اختصار ذلك غالبًا إلى
$$O\bigl(H(L)\,T_{\mathrm{prime}}\bigr).$$
أما عمق العودية فيساوي عدد الخانات العشرية لأكبر بادئة يجري استكشافها، ولذلك تكون الذاكرة الإضافية على المكدس من رتبة \(O(\log_{10} L)\). وهذا أصغر بكثير عمليًا من مسح جميع الأعداد أو جميع الأعداد الأولية الأصغر من \(L\).