For each digit \(d \in \{0,1,\dots,9\}\), let \(M(10,d)\) be the largest number of times that \(d\) can appear in a 10-digit prime, and let \(S(10,d)\) be the sum of all 10-digit primes that attain this maximum repetition count. The goal is to compute
$$\sum_{d=0}^{9} S(10,d).$$
The important point is that the optimization is digit-specific. For each fixed digit \(d\), we are not looking for all primes with many repeated digits in general; we are looking for primes with as many copies of that one chosen digit as possible.
The implementations solve the problem by turning "maximum repetition" into the equivalent question "how few positions must be changed before a prime appears?" That reformulation matches the combinatorial structure of the search exactly.
Fix a digit \(d\). Let \(r_d\) be the smallest integer \(r \ge 1\) for which there exists a 10-digit prime with exactly \(r\) digits different from \(d\). Then a prime found at that first successful level contains \(10-r_d\) copies of \(d\), so
$$M(10,d)=10-r_d.$$
If we write \(\mathcal{P}(d,r)\) for the set of 10-digit primes with exactly \(r\) non-\(d\) digits, then the desired sum for digit \(d\) is
$$S(10,d)=\sum_{p\in \mathcal{P}(d,r_d)} p.$$
This is why the search can stop immediately once primes are found: any larger value of \(r\) would only decrease the number of repeated \(d\)'s, so it can never improve \(M(10,d)\).
For a fixed pair \((d,r)\), start from the word \(dddddddddd\). Choose a set \(P\subseteq\{0,1,\dots,9\}\) of \(r\) positions that will be changed, and then assign to each chosen position a digit from \(\{0,\dots,9\}\setminus\{d\}\). Because changed positions are forced to receive digits different from \(d\), every valid assignment has exactly \(r\) non-\(d\) digits and is generated exactly once.
Before any decimal or primality filters, the raw search space at level \(r\) is therefore
$$\binom{10}{r} 9^r.$$
This factorization into combinations of positions and assignments of digits is the central combinatorial object in the solution, and all three implementations mirror it directly.
Not every assignment can represent a 10-digit prime. Two elementary facts eliminate many cases before primality testing.
First, the leading digit cannot be zero. If \(d=0\) and the first position is not among the changed positions, then the candidate is not a 10-digit integer at all.
Second, every prime greater than \(5\) ends in \(1\), \(3\), \(7\), or \(9\). So if the last position is unchanged and \(d\notin\{1,3,7,9\}\), that entire pattern is impossible. If the last position is changed, only digits in \(\{1,3,7,9\}\setminus\{d\}\) need to be tried there.
The C++ implementation applies the ending-digit rule explicitly before calling the prime test. The same mathematics is still present in the Python and Java versions, even when the filter is enforced implicitly by the prime test.
This is a good example of the difference between a structural argument and blind brute force. Suppose only one position were allowed to differ from \(0\).
If the first digit is not changed, the number begins with \(0\), so it is not a valid 10-digit number. If the first digit is the unique changed position, then the final digit is still \(0\), so the number is divisible by \(10\) and cannot be prime. Therefore one replacement is impossible for \(d=0\).
So we know immediately that
$$r_0\ge 2,\qquad M(10,0)\le 8.$$
The search still confirms this computationally, but the conclusion comes from place-value arithmetic alone.
Suppose the search reaches a value \(r\) and finds at least one prime. Then every one of those primes has exactly \(10-r\) copies of \(d\). On the other hand, the search has already proved that no prime exists for any smaller replacement count \(1,2,\dots,r-1\). Hence no 10-digit prime can contain more than \(10-r\) copies of \(d\), and the current level is automatically optimal.
That observation is the key invariant of the whole approach: descending repetition counts are equivalent to ascending replacement counts, and the first successful level already determines both \(M(10,d)\) and \(S(10,d)\).
The C++, Python, and Java implementations loop over \(d=0,1,\dots,9\). For each digit they try \(r=1,2,\dots,10\), where \(r\) is the number of positions that are not equal to \(d\). That is the computational version of searching for \(r_d\), the minimal replacement count.
At a fixed \((d,r)\), the implementation fills a 10-slot digit array with \(d\), enumerates all \(\binom{10}{r}\) choices of changed positions, and then enumerates all digit assignments on those positions that avoid the value \(d\). Because the repeated digit is restored after each branch, every completed array still represents a number with exactly \(10-r\) copies of \(d\).
Leading-zero cases are rejected immediately. The C++ implementation also skips numbers whose final digit is even or equal to \(5\), because such numbers cannot be prime unless the whole number is \(2\) or \(5\), which is impossible here.
Once a candidate passes the decimal filters, it is converted to an integer and tested for primality. The C++ implementation uses modular multiplication, modular exponentiation, and a deterministic Miller-Rabin test that is valid for 64-bit inputs in this range. The Python and Java implementations rely on mature high-level primality routines. All primes found at the first successful level for digit \(d\) are added together, and the final answer is the sum of those ten digit-specific totals.
If \(r_d\) is the first successful replacement count for digit \(d\), then the work for that digit is bounded by
$$O\!\left(\sum_{r=1}^{r_d}\binom{10}{r}9^r \cdot T_{\mathrm{prime}}\right),$$
where \(T_{\mathrm{prime}}\) is the cost of one primality test on a 10-digit integer. This expression is problem-adaptive: it measures exactly the amount of search the implementations perform before the optimal repetition count is certified.
Memory usage is \(O(10)\) for the current digit array plus small temporary storage for the primes found at the first successful level. Since the target length is fixed at 10 digits and the search stops as soon as the optimum is reached for each digit, the practical runtime is very small.
Für jede Ziffer \(d \in \{0,1,\dots,9\}\) sei \(M(10,d)\) die größte Anzahl von Vorkommen der Ziffer \(d\) in einer 10-stelligen Primzahl, und \(S(10,d)\) sei die Summe aller 10-stelligen Primzahlen, die genau dieses Maximum erreichen. Gesucht ist
$$\sum_{d=0}^{9} S(10,d).$$
Entscheidend ist, dass die Optimierung für jede Ziffer getrennt erfolgt. Für ein festes \(d\) suchen wir also nicht allgemein nach Primzahlen mit vielen Wiederholungen, sondern nach Primzahlen mit möglichst vielen Kopien genau dieser einen Ziffer.
Die Implementierungen formulieren das Problem dual: Statt direkt die maximale Wiederholungszahl zu suchen, fragen sie, wie wenige Stellen gegenüber einer vollständig aus \(d\) bestehenden Zahl geändert werden müssen, damit eine Primzahl entsteht.
Fixiere eine Ziffer \(d\). Sei \(r_d\) die kleinste ganze Zahl \(r \ge 1\), für die es eine 10-stellige Primzahl mit genau \(r\) von \(d\) verschiedenen Stellen gibt. Dann enthält jede Primzahl auf dieser ersten erfolgreichen Ebene genau \(10-r_d\) Kopien von \(d\), also gilt
$$M(10,d)=10-r_d.$$
Bezeichnen wir mit \(\mathcal{P}(d,r)\) die Menge aller 10-stelligen Primzahlen mit genau \(r\) Nicht-\(d\)-Stellen, dann ist
$$S(10,d)=\sum_{p\in \mathcal{P}(d,r_d)} p.$$
Deshalb darf die Suche sofort abbrechen, sobald Primzahlen gefunden wurden: Ein größeres \(r\) würde die Anzahl der wiederholten \(d\)'s nur verkleinern und kann \(M(10,d)\) nie verbessern.
Für ein festes Paar \((d,r)\) startet man mit dem Wort \(dddddddddd\). Danach wählt man eine Menge \(P\subseteq\{0,1,\dots,9\}\) von \(r\) Positionen, die verändert werden, und weist jeder dieser Positionen eine Ziffer aus \(\{0,\dots,9\}\setminus\{d\}\) zu. Da geänderte Positionen ausdrücklich nicht wieder \(d\) erhalten dürfen, wird jede gültige Zahl mit genau \(r\) Nicht-\(d\)-Stellen genau einmal erzeugt.
Vor allen Dezimal- und Primzahlfiltern hat die Suche auf Ebene \(r\) somit die rohe Größe
$$\binom{10}{r} 9^r.$$
Gerade diese Zerlegung in Positionswahl und Ziffernbelegung ist das zentrale kombinatorische Objekt der Lösung, und alle drei Implementierungen bilden sie direkt nach.
Nicht jede Belegung kann eine 10-stellige Primzahl darstellen. Zwei elementare Tatsachen eliminieren viele Fälle schon vor dem Primzahltest.
Erstens darf die führende Ziffer nicht \(0\) sein. Falls also \(d=0\) und die erste Position nicht unter den geänderten Stellen liegt, ist der Kandidat gar keine 10-stellige Zahl.
Zweitens endet jede Primzahl größer als \(5\) auf \(1\), \(3\), \(7\) oder \(9\). Wenn also die letzte Stelle unverändert bleibt und \(d\notin\{1,3,7,9\}\) ist, ist dieses gesamte Positionsmuster unmöglich. Falls die letzte Stelle geändert wird, muss dort nur aus \(\{1,3,7,9\}\setminus\{d\}\) gewählt werden.
Die C++-Implementierung nutzt diese Endziffer-Regel explizit vor dem Primzahltest. In Python und Java steckt dieselbe Mathematik weiterhin im Verfahren, auch wenn manche Fälle erst durch den Primzahltest ausscheiden.
Dieses Beispiel zeigt gut, dass hier Struktur und nicht bloß rohe Gewalt entscheidet. Angenommen, nur eine einzige Position dürfte von \(0\) abweichen.
Wird die erste Stelle nicht verändert, beginnt die Zahl mit \(0\) und ist damit keine gültige 10-stellige Zahl. Ist die erste Stelle die einzig geänderte Position, bleibt die letzte Stelle \(0\), also ist die Zahl durch \(10\) teilbar und sicher nicht prim. Damit ist eine einzige Ersetzung für \(d=0\) ausgeschlossen.
Wir wissen also sofort:
$$r_0\ge 2,\qquad M(10,0)\le 8.$$
Die Suche bestätigt das rechnerisch, aber die Aussage folgt bereits aus der Stellenwertstruktur des Dezimalsystems.
Nehmen wir an, die Suche erreicht einen Wert \(r\) und findet dort mindestens eine Primzahl. Dann besitzt jede dieser Primzahlen genau \(10-r\) Kopien von \(d\). Zugleich hat die Suche bereits bewiesen, dass es für alle kleineren Ersetzungszahlen \(1,2,\dots,r-1\) keine Primzahl gibt. Also kann keine 10-stellige Primzahl mehr als \(10-r\) Kopien von \(d\) enthalten, und die aktuelle Ebene ist automatisch optimal.
Das ist die entscheidende Invariante des gesamten Verfahrens: fallende Wiederholungszahlen entsprechen steigenden Ersetzungszahlen, und die erste erfolgreiche Ebene bestimmt bereits sowohl \(M(10,d)\) als auch \(S(10,d)\).
Die C++-, Python- und Java-Implementierungen iterieren über \(d=0,1,\dots,9\). Für jede Ziffer probieren sie \(r=1,2,\dots,10\), wobei \(r\) die Anzahl der Stellen bezeichnet, die nicht gleich \(d\) sind. Genau das ist die algorithmische Suche nach \(r_d\), also nach der minimalen Ersetzungszahl.
Für ein festes \((d,r)\) füllt die Implementierung zunächst ein 10-stelliges Array mit \(d\), erzeugt dann alle \(\binom{10}{r}\) Mengen geänderter Positionen und anschließend alle Ziffernbelegungen auf diesen Positionen, die den Wert \(d\) vermeiden. Weil nach jedem Suchzweig wieder auf \(d\) zurückgesetzt wird, repräsentiert jedes vollständige Array weiterhin eine Zahl mit genau \(10-r\) Kopien von \(d\).
Fälle mit führender Null werden sofort verworfen. Die C++-Implementierung überspringt zusätzlich Zahlen, deren letzte Ziffer gerade oder gleich \(5\) ist, weil solche Zahlen hier nicht prim sein können.
Nachdem ein Kandidat die dezimalen Filter überstanden hat, wird er in eine ganze Zahl umgewandelt und auf Primzahl geprüft. C++ benutzt modulare Multiplikation, modulare Exponentiation und einen deterministischen Miller-Rabin-Test, der in diesem 64-Bit-Bereich korrekt ist. Python und Java greifen auf robuste Bibliotheksroutinen zur Primzahlprüfung zurück. Alle Primzahlen der ersten erfolgreichen Ebene für die jeweilige Ziffer werden aufsummiert; die Endantwort ist die Summe dieser zehn ziffernspezifischen Teilsummen.
Wenn \(r_d\) die erste erfolgreiche Ersetzungszahl für die Ziffer \(d\) ist, dann ist der Aufwand für diese Ziffer durch
$$O\!\left(\sum_{r=1}^{r_d}\binom{10}{r}9^r \cdot T_{\mathrm{prime}}\right)$$
beschränkt, wobei \(T_{\mathrm{prime}}\) die Kosten eines Primzahltests für eine 10-stellige Zahl bezeichnet. Diese Formel ist problemspezifisch: Sie misst genau, wie viel Suche betrieben wird, bis die optimale Wiederholungszahl nachgewiesen ist.
Der Speicherbedarf ist \(O(10)\) für das aktuelle Ziffernarray plus kleiner temporärer Speicher für die Primzahlen auf der ersten erfolgreichen Ebene. Da die Ziellänge fest 10 ist und die Suche für jede Ziffer sofort nach Erreichen des Optimums stoppt, bleibt die Laufzeit in der Praxis sehr klein.
Her \(d \in \{0,1,\dots,9\}\) rakamı için \(M(10,d)\), 10 basamaklı bir asal sayı içinde \(d\)'nin ulaşabildiği en büyük tekrar sayısı; \(S(10,d)\) ise bu maksimumu sağlayan bütün 10 basamaklı asalların toplamı olsun. İstenen değer
$$\sum_{d=0}^{9} S(10,d)$$
toplamıdır. Buradaki optimizasyon her rakam için ayrı yapılıyor. Yani amaç, genel olarak çok tekrarlı asalları bulmak değil; seçilen tek bir \(d\) rakamını mümkün olduğunca çok sayıda içeren asalları bulmaktır.
Uygulamalar problemi doğrudan "en büyük tekrar sayısı" üzerinden değil, ona eşdeğer olan "asal çıkması için en az kaç konumu değiştirmek gerekir?" sorusu üzerinden çözüyor. Bu dönüşüm, aramanın kombinatorik yapısını tam olarak ortaya çıkarıyor.
Sabit bir \(d\) rakamı seçelim. \(r_d\), tam olarak \(r\) tane \(d\)-olmayan basamağa sahip bir 10 basamaklı asalın var olduğu en küçük \(r \ge 1\) olsun. O zaman bu ilk başarılı seviyede bulunan her asal sayı tam olarak \(10-r_d\) adet \(d\) içerir; dolayısıyla
$$M(10,d)=10-r_d.$$
\(\mathcal{P}(d,r)\) ile tam olarak \(r\) tane \(d\)-olmayan basamağa sahip 10 basamaklı asallar kümesini gösterirsek, o rakam için gereken toplam
$$S(10,d)=\sum_{p\in \mathcal{P}(d,r_d)} p$$
olur. Bu yüzden kod ilk asal kümesini bulduğu anda durabilir; daha büyük bir \(r\), tekrar eden \(d\) sayısını yalnızca azaltır ve \(M(10,d)\)'yi iyileştiremez.
Sabit bir \((d,r)\) çifti için başlangıç noktası \(dddddddddd\) dizisidir. Sonra değişecek \(r\) konumdan oluşan \(P\subseteq\{0,1,\dots,9\}\) kümesi seçilir ve bu konumların her birine \(\{0,\dots,9\}\setminus\{d\}\) içinden bir rakam atanır. Değiştirilen basamakların tekrar \(d\) olmasına izin verilmediği için, her geçerli aday tam olarak \(r\) tane \(d\)-olmayan basamağa sahiptir ve yalnızca bir kez üretilir.
Herhangi bir onluk veya asallık filtresi uygulanmadan önce \(r\) seviyesindeki ham arama uzayı
$$\binom{10}{r} 9^r$$
kadardır. Çözümün merkezindeki kombinatorik nesne budur: dışta değişecek konumların seçimi, içte ise bu konumlara yerleştirilecek rakamların seçimi vardır. Üç uygulamanın da doğrudan yaptığı şey budur.
Her atama geçerli bir 10 basamaklı asal vermez. İki temel aritmetik gerçek, pek çok durumu asallık testinden önce yok eder.
Birincisi, ilk basamak \(0\) olamaz. Bu nedenle \(d=0\) iken ilk konum değiştirilmemişse aday sayı aslında 10 basamaklı değildir.
İkincisi, \(5\)'ten büyük her asalın son basamağı \(1\), \(3\), \(7\) veya \(9\) olmak zorundadır. O halde son konum sabit kalıyor ve \(d\notin\{1,3,7,9\}\) ise, o konum kalıbının tamamı imkansızdır. Son konum değişiyorsa da orada yalnızca \(\{1,3,7,9\}\setminus\{d\}\) içindeki rakamları denemek gerekir.
C++ uygulaması bu son basamak kuralını asallık testinden önce açıkça kullanıyor. Python ve Java sürümlerinde filtre daha az görünür olsa da aynı matematik hâlâ geçerlidir.
Bu örnek, kör bir brute-force yerine yapısal düşünmenin neden önemli olduğunu gösterir. Diyelim ki sadece bir basamağın \(0\)'dan farklı olmasına izin veriyoruz.
Eğer ilk basamak değiştirilmezse sayı \(0\) ile başlar ve geçerli bir 10 basamaklı sayı olmaz. Eğer ilk basamak tek değişen yer ise, son basamak hâlâ \(0\) kalır; bu durumda sayı \(10\)'a bölünür ve asal olamaz. Demek ki \(d=0\) için tek değiştirme imkansızdır.
Dolayısıyla hemen şunu biliriz:
$$r_0\ge 2,\qquad M(10,0)\le 8.$$
Arama bunu hesaplamayla doğrular, fakat sonuç aslında doğrudan onluk basamak yapısından gelir.
Arama \(r\) değerine ulaşıp en az bir asal bulsun. O zaman bu seviyedeki her asal sayıda tam olarak \(10-r\) adet \(d\) vardır. Öte yandan arama daha küçük bütün değiştirme sayıları \(1,2,\dots,r-1\) için hiç asal olmadığını zaten göstermiştir. O halde hiçbir 10 basamaklı asal \(d\)'yi \(10-r\)'den fazla kez içeremez ve mevcut seviye otomatik olarak optimumdur.
Yaklaşımın temel değişmezi budur: azalan tekrar sayıları ile artan değiştirme sayıları birbirine denktir ve ilk başarılı seviye hem \(M(10,d)\)'yi hem de \(S(10,d)\)'yi belirler.
C++, Python ve Java uygulamaları \(d=0,1,\dots,9\) üzerinden döner. Her rakam için \(r=1,2,\dots,10\) denenir; burada \(r\), \(d\)'ye eşit olmayan konum sayısıdır. Bu, minimal değiştirme sayısı \(r_d\)'yi bulmanın doğrudan hesaplamalı karşılığıdır.
Sabit \((d,r)\) için uygulama önce 10 elemanlı bir diziye bütünüyle \(d\) yazar, sonra değişecek \(\binom{10}{r}\) konum kümelerini üretir ve ardından bu konumlara \(d\) dışındaki rakamların bütün atamalarını dener. Her dal tamamlandıktan sonra rakamlar tekrar \(d\)'ye döndürüldüğü için, oluşan her aday sayı tam olarak \(10-r\) tane \(d\) içerir.
Baştaki sıfır durumları hemen elenir. C++ uygulaması ayrıca son basamağı çift veya \(5\) olan adayları da asallık testine göndermeden atlar.
Bir aday onluk kısıtlardan geçtikten sonra tam sayıya çevrilir ve asal olup olmadığı sınanır. C++ sürümü modüler çarpma, modüler üs alma ve bu boyuttaki 64-bit girdiler için güvenli olan deterministik Miller-Rabin testini kullanır. Python ve Java sürümleri olgun üst seviye asallık yordamlarına dayanır. Her rakam için ilk başarılı seviyede bulunan tüm asallar toplanır; son cevap bu on parçalı toplamın yeniden toplanmasıdır.
\(r_d\), rakam \(d\) için ilk başarılı değiştirme sayısı ise, o rakamın maliyeti
$$O\!\left(\sum_{r=1}^{r_d}\binom{10}{r}9^r \cdot T_{\mathrm{prime}}\right)$$
ile üstten sınırlanır. Burada \(T_{\mathrm{prime}}\), 10 basamaklı bir tamsayı üzerinde yapılan tek bir asallık testinin maliyetidir. Bu ifade problem-adaptiftir; çünkü optimum tekrar sayısı kesinleşene kadar gerçekte ne kadar arama yapıldığını doğrudan ölçer.
Bellek kullanımı, mevcut rakam dizisi için \(O(10)\) ve ilk başarılı seviyede bulunan asallar için küçük bir geçici depolama kadardır. Hedef uzunluk sabit olarak 10 olduğu ve her rakam için optimum bulunur bulunmaz arama durduğu için pratik çalışma süresi çok küçüktür.
Para cada dígito \(d \in \{0,1,\dots,9\}\), sea \(M(10,d)\) el mayor número de veces que \(d\) puede aparecer en un primo de 10 cifras, y sea \(S(10,d)\) la suma de todos los primos de 10 cifras que alcanzan ese máximo. Hay que calcular
$$\sum_{d=0}^{9} S(10,d).$$
La optimización se hace por dígito. Para un \(d\) fijo no buscamos, en abstracto, primos con muchos dígitos repetidos; buscamos primos que contengan el mayor número posible de copias de ese dígito concreto.
Las implementaciones resuelven el problema reformulándolo: en vez de preguntar por la repetición máxima, preguntan cuántas posiciones hay que cambiar, como mínimo, para que aparezca un primo. Esa versión es exactamente la que encaja con la estructura combinatoria del algoritmo.
Fijemos un dígito \(d\). Sea \(r_d\) el menor entero \(r \ge 1\) tal que existe un primo de 10 cifras con exactamente \(r\) posiciones distintas de \(d\). Entonces cualquier primo hallado en ese primer nivel exitoso contiene exactamente \(10-r_d\) copias de \(d\), y por tanto
$$M(10,d)=10-r_d.$$
Si \(\mathcal{P}(d,r)\) denota el conjunto de primos de 10 cifras con exactamente \(r\) cifras no iguales a \(d\), entonces
$$S(10,d)=\sum_{p\in \mathcal{P}(d,r_d)} p.$$
Por eso la búsqueda puede detenerse en cuanto aparece el primer conjunto no vacío de primos: un valor mayor de \(r\) solo reduciría el número de copias de \(d\), así que nunca podría mejorar \(M(10,d)\).
Para un par fijo \((d,r)\), se empieza con la palabra \(dddddddddd\). Luego se elige un conjunto \(P\subseteq\{0,1,\dots,9\}\) de \(r\) posiciones que se van a modificar, y a cada una de ellas se le asigna un dígito de \(\{0,\dots,9\}\setminus\{d\}\). Como las posiciones modificadas no pueden volver a tomar el valor \(d\), cada candidato válido tiene exactamente \(r\) cifras no-\(d\) y se genera una sola vez.
Antes de aplicar filtros decimales o de primalidad, el tamaño bruto del espacio de búsqueda en el nivel \(r\) es
$$\binom{10}{r} 9^r.$$
Esta factorización entre elección de posiciones y asignación de dígitos es el objeto combinatorio central de la solución, y las tres implementaciones la siguen de manera literal.
No toda asignación puede representar un primo de 10 cifras. Hay dos hechos elementales que descartan muchísimos casos antes del test de primalidad.
Primero, la cifra inicial no puede ser \(0\). Por tanto, si \(d=0\) y la primera posición no está entre las modificadas, el candidato ni siquiera representa un entero de 10 cifras.
Segundo, todo primo mayor que \(5\) termina en \(1\), \(3\), \(7\) o \(9\). Así, si la última posición permanece fija y \(d\notin\{1,3,7,9\}\), ese patrón completo es imposible. Si la última posición se modifica, solo merece la pena probar allí valores en \(\{1,3,7,9\}\setminus\{d\}\).
La implementación en C++ usa esta regla del último dígito de forma explícita antes de invocar el test de primalidad. En Python y Java la misma matemática sigue presente, aunque algunos descartes se produzcan más tarde.
Este caso muestra bien que el razonamiento estructural importa tanto como la enumeración. Supongamos que solo una posición pudiera diferir de \(0\).
Si la primera cifra no cambia, el número empieza con \(0\) y deja de ser un número válido de 10 cifras. Si la primera cifra es la única modificada, la última cifra sigue siendo \(0\), de modo que el número es divisible por \(10\) y no puede ser primo. Por consiguiente, un solo reemplazo es imposible para \(d=0\).
Obtenemos de inmediato
$$r_0\ge 2,\qquad M(10,0)\le 8.$$
La búsqueda lo confirma computacionalmente, pero la conclusión nace de la propia estructura decimal.
Supongamos que la búsqueda alcanza un cierto valor \(r\) y encuentra al menos un primo. Entonces todos los primos de ese nivel tienen exactamente \(10-r\) copias de \(d\). A la vez, la búsqueda ya ha demostrado que no existen primos para los valores menores \(1,2,\dots,r-1\). Por lo tanto, ningún primo de 10 cifras puede contener más de \(10-r\) copias de \(d\), y el nivel actual es automáticamente óptimo.
Esa es la invariante fundamental del método: bajar la repetición equivale a subir el número de reemplazos, y el primer nivel exitoso fija por sí solo tanto \(M(10,d)\) como \(S(10,d)\).
Las implementaciones en C++, Python y Java recorren \(d=0,1,\dots,9\). Para cada dígito prueban \(r=1,2,\dots,10\), donde \(r\) significa "cuántas posiciones no son iguales a \(d\)". Eso es exactamente la versión computacional de buscar \(r_d\), el número mínimo de reemplazos.
Para un \((d,r)\) fijo, la implementación llena primero un arreglo de 10 cifras con el valor \(d\), enumera las \(\binom{10}{r}\) elecciones posibles de posiciones modificadas y después recorre todas las asignaciones de dígitos en esas posiciones evitando el propio \(d\). Como tras cada rama se restaura el valor repetido, cada arreglo completo sigue representando un número con exactamente \(10-r\) copias de \(d\).
Los casos con cero inicial se descartan de inmediato. La implementación en C++ además evita enviar al test de primalidad números cuyo último dígito sea par o igual a \(5\).
Cuando un candidato supera los filtros decimales, se convierte a entero y se comprueba si es primo. La versión en C++ usa multiplicación modular, exponenciación modular y un Miller-Rabin determinista adecuado para entradas de 64 bits en este rango. Las versiones de Python y Java delegan en rutinas de primalidad de alto nivel. Todos los primos hallados en el primer nivel exitoso para cada dígito se suman, y la respuesta final es la suma de esas diez contribuciones.
Si \(r_d\) es el primer número de reemplazos que funciona para el dígito \(d\), entonces el coste para ese dígito queda acotado por
$$O\!\left(\sum_{r=1}^{r_d}\binom{10}{r}9^r \cdot T_{\mathrm{prime}}\right),$$
donde \(T_{\mathrm{prime}}\) es el coste de un único test de primalidad sobre un entero de 10 cifras. La fórmula es adaptativa al problema, porque describe exactamente cuánta exploración se realiza antes de certificar el nivel óptimo de repetición.
El uso de memoria es \(O(10)\) para el arreglo actual de cifras, más un almacenamiento temporal pequeño para los primos encontrados en el primer nivel exitoso. Como la longitud está fijada en 10 y la búsqueda se detiene en cuanto cada dígito alcanza su óptimo, el tiempo real de ejecución es muy pequeño.
对每个数字 \(d \in \{0,1,\dots,9\}\)，记 \(M(10,d)\) 为一个 10 位质数中数字 \(d\) 能出现的最大次数，记 \(S(10,d)\) 为所有达到这个最大次数的 10 位质数之和。题目要求计算
$$\sum_{d=0}^{9} S(10,d).$$
这里的优化是按数字分别进行的。也就是说，对于固定的 \(d\)，我们不是泛泛地寻找“重复数字很多的质数”，而是要寻找“包含尽可能多的 \(d\)”的 10 位质数。
实现采用了一个更适合搜索的等价表述：与其直接问“\(d\) 最多能重复多少次”，不如问“从全是 \(d\) 的 10 位数出发，最少需要改动几个位置才能得到一个质数”。这个表述与代码的组合枚举结构完全一致。
固定一个数字 \(d\)。定义 \(r_d\) 为满足下述条件的最小整数 \(r \ge 1\)：存在一个 10 位质数，它恰好有 \(r\) 个位置不是 \(d\)。那么在这个第一个成功层上找到的每个质数都恰好含有 \(10-r_d\) 个 \(d\)，因此
$$M(10,d)=10-r_d.$$
如果用 \(\mathcal{P}(d,r)\) 表示所有“恰有 \(r\) 个非 \(d\) 数字”的 10 位质数集合，那么对应的和就是
$$S(10,d)=\sum_{p\in \mathcal{P}(d,r_d)} p.$$
这就解释了为什么搜索一旦在某个 \(r\) 上找到质数就可以立即停止：更大的 \(r\) 只会减少 \(d\) 的重复次数，不可能再改进 \(M(10,d)\)。
对于固定的 \((d,r)\)，先从字符串 \(dddddddddd\) 出发。然后选择一个位置集合 \(P\subseteq\{0,1,\dots,9\}\)，其中恰有 \(r\) 个位置要被改动；接着给这些位置分别填入 \(\{0,\dots,9\}\setminus\{d\}\) 中的数字。由于被改动的位置不允许再写回 \(d\)，所以每个合法候选数都恰好有 \(r\) 个非 \(d\) 位，而且只会被生成一次。
在任何十进制合法性检查或质数测试之前，第 \(r\) 层的原始搜索规模就是
$$\binom{10}{r} 9^r.$$
这正是本题的核心组合对象：外层是改动位置的选择，内层是这些位置上的数字赋值。三种语言的实现都直接按照这个分解来组织枚举。
并不是每一种赋值都可能成为 10 位质数。有两条最基本的十进制规则可以提前剪掉大量分支。
第一，首位不能是 \(0\)。因此如果 \(d=0\) 且第一个位置不在被改动的位置集合中，那么这个候选根本不是一个合法的 10 位整数。
第二，所有大于 \(5\) 的质数末位都必须是 \(1\)、\(3\)、\(7\) 或 \(9\)。所以如果最后一位没有被改动，而 \(d\notin\{1,3,7,9\}\)，那么这种位置模式整体都不可能产生质数。如果最后一位被改动，那么那里只需要尝试 \(\{1,3,7,9\}\setminus\{d\}\) 中的数字。
C++ 实现把末位规则显式地写成了质数测试前的过滤；Python 和 Java 即使没有同样显式的剪枝，本质上仍然依赖同样的数学事实。
这个例子很适合说明，本题并不是盲目暴力搜索，而是有明确结构约束。假设只允许一位与 \(0\) 不同。
如果首位没有被改动，那么数字以 \(0\) 开头，不是合法的 10 位数。反过来，如果首位是唯一被改动的位置，那么末位仍然是 \(0\)，整个数就能被 \(10\) 整除，当然不可能是质数。因此，对 \(d=0\) 来说，一次替换根本不可能成功。
于是我们立刻得到
$$r_0\ge 2,\qquad M(10,0)\le 8.$$
程序会把这个结论再算一遍，但它其实已经由十进制位值结构本身决定了。
设搜索在某个 \(r\) 上第一次找到了至少一个质数。那么这个层上的每个质数都恰好含有 \(10-r\) 个 \(d\)。与此同时，搜索已经证明所有更小的替换数 \(1,2,\dots,r-1\) 都不可能产生质数。因此，不存在任何 10 位质数能包含超过 \(10-r\) 个 \(d\)，当前层自动就是最优层。
这就是整个方法的核心不变量：重复数减少一层，等价于替换数增加一层；而第一个成功层已经同时确定了 \(M(10,d)\) 和 \(S(10,d)\)。
C++、Python 和 Java 实现都会先遍历 \(d=0,1,\dots,9\)。对每个 \(d\)，再依次尝试 \(r=1,2,\dots,10\)，其中 \(r\) 表示“不等于 \(d\) 的位置数”。这正是对最小替换数 \(r_d\) 的直接搜索。
在固定的 \((d,r)\) 下，实现先用 \(d\) 填满一个 10 长度数组，然后枚举所有 \(\binom{10}{r}\) 个被改动的位置集合，再枚举这些位置上的所有数字赋值，并要求赋的值不能等于 \(d\)。由于每个分支结束后都会把数组恢复成原来的重复数字状态，所以每个完整候选都恰好包含 \(10-r\) 个 \(d\)。
首位为零的情形会立即丢弃。C++ 版本还会在进入质数测试前，直接跳过末位为偶数或 \(5\) 的候选数。
当一个候选通过十进制过滤后，它会被转换成整数并接受质数测试。C++ 使用模乘、模幂和适用于这一 64 位范围的确定性 Miller-Rabin；Python 与 Java 则调用成熟的高层质数判定例程。对于每个数字 \(d\)，只要在某个最小 \(r\) 上找到了质数，就把这一层的全部质数求和，并把这个和加入最终答案。
如果 \(r_d\) 是数字 \(d\) 的第一个成功替换数，那么该数字对应的工作量可由
$$O\!\left(\sum_{r=1}^{r_d}\binom{10}{r}9^r \cdot T_{\mathrm{prime}}\right)$$
界定，其中 \(T_{\mathrm{prime}}\) 表示一次 10 位整数质数测试的代价。这个表达式是与题目结构直接匹配的，因为它准确刻画了在最优重复层被确认之前，程序究竟枚举了多少候选。
空间复杂度为当前 10 位数字数组的 \(O(10)\)，再加上在首个成功层暂存质数的少量附加空间。由于目标长度固定为 10，而且每个数字一旦找到最优层就立即停止，实际运行时间非常短。
Для каждой цифры \(d \in \{0,1,\dots,9\}\) обозначим через \(M(10,d)\) максимальное число вхождений цифры \(d\) в десятизначное простое число, а через \(S(10,d)\) сумму всех десятизначных простых, достигающих этого максимума. Требуется вычислить
$$\sum_{d=0}^{9} S(10,d).$$
Оптимизация проводится отдельно для каждой цифры. Иными словами, для фиксированного \(d\) нас интересуют не вообще простые с большим количеством повторов, а именно простые, содержащие как можно больше копий этой конкретной цифры.
Реализации решают задачу через эквивалентную постановку: вместо поиска максимального числа повторений спрашивается, сколько позиций нужно изменить как можно меньше, чтобы из числа, состоящего только из \(d\), получить простое. Эта формулировка точно совпадает с комбинаторной структурой перебора.
Зафиксируем цифру \(d\). Пусть \(r_d\) - наименьшее целое \(r \ge 1\), для которого существует десятизначное простое число, имеющее ровно \(r\) позиций, отличных от \(d\). Тогда любое простое, найденное на этом первом успешном уровне, содержит ровно \(10-r_d\) копий цифры \(d\), значит
$$M(10,d)=10-r_d.$$
Если \(\mathcal{P}(d,r)\) обозначает множество всех десятизначных простых с ровно \(r\) цифрами, не равными \(d\), то
$$S(10,d)=\sum_{p\in \mathcal{P}(d,r_d)} p.$$
Именно поэтому поиск можно прекращать сразу после появления первых простых: больший \(r\) лишь уменьшит число повторений \(d\) и уже не сможет улучшить \(M(10,d)\).
Для фиксированной пары \((d,r)\) отправной точкой служит слово \(dddddddddd\). Затем выбирается множество \(P\subseteq\{0,1,\dots,9\}\) из \(r\) позиций, которые будут изменены, и каждой из этих позиций присваивается цифра из \(\{0,\dots,9\}\setminus\{d\}\). Поскольку изменяемым позициям запрещено снова принимать значение \(d\), каждый допустимый кандидат имеет ровно \(r\) не-\(d\) цифр и порождается ровно один раз.
До каких-либо десятичных или простых фильтров размер сырого пространства поиска на уровне \(r\) равен
$$\binom{10}{r} 9^r.$$
Это и есть центральный комбинаторный объект задачи: внешний выбор меняемых позиций и внутренний выбор цифр в этих позициях. Все три реализации буквально повторяют именно эту факторизацию.
Не всякое присваивание может дать десятизначное простое. Два элементарных факта позволяют отбросить множество случаев ещё до проверки на простоту.
Во-первых, первая цифра не может быть равна \(0\). Поэтому если \(d=0\) и первая позиция не входит в множество замен, кандидат вообще не является корректным десятизначным числом.
Во-вторых, любое простое число больше \(5\) оканчивается на \(1\), \(3\), \(7\) или \(9\). Следовательно, если последняя позиция не меняется и \(d\notin\{1,3,7,9\}\), то весь такой шаблон невозможен. Если же последняя позиция меняется, на ней имеет смысл пробовать только цифры из \(\{1,3,7,9\}\setminus\{d\}\).
В реализации на C++ это правило последней цифры используется явно до запуска теста простоты. В версиях на Python и Java та же математика сохраняется, даже если часть отсеиваний выполняется уже самим тестом.
Этот случай хорошо показывает, что здесь важна структура, а не слепой перебор. Предположим, что разрешена только одна позиция, отличная от \(0\).
Если первая цифра не меняется, число начинается с \(0\) и не является допустимым десятизначным числом. Если же первая цифра - единственная изменённая позиция, то последняя цифра остаётся равной \(0\), а значит число делится на \(10\) и не может быть простым. Следовательно, для \(d=0\) одна замена невозможна.
Сразу получаем
$$r_0\ge 2,\qquad M(10,0)\le 8.$$
Поиск затем подтверждает это вычислительно, но вывод уже следует из самой десятичной записи.
Пусть поиск впервые находит хотя бы одно простое при некотором \(r\). Тогда каждое простое на этом уровне содержит ровно \(10-r\) копий цифры \(d\). Одновременно уже доказано, что для всех меньших чисел замен \(1,2,\dots,r-1\) простых нет. Значит, не существует десятизначного простого с более чем \(10-r\) копиями \(d\), и текущий уровень автоматически оптимален.
Это главный инвариант метода: уменьшение числа повторов эквивалентно увеличению числа замен, а первый успешный уровень сразу определяет и \(M(10,d)\), и \(S(10,d)\).
Реализации на C++, Python и Java перебирают \(d=0,1,\dots,9\). Для каждой цифры пробуются значения \(r=1,2,\dots,10\), где \(r\) означает количество позиций, не равных \(d\). Это и есть программный поиск минимального числа замен \(r_d\).
Для фиксированного \((d,r)\) реализация сначала заполняет массив из 10 цифр значением \(d\), затем перечисляет все \(\binom{10}{r}\) наборы изменяемых позиций и после этого перебирает все присваивания цифр в этих позициях, избегая значения \(d\). Поскольку после каждой ветви массив восстанавливается, каждый завершённый кандидат всё ещё содержит ровно \(10-r\) копий \(d\).
Случаи с ведущим нулём отбрасываются сразу. Версия на C++ также пропускает числа с чётной последней цифрой или с последней цифрой \(5\) ещё до теста на простоту.
Когда кандидат проходит десятичные фильтры, он преобразуется в целое число и проверяется на простоту. C++ использует модульное умножение, модульное возведение в степень и детерминированный тест Миллера-Рабина, корректный для этого диапазона 64-битных значений. Python и Java опираются на надёжные высокоуровневые процедуры проверки простоты. Все простые, найденные на первом успешном уровне для данной цифры, суммируются; окончательный ответ - это сумма десяти таких частичных сумм.
Если \(r_d\) - первое успешное число замен для цифры \(d\), то трудоёмкость для этой цифры ограничена выражением
$$O\!\left(\sum_{r=1}^{r_d}\binom{10}{r}9^r \cdot T_{\mathrm{prime}}\right),$$
где \(T_{\mathrm{prime}}\) обозначает стоимость одной проверки на простоту для десятизначного числа. Эта оценка адаптирована к структуре задачи, потому что она точно измеряет, сколько поиска выполняется до подтверждения оптимального уровня повторений.
Память составляет \(O(10)\) для текущего массива цифр плюс небольшой временный объём для простых чисел на первом успешном уровне. Так как длина фиксирована и равна 10, а поиск для каждой цифры прекращается сразу после достижения оптимума, реальное время работы остаётся очень малым.
لكل رقم \(d \in \{0,1,\dots,9\}\)، نرمز بـ \(M(10,d)\) إلى أكبر عدد ممكن من مرات ظهور الرقم \(d\) داخل عدد أولي مكوّن من 10 خانات، ونرمز بـ \(S(10,d)\) إلى مجموع كل الأعداد الأولية ذات 10 خانات التي تحقق هذا الحد الأقصى. المطلوب هو حساب
$$\sum_{d=0}^{9} S(10,d).$$
فكرة المسألة تعتمد على التعامل مع كل رقم على حدة. عند تثبيت \(d\)، لسنا نبحث عن أعداد أولية كثيرة التكرار بشكل عام، بل نبحث عن أعداد أولية تحتوي على أكبر عدد ممكن من النسخ للرقم نفسه \(d\).
التنفيذات لا تبدأ مباشرة من عبارة "أقصى عدد من التكرارات"، بل تحوّلها إلى صياغة مكافئة وأكثر ملاءمة للبحث: ما أقل عدد من المواضع التي يجب تغييرها في العدد المكوّن كله من الرقم \(d\) حتى نحصل على عدد أولي؟ هذه هي البنية الرياضية الحقيقية التي يعتمد عليها الحل.
ثبّت رقماً \(d\). ولتكن \(r_d\) أصغر قيمة \(r \ge 1\) بحيث يوجد عدد أولي من 10 خانات فيه بالضبط \(r\) خانات لا تساوي \(d\). عندئذٍ فإن كل عدد أولي يظهر في أول مستوى ناجح يحتوي بالضبط على \(10-r_d\) نسخ من \(d\)، ومن ثم
$$M(10,d)=10-r_d.$$
إذا رمزنا بـ \(\mathcal{P}(d,r)\) إلى مجموعة الأعداد الأولية ذات 10 خانات التي تحتوي بالضبط على \(r\) خانات غير مساوية لـ \(d\)، فإن
$$S(10,d)=\sum_{p\in \mathcal{P}(d,r_d)} p.$$
لهذا السبب يتوقف البحث فور العثور على أول مستوى غير فارغ: أي قيمة أكبر لـ \(r\) ستنقص عدد مرات ظهور \(d\)، وبالتالي لا يمكن أن تحسن \(M(10,d)\).
لزوج ثابت \((d,r)\)، تكون نقطة البداية هي السلسلة \(dddddddddd\). بعد ذلك نختار مجموعة مواضع \(P\subseteq\{0,1,\dots,9\}\) وعددها \(r\) لكي نغيّرها، ثم نضع في كل موضع مختار رقماً من \(\{0,\dots,9\}\setminus\{d\}\). وبما أن المواضع التي نغيّرها ممنوعة من العودة إلى القيمة \(d\)، فإن كل مرشح صالح يحتوي بالضبط على \(r\) خانات غير \(d\)، ويُولَّد مرة واحدة فقط.
قبل أي قيود عشرية أو اختبار للأولية، يكون حجم فضاء البحث الخام عند المستوى \(r\) هو
$$\binom{10}{r} 9^r.$$
هذا التفكيك إلى اختيار مواضع ثم إسناد قيم هو الكائن التوافقي الأساسي في الحل، وهو ما تعكسه تطبيقات C++ وPython وJava بشكل مباشر.
ليس كل إسناد يمكن أن يمثل عدداً أولياً من 10 خانات. هناك حقيقتان بسيطتان تستبعدان كثيراً من الحالات قبل الوصول إلى اختبار الأولية.
أولاً، الخانة الأولى لا يجوز أن تكون \(0\). لذلك إذا كان \(d=0\) ولم يكن الموضع الأول ضمن المواضع المعدّلة، فالمرشح ليس عدداً صحيحاً ذا 10 خانات أصلاً.
ثانياً، كل عدد أولي أكبر من \(5\) يجب أن ينتهي بأحد الأرقام \(1\) أو \(3\) أو \(7\) أو \(9\). لذا إذا بقيت الخانة الأخيرة ثابتة وكان \(d\notin\{1,3,7,9\}\)، فإن نمط المواضع كله مستحيل. وإذا كانت الخانة الأخيرة من المواضع المعدّلة، فلا حاجة لتجربة إلا القيم الموجودة في \(\{1,3,7,9\}\setminus\{d\}\).
تنفيذ C++ يطبق قاعدة الخانة الأخيرة بشكل صريح قبل اختبار الأولية. أما في نسختي Python وJava فالمبدأ الرياضي نفسه حاضر حتى لو تم استبعاد بعض الحالات في مرحلة لاحقة.
هذا المثال يوضح أن المسألة ليست تعداداً أعمى، بل تعتمد على بنية العدد العشرية. افترض أن خانة واحدة فقط مسموح لها أن تختلف عن \(0\).
إذا لم تتغير الخانة الأولى، فالعدد يبدأ بـ \(0\)، وبالتالي لا يكون عدداً صالحاً من 10 خانات. وإذا كانت الخانة الأولى هي الوحيدة التي تغيّرت، فستبقى الخانة الأخيرة \(0\)، ومن ثم يكون العدد قابلاً للقسمة على \(10\) ولا يمكن أن يكون أولياً. إذن الاستبدال الواحد مستحيل عندما \(d=0\).
فنحصل مباشرة على
$$r_0\ge 2,\qquad M(10,0)\le 8.$$
البحث البرمجي يؤكد هذه النتيجة، لكن سببها يأتي من بنية النظام العشري نفسه.
إذا وصل البحث إلى قيمة \(r\) ووجد عندها عدداً أولياً واحداً على الأقل، فإن كل عدد أولي في هذا المستوى يحتوي بالضبط على \(10-r\) نسخ من الرقم \(d\). وفي الوقت نفسه يكون البحث قد أثبت أن كل القيم الأصغر \(1,2,\dots,r-1\) لا تنتج أي عدد أولي. لذلك لا يمكن أن يوجد عدد أولي من 10 خانات يحتوي على أكثر من \(10-r\) نسخ من \(d\)، ويكون المستوى الحالي هو المستوى الأمثل تلقائياً.
هذه هي الثابتة الأساسية في المنهج: تقليل عدد التكرارات يعادل زيادة عدد الاستبدالات، وأول مستوى ناجح يحدد معاً كلاً من \(M(10,d)\) و\(S(10,d)\).
تقوم تطبيقات C++ وPython وJava بالدوران على \(d=0,1,\dots,9\). ولكل رقم تجرّب القيم \(r=1,2,\dots,10\)، حيث يمثّل \(r\) عدد المواضع التي لا تساوي \(d\). وهذا هو المقابل البرمجي المباشر للبحث عن \(r_d\)، أي أقل عدد من الاستبدالات اللازمة.
عند تثبيت \((d,r)\)، يملأ التنفيذ مصفوفة من 10 خانات بالقيمة \(d\)، ثم يعدّد جميع اختيارات المواضع المعدّلة وعددها \(\binom{10}{r}\)، ثم يعدّد جميع إسنادات الأرقام إلى هذه المواضع بشرط ألا تساوي \(d\). وبما أن المصفوفة تُستعاد بعد كل فرع، فإن كل مرشح مكتمل يبقى عدداً يحتوي بالضبط على \(10-r\) نسخ من \(d\).
الحالات ذات الصفر البادئ تُرفض مباشرة. كما أن تنفيذ C++ يتجاوز أيضاً الأعداد التي تنتهي برقم زوجي أو بالرقم \(5\) قبل إرسالها إلى اختبار الأولية.
بعد أن يجتاز المرشح القيود العشرية، يُحوَّل إلى عدد صحيح ويُفحص إن كان أولياً. يستخدم C++ الضرب المعياري والأسّ المعياري واختبار Miller-Rabin حتمياً مناسباً لهذا المجال من أعداد 64-بت. أما Python وJava فيعتمدان على إجراءات أولية عالية المستوى. كل الأعداد الأولية التي تظهر في أول مستوى ناجح لرقم معيّن تُجمع معاً، ثم يُجمع حاصل هذه المجاميع العشرة للحصول على الجواب النهائي.
إذا كانت \(r_d\) هي أول قيمة ناجحة لعدد الاستبدالات بالنسبة إلى الرقم \(d\)، فإن كلفة المعالجة لذلك الرقم محدودة بـ
$$O\!\left(\sum_{r=1}^{r_d}\binom{10}{r}9^r \cdot T_{\mathrm{prime}}\right),$$
حيث تمثل \(T_{\mathrm{prime}}\) كلفة اختبار أولية واحد لعدد من 10 خانات. هذا التعبير ملائم تماماً لبنية المسألة، لأنه يقيس بدقة مقدار البحث الفعلي قبل إثبات المستوى الأمثل للتكرار.
استهلاك الذاكرة هو \(O(10)\) للمصفوفة الحالية من الخانات، مع مساحة مؤقتة صغيرة لتجميع الأعداد الأولية في أول مستوى ناجح. وبما أن الطول ثابت ويساوي 10، وبما أن البحث يتوقف فور الوصول إلى المستوى الأمثل لكل رقم، فإن زمن التنفيذ العملي صغير جداً.