Fix a limit \(L\). We look at the primes up to \(L\), and we connect two primes when one legal decimal edit turns one into the other while staying prime. The allowed edits are: replace one digit without creating a leading zero, delete the most significant digit, or prepend one new nonzero digit.
The required sum is not over all unreachable primes in the full graph. For each prime \(p\), we only allow primes \(\le p\) as intermediate vertices. A prime contributes exactly when 2 is still disconnected from \(p\) inside that restricted graph.
Let \(\mathbb{P}\) denote the set of primes and define
$$V_L=\mathbb{P}\cap [2,L].$$
We build an undirected graph \(G_L=(V_L,E_L)\). An edge joins two primes if one can be obtained from the other by exactly one allowed decimal edit. Replacing a digit is symmetric, and deleting the leading digit is the inverse of prepending a leading digit, so the graph may be treated as undirected.
If a prime has \(d\) digits, then its neighbors are generated by three families of moves:
1. change one of the \(d\) digits to another digit, with the restriction that the first digit cannot become 0;
2. if \(d \ge 2\), remove the first digit;
3. prepend one digit from 1 through 9.
Only prime results remain in the graph.
For every threshold \(t \le L\), let \(G_{\le t}\) be the induced subgraph on
$$V_t=\mathbb{P}\cap [2,t].$$
Write \(2 \sim_t p\) when 2 and \(p\) are connected in \(G_{\le t}\). Then the problem asks for
$$S(L)=\sum_{\substack{p\in\mathbb{P}\\ p\le L\\ 2 \not\sim_p p}} p.$$
So each prime has its own threshold: we do not ask whether \(p\) is connected to 2 somewhere in the full graph up to \(L\), but whether it is already connected at the moment the graph is truncated at \(p\).
Define \(\tau(p)\) as the smallest threshold \(t\) such that \(2 \sim_t p\). Equivalently, for any path
$$P=(q_0=2,q_1,\dots,q_k=p),$$
define its bottleneck value by
$$B(P)=\max_{0\le i\le k} q_i.$$
Then
$$\tau(p)=\min_{P:2\leadsto p} B(P).$$
This identity is the key reduction. If a path has bottleneck \(M\), then every vertex of that path lies in \(G_{\le M}\), so \(2 \sim_M p\). Conversely, if \(2 \sim_t p\), some path in \(G_{\le t}\) connects them, and that path has maximum vertex at most \(t\). Therefore the minimum threshold and the minimum bottleneck are the same quantity.
The contribution test now becomes simply
$$\tau(p)>p.$$
In words: every path from 2 to \(p\) is forced to pass through some prime strictly larger than \(p\).
The minimax value \(\tau(p)\) can be computed by the same greedy structure as Dijkstra's algorithm. Instead of ordinary path length, each vertex stores its best known bottleneck value. Start with label 2 at the vertex 2 and \(+\infty\) elsewhere.
Suppose a prime \(u\) has already been reached with current label \(d(u)\), and \(v\) is a prime neighbor of \(u\). Any path to \(u\) with bottleneck \(d(u)\) extends to a path to \(v\) with bottleneck
$$\max(d(u),v).$$
Hence the relaxation rule is
$$d(v)\leftarrow \min\bigl(d(v),\max(d(u),v)\bigr).$$
This works because extending a path cannot decrease its bottleneck. The labels are monotone, so once the smallest tentative label is extracted from the priority queue, no later path can improve it. That is exactly the usual correctness argument for Dijkstra, with addition replaced by \(\max\).
The prime 11 is the first nontrivial example. There is a path
$$2 \to 3 \to 13 \to 11,$$
so \(\tau(11)\le 13\). On the other hand, in the threshold graph \(G_{\le 11}\), the vertex 11 has no valid incident edge: every legal one-step edit gives either a non-prime, a number with a leading zero, or a prime greater than 11. Therefore \(2 \not\sim_{11} 11\), and
$$\tau(11)=13>11.$$
So 11 contributes to the sum.
The same minimax search shows
$$\tau(101)=\tau(103)=\tau(107)=\tau(109)=113.$$
Hence the contributing primes below \(10^3\) are
$$11,\ 101,\ 103,\ 107,\ 109,$$
and therefore
$$S(10^3)=11+101+103+107+109=431.$$
This matches the checkpoint used by the implementation. A second checkpoint is
$$S(10^4)=78728.$$
The C++, Python, and Java implementations first build a sieve of Eratosthenes up to \(L\), so primality tests become constant-time table lookups. They also precompute powers of 10 in order to address decimal positions directly.
The graph is never materialized in full. Instead, whenever the priority queue extracts a prime, the implementation generates all valid one-step edits of its decimal representation: same-length digit replacements, deletion of the most significant digit, and prepending of one nonzero digit. Every candidate is tested against the sieve, and prime candidates are relaxed with the bottleneck update above.
After the queue is exhausted, each prime \(p\) has its final threshold value \(\tau(p)\). The program then scans the prime list once and accumulates exactly those primes with \(\tau(p)>p\).
Let
$$V=\pi(L),\qquad D=\lfloor \log_{10} L \rfloor + 1.$$
The sieve costs \(O(L\log\log L)\) time and \(O(L)\) memory. For each extracted prime, neighbor generation inspects at most \(9D\) replacements, one deletion, and up to nine prepends, so the implicit graph contributes \(E=O(VD)\) candidate relaxations. The priority queue phase therefore costs
$$O(E\log V)=O(VD\log V).$$
The total complexity is
$$O(L\log\log L + VD\log V)$$
time and \(O(L)\) memory, which is efficient enough for the required limit.
Sei \(L\) eine feste Grenze. Wir betrachten alle Primzahlen bis \(L\) und verbinden zwei Primzahlen, wenn eine erlaubte Dezimaloperation die eine in die andere überführt und das Ergebnis wieder prim ist. Erlaubt sind: das Ersetzen genau einer Ziffer ohne führende Null, das Entfernen der höchstwertigen Ziffer und das Voranstellen einer neuen Ziffer von 1 bis 9.
Gesucht ist nicht einfach die Menge aller im Gesamtnetz unerreichbaren Primzahlen. Für jede Primzahl \(p\) dürfen Zwischenstationen nur Primzahlen \(\le p\) sein. Eine Primzahl trägt genau dann zur Summe bei, wenn 2 in diesem abgeschnittenen Graphen noch nicht mit \(p\) verbunden ist.
Sei \(\mathbb{P}\) die Menge der Primzahlen und
$$V_L=\mathbb{P}\cap [2,L].$$
Wir definieren einen ungerichteten Graphen \(G_L=(V_L,E_L)\). Zwei Primzahlen werden durch eine Kante verbunden, wenn sie sich durch genau eine erlaubte Dezimaloperation ineinander umwandeln lassen. Ziffernersetzung ist symmetrisch, und das Entfernen der führenden Ziffer ist die Umkehrung des Voranstellens einer Ziffer; daher darf man den Graphen als ungerichtet auffassen.
Hat eine Primzahl \(d\) Stellen, dann entstehen ihre Nachbarn aus drei Typen von Operationen:
1. eine der \(d\) Ziffern wird ersetzt, wobei die erste Ziffer nicht zu 0 werden darf;
2. falls \(d \ge 2\), wird die führende Ziffer entfernt;
3. es wird links eine Ziffer aus \(\{1,\dots,9\}\) angefügt.
Im Graphen bleiben nur jene Resultate, die prim sind.
Für jeden Schwellenwert \(t \le L\) bezeichne \(G_{\le t}\) den induzierten Teilgraphen auf
$$V_t=\mathbb{P}\cap [2,t].$$
Wir schreiben \(2 \sim_t p\), wenn 2 und \(p\) in \(G_{\le t}\) verbunden sind. Dann lautet die gesuchte Summe
$$S(L)=\sum_{\substack{p\in\mathbb{P}\\ p\le L\\ 2 \not\sim_p p}} p.$$
Entscheidend ist also nicht, ob \(p\) irgendwann im vollständigen Graphen bis \(L\) von 2 aus erreichbar ist, sondern ob diese Verbindung bereits existiert, sobald man alle Primzahlen oberhalb von \(p\) entfernt.
Definiere \(\tau(p)\) als den kleinsten Schwellenwert \(t\), für den \(2 \sim_t p\) gilt. Für einen Pfad
$$P=(q_0=2,q_1,\dots,q_k=p)$$
setze den Bottleneck-Wert
$$B(P)=\max_{0\le i\le k} q_i.$$
Dann gilt
$$\tau(p)=\min_{P:2\leadsto p} B(P).$$
Diese Identität ist die zentrale mathematische Umformung. Hat ein Pfad Bottleneck \(M\), dann liegen alle seine Knoten in \(G_{\le M}\), also ist \(2 \sim_M p\). Umgekehrt liefert jede Verbindung in \(G_{\le t}\) einen Pfad, dessen größter Knoten höchstens \(t\) ist. Minimaler Schwellenwert und minimaler Bottleneck sind daher dieselbe Größe.
Damit vereinfacht sich das Kriterium für einen Summanden zu
$$\tau(p)>p.$$
Anders gesagt: Jeder Pfad von 2 nach \(p\) ist gezwungen, irgendwann eine Primzahl zu betreten, die strikt größer als \(p\) ist.
Der Minimax-Wert \(\tau(p)\) lässt sich mit derselben Greedy-Struktur wie der Dijkstra-Algorithmus berechnen. Statt gewöhnlicher Weglängen speichert jeder Knoten den derzeit besten bekannten Bottleneck-Wert. Initial steht beim Knoten 2 die Zahl 2 und bei allen anderen \(+\infty\).
Sei \(u\) eine Primzahl mit aktuellem Wert \(d(u)\), und sei \(v\) ein Primnachbar von \(u\). Dann erzeugt ein Weg nach \(u\) mit Bottleneck \(d(u)\) einen Weg nach \(v\) mit Bottleneck
$$\max(d(u),v).$$
Also lautet die Relaxation
$$d(v)\leftarrow \min\bigl(d(v),\max(d(u),v)\bigr).$$
Die Korrektheit folgt wie bei Dijkstra daraus, dass das Verlängern eines Pfades den Bottleneck nie verkleinern kann. Sobald also der kleinste vorläufige Wert aus der Prioritätswarteschlange entnommen wurde, kann ihn kein späterer Pfad mehr verbessern.
Die Primzahl 11 ist das erste interessante Beispiel. Es gibt den Pfad
$$2 \to 3 \to 13 \to 11,$$
also \(\tau(11)\le 13\). Im Schwellengraphen \(G_{\le 11}\) besitzt 11 jedoch keine gültige inzidente Kante: Jede erlaubte Ein-Schritt-Operation liefert entweder keine Primzahl, eine Zahl mit führender Null oder eine Primzahl größer als 11. Also gilt \(2 \not\sim_{11} 11\), und damit
$$\tau(11)=13>11.$$
Daher trägt 11 zur Summe bei.
Dieselbe Minimax-Suche ergibt außerdem
$$\tau(101)=\tau(103)=\tau(107)=\tau(109)=113.$$
Damit sind die beitragenden Primzahlen unter \(10^3\)
$$11,\ 101,\ 103,\ 107,\ 109,$$
und folglich
$$S(10^3)=11+101+103+107+109=431.$$
Genau dies ist der Kontrollwert der Implementierung. Ein zweiter Kontrollwert ist
$$S(10^4)=78728.$$
Die Implementierungen in C++, Python und Java bauen zunächst ein Sieb des Eratosthenes bis \(L\) auf, sodass Primzahltests nur noch Tabellenzugriffe sind. Zusätzlich werden Zehnerpotenzen vorab berechnet, damit einzelne Dezimalstellen direkt angesprochen werden können.
Der Graph wird nie vollständig gespeichert. Stattdessen erzeugt die Implementierung immer dann, wenn eine Primzahl aus der Prioritätswarteschlange entnommen wird, alle erlaubten Ein-Schritt-Edits ihrer Dezimaldarstellung: Ziffern ersetzen, führende Ziffer entfernen und eine neue führende Ziffer anfügen. Jeder Kandidat wird gegen das Sieb geprüft; nur Primzahlen werden mit der Bottleneck-Regel relaxiert.
Nach Abschluss der Suche besitzt jede Primzahl \(p\) ihren endgültigen Schwellenwert \(\tau(p)\). Anschließend wird die Primzahlliste genau einmal durchlaufen und über alle \(p\) mit \(\tau(p)>p\) aufsummiert.
Setze
$$V=\pi(L),\qquad D=\lfloor \log_{10} L \rfloor + 1.$$
Das Sieb benötigt \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher. Für jede entnommene Primzahl untersucht die Nachbarschaftserzeugung höchstens \(9D\) Ersetzungen, eine Löschung und bis zu neun Voranstellungen, also insgesamt einen impliziten Graphen mit \(E=O(VD)\) Kandidatenrelaxationen. Die Prioritätswarteschlange kostet damit
$$O(E\log V)=O(VD\log V).$$
Insgesamt ergibt sich somit
$$O(L\log\log L + VD\log V)$$
Zeit und \(O(L)\) Speicher.
\(L\) sabit bir üst sınır olsun. \(L\)'ye kadar olan asal sayılar üzerinde bir grafik kuruyoruz. İki asal, biri diğerine izin verilen tek bir ondalık düzenleme ile dönüşebiliyorsa ve sonuç yine asal kalıyorsa komşudur. İzin verilen işlemler şunlardır: baştaki basamağı 0 yapmadan tek basamak değiştirmek, en soldaki basamağı silmek ve sola yeni bir sıfır olmayan basamak eklemek.
İstenen toplam, tam grafikte ulaşılamayan tüm asalların toplamı değildir. Her asal \(p\) için ara düğüm olarak yalnızca \(\le p\) olan asallara izin verilir. Bir asal tam olarak, bu kısıtlı grafikte 2 ile hâlâ bağlı değilse toplama girer.
\(\mathbb{P}\) asal sayı kümesi olsun ve
$$V_L=\mathbb{P}\cap [2,L].$$
Buradan \(G_L=(V_L,E_L)\) adlı yönsüz bir grafik tanımlarız. İki asal arasında, biri diğerinden tam bir izinli ondalık işlemle elde ediliyorsa bir kenar vardır. Basamak değiştirme simetriktir; en soldaki basamağı silmek de sola basamak eklemenin tersidir. Bu yüzden grafik yönsüz kabul edilebilir.
Bir asal \(d\) basamaklıysa komşular üç hareket ailesinden gelir:
1. \(d\) basamaktan biri değiştirilir, ancak ilk basamak 0 yapılamaz;
2. eğer \(d \ge 2\) ise ilk basamak silinir;
3. sola \(\{1,\dots,9\}\) kümesinden bir basamak eklenir.
Grafikte yalnızca asal sonuçlar tutulur.
Her \(t \le L\) için,
$$V_t=\mathbb{P}\cap [2,t]$$
üzerindeki indüklenmiş alt grafiğe \(G_{\le t}\) diyelim. 2 ile \(p\)'nin \(G_{\le t}\) içinde bağlı olmasını \(2 \sim_t p\) ile gösterelim. O zaman aranan toplam
$$S(L)=\sum_{\substack{p\in\mathbb{P}\\ p\le L\\ 2 \not\sim_p p}} p$$
şeklindedir. Dolayısıyla soru, \(p\)'nin tam grafikte bir noktada 2'ye bağlanıp bağlanmadığı değildir; \(\,p\)'den büyük tüm asallar atıldığında bağlantının zaten oluşmuş olup olmadığıdır.
\(\tau(p)\), 2 ile \(p\)'yi birbirine bağlayan en küçük eşik değeri olsun. Yani 2 ile \(p\), \(G_{\le \tau(p)}\) içinde ilk kez bağlanır. Bir yol için
$$P=(q_0=2,q_1,\dots,q_k=p)$$
şişe-boynu değerini
$$B(P)=\max_{0\le i\le k} q_i$$
olarak tanımlayalım. O zaman
$$\tau(p)=\min_{P:2\leadsto p} B(P).$$
Bu özdeşlik çözümün ana matematiksel indirgemesidir. Bir yolun şişe-boynu \(M\) ise o yoldaki tüm düğümler \(G_{\le M}\) içinde kalır; dolayısıyla \(2 \sim_M p\). Tersine, \(2 \sim_t p\) ise \(G_{\le t}\) içinde onları bağlayan bir yol vardır ve bu yol üzerindeki en büyük asal en fazla \(t\)'dir. Böylece en küçük eşik ile en küçük şişe-boynu aynı nicelik olur.
Artık toplama girme ölçütü doğrudan
$$\tau(p)>p$$
şeklindedir. Yani 2'den \(p\)'ye giden her yol, bir noktada \(p\)'den büyük bir asal üzerinden geçmek zorundadır.
\(\tau(p)\) minimax tipi bir değer olsa da, Dijkstra algoritmasının aynı açgözlü yapısıyla hesaplanabilir. Olağan yol uzunluğu yerine her düğüm için bilinen en iyi şişe-boynu etiketi tutulur. Başlangıçta 2'nin etiketi 2, diğer tüm düğümlerin etiketi \(+\infty\) alınır.
\(u\) asalı mevcut \(d(u)\) etiketiyle biliniyor ve \(v\) onun asal komşusu olsun. \(u\)'ya kadar şişe-boynu \(d(u)\) olan bir yol, \(v\)'ye uzatıldığında yeni şişe-boynu
$$\max(d(u),v)$$
olur. Bu nedenle gevşetme kuralı
$$d(v)\leftarrow \min\bigl(d(v),\max(d(u),v)\bigr)$$
şeklindedir. Yol uzadıkça şişe-boynu küçülemeyeceği için etiketler monotondur; dolayısıyla öncelik kuyruğundan çıkan en küçük geçici etiket daha sonra iyileştirilemez. Bu, Dijkstra'nın klasik doğruluk kanıtının aynısıdır; yalnızca toplama yerine \(\max\) kullanılır.
11, ilk ilginç örnektir. Şu yol vardır:
$$2 \to 3 \to 13 \to 11,$$
bu yüzden \(\tau(11)\le 13\). Öte yandan \(G_{\le 11}\) içinde 11'in geçerli bir komşusu yoktur: izin verilen tek adımlık işlemlerin her biri ya asal olmayan bir sayı, ya başında 0 bulunan geçersiz bir gösterim, ya da 11'den büyük bir asal üretir. Demek ki \(2 \not\sim_{11} 11\) ve
$$\tau(11)=13>11.$$
Dolayısıyla 11 toplama girer.
Aynı minimax araması ayrıca
$$\tau(101)=\tau(103)=\tau(107)=\tau(109)=113$$
sonucunu verir. Böylece \(10^3\)'ten küçük katkı veren asallar
$$11,\ 101,\ 103,\ 107,\ 109$$
olur ve
$$S(10^3)=11+101+103+107+109=431$$
elde edilir. Bu, uygulamadaki kontrol değeriyle aynıdır. İkinci bir kontrol değeri de
$$S(10^4)=78728$$
şeklindedir.
C++, Python ve Java uygulamaları önce \(L\)'ye kadar bir Eratosthenes eleği kurar; böylece asal testi sabit zamanlı tablo sorgusuna dönüşür. Ayrıca ondalık basamaklara doğrudan erişebilmek için 10'un kuvvetleri önceden hazırlanır.
Grafik açıkça kurulmaz. Bunun yerine, öncelik kuyruğundan bir asal çıktığında onun ondalık gösteriminden tüm geçerli tek adımlık düzenlemeler üretilir: aynı uzunlukta basamak değiştirme, en soldaki basamağı silme ve sola sıfır olmayan bir basamak ekleme. Her aday elekten geçirilir; asal olanlar yukarıdaki şişe-boynu kuralıyla gevşetilir.
Kuyruk boşaldıktan sonra her asal \(p\) için nihai eşik değeri \(\tau(p)\) belirlenmiş olur. Son adımda asal listesi bir kez taranır ve yalnızca \(\tau(p)>p\) koşulunu sağlayan asallar toplanır.
Şu notasyonu kullanalım:
$$V=\pi(L),\qquad D=\lfloor \log_{10} L \rfloor + 1.$$
Elek \(O(L\log\log L)\) zaman ve \(O(L)\) bellek ister. Çıkarılan her asal için komşu üretimi en fazla \(9D\) basamak değişimi, bir silme ve en çok dokuz sola ekleme inceler; dolayısıyla örtük grafik tarafı \(E=O(VD)\) aday gevşetme içerir. Öncelik kuyruğu aşaması bu yüzden
$$O(E\log V)=O(VD\log V)$$
maliyetine sahiptir. Toplam karmaşıklık
$$O(L\log\log L + VD\log V)$$
zaman ve \(O(L)\) bellek olur.
Fijado un límite \(L\), consideramos todos los primos hasta \(L\) y unimos dos de ellos cuando una sola edición decimal permitida transforma uno en el otro y el resultado sigue siendo primo. Las ediciones permitidas son: cambiar un dígito sin crear un cero inicial, eliminar el dígito más significativo o anteponer un nuevo dígito distinto de cero.
La suma pedida no recorre simplemente los primos inalcanzables en el grafo completo. Para cada primo \(p\), solo se permiten como vértices intermedios los primos \(\le p\). Un primo aporta exactamente cuando 2 sigue desconectado de \(p\) dentro de ese subgrafo restringido.
Sea \(\mathbb{P}\) el conjunto de los primos y definamos
$$V_L=\mathbb{P}\cap [2,L].$$
Construimos un grafo no dirigido \(G_L=(V_L,E_L)\). Dos primos están unidos por una arista si uno se obtiene del otro mediante exactamente una edición decimal permitida. Cambiar un dígito es una operación simétrica, y eliminar el dígito inicial es la inversa de anteponer un dígito, así que el grafo puede tratarse como no dirigido.
Si un primo tiene \(d\) cifras, sus vecinos proceden de tres familias de movimientos:
1. cambiar una de las \(d\) cifras, con la restricción de que la primera no puede pasar a 0;
2. si \(d \ge 2\), eliminar la primera cifra;
3. anteponer a la izquierda una cifra de \(\{1,\dots,9\}\).
Solo permanecen en el grafo los resultados que siguen siendo primos.
Para cada \(t \le L\), llamemos \(G_{\le t}\) al subgrafo inducido sobre
$$V_t=\mathbb{P}\cap [2,t].$$
Escribimos \(2 \sim_t p\) cuando 2 y \(p\) están conectados en \(G_{\le t}\). Entonces la suma buscada es
$$S(L)=\sum_{\substack{p\in\mathbb{P}\\ p\le L\\ 2 \not\sim_p p}} p.$$
La condición correcta, por tanto, no es si \(p\) se conecta con 2 en algún momento dentro del grafo completo hasta \(L\), sino si ya se conecta cuando eliminamos todos los primos mayores que \(p\).
Definimos \(\tau(p)\) como el menor umbral \(t\) para el cual \(2 \sim_t p\). Para cualquier camino
$$P=(q_0=2,q_1,\dots,q_k=p)$$
definimos su valor de cuello de botella por
$$B(P)=\max_{0\le i\le k} q_i.$$
Entonces se cumple
$$\tau(p)=\min_{P:2\leadsto p} B(P).$$
Esta identidad es la reducción clave. Si un camino tiene cuello de botella \(M\), todos sus vértices pertenecen a \(G_{\le M}\), así que \(2 \sim_M p\). A la inversa, si \(2 \sim_t p\), existe un camino en \(G_{\le t}\) cuyo vértice máximo no supera \(t\). Por eso el umbral mínimo y el mínimo cuello de botella coinciden.
Por tanto, el criterio de contribución se reduce a
$$\tau(p)>p.$$
Es decir, todo camino desde 2 hasta \(p\) está obligado a pasar por algún primo estrictamente mayor que \(p\).
El valor minimax \(\tau(p)\) puede calcularse con la misma estructura voraz que el algoritmo de Dijkstra. En lugar de una distancia aditiva ordinaria, cada vértice guarda el mejor cuello de botella conocido. La inicialización es \(2\) en el vértice 2 y \(+\infty\) en los demás.
Si \(u\) es un primo ya alcanzado con etiqueta actual \(d(u)\) y \(v\) es un vecino primo de \(u\), cualquier camino a \(u\) con cuello de botella \(d(u)\) se prolonga a \(v\) con cuello de botella
$$\max(d(u),v).$$
Por tanto la relajación es
$$d(v)\leftarrow \min\bigl(d(v),\max(d(u),v)\bigr).$$
La corrección es la misma que en Dijkstra: al extender un camino, el cuello de botella no puede disminuir. Por ello, una vez extraída de la cola de prioridad la menor etiqueta tentativa, ninguna ruta futura puede mejorarla.
El primo 11 es el primer caso interesante. Existe el camino
$$2 \to 3 \to 13 \to 11,$$
de modo que \(\tau(11)\le 13\). Sin embargo, dentro del grafo umbral \(G_{\le 11}\), el vértice 11 no tiene ninguna arista válida: toda edición decimal permitida produce un compuesto, un número con cero inicial o un primo mayor que 11. Luego \(2 \not\sim_{11} 11\) y
$$\tau(11)=13>11.$$
Por eso 11 sí aporta a la suma.
La misma búsqueda minimax también da
$$\tau(101)=\tau(103)=\tau(107)=\tau(109)=113.$$
Así, los primos que contribuyen por debajo de \(10^3\) son
$$11,\ 101,\ 103,\ 107,\ 109,$$
y por tanto
$$S(10^3)=11+101+103+107+109=431.$$
Este valor coincide con el punto de control usado por la implementación. Un segundo punto de control es
$$S(10^4)=78728.$$
Las implementaciones en C++, Python y Java empiezan construyendo una criba de Eratóstenes hasta \(L\), de modo que la primalidad se consulta en tiempo constante. También precomputan las potencias de 10 para acceder directamente a cada posición decimal.
El grafo nunca se materializa por completo. En su lugar, cada vez que la cola de prioridad extrae un primo, la implementación genera al vuelo todas las ediciones válidas de un paso sobre su representación decimal: reemplazos de cifra con la misma longitud, eliminación de la cifra más significativa y anteposición de una cifra no nula. Cada candidato se filtra con la criba, y los candidatos primos se relajan con la regla minimax anterior.
Cuando la cola se vacía, cada primo \(p\) tiene fijado su valor final \(\tau(p)\). La respuesta se obtiene recorriendo la lista de primos una sola vez y sumando exactamente aquellos con \(\tau(p)>p\).
Sea
$$V=\pi(L),\qquad D=\lfloor \log_{10} L \rfloor + 1.$$
La criba cuesta \(O(L\log\log L)\) tiempo y \(O(L)\) memoria. Para cada primo extraído se examinan como mucho \(9D\) reemplazos, una eliminación y hasta nueve anteposiciones, así que el grafo implícito aporta \(E=O(VD)\) relajaciones candidatas. La fase con cola de prioridad cuesta entonces
$$O(E\log V)=O(VD\log V).$$
En conjunto, la complejidad total es
$$O(L\log\log L + VD\log V)$$
en tiempo y \(O(L)\) en memoria.
固定上界 \(L\)。我们只考虑不超过 \(L\) 的质数，并在这些质数之间建立一张图。如果一个质数能够通过一次合法的十进制编辑变成另一个质数，而且结果仍然是质数，那么这两个质数之间连一条边。允许的编辑包括：修改一位数字但不能产生前导零，删除最高位数字，或在最前面添加一个新的非零数字。
题目要求的并不是整张图中所有“不可达”质数之和。对于每个质数 \(p\)，中间经过的质数只能取到 \(\le p\)。只有当 2 在这个截断后的子图里仍然无法连到 \(p\) 时，\(p\) 才计入答案。
记 \(\mathbb{P}\) 为质数集合，并定义
$$V_L=\mathbb{P}\cap [2,L].$$
构造无向图 \(G_L=(V_L,E_L)\)。如果两个质数可以通过一次允许的十进制编辑互相得到，就在它们之间连边。改一位数字本身是对称的；删除最高位与前置一位数字互为逆操作，因此整张图可以看成无向图。
若某个质数有 \(d\) 位，它的邻居来自三类操作：
1. 修改这 \(d\) 位中的某一位，但首位不能改成 0；
2. 若 \(d \ge 2\)，删除最高位；
3. 在最前面添加一位 \(\{1,\dots,9\}\) 中的数字。
只有结果仍为质数时，对应顶点才保留在图中。
对每个 \(t \le L\)，令 \(G_{\le t}\) 表示顶点集
$$V_t=\mathbb{P}\cap [2,t]$$
上的诱导子图。若 2 与 \(p\) 在 \(G_{\le t}\) 中连通，记作 \(2 \sim_t p\)。那么所求和为
$$S(L)=\sum_{\substack{p\in\mathbb{P}\\ p\le L\\ 2 \not\sim_p p}} p.$$
因此关键不在于 \(p\) 是否最终会在完整图中与 2 连通，而在于当我们把所有大于 \(p\) 的质数都删掉时，这种连通性是否已经出现。
定义 \(\tau(p)\) 为使得 \(2 \sim_t p\) 成立的最小阈值 \(t\)。对任意路径
$$P=(q_0=2,q_1,\dots,q_k=p)$$
定义其瓶颈值为
$$B(P)=\max_{0\le i\le k} q_i.$$
则有
$$\tau(p)=\min_{P:2\leadsto p} B(P).$$
这是整道题最重要的数学化简。若某条路径的瓶颈值为 \(M\)，则该路径上的所有顶点都落在 \(G_{\le M}\) 中，所以 \(2 \sim_M p\)。反过来，如果 \(2 \sim_t p\)，那么 \(G_{\le t}\) 中存在一条连接 2 与 \(p\) 的路径，它的最大顶点不超过 \(t\)。因此，“最小可连通阈值”和“最小可能瓶颈值”是同一个量。
于是贡献条件可以直接写成
$$\tau(p)>p.$$
这句话的含义是：从 2 走到 \(p\) 的任何路径，都被迫经过一个严格大于 \(p\) 的质数。
虽然 \(\tau(p)\) 不是普通的加法距离，但仍可用与 Dijkstra 算法相同的贪心结构来计算。每个顶点维护当前已知的最优瓶颈标签。初始化时，顶点 2 的标签为 2，其余顶点为 \(+\infty\)。
设当前已知某个质数 \(u\) 的标签为 \(d(u)\)，而 \(v\) 是 \(u\) 的一个质数邻居。若到 \(u\) 的路径瓶颈为 \(d(u)\)，那么把这条路径延伸到 \(v\) 后，新的瓶颈就是
$$\max(d(u),v).$$
因此松弛公式为
$$d(v)\leftarrow \min\bigl(d(v),\max(d(u),v)\bigr).$$
这与普通 Dijkstra 的正确性证明完全同构，因为路径一旦延长，瓶颈不可能下降。所以当优先队列中最小的暂定标签被取出之后，后续路径不可能再把它改得更小。
质数 11 是第一个真正有代表性的例子。存在路径
$$2 \to 3 \to 13 \to 11,$$
所以 \(\tau(11)\le 13\)。另一方面，在阈值子图 \(G_{\le 11}\) 中，顶点 11 没有任何合法邻边：任意一次允许的十进制编辑都会得到合数、带前导零的非法表示，或者一个大于 11 的质数。因此 \(2 \not\sim_{11} 11\)，从而
$$\tau(11)=13>11.$$
所以 11 必须计入答案。
同样的 minimax 搜索还给出
$$\tau(101)=\tau(103)=\tau(107)=\tau(109)=113.$$
因此，\(10^3\) 以下会贡献的质数恰好是
$$11,\ 101,\ 103,\ 107,\ 109,$$
于是
$$S(10^3)=11+101+103+107+109=431.$$
这与实现中的校验值一致。第二个校验值是
$$S(10^4)=78728.$$
C++、Python 和 Java 实现都先建立到 \(L\) 为止的埃拉托斯特尼筛，从而把质数判定变成常数时间的表查询。同时还预计算了若干个 10 的幂，便于直接访问十进制的各个位置。
整张图不会被显式构造。相反，每当优先队列弹出一个质数时，程序就按需生成它十进制表示的一步合法变换：同位数改一位、删除最高位、或前置一个非零数字。每个候选值都通过筛表检查，只对质数候选执行上面的瓶颈松弛。
当优先队列处理完毕后，每个质数 \(p\) 都得到了最终的 \(\tau(p)\)。最后只需扫描一遍质数表，把所有满足 \(\tau(p)>p\) 的质数相加即可。
记
$$V=\pi(L),\qquad D=\lfloor \log_{10} L \rfloor + 1.$$
筛法耗时 \(O(L\log\log L)\)，空间 \(O(L)\)。对每个被取出的质数，邻居生成最多检查 \(9D\) 次替换、1 次删除以及至多 9 次前置，因此隐式图一共对应 \(E=O(VD)\) 次候选松弛。优先队列部分的代价于是为
$$O(E\log V)=O(VD\log V).$$
总时间复杂度为
$$O(L\log\log L + VD\log V),$$
总空间复杂度为 \(O(L)\)。
Пусть задан предел \(L\). Рассматриваются все простые числа, не превосходящие \(L\), и строится граф, в котором два простых соединены ребром, если одно разрешенное десятичное редактирование переводит одно число в другое и результат снова является простым. Разрешены три операции: заменить одну цифру без появления ведущего нуля, удалить старшую цифру или приписать слева новую ненулевую цифру.
Требуемая сумма берется не по всем вершинам, недостижимым в полном графе. Для каждого простого \(p\) промежуточными вершинами разрешены только простые \(\le p\). Простое число входит в ответ тогда и только тогда, когда в этом усеченном графе число 2 все еще не соединено с \(p\).
Обозначим через \(\mathbb{P}\) множество простых чисел и положим
$$V_L=\mathbb{P}\cap [2,L].$$
Строим неориентированный граф \(G_L=(V_L,E_L)\). Ребро соединяет два простых тогда и только тогда, когда одно разрешенное десятичное изменение переводит одно число в другое. Замена цифры симметрична, а удаление старшей цифры является обратной операцией к приписыванию цифры слева, поэтому граф естественно считать неориентированным.
Если простое число имеет \(d\) цифр, его соседи получаются из трех типов ходов:
1. заменить одну из \(d\) цифр, причем первая цифра не может стать 0;
2. если \(d \ge 2\), удалить старшую цифру;
3. приписать слева цифру из \(\{1,\dots,9\}\).
В графе сохраняются только те результаты, которые тоже являются простыми.
Для каждого \(t \le L\) обозначим через \(G_{\le t}\) индуцированный подграф на множестве
$$V_t=\mathbb{P}\cap [2,t].$$
Пишем \(2 \sim_t p\), если 2 и \(p\) связаны в \(G_{\le t}\). Тогда искомая сумма равна
$$S(L)=\sum_{\substack{p\in\mathbb{P}\\ p\le L\\ 2 \not\sim_p p}} p.$$
Иными словами, важно не то, достижимо ли \(p\) из 2 где-нибудь в полном графе до \(L\), а то, существует ли связь уже после удаления всех простых, больших \(p\).
Определим \(\tau(p)\) как наименьший порог \(t\), при котором выполняется \(2 \sim_t p\). Для любого пути
$$P=(q_0=2,q_1,\dots,q_k=p)$$
введем bottleneck-значение
$$B(P)=\max_{0\le i\le k} q_i.$$
Тогда
$$\tau(p)=\min_{P:2\leadsto p} B(P).$$
Это и есть основное математическое упрощение. Если у пути bottleneck равен \(M\), то все его вершины лежат в \(G_{\le M}\), следовательно, \(2 \sim_M p\). Обратно, если \(2 \sim_t p\), то в \(G_{\le t}\) существует путь от 2 к \(p\), а его максимальная вершина не превосходит \(t\). Значит, минимальный порог совпадает с минимальным возможным bottleneck-значением.
Условие участия в сумме теперь просто таково:
$$\tau(p)>p.$$
То есть любой путь от 2 к \(p\) вынужден проходить через простое, строго большее самого \(p\).
Хотя \(\tau(p)\) не является обычной аддитивной длиной пути, его можно вычислять тем же жадным механизмом, что и в алгоритме Дейкстры. Вместо стандартного расстояния у каждой вершины хранится лучший известный bottleneck. Инициализация такова: для вершины 2 ставится значение 2, для всех остальных \(+\infty\).
Пусть для простого \(u\) текущая метка равна \(d(u)\), а \(v\) является простым соседом \(u\). Тогда путь к \(u\) с bottleneck \(d(u)\) продолжается до \(v\) с bottleneck
$$\max(d(u),v).$$
Поэтому шаг релаксации выглядит так:
$$d(v)\leftarrow \min\bigl(d(v),\max(d(u),v)\bigr).$$
Корректность повторяет стандартный довод для Дейкстры: при продолжении пути bottleneck не может уменьшиться. Значит, когда из очереди с приоритетом извлекается наименьшая временная метка, позднее ее уже нельзя улучшить.
Первый показательный пример дает простое число 11. Существует путь
$$2 \to 3 \to 13 \to 11,$$
поэтому \(\tau(11)\le 13\). Но в пороговом графе \(G_{\le 11}\) вершина 11 не имеет ни одного допустимого инцидентного ребра: каждое разрешенное десятичное редактирование дает либо составное число, либо запись с ведущим нулем, либо простое число, большее 11. Следовательно, \(2 \not\sim_{11} 11\), а значит
$$\tau(11)=13>11.$$
Поэтому 11 входит в ответ.
Тот же minimax-поиск дает также
$$\tau(101)=\tau(103)=\tau(107)=\tau(109)=113.$$
Значит, под \(10^3\) вклад дают простые
$$11,\ 101,\ 103,\ 107,\ 109,$$
и потому
$$S(10^3)=11+101+103+107+109=431.$$
Это совпадает с контрольным значением реализации. Второй контрольный результат равен
$$S(10^4)=78728.$$
Реализации на C++, Python и Java сначала строят решето Эратосфена до \(L\), после чего проверка простоты сводится к чтению из таблицы. Дополнительно заранее вычисляются степени 10, чтобы быстро обращаться к отдельным десятичным позициям.
Полный граф в памяти не хранится. Вместо этого при извлечении очередного простого из очереди с приоритетом программа на лету порождает все допустимые одношаговые изменения его десятичной записи: замены цифры, удаление старшей цифры и приписывание слева новой ненулевой цифры. Каждый кандидат фильтруется через решето, и только простые кандидаты проходят minimax-релаксацию.
Когда очередь опустевает, для каждого простого \(p\) уже известно окончательное значение \(\tau(p)\). Остается один раз пройти по списку простых и просуммировать те из них, для которых \(\tau(p)>p\).
Положим
$$V=\pi(L),\qquad D=\lfloor \log_{10} L \rfloor + 1.$$
Решето требует \(O(L\log\log L)\) времени и \(O(L)\) памяти. Для каждого извлеченного простого порождение соседей проверяет не более \(9D\) замен, одно удаление и до девяти приписываний, поэтому неявный граф дает \(E=O(VD)\) кандидатных релаксаций. Работа очереди с приоритетом составляет
$$O(E\log V)=O(VD\log V).$$
Итоговая сложность равна
$$O(L\log\log L + VD\log V)$$
по времени и \(O(L)\) по памяти.
لنثبت حدًا أعلى \(L\). ننظر إلى جميع الأعداد الأولية حتى \(L\)، ونبني رسمًا بيانيًا تصل فيه بين عددين أوليين حافة واحدة إذا أمكن الحصول على أحدهما من الآخر بتعديل عشري مسموح واحد مع بقاء الناتج أوليًا. التعديلات المسموحة هي: تغيير رقم واحد من دون توليد صفر بادئ، حذف الرقم الأكثر أهمية، أو إضافة رقم جديد غير صفري في اليسار.
المجموع المطلوب ليس مجموع جميع الأوليات غير القابلة للوصول في الرسم الكامل. لكل عدد أولي \(p\)، لا يُسمح باستعمال أعداد أولية وسيطة إلا إذا كانت \(\le p\). ويساهم العدد \(p\) في الجواب بالضبط عندما يبقى العدد 2 غير متصل به داخل هذا الرسم المقتطع.
لنرمز إلى مجموعة الأعداد الأولية بـ \(\mathbb{P}\)، ونعرّف
$$V_L=\mathbb{P}\cap [2,L].$$
ننشئ رسمًا بيانيًا غير موجه \(G_L=(V_L,E_L)\). تصل حافة بين عددين أوليين إذا أمكن الانتقال من أحدهما إلى الآخر بواسطة تعديل عشري مسموح واحد بالضبط. تغيير الرقم عملية متناظرة، كما أن حذف الرقم الأيسر هو المعكوس المباشر لعملية إضافة رقم جديد في اليسار، ولذلك يمكن التعامل مع الرسم على أنه غير موجه.
إذا كان للعدد الأولي \(d\) من الخانات، فإن جيرانه ينتجون من ثلاث عائلات من الحركات:
1. تغيير إحدى الخانات \(d\)، مع منع تحويل الخانة الأولى إلى 0؛
2. إذا كان \(d \ge 2\)، حذف الخانة الأولى؛
3. إضافة خانة من \(\{1,\dots,9\}\) في اليسار.
ولا تبقى في الرسم إلا النتائج التي تظل أولية.
لكل \(t \le L\)، لنسَمِّ \(G_{\le t}\) الرسم الجزئي المستحث على المجموعة
$$V_t=\mathbb{P}\cap [2,t].$$
ونكتب \(2 \sim_t p\) إذا كان 2 و\(p\) متصلين داخل \(G_{\le t}\). عندئذ يصبح المطلوب
$$S(L)=\sum_{\substack{p\in\mathbb{P}\\ p\le L\\ 2 \not\sim_p p}} p.$$
إذن السؤال الحقيقي ليس هل يتصل \(p\) في النهاية بالعدد 2 داخل الرسم الكامل حتى \(L\)، بل هل يحصل هذا الاتصال بالفعل بعد حذف جميع الأوليات الأكبر من \(p\).
عرّف \(\tau(p)\) بأنه أصغر حد \(t\) يحقق \(2 \sim_t p\). ولكل مسار
$$P=(q_0=2,q_1,\dots,q_k=p)$$
نعرّف قيمة عنق الزجاجة بـ
$$B(P)=\max_{0\le i\le k} q_i.$$
وعندئذ
$$\tau(p)=\min_{P:2\leadsto p} B(P).$$
هذه هي الخطوة الرياضية الحاسمة. فإذا كان لمسار ما عنق زجاجة قيمته \(M\)، فإن جميع رؤوسه تقع داخل \(G_{\le M}\)، ومن ثم \(2 \sim_M p\). وبالعكس، إذا تحقق \(2 \sim_t p\)، فهناك مسار داخل \(G_{\le t}\) يصل بينهما، وأكبر رأس عليه لا يتجاوز \(t\). لذا فإن أصغر عتبة اتصال تساوي بالضبط أصغر قيمة bottleneck ممكنة.
ومن ثم يصبح شرط المساهمة ببساطة
$$\tau(p)>p.$$
أي إن كل مسار من 2 إلى \(p\) مضطر إلى المرور بعدد أولي أكبر من \(p\) نفسه.
رغم أن \(\tau(p)\) ليست مسافة جمعيّة عادية، فإنها تُحسب بالبنية الجشعة نفسها المستعملة في خوارزمية ديكسترا. بدل طول المسار المعتاد، يحتفظ كل رأس بأفضل وسم bottleneck معروف حتى الآن. التهيئة هي: وسم الرأس 2 يساوي 2، وجميع الرؤوس الأخرى تساوي \(+\infty\).
إذا كان \(u\) عددًا أوليًا معروفًا حاليًا بوسم \(d(u)\)، وكان \(v\) جارًا أوليًا له، فإن أي مسار إلى \(u\) بعنق زجاجة \(d(u)\) يمتد إلى \(v\) بعنق زجاجة
$$\max(d(u),v).$$
لذلك تكون قاعدة الاسترخاء
$$d(v)\leftarrow \min\bigl(d(v),\max(d(u),v)\bigr).$$
والسبب في صحة هذه الفكرة هو أن تمديد المسار لا يمكن أن يُنقص قيمة عنق الزجاجة. لذا، فعندما تخرج أصغر قيمة مؤقتة من طابور الأولوية، لا يمكن لأي مسار لاحق أن يحسنها. وهذا هو برهان ديكسترا المعتاد نفسه، مع استبدال الجمع بـ \(\max\).
العدد 11 هو أول مثال غير تافه. يوجد المسار
$$2 \to 3 \to 13 \to 11,$$
ومن ثم \(\tau(11)\le 13\). لكن داخل رسم العتبة \(G_{\le 11}\)، لا يملك الرأس 11 أي حافة صالحة: كل تعديل عشري مسموح بخطوة واحدة يعطي إما عددًا غير أولي، أو تمثيلًا ذا صفر بادئ، أو عددًا أوليًا أكبر من 11. لذلك \(2 \not\sim_{11} 11\)، وبالتالي
$$\tau(11)=13>11.$$
إذن 11 يُضاف إلى المجموع.
ويُظهر البحث minimax نفسه أيضًا أن
$$\tau(101)=\tau(103)=\tau(107)=\tau(109)=113.$$
وعليه فإن الأوليات التي تسهم تحت \(10^3\) هي
$$11,\ 101,\ 103,\ 107,\ 109,$$
ومن ثم
$$S(10^3)=11+101+103+107+109=431.$$
وهذا يطابق قيمة الفحص المستعملة في التنفيذ. كما أن قيمة فحص ثانية هي
$$S(10^4)=78728.$$
تبدأ التطبيقات المكتوبة بلغة C++ وPython وJava ببناء غربال إراتوستينس حتى \(L\)، وبذلك تصبح فحوص الأولية مجرد وصول مباشر إلى جدول. كما تُحسب مسبقًا قوى العدد 10 من أجل الوصول السريع إلى مواضع الخانات العشرية.
ولا يُبنى الرسم البياني كاملًا في الذاكرة. بدلًا من ذلك، كلما أخرج طابور الأولوية عددًا أوليًا، تولد التطبيقات جميع التعديلات الصحيحة ذات الخطوة الواحدة على تمثيله العشري: استبدال رقم مع الحفاظ على الطول، حذف الخانة الأكثر أهمية، أو إضافة خانة غير صفرية في اليسار. بعد ذلك تُصفّى القيم المرشحة بواسطة الغربال، ولا تُرخّى إلا المرشحات الأولية وفق قاعدة bottleneck السابقة.
بعد انتهاء عمل الطابور، يكون لكل عدد أولي \(p\) وسمه النهائي \(\tau(p)\). وفي الخطوة الأخيرة تُفحص قائمة الأوليات مرة واحدة، ويُجمع منها فقط ما يحقق \(\tau(p)>p\).
لنكتب
$$V=\pi(L),\qquad D=\lfloor \log_{10} L \rfloor + 1.$$
تكلفة الغربال هي \(O(L\log\log L)\) زمنًا و\(O(L)\) ذاكرة. ولكل عدد أولي يُستخرج من الطابور، فإن توليد الجيران يفحص في أسوأ الأحوال \(9D\) استبدالات، وعملية حذف واحدة، وحتى تسع عمليات إضافة على اليسار، لذا فإن الرسم الضمني ينتج \(E=O(VD)\) عملية استرخاء مرشحة. ومن ثم فإن مرحلة طابور الأولوية تكلف
$$O(E\log V)=O(VD\log V).$$
وعليه يكون التعقيد الكلي
$$O(L\log\log L + VD\log V)$$
زمنًا و\(O(L)\) ذاكرة.