We seek the \(n\)-th positive integer whose decimal digit sum is prime. A direct scan would be far too slow for the real target, so the solution counts how many valid numbers lie in \([1,x]\), then finds the first \(x\) whose count reaches \(n\).
Let \(s(x)\) be the base-10 digit sum of \(x\), and let \(\mathcal{P}\) denote the set of prime numbers. The central counting function is
$$C(x)=\#\{1\le m\le x : s(m)\in\mathcal{P}\}.$$
Once \(C(x)\) can be evaluated quickly, the answer is simply the smallest \(x\) with \(C(x)\ge n\).
The method is a digit dynamic program. Instead of enumerating every number up to \(x\), it counts possible suffixes by their digit sums and reuses those counts while scanning the decimal representation of \(x\).
The implementations reserve tables for at most \(D=20\) decimal positions, so the largest relevant digit sum is \(S=9D=180\).
For \(\ell\ge 0\) and \(0\le t\le S\), define
$$W(\ell,t)=\#\{(d_1,\dots,d_\ell)\in\{0,\dots,9\}^{\ell}: d_1+\cdots+d_\ell=t\}.$$
Leading zeros are allowed. This matters because a string such as \(04\) represents the ordinary number \(4\), so the same table automatically covers shorter numbers when we later compare against a fixed-length bound.
The initial conditions are
$$W(0,0)=1,\qquad W(0,t)=0\text{ for }t>0,$$
and the recurrence is
$$W(\ell,t)=\sum_{d=0}^{9} W(\ell-1,t-d),$$
with the convention that \(W(\ell,u)=0\) whenever \(u \lt 0\). After this table is built, we know how many tails of any remaining length realize any required digit sum.
Suppose a prefix already contributes digit sum \(p\), and there are \(r\) digits still to choose. We need the number of tails that make the final total prime. Define
$$G(r,p)=\sum_{\substack{u\ge 0\\ p+u\in\mathcal{P}}} W(r,u).$$
Thus \(G(r,p)\) counts all length-\(r\) suffixes whose digit sum \(u\) turns the current prefix sum \(p\) into a prime total \(p+u\). This second table becomes the counting oracle used for every query.
Because the largest possible total is only \(180\), primality can be precomputed once by a small sieve and then reused for every state \((r,p)\).
Write the decimal expansion of \(x\) as \(x_0x_1\dots x_{k-1}\), and let
$$\sigma_i=x_0+x_1+\cdots+x_{i-1}$$
be the sum of the digits strictly before position \(i\), with \(\sigma_0=0\).
While scanning from left to right, position \(i\) offers two possibilities: follow the actual digit \(x_i\), or choose any smaller digit \(d \lt x_i\). If we choose a smaller digit, then the remaining \(k-1-i\) positions are completely free, so their contribution is exactly
$$G(k-1-i,\sigma_i+d).$$
Summing this over every position and every smaller digit yields all valid numbers strictly below \(x\). After the scan, we add one more if the digit sum of \(x\) itself is prime. In compact form,
$$C(x)=\sum_{i=0}^{k-1}\sum_{d=0}^{x_i-1} G(k-1-i,\sigma_i+d)+\varepsilon(x),$$
where \(\varepsilon(x)=1\) when \(s(x)\in\mathcal{P}\), and \(\varepsilon(x)=0\) otherwise.
If \(x\) has \(k\) digits, then every positive integer with fewer than \(k\) digits is still represented as a length-\(k\) string by padding it with leading zeros. For example, \(37\) is treated as \(037\) when compared against a 3-digit bound.
This removes the need for separate cases for 1-digit, 2-digit, and longer numbers. The number \(0\) causes no trouble, because its digit sum is \(0\), and \(0\notin\mathcal{P}\).
The function \(C(x)\) is nondecreasing, because enlarging \([1,x]\) can only add more valid integers. Therefore the target value is
$$\min\{x\ge 1 : C(x)\ge n\}.$$
The implementations first grow an upper bound by repeated doubling until the count reaches \(n\). Once such a bound is found, ordinary binary search isolates the first \(x\) with \(C(x)\ge n\).
A useful checkpoint is that the 61st positive integer with prime digit sum is \(157\). The digit-DP explains this neatly.
First consider all numbers from \(0\) to \(99\). Using 2-digit strings with leading zeros, the prime digit sums are \(2,3,5,7,11,13,17\). The table \(W(2,t)\) gives
$$W(2,2)=3,\quad W(2,3)=4,\quad W(2,5)=6,\quad W(2,7)=8,\quad W(2,11)=8,\quad W(2,13)=6,\quad W(2,17)=2,$$
so
$$G(2,0)=3+4+6+8+8+6+2=37.$$
Thus exactly \(37\) numbers in \([1,99]\) have prime digit sum.
Now move to numbers below \(157\). Fix the hundreds digit as \(1\). For a tens digit smaller than \(5\), the current prefix sums are \(1,2,3,4,5\). The 1-digit suffix table gives
$$G(1,1)=4,\quad G(1,2)=5,\quad G(1,3)=4,\quad G(1,4)=4,\quad G(1,5)=4,$$
hence the block \(100\) to \(149\) contributes
$$4+5+4+4+4=21.$$
Finally, within \(150\) to \(156\), only \(151\) and \(155\) have prime digit sum, so this last partial block contributes \(2\). Therefore
$$C(156)=37+21+2=60.$$
Since \(1+5+7=13\) is prime, \(157\) itself is valid, giving
$$C(157)=61.$$
So the 61st term is indeed \(157\), exactly matching the checkpoint used by the implementations.
The C++, Python, and Java implementations follow the same pipeline. They first precompute primality for every possible digit sum from \(0\) to \(180\). Next they build the table \(W(\ell,t)\) for all lengths up to \(20\), then build the suffix-completion table \(G(r,p)\).
For a query \(C(x)\), the implementation converts \(x\) to decimal, scans left to right, and whenever a smaller digit than the bound is possible at the current position, it adds the precomputed number of prime-completing tails. After the full scan, it checks whether the bound itself has prime digit sum and includes it if appropriate.
To obtain the \(n\)-th valid integer, the implementation repeatedly doubles an upper bound until enough valid numbers are covered, and then performs a standard binary search on that interval. No brute-force pass over all intermediate integers is needed.
Let \(D\) be the maximum number of digits and \(S=9D\) the maximum digit sum. Building the prime table costs \(O(S\log\log S)\). Building \(W\) costs \(O(10DS)\). Building the suffix table \(G\) in the straightforward form used here costs \(O(DS^2)\), because each state \((r,p)\) scans all feasible tail sums.
One evaluation of \(C(x)\) costs \(O(10D)\): there are \(D\) positions and at most 10 candidate digits per position. The final search uses \(O(\log X)\) such evaluations, where \(X\) is the answer. Memory usage is \(O(DS)\). In these implementations, \(D=20\) and \(S=180\), so the constants are very small.
Gesucht ist die \(n\)-te positive Zahl, deren Dezimalziffernsumme prim ist. Ein direktes Durchprobieren aller Zahlen wäre für das echte Ziel viel zu langsam. Deshalb zählt die Lösung zunächst, wie viele gültige Zahlen in \([1,x]\) liegen, und bestimmt danach das erste \(x\), bei dem dieser Zähler den Wert \(n\) erreicht.
Sei \(s(x)\) die Ziffernsumme in Basis 10 und \(\mathcal{P}\) die Menge der Primzahlen. Die zentrale Zählfunktion lautet
$$C(x)=\#\{1\le m\le x : s(m)\in\mathcal{P}\}.$$
Sobald sich \(C(x)\) schnell auswerten lässt, ist die Antwort einfach das kleinste \(x\) mit \(C(x)\ge n\).
Die Methode ist eine Digit-DP. Anstatt jede Zahl bis \(x\) einzeln zu testen, zählt sie mögliche Suffixe nach ihrer Ziffernsumme und verwendet diese Zählungen wieder, während die Dezimaldarstellung von \(x\) von links nach rechts durchlaufen wird.
Die Implementierungen reservieren Tabellen für höchstens \(D=20\) Dezimalstellen. Daher ist die größte relevante Ziffernsumme \(S=9D=180\).
Für \(\ell\ge 0\) und \(0\le t\le S\) definieren wir
$$W(\ell,t)=\#\{(d_1,\dots,d_\ell)\in\{0,\dots,9\}^{\ell}: d_1+\cdots+d_\ell=t\}.$$
Führende Nullen sind erlaubt. Das ist wichtig, denn eine Folge wie \(04\) repräsentiert die gewöhnliche Zahl \(4\). Damit deckt dieselbe Tabelle automatisch auch kürzere Zahlen ab, wenn später gegen eine feste Stellenzahl verglichen wird.
Die Anfangsbedingungen sind
$$W(0,0)=1,\qquad W(0,t)=0\text{ für }t>0,$$
und die Rekursion lautet
$$W(\ell,t)=\sum_{d=0}^{9} W(\ell-1,t-d),$$
wobei \(W(\ell,u)=0\) gilt, sobald \(u \lt 0\) ist. Nach dem Aufbau dieser Tabelle kennen wir für jede Restlänge die Anzahl aller Suffixe mit vorgegebener Ziffernsumme.
Angenommen, ein Präfix hat bereits Ziffernsumme \(p\), und es bleiben noch \(r\) Stellen zu wählen. Dann brauchen wir die Anzahl der Endstücke, die die Gesamtsumme zu einer Primzahl machen. Wir definieren
$$G(r,p)=\sum_{\substack{u\ge 0\\ p+u\in\mathcal{P}}} W(r,u).$$
Also zählt \(G(r,p)\) alle Suffixe der Länge \(r\), deren Ziffernsumme \(u\) die aktuelle Präfixsumme \(p\) zu einer Primzahl \(p+u\) ergänzt. Diese zweite Tabelle ist das eigentliche Zählorakel für jede Anfrage.
Da die größte mögliche Gesamtsumme nur \(180\) beträgt, lässt sich die Primzahligkeit einmal mit einem kleinen Sieb vorberechnen und danach in allen Zuständen \((r,p)\) wiederverwenden.
Schreibe die Dezimaldarstellung von \(x\) als \(x_0x_1\dots x_{k-1}\), und setze
$$\sigma_i=x_0+x_1+\cdots+x_{i-1}$$
für die Summe der Ziffern vor Position \(i\), mit \(\sigma_0=0\).
Beim Durchlauf von links nach rechts gibt es an Position \(i\) zwei Möglichkeiten: Man folgt der tatsächlichen Ziffer \(x_i\), oder man wählt eine kleinere Ziffer \(d \lt x_i\). Im zweiten Fall sind die restlichen \(k-1-i\) Stellen frei wählbar, und ihr Beitrag ist genau
$$G(k-1-i,\sigma_i+d).$$
Summiert man das über alle Positionen und alle kleineren Ziffern, erhält man alle gültigen Zahlen, die echt kleiner als \(x\) sind. Danach addiert man noch \(1\), falls die Ziffernsumme von \(x\) selbst prim ist. Kompakt geschrieben:
$$C(x)=\sum_{i=0}^{k-1}\sum_{d=0}^{x_i-1} G(k-1-i,\sigma_i+d)+\varepsilon(x),$$
wobei \(\varepsilon(x)=1\) gilt, wenn \(s(x)\in\mathcal{P}\) ist, und sonst \(\varepsilon(x)=0\).
Hat \(x\) genau \(k\) Stellen, dann wird jede positive Zahl mit weniger als \(k\) Stellen als Folge der Länge \(k\) mit führenden Nullen dargestellt. Zum Beispiel wird \(37\) bei einem 3-stelligen Vergleich als \(037\) behandelt.
Dadurch braucht man keine getrennten Fälle für 1-stellige, 2-stellige oder allgemein kürzere Zahlen. Die Zahl \(0\) stört nicht, denn ihre Ziffernsumme ist \(0\), und \(0\notin\mathcal{P}\).
Die Funktion \(C(x)\) ist monoton nicht fallend, weil ein größeres Intervall \([1,x]\) nur zusätzliche gültige Zahlen enthalten kann. Daher ist die Zielzahl
$$\min\{x\ge 1 : C(x)\ge n\}.$$
Die Implementierungen vergrößern zuerst eine obere Schranke durch wiederholtes Verdoppeln, bis der Zähler mindestens \(n\) erreicht. Danach isoliert eine gewöhnliche Binärsuche das erste \(x\) mit \(C(x)\ge n\).
Ein nützlicher Kontrollpunkt ist: Die 61. positive Zahl mit primzahliger Ziffernsumme ist \(157\). Die Digit-DP macht das transparent.
Zuerst betrachten wir alle Zahlen von \(0\) bis \(99\). Mit 2-stelligen Folgen inklusive führender Nullen sind die primen Ziffernsummen \(2,3,5,7,11,13,17\). Aus der Tabelle \(W(2,t)\) erhält man
$$W(2,2)=3,\quad W(2,3)=4,\quad W(2,5)=6,\quad W(2,7)=8,\quad W(2,11)=8,\quad W(2,13)=6,\quad W(2,17)=2,$$
also
$$G(2,0)=3+4+6+8+8+6+2=37.$$
Damit gibt es genau \(37\) Zahlen in \([1,99]\) mit primzahliger Ziffernsumme.
Nun gehen wir zu Zahlen unter \(157\). Fixiere die Hunderterziffer als \(1\). Für Zehnerziffern kleiner als \(5\) lauten die bisherigen Präfixsummen \(1,2,3,4,5\). Die Tabelle für 1-stellige Suffixe liefert
$$G(1,1)=4,\quad G(1,2)=5,\quad G(1,3)=4,\quad G(1,4)=4,\quad G(1,5)=4,$$
weshalb der Block \(100\) bis \(149\) insgesamt
$$4+5+4+4+4=21$$
beisteuert.
Im letzten Teilblock \(150\) bis \(156\) besitzen nur \(151\) und \(155\) eine primzahlige Ziffernsumme. Dieser Abschnitt liefert also \(2\). Daher gilt
$$C(156)=37+21+2=60.$$
Da \(1+5+7=13\) prim ist, ist auch \(157\) selbst gültig, also
$$C(157)=61.$$
Folglich ist das 61. Element tatsächlich \(157\), genau wie es die Implementierungen bestätigen.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Abfolge. Zuerst berechnen sie die Primzahligkeit aller möglichen Ziffernsummen von \(0\) bis \(180\). Danach füllen sie die Tabelle \(W(\ell,t)\) für alle Längen bis \(20\) und erzeugen daraus die Suffix-Tabelle \(G(r,p)\).
Für eine Anfrage \(C(x)\) wird \(x\) in seine Dezimaldarstellung umgewandelt und von links nach rechts verarbeitet. Immer wenn an einer Position eine kleinere Ziffer als die Schranke möglich ist, addiert die Implementierung die bereits vorbereitete Anzahl von Suffixen, die zu einer primen Gesamtsumme führen. Nach dem vollständigen Durchlauf wird noch geprüft, ob auch die Schranke selbst gültig ist.
Um die \(n\)-te gültige Zahl zu erhalten, verdoppelt die Implementierung zunächst eine obere Schranke so lange, bis genügend gültige Zahlen enthalten sind. Anschließend führt sie auf diesem Intervall eine normale Binärsuche aus. Ein brutaler Komplettdurchlauf aller Zwischenzahlen ist nicht nötig.
Seien \(D\) die maximale Stellenzahl und \(S=9D\) die maximale Ziffernsumme. Das Primzahlsieb kostet \(O(S\log\log S)\). Der Aufbau von \(W\) benötigt \(O(10DS)\). Der Aufbau der Suffix-Tabelle \(G\) kostet in der hier verwendeten direkten Form \(O(DS^2)\), weil jeder Zustand \((r,p)\) alle erreichbaren Restsummen durchläuft.
Eine Auswertung von \(C(x)\) kostet \(O(10D)\): Es gibt \(D\) Positionen und pro Position höchstens 10 Kandidatenziffern. Die abschließende Suche benötigt \(O(\log X)\) solcher Auswertungen, wobei \(X\) die Antwort ist. Der Speicherbedarf beträgt \(O(DS)\). In diesen Implementierungen gilt \(D=20\) und \(S=180\), daher sind die Konstanten sehr klein.
Aranan şey, onluk tabanda rakamları toplamı asal olan sayıların \(n\). pozitif elemanıdır. Gerçek hedef için sayıları tek tek denemek çok yavaştır. Bu yüzden çözüm önce \([1,x]\) aralığında kaç geçerli sayı bulunduğunu sayar, sonra bu sayının \(n\)'ye ilk ulaştığı \(x\) değerini bulur.
\(s(x)\) onluk rakam toplamını, \(\mathcal{P}\) ise asal sayılar kümesini göstersin. Temel sayım fonksiyonu
$$C(x)=\#\{1\le m\le x : s(m)\in\mathcal{P}\}.$$
\(C(x)\) hızlı hesaplanabildiğinde cevap, \(C(x)\ge n\) koşulunu sağlayan en küçük \(x\) olur.
Yöntem bir digit-DP yaklaşımıdır. Amaç, \(x\)'e kadar tüm sayıları tek tek üretmek değil; olası son ekleri rakam toplamlarına göre sayıp bu sayımları \(x\)'in onluk yazılımını soldan sağa gezerken yeniden kullanmaktır.
İmplementasyonlar en fazla \(D=20\) basamak için tablo ayırır. Bu yüzden ilgili en büyük rakam toplamı \(S=9D=180\) olur.
\(\ell\ge 0\) ve \(0\le t\le S\) için
$$W(\ell,t)=\#\{(d_1,\dots,d_\ell)\in\{0,\dots,9\}^{\ell}: d_1+\cdots+d_\ell=t\}$$
tanımını yapalım.
Baştaki sıfırlara izin verilir. Bu kritik bir noktadır; örneğin \(04\) dizisi sıradan \(4\) sayısını temsil eder. Böylece aynı tablo, daha sonra sabit uzunlukta bir üst sınıra karşılaştırma yapılırken kısa sayıları da otomatik olarak kapsar.
Başlangıç koşulları
$$W(0,0)=1,\qquad W(0,t)=0\text{ for }t>0,$$
ve yineleme bağıntısı
$$W(\ell,t)=\sum_{d=0}^{9} W(\ell-1,t-d)$$
şeklindedir. Burada \(u \lt 0\) ise \(W(\ell,u)=0\) kabul edilir. Bu tablo kurulduktan sonra, kalan uzunluğu belli olan her son ek için hangi rakam toplamının kaç farklı şekilde elde edildiği bilinir.
Diyelim ki seçilmiş bir ön ekin rakam toplamı \(p\) ve geriye seçilecek \(r\) basamak kaldı. Bu son eklerin toplamı öyle bir \(u\) olmalı ki \(p+u\) asal olsun. Bunun için
$$G(r,p)=\sum_{\substack{u\ge 0\\ p+u\in\mathcal{P}}} W(r,u)$$
tanımlanır.
Yani \(G(r,p)\), uzunluğu \(r\) olan ve mevcut ön ek toplamı \(p\)'yi asal bir toplam olan \(p+u\)'ya dönüştüren tüm son eklerin sayısını verir. Sorgular sırasında kullanılan esas sayım tablosu budur.
Toplam en fazla \(180\) olabildiği için asallık bilgisi küçük bir elek ile bir kez hazırlanır ve sonra her \((r,p)\) durumunda tekrar kullanılır.
\(x\)'in onluk açılımı \(x_0x_1\dots x_{k-1}\) olsun. Ayrıca
$$\sigma_i=x_0+x_1+\cdots+x_{i-1}$$
ile \(i\). basamaktan önce gelen rakamların toplamını gösterelim; \(\sigma_0=0\).
Soldan sağa ilerlerken her konumda iki seçenek vardır: ya gerçek rakam \(x_i\) ile devam edilir, ya da bundan küçük bir \(d \lt x_i\) seçilir. Küçük bir rakam seçildiği anda geriye kalan \(k-1-i\) basamak tamamen serbest olur ve katkı tam olarak
$$G(k-1-i,\sigma_i+d)$$
olur.
Bunu tüm konumlar ve tüm küçük rakam seçimleri için topladığımızda \(x\)'ten küçük bütün geçerli sayıları elde ederiz. Tarama bittikten sonra \(x\)'in kendi rakam toplamı asalsa bir de \(1\) eklenir. Kısa yazımıyla
$$C(x)=\sum_{i=0}^{k-1}\sum_{d=0}^{x_i-1} G(k-1-i,\sigma_i+d)+\varepsilon(x),$$
burada \(s(x)\in\mathcal{P}\) ise \(\varepsilon(x)=1\), aksi halde \(\varepsilon(x)=0\).
Eğer \(x\) tam \(k\) basamaklıysa, \(k\)'dan daha kısa her pozitif sayı başına yeterince sıfır eklenerek \(k\) uzunluklu bir dizi gibi temsil edilir. Örneğin 3 basamaklı bir üst sınır altında \(37\), \(037\) olarak düşünülür.
Böylece 1 basamaklı, 2 basamaklı veya daha kısa sayılar için ayrı ayrı durum ayırmaya gerek kalmaz. \(0\) sayısı da sorun yaratmaz; çünkü rakam toplamı \(0\)'dır ve \(0\notin\mathcal{P}\).
\(C(x)\) azalmayan bir fonksiyondur; çünkü \([1,x]\) aralığını büyütmek yalnızca daha fazla geçerli sayı ekleyebilir. Bu nedenle aranan değer
$$\min\{x\ge 1 : C(x)\ge n\}$$
şeklindedir.
İmplementasyonlar önce bir üst sınırı tekrar tekrar ikiyle çarparak sayımın \(n\)'ye ulaştığı ilk aralığı bulur. Ardından sıradan ikili arama ile \(C(x)\ge n\) koşulunu sağlayan ilk \(x\) izole edilir.
Kullanışlı bir kontrol noktası şudur: Rakam toplamı asal olan sayıların 61.'si \(157\)'dir. Digit-DP bunu açıkça gösterir.
Önce \(0\) ile \(99\) arasındaki tüm sayılara bakalım. Baştaki sıfırlara izin veren 2 basamaklı diziler için asal rakam toplamları \(2,3,5,7,11,13,17\) olur. \(W(2,t)\) tablosundan
$$W(2,2)=3,\quad W(2,3)=4,\quad W(2,5)=6,\quad W(2,7)=8,\quad W(2,11)=8,\quad W(2,13)=6,\quad W(2,17)=2,$$
dolayısıyla
$$G(2,0)=3+4+6+8+8+6+2=37$$
elde edilir.
Yani \([1,99]\) içinde rakam toplamı asal olan tam \(37\) sayı vardır.
Şimdi \(157\)'den küçük sayılara geçelim. Yüzler basamağını \(1\) sabit tutalım. Onlar basamağı \(5\)'ten küçük olduğunda mevcut ön ek toplamları \(1,2,3,4,5\) olur. Tek basamaklı son ek tablosu
$$G(1,1)=4,\quad G(1,2)=5,\quad G(1,3)=4,\quad G(1,4)=4,\quad G(1,5)=4$$
değerlerini verir. Böylece \(100\) ile \(149\) arası toplam
$$4+5+4+4+4=21$$
katkı yapar.
Son kısım olan \(150\) ile \(156\) arasında ise yalnızca \(151\) ve \(155\) asal rakam toplamına sahiptir. Bu da \(2\) ekler. O halde
$$C(156)=37+21+2=60.$$
\(1+5+7=13\) asal olduğundan \(157\) de geçerlidir ve
$$C(157)=61$$
olur. Böylece 61. terimin gerçekten \(157\) olduğu görülür; implementasyonların kontrolü de tam olarak bunu doğrular.
C++, Python ve Java implementasyonları aynı akışı izler. Önce \(0\) ile \(180\) arasındaki tüm olası rakam toplamları için asallık bilgisi hazırlanır. Sonra \(20\) basamağa kadar \(W(\ell,t)\) tablosu doldurulur ve buradan \(G(r,p)\) son-ek tamamlama tablosu üretilir.
Bir \(C(x)\) sorgusunda implementasyon \(x\)'i onluk yazıya çevirir, soldan sağa ilerler ve mevcut konumda üst sınır rakamından küçük bir seçim mümkün olduğunda, önceden hesaplanmış asal-tamamlayan son ek sayısını toplama ekler. Tarama tamamlanınca üst sınırın kendisinin de geçerli olup olmadığı kontrol edilir.
\(n\). geçerli tamsayıyı bulmak için de önce üst sınır tekrar tekrar iki katına çıkarılır; yeterince geçerli sayı kapsandıktan sonra bu aralıkta standart bir ikili arama yapılır. Böylece aradaki tüm sayıları kaba kuvvetle taramaya gerek kalmaz.
\(D\) maksimum basamak sayısı, \(S=9D\) maksimum rakam toplamı olsun. Asal tablosunun kurulması \(O(S\log\log S)\) sürer. \(W\) tablosu \(O(10DS)\) zamanda hazırlanır. Burada kullanılan doğrudan yöntemle \(G\) tablosunun kurulması \(O(DS^2)\) maliyetlidir; çünkü her \((r,p)\) durumu için tüm mümkün kuyruk toplamları taranır.
Tek bir \(C(x)\) sorgusu \(O(10D)\) sürer: \(D\) konum vardır ve her konumda en fazla 10 rakam denenir. Son arama, cevap \(X\) olmak üzere \(O(\log X)\) adet böyle sorgu kullanır. Bellek kullanımı \(O(DS)\)'dir. Bu implementasyonlarda \(D=20\) ve \(S=180\) olduğundan sabitler küçüktür.
Buscamos el \(n\)-ésimo entero positivo cuya suma decimal de dígitos es prima. Probar los números uno a uno sería demasiado lento para el objetivo real, así que la solución primero cuenta cuántos valores válidos hay en \([1,x]\) y luego encuentra el primer \(x\) para el que ese conteo alcanza \(n\).
Sea \(s(x)\) la suma de dígitos en base 10 y sea \(\mathcal{P}\) el conjunto de los números primos. La función central es
$$C(x)=\#\{1\le m\le x : s(m)\in\mathcal{P}\}.$$
Una vez que \(C(x)\) se puede evaluar con rapidez, la respuesta es el menor \(x\) que satisface \(C(x)\ge n\).
El método es una digit-DP. En vez de enumerar todos los números hasta \(x\), cuenta los sufijos posibles por su suma de dígitos y reutiliza esos conteos mientras recorre la representación decimal de \(x\).
Las implementaciones reservan tablas para como máximo \(D=20\) posiciones decimales, así que la mayor suma relevante es \(S=9D=180\).
Para \(\ell\ge 0\) y \(0\le t\le S\), definimos
$$W(\ell,t)=\#\{(d_1,\dots,d_\ell)\in\{0,\dots,9\}^{\ell}: d_1+\cdots+d_\ell=t\}.$$
Se permiten ceros a la izquierda. Eso es importante porque una cadena como \(04\) representa el número ordinario \(4\), de modo que la misma tabla también cubre automáticamente los números más cortos cuando después se compara contra una cota de longitud fija.
Las condiciones iniciales son
$$W(0,0)=1,\qquad W(0,t)=0\text{ para }t>0,$$
y la recurrencia es
$$W(\ell,t)=\sum_{d=0}^{9} W(\ell-1,t-d),$$
entendiendo que \(W(\ell,u)=0\) cuando \(u \lt 0\). Una vez construida esta tabla, sabemos cuántos sufijos de cualquier longitud restante producen una suma concreta.
Supongamos que un prefijo ya aporta suma \(p\), y que faltan \(r\) dígitos por elegir. Queremos saber cuántas colas hacen que la suma final sea prima. Definimos
$$G(r,p)=\sum_{\substack{u\ge 0\\ p+u\in\mathcal{P}}} W(r,u).$$
Así, \(G(r,p)\) cuenta todos los sufijos de longitud \(r\) cuya suma \(u\) transforma la suma parcial \(p\) en un total primo \(p+u\). Esta segunda tabla es el oráculo de conteo usado en cada consulta.
Como la suma total nunca supera \(180\), basta con precalcular una vez la primalidad mediante un cribado pequeño y reutilizarla en todos los estados \((r,p)\).
Escribimos la expansión decimal de \(x\) como \(x_0x_1\dots x_{k-1}\), y definimos
$$\sigma_i=x_0+x_1+\cdots+x_{i-1}$$
como la suma de los dígitos estrictamente anteriores a la posición \(i\), con \(\sigma_0=0\).
Al recorrer de izquierda a derecha, en la posición \(i\) podemos seguir el dígito real \(x_i\) o elegir un dígito menor \(d \lt x_i\). Si elegimos uno menor, las \(k-1-i\) posiciones restantes quedan libres, y su contribución es exactamente
$$G(k-1-i,\sigma_i+d).$$
Al sumar esto sobre todas las posiciones y todos los dígitos menores, obtenemos todos los números válidos estrictamente inferiores a \(x\). Al final añadimos uno más si la suma de dígitos de \(x\) es prima. En forma compacta,
$$C(x)=\sum_{i=0}^{k-1}\sum_{d=0}^{x_i-1} G(k-1-i,\sigma_i+d)+\varepsilon(x),$$
donde \(\varepsilon(x)=1\) cuando \(s(x)\in\mathcal{P}\), y \(\varepsilon(x)=0\) en caso contrario.
Si \(x\) tiene \(k\) dígitos, cualquier entero positivo con menos de \(k\) dígitos puede verse como una cadena de longitud \(k\) añadiendo ceros delante. Por ejemplo, \(37\) se trata como \(037\) frente a una cota de 3 dígitos.
Eso evita dividir el problema en casos separados para números de 1 dígito, 2 dígitos y así sucesivamente. El número \(0\) no molesta, porque su suma de dígitos es \(0\) y \(0\notin\mathcal{P}\).
La función \(C(x)\) es no decreciente, porque ampliar \([1,x]\) solo puede añadir más enteros válidos. Por tanto, el valor buscado es
$$\min\{x\ge 1 : C(x)\ge n\}.$$
Las implementaciones primero hacen crecer una cota superior duplicándola hasta que el conteo alcanza \(n\). Una vez encontrada esa cota, una búsqueda binaria ordinaria aísla el primer \(x\) con \(C(x)\ge n\).
Un buen punto de control es que el entero positivo número 61 con suma de dígitos prima es \(157\). La digit-DP lo explica de forma limpia.
Primero consideremos todos los números entre \(0\) y \(99\). Usando cadenas de 2 dígitos con ceros iniciales, las sumas primas son \(2,3,5,7,11,13,17\). La tabla \(W(2,t)\) da
$$W(2,2)=3,\quad W(2,3)=4,\quad W(2,5)=6,\quad W(2,7)=8,\quad W(2,11)=8,\quad W(2,13)=6,\quad W(2,17)=2,$$
de modo que
$$G(2,0)=3+4+6+8+8+6+2=37.$$
Así, exactamente \(37\) números de \([1,99]\) tienen suma de dígitos prima.
Ahora pasemos a los números menores que \(157\). Fijamos la centena igual a \(1\). Para una decena menor que \(5\), las sumas parciales posibles son \(1,2,3,4,5\). La tabla de sufijos de 1 dígito da
$$G(1,1)=4,\quad G(1,2)=5,\quad G(1,3)=4,\quad G(1,4)=4,\quad G(1,5)=4,$$
y por ello el bloque \(100\) a \(149\) aporta
$$4+5+4+4+4=21.$$
Finalmente, entre \(150\) y \(156\), solo \(151\) y \(155\) tienen suma de dígitos prima, así que este último bloque parcial aporta \(2\). Por tanto,
$$C(156)=37+21+2=60.$$
Como \(1+5+7=13\) es primo, \(157\) también es válido, y entonces
$$C(157)=61.$$
Por eso el término 61 es exactamente \(157\), igual que verifican las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero precalculan la primalidad de todas las sumas de dígitos posibles entre \(0\) y \(180\). Después construyen la tabla \(W(\ell,t)\) para todas las longitudes hasta \(20\) y, a partir de ella, la tabla de completación de sufijos \(G(r,p)\).
Para una consulta \(C(x)\), la implementación convierte \(x\) a decimal, recorre sus dígitos de izquierda a derecha y, cada vez que en una posición se puede elegir un dígito menor que el de la cota, añade el número ya precalculado de colas que completan a suma prima. Al final también comprueba si la propia cota es válida.
Para obtener el \(n\)-ésimo entero válido, la implementación duplica una cota superior hasta abarcar suficientes soluciones y luego aplica búsqueda binaria estándar sobre ese intervalo. No hace falta recorrer a la fuerza todos los enteros intermedios.
Sea \(D\) el número máximo de dígitos y \(S=9D\) la suma máxima. Construir la tabla de primalidad cuesta \(O(S\log\log S)\). Construir \(W\) cuesta \(O(10DS)\). Construir la tabla \(G\) en la forma directa usada aquí cuesta \(O(DS^2)\), porque cada estado \((r,p)\) recorre todas las sumas de cola factibles.
Una evaluación de \(C(x)\) cuesta \(O(10D)\): hay \(D\) posiciones y, en cada una, a lo sumo 10 dígitos candidatos. La búsqueda final usa \(O(\log X)\) evaluaciones de este tipo, donde \(X\) es la respuesta. La memoria es \(O(DS)\). En estas implementaciones, \(D=20\) y \(S=180\), así que los factores constantes son pequeños.
题目要求找出“十进制数位和为素数”的第 \(n\) 个正整数。如果从 \(1\) 开始逐个检查，面对真实目标会非常慢，所以解法先回答另一个问题：在区间 \([1,x]\) 中到底有多少个满足条件的整数。只要这个计数函数能快速计算，最终答案就是第一个使计数达到 \(n\) 的 \(x\)。
记 \(s(x)\) 为 \(x\) 的十进制数位和，记 \(\mathcal{P}\) 为素数集合。核心函数定义为
$$C(x)=\#\{1\le m\le x : s(m)\in\mathcal{P}\}.$$
因此整道题可以分成两层：先高效计算 \(C(x)\)，再用单调性找到最小的 \(x\) 使得 \(C(x)\ge n\)。
这里使用的是典型的 digit DP。它并不枚举所有不超过 \(x\) 的整数，而是先统计“剩余若干位能够形成哪些数位和”，再在扫描 \(x\) 的十进制表示时，把这些统计结果反复复用。
实现中为最多 \(D=20\) 个十进制位置预留状态，因此最大的相关数位和是 \(S=9D=180\)。这使得状态空间非常小，适合一次预处理后反复查询。
对 \(\ell\ge 0\) 和 \(0\le t\le S\)，定义
$$W(\ell,t)=\#\{(d_1,\dots,d_\ell)\in\{0,\dots,9\}^{\ell}: d_1+\cdots+d_\ell=t\}.$$
这里允许前导零。这个细节非常关键，因为像 \(04\) 这样的 2 位数字串，本质上就对应普通整数 \(4\)。因此，一旦我们把所有长度固定为某个上界，较短的数字会自动以“前面补零”的形式被纳入同一张表中。
初始条件是
$$W(0,0)=1,\qquad W(0,t)=0\text{ for }t>0,$$
递推式为
$$W(\ell,t)=\sum_{d=0}^{9} W(\ell-1,t-d),$$
并约定当 \(u \lt 0\) 时 \(W(\ell,u)=0\)。这张表建好以后，我们就知道“还剩 \(\ell\) 位时，数位和恰好为 \(t\) 的尾部”一共有多少种。
假设当前已经固定了一个前缀，它的数位和是 \(p\)，并且还剩 \(r\) 位没有选。我们需要的不是任意尾部，而是那些能让最终总和变成素数的尾部。于是定义
$$G(r,p)=\sum_{\substack{u\ge 0\\ p+u\in\mathcal{P}}} W(r,u).$$
这里的含义非常直接：\(G(r,p)\) 表示“在当前前缀和为 \(p\) 的情况下，长度为 \(r\) 的尾部中，有多少个会把总和补成素数”。也就是说，\(G\) 表正是后续查询 \(C(x)\) 时真正要调用的计数工具。
因为最终总和最大只有 \(180\)，所以只需要先对 \(0\) 到 \(180\) 做一次很小的素数筛，之后所有状态 \((r,p)\) 都可以复用这份素性信息。
把 \(x\) 的十进制展开写成 \(x_0x_1\dots x_{k-1}\)，再定义
$$\sigma_i=x_0+x_1+\cdots+x_{i-1}$$
表示位置 \(i\) 之前所有数字的和，其中 \(\sigma_0=0\)。
当我们从左到右扫描 \(x\) 时，在第 \(i\) 位有两种选择：要么继续沿着真实数字 \(x_i\) 往下走；要么在这里改选一个更小的数字 \(d \lt x_i\)。一旦改选了更小的数字，后面的 \(k-1-i\) 位就不再受到上界限制，因此它们的贡献恰好是
$$G(k-1-i,\sigma_i+d).$$
把所有位置、所有更小数字的贡献加起来，就得到了所有严格小于 \(x\) 的合法整数数量。扫描完整个 \(x\) 之后，如果 \(x\) 自己的数位和也是素数，还要再加上 \(1\)。因此可以写成
$$C(x)=\sum_{i=0}^{k-1}\sum_{d=0}^{x_i-1} G(k-1-i,\sigma_i+d)+\varepsilon(x),$$
其中 \(\varepsilon(x)=1\) 当且仅当 \(s(x)\in\mathcal{P}\)，否则 \(\varepsilon(x)=0\)。
如果上界 \(x\) 有 \(k\) 位，那么所有位数少于 \(k\) 的正整数都可以看成一个长度为 \(k\) 的数字串，只不过前面补了一些零。比如在 3 位上界下，数字 \(37\) 会被当作 \(037\) 来处理。
这样做的好处是，我们完全不必分别讨论“1 位数有多少个、2 位数有多少个、3 位数有多少个”。同一套递推和同一套查询公式就能把它们全部覆盖。至于数字 \(0\)，它虽然也会以全零串出现，但它的数位和是 \(0\)，而 \(0\) 不是素数，所以不会被错误计入答案。
函数 \(C(x)\) 是单调不减的，因为区间 \([1,x]\) 变大以后，只可能包含更多满足条件的整数，不可能减少。于是目标答案就是
$$\min\{x\ge 1 : C(x)\ge n\}.$$
实现中先不断把上界翻倍，直到当前上界已经包含至少 \(n\) 个合法整数。找到这样一个区间后，再在其中做标准二分查找，定位第一个满足 \(C(x)\ge n\) 的 \(x\)。
一个很好的校验点是：数位和为素数的第 61 个正整数等于 \(157\)。这个结论可以直接用上面的 digit DP 过程解释出来。
先看 \(0\) 到 \(99\)。把它们视为允许前导零的 2 位数字串后，素数数位和只有 \(2,3,5,7,11,13,17\)。由 \(W(2,t)\) 可得
$$W(2,2)=3,\quad W(2,3)=4,\quad W(2,5)=6,\quad W(2,7)=8,\quad W(2,11)=8,\quad W(2,13)=6,\quad W(2,17)=2,$$
于是
$$G(2,0)=3+4+6+8+8+6+2=37.$$
这说明区间 \([1,99]\) 里恰好有 \(37\) 个数的数位和是素数。
接下来处理小于 \(157\) 的三位数。先把百位固定为 \(1\)。当十位取比 \(5\) 小的数字时，前缀和依次是 \(1,2,3,4,5\)。对于只剩 1 位的尾部，表 \(G\) 给出
$$G(1,1)=4,\quad G(1,2)=5,\quad G(1,3)=4,\quad G(1,4)=4,\quad G(1,5)=4,$$
所以整个 \(100\) 到 \(149\) 区间贡献
$$4+5+4+4+4=21.$$
最后看 \(150\) 到 \(156\)。其中只有 \(151\) 和 \(155\) 的数位和为素数，因此这一段再贡献 \(2\)。于是
$$C(156)=37+21+2=60.$$
而 \(157\) 本身的数位和是 \(1+5+7=13\)，仍然是素数，所以
$$C(157)=61.$$
这就说明第 61 个满足条件的正整数正是 \(157\)，与实现中的校验结果完全一致。
C++、Python 和 Java 实现遵循同一条流程。第一步是预处理 \(0\) 到 \(180\) 所有可能数位和的素性。第二步是填出所有长度不超过 \(20\) 的 \(W(\ell,t)\) 表。第三步根据这张表构造“前缀和为 \(p\)、剩余 \(r\) 位时可补成素数”的 \(G(r,p)\) 表。
在执行一次 \(C(x)\) 查询时，实现会把 \(x\) 转成十进制字符串，按位从左向右扫描。每当某一位可以选择一个比上界更小的数字时，就把对应的“合法尾部个数”直接加到答案里。全部位扫描结束后，再单独判断上界 \(x\) 自己是否也应该计入。
为了求第 \(n\) 个合法整数，实现先不断扩张上界，直到合法整数数量不少于 \(n\)，然后再在这个区间里做标准二分。整个过程避免了对中间所有整数进行暴力测试。
设 \(D\) 为最大位数，\(S=9D\) 为最大数位和。素数筛的代价是 \(O(S\log\log S)\)。构造 \(W\) 表需要 \(O(10DS)\)。按这里的直接写法，构造 \(G\) 表需要 \(O(DS^2)\)，因为每个状态 \((r,p)\) 都会遍历所有可行的尾部和。
单次计算 \(C(x)\) 的代价是 \(O(10D)\)：总共有 \(D\) 个位置，每个位置最多尝试 10 个候选数字。最后的搜索需要 \(O(\log X)\) 次这样的查询，其中 \(X\) 是答案本身。空间复杂度为 \(O(DS)\)。在这些实现里 \(D=20\)、\(S=180\)，所以常数非常小。
Нужно найти \(n\)-е положительное число, у которого сумма десятичных цифр является простым числом. Полный перебор подряд слишком медленный для реальной цели, поэтому решение сначала умеет быстро считать, сколько подходящих чисел лежит в \([1,x]\), а затем находит первое \(x\), при котором этот счетчик достигает \(n\).
Пусть \(s(x)\) обозначает сумму цифр числа \(x\) в десятичной записи, а \(\mathcal{P}\) — множество простых чисел. Основная функция подсчета имеет вид
$$C(x)=\#\{1\le m\le x : s(m)\in\mathcal{P}\}.$$
Как только \(C(x)\) можно вычислять быстро, ответом становится наименьшее \(x\), для которого \(C(x)\ge n\).
Здесь используется digit DP. Вместо того чтобы рассматривать каждое число до \(x\) по отдельности, метод заранее считает, сколько суффиксов дают ту или иную сумму цифр, а затем многократно использует эти данные при проходе по десятичной записи \(x\).
В реализациях таблицы рассчитаны максимум на \(D=20\) десятичных позиций, поэтому максимальная сумма цифр равна \(S=9D=180\).
Для \(\ell\ge 0\) и \(0\le t\le S\) определим
$$W(\ell,t)=\#\{(d_1,\dots,d_\ell)\in\{0,\dots,9\}^{\ell}: d_1+\cdots+d_\ell=t\}.$$
Ведущие нули разрешены. Это важно, потому что строка \(04\) представляет обычное число \(4\), а значит одна и та же таблица автоматически охватывает и более короткие числа, когда позже мы сравниваем их с верхней границей фиксированной длины.
Начальные условия таковы:
$$W(0,0)=1,\qquad W(0,t)=0\text{ при }t>0,$$
а рекуррентная формула имеет вид
$$W(\ell,t)=\sum_{d=0}^{9} W(\ell-1,t-d),$$
причем \(W(\ell,u)=0\), если \(u \lt 0\). После построения этой таблицы мы знаем, сколько хвостов любой оставшейся длины дают нужную сумму цифр.
Пусть уже выбранный префикс дает сумму цифр \(p\), и осталось выбрать еще \(r\) цифр. Нас интересуют только те хвосты, которые делают итоговую сумму простой. Для этого вводим
$$G(r,p)=\sum_{\substack{u\ge 0\\ p+u\in\mathcal{P}}} W(r,u).$$
Иначе говоря, \(G(r,p)\) считает все суффиксы длины \(r\), чья сумма \(u\) превращает текущую сумму префикса \(p\) в простое число \(p+u\). Именно эта таблица служит счетным оракулом при каждом запросе.
Так как итоговая сумма никогда не превосходит \(180\), простоту можно один раз предвычислить небольшим решетом и затем использовать для всех состояний \((r,p)\).
Запишем десятичное представление \(x\) как \(x_0x_1\dots x_{k-1}\), и пусть
$$\sigma_i=x_0+x_1+\cdots+x_{i-1}$$
обозначает сумму цифр строго левее позиции \(i\), причем \(\sigma_0=0\).
При проходе слева направо на позиции \(i\) можно либо взять реальную цифру \(x_i\), либо выбрать меньшую цифру \(d \lt x_i\). Если выбрана меньшая цифра, то оставшиеся \(k-1-i\) позиций уже ничем не ограничены, и их вклад равен
$$G(k-1-i,\sigma_i+d).$$
Суммирование по всем позициям и по всем меньшим цифрам дает количество всех подходящих чисел, строго меньших \(x\). После завершения прохода нужно добавить еще \(1\), если сумма цифр самого \(x\) проста. Компактная запись такова:
$$C(x)=\sum_{i=0}^{k-1}\sum_{d=0}^{x_i-1} G(k-1-i,\sigma_i+d)+\varepsilon(x),$$
где \(\varepsilon(x)=1\), если \(s(x)\in\mathcal{P}\), и \(\varepsilon(x)=0\) в противном случае.
Если у верхней границы \(x\) ровно \(k\) цифр, то любое положительное число с меньшим числом цифр можно представить как строку длины \(k\), дополнив ее нулями слева. Например, число \(37\) при сравнении с трехзначной границей рассматривается как \(037\).
Благодаря этому не нужно отдельно разбирать однозначные, двузначные и другие более короткие числа. Число \(0\) не создает проблем, потому что сумма его цифр равна \(0\), а \(0\notin\mathcal{P}\).
Функция \(C(x)\) монотонно не убывает: если расширить интервал \([1,x]\), подходящих чисел может стать только больше. Следовательно, искомый ответ равен
$$\min\{x\ge 1 : C(x)\ge n\}.$$
Реализации сначала многократно удваивают верхнюю границу, пока счетчик не достигнет \(n\). После этого обычный бинарный поиск находит первое \(x\), для которого выполняется \(C(x)\ge n\).
Удобная контрольная точка такова: 61-е положительное число с простой суммой цифр равно \(157\). Это легко увидеть через ту же digit DP.
Сначала рассмотрим все числа от \(0\) до \(99\). Если записывать их как 2-значные строки с ведущими нулями, то простые суммы цифр равны \(2,3,5,7,11,13,17\). Таблица \(W(2,t)\) дает
$$W(2,2)=3,\quad W(2,3)=4,\quad W(2,5)=6,\quad W(2,7)=8,\quad W(2,11)=8,\quad W(2,13)=6,\quad W(2,17)=2,$$
поэтому
$$G(2,0)=3+4+6+8+8+6+2=37.$$
Значит, в диапазоне \([1,99]\) имеется ровно \(37\) чисел с простой суммой цифр.
Теперь перейдем к числам меньше \(157\). Зафиксируем сотни равными \(1\). Если десятки меньше \(5\), то возможные суммы префикса равны \(1,2,3,4,5\). Таблица одноразрядных суффиксов дает
$$G(1,1)=4,\quad G(1,2)=5,\quad G(1,3)=4,\quad G(1,4)=4,\quad G(1,5)=4,$$
и потому блок от \(100\) до \(149\) добавляет
$$4+5+4+4+4=21.$$
В последнем неполном блоке \(150\)–\(156\) только числа \(151\) и \(155\) имеют простую сумму цифр, так что добавляется еще \(2\). Следовательно,
$$C(156)=37+21+2=60.$$
Так как \(1+5+7=13\) — простое число, само \(157\) тоже подходит, и мы получаем
$$C(157)=61.$$
Тем самым 61-е подходящее число действительно равно \(157\), в точности как показывают реализации.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала они предвычисляют простоту всех возможных сумм цифр от \(0\) до \(180\). Затем строят таблицу \(W(\ell,t)\) для всех длин до \(20\), а после этого — таблицу \(G(r,p)\), показывающую, сколько хвостов дополняют текущую сумму до простой.
При запросе \(C(x)\) реализация переводит \(x\) в десятичную строку, проходит ее слева направо и каждый раз, когда в текущей позиции можно выбрать цифру меньше цифры верхней границы, сразу добавляет заранее посчитанное число допустимых хвостов. После полного прохода отдельно проверяется, нужно ли включить саму границу \(x\).
Чтобы получить \(n\)-е подходящее число, реализация сначала расширяет верхнюю границу удвоением, пока подходящих чисел не станет достаточно, а затем выполняет стандартный бинарный поиск по найденному интервалу. Полный перебор промежуточных чисел не требуется.
Пусть \(D\) — максимальное число цифр, а \(S=9D\) — максимальная сумма цифр. Построение таблицы простоты требует \(O(S\log\log S)\). Построение \(W\) занимает \(O(10DS)\). Построение таблицы \(G\) в прямой форме, использованной здесь, стоит \(O(DS^2)\), потому что для каждого состояния \((r,p)\) перебираются все допустимые суммы хвоста.
Один вызов \(C(x)\) стоит \(O(10D)\): есть \(D\) позиций и не более 10 кандидатных цифр в каждой. Финальный поиск использует \(O(\log X)\) таких вызовов, где \(X\) — ответ. Память равна \(O(DS)\). В этих реализациях \(D=20\) и \(S=180\), так что константы малы.
نريد إيجاد العدد الموجب رقم \(n\) الذي يكون مجموع أرقامه العشرية عددًا أوليًا. فحص الأعداد واحدًا واحدًا بطيء جدًا للهدف الحقيقي، لذلك تحسب الفكرة أولًا عدد القيم الصالحة داخل الفترة \([1,x]\)، ثم تبحث عن أول \(x\) يصل عنده هذا العد إلى \(n\).
لنرمز إلى مجموع الأرقام العشري بالرمز \(s(x)\)، ولتكن \(\mathcal{P}\) مجموعة الأعداد الأولية. دالة العد الأساسية هي
$$C(x)=\#\{1\le m\le x : s(m)\in\mathcal{P}\}.$$
متى أمكن حساب \(C(x)\) بسرعة، تصبح الإجابة هي أصغر \(x\) يحقق \(C(x)\ge n\).
الطريقة هنا هي digit DP. بدلًا من تعداد كل عدد حتى \(x\)، نقوم أولًا بعدّ الذيول الممكنة بحسب مجموع أرقامها، ثم نعيد استخدام هذه النتائج أثناء المرور على التمثيل العشري لـ \(x\) من اليسار إلى اليمين.
التنفيذات تحجز جداول لما يصل إلى \(D=20\) منزلة عشرية، ولذلك فإن أكبر مجموع أرقام ذي صلة هو \(S=9D=180\).
لكل \(\ell\ge 0\) و\(0\le t\le S\) نعرّف
$$W(\ell,t)=\#\{(d_1,\dots,d_\ell)\in\{0,\dots,9\}^{\ell}: d_1+\cdots+d_\ell=t\}.$$
نسمح بالأصفار البادئة. هذه نقطة مهمة، لأن سلسلة مثل \(04\) تمثل في الحقيقة العدد العادي \(4\)، وبالتالي فإن الجدول نفسه يغطي تلقائيًا الأعداد الأقصر عندما نقارن لاحقًا بحد أعلى ذي طول ثابت.
شروط البداية هي
$$W(0,0)=1,\qquad W(0,t)=0\text{ for }t>0,$$
أما علاقة الانتقال فهي
$$W(\ell,t)=\sum_{d=0}^{9} W(\ell-1,t-d),$$
مع الاتفاق على أن \(W(\ell,u)=0\) إذا كان \(u \lt 0\). بعد بناء هذا الجدول نعرف عدد الذيول ذات أي طول متبقٍّ والتي تعطي مجموع أرقام محددًا.
لنفترض أن بادئة العدد تعطي مجموعًا يساوي \(p\)، وما زال أمامنا \(r\) منازل نختارها. نريد فقط الذيول التي تجعل المجموع النهائي أوليًا. لذلك نعرّف
$$G(r,p)=\sum_{\substack{u\ge 0\\ p+u\in\mathcal{P}}} W(r,u).$$
إذن \(G(r,p)\) هو عدد الذيول ذات الطول \(r\) التي يكون مجموعها \(u\) بحيث يصبح المجموع الكلي \(p+u\) عددًا أوليًا. هذا هو جدول العد الحقيقي الذي تعتمد عليه كل استعلامات الحل.
وبما أن المجموع النهائي لا يمكن أن يتجاوز \(180\)، فيكفي إجراء غربال صغير للأعداد الأولية مرة واحدة ثم إعادة استخدامه في جميع الحالات \((r,p)\).
لنكتب التمثيل العشري لـ \(x\) على الصورة \(x_0x_1\dots x_{k-1}\)، ولنعرّف
$$\sigma_i=x_0+x_1+\cdots+x_{i-1}$$
على أنه مجموع الأرقام الواقعة قبل المنزلة \(i\)، مع \(\sigma_0=0\).
عند المسح من اليسار إلى اليمين توجد عند المنزلة \(i\) حالتان: إما أن نتابع بالرقم الحقيقي \(x_i\)، أو نختار رقمًا أصغر \(d \lt x_i\). إذا اخترنا رقمًا أصغر، فإن المنازل الباقية وعددها \(k-1-i\) تصبح حرة بالكامل، وعندها يكون إسهامها مساويًا تمامًا لـ
$$G(k-1-i,\sigma_i+d).$$
عند جمع هذا المقدار على جميع المنازل وجميع الاختيارات الأصغر، نحصل على عدد الأعداد الصالحة الأصغر من \(x\). وبعد انتهاء المسح نضيف \(1\) أخرى إذا كان مجموع أرقام \(x\) نفسه أوليًا. والصيغة المختصرة هي
$$C(x)=\sum_{i=0}^{k-1}\sum_{d=0}^{x_i-1} G(k-1-i,\sigma_i+d)+\varepsilon(x),$$
حيث \(\varepsilon(x)=1\) عندما يكون \(s(x)\in\mathcal{P}\)، وإلا فالقيمة \(\varepsilon(x)=0\).
إذا كان للحد الأعلى \(x\) عدد منازل يساوي \(k\)، فإن كل عدد موجب أقصر من ذلك يمكن تمثيله كسلسلة بطول \(k\) بعد إضافة أصفار من اليسار. على سبيل المثال، يعامل العدد \(37\) على أنه \(037\) عند المقارنة مع حد أعلى مكوَّن من ثلاث منازل.
وبهذا لا نحتاج إلى فصل الحالة إلى أعداد من منزلة واحدة أو منزلتين أو أكثر. أما العدد \(0\) فلا يسبب مشكلة، لأن مجموع أرقامه يساوي \(0\)، و\(0\notin\mathcal{P}\).
الدالة \(C(x)\) غير متناقصة، لأن تكبير الفترة \([1,x]\) لا يمكن إلا أن يضيف أعدادًا صالحة جديدة. لذلك فإن الجواب المطلوب هو
$$\min\{x\ge 1 : C(x)\ge n\}.$$
التنفيذات تبدأ بتوسيع حد أعلى عبر المضاعفة المتكررة حتى يصل العد إلى \(n\). وبعد العثور على هذا الحد، يُستخدم بحث ثنائي عادي لعزل أول \(x\) يحقق \(C(x)\ge n\).
من نقاط التحقق المفيدة أن العدد الموجب رقم 61 الذي يكون مجموع أرقامه أوليًا هو \(157\). ويمكن تفسير ذلك مباشرة بنفس digit DP.
لنبدأ بالأعداد من \(0\) إلى \(99\). إذا اعتبرناها سلاسل من منزلتين مع السماح بالأصفار البادئة، فإن مجاميع الأرقام الأولية الممكنة هي \(2,3,5,7,11,13,17\). ومن جدول \(W(2,t)\) نحصل على
$$W(2,2)=3,\quad W(2,3)=4,\quad W(2,5)=6,\quad W(2,7)=8,\quad W(2,11)=8,\quad W(2,13)=6,\quad W(2,17)=2,$$
ومن ثم
$$G(2,0)=3+4+6+8+8+6+2=37.$$
وهذا يعني أن عدد الأعداد في \([1,99]\) ذات مجموع الأرقام الأولي يساوي \(37\) بالضبط.
الآن ننتقل إلى الأعداد الأصغر من \(157\). نثبت منزلة المئات مساوية لـ \(1\). إذا كانت منزلة العشرات أصغر من \(5\)، فإن مجاميع البادئة الممكنة هي \(1,2,3,4,5\). جدول الذيول ذات المنزلة الواحدة يعطينا
$$G(1,1)=4,\quad G(1,2)=5,\quad G(1,3)=4,\quad G(1,4)=4,\quad G(1,5)=4,$$
ولذلك فإن الكتلة من \(100\) إلى \(149\) تسهم بمقدار
$$4+5+4+4+4=21.$$
وفي الجزء الأخير من \(150\) إلى \(156\)، لا يملك مجموع أرقام أوليًا إلا العددان \(151\) و\(155\)، فيكون الإسهام \(2\). إذن
$$C(156)=37+21+2=60.$$
وبما أن \(1+5+7=13\) عدد أولي، فإن \(157\) نفسه صالح أيضًا، ومن ثم
$$C(157)=61.$$
وعليه فإن الحد رقم 61 هو فعلًا \(157\)، تمامًا كما تؤكد التنفيذات.
تنفيذات C++ وPython وJava تتبع المسار نفسه. فهي تبدأ بحساب أولية كل مجموع أرقام ممكن من \(0\) إلى \(180\). ثم تبني جدول \(W(\ell,t)\) لجميع الأطوال حتى \(20\)، وبعد ذلك تبني جدول \(G(r,p)\) الذي يخبرنا بعدد الذيول التي تكمل مجموع البادئة إلى عدد أولي.
عند تنفيذ استعلام \(C(x)\)، يحول التنفيذ العدد \(x\) إلى تمثيله العشري، ويمسح الأرقام من اليسار إلى اليمين. وكلما أمكن اختيار رقم أصغر من رقم الحد الأعلى في موضع ما، أضيف مباشرة عدد الذيول الصالحة المحسوب مسبقًا. وبعد نهاية المسح يُفحص أيضًا ما إذا كان \(x\) نفسه يجب أن يُحسب.
ولإيجاد العدد الصالح رقم \(n\)، يضاعف التنفيذ حدًا أعلى حتى يغطي عددًا كافيًا من الحلول، ثم يطبق بحثًا ثنائيًا قياسيًا داخل ذلك المجال. وبهذا لا توجد حاجة إلى فحص الأعداد الوسيطة بالقوة الغاشمة.
إذا كان \(D\) هو أقصى عدد منازل و\(S=9D\) هو أقصى مجموع أرقام، فإن بناء جدول الأولية يكلف \(O(S\log\log S)\). وبناء جدول \(W\) يكلف \(O(10DS)\). أما بناء جدول \(G\) بالطريقة المباشرة المستعملة هنا فيكلف \(O(DS^2)\)، لأن كل حالة \((r,p)\) تمسح جميع مجاميع الذيول الممكنة.
حساب \(C(x)\) مرة واحدة يكلف \(O(10D)\): توجد \(D\) منازل، وفي كل منزلة يوجد على الأكثر 10 اختيارات رقمية مرشحة. والبحث النهائي يحتاج إلى \(O(\log X)\) من هذه الاستعلامات، حيث \(X\) هو الجواب. أما الذاكرة فتساوي \(O(DS)\). وفي هذه التنفيذات تحديدًا لدينا \(D=20\) و\(S=180\)، لذا فالثوابت صغيرة.