A two-sided truncatable prime is a prime number that stays prime after repeatedly deleting digits from the left and also after repeatedly deleting digits from the right. The single-digit primes \(2,3,5,7\) are excluded, so the search starts with multi-digit candidates only.
The goal is to find the 11 such numbers in base 10 and add them. The implementations use the fact that the problem statement guarantees there are exactly 11 solutions, so the search can stop as soon as the eleventh one is found. The resulting sum is \(748317\).
There is no recurrence or hidden closed form here. The central mathematical object is the decimal expansion of a prime and the invariant that every proper prefix and every proper suffix of that expansion must also be prime.
Let
$$p = d_1 d_2 \cdots d_k$$
be the decimal representation of a \(k\)-digit prime. For each cut position \(c=1,2,\dots,k-1\), define the right truncation and left truncation by
$$R_c = \left\lfloor \frac{p}{10^c} \right\rfloor,$$
$$L_c = \text{the integer represented by } d_{c+1} d_{c+2} \cdots d_k.$$
Then \(p\) is truncatable exactly when
$$p,\ R_1,\dots,R_{k-1},\ L_1,\dots,L_{k-1}$$
are all prime. In other words, every proper prefix and every proper suffix of the decimal string must be prime. This is the precise condition checked by the C++, Python, and Java implementations.
Some digits are impossible before any search begins. The first digit \(d_1\) must be one of \(2,3,5,7\), because after enough right truncations only that digit remains. The last digit \(d_k\) must be \(3\) or \(7\): it must itself be prime after all left truncations, but a multi-digit prime cannot end in \(2\) or \(5\).
Every interior digit must belong to \(\{1,3,7,9\}\). The reason is that each interior digit becomes the last digit of some proper prefix, and every such prefix must be prime. An even interior digit or a \(5\) would force one of those prefixes to be composite. These restrictions explain why valid examples are rare.
Since every truncatable prime in this problem has at least two digits, it is odd and larger than \(10\). Therefore the search may begin at \(11\) and advance by \(2\), never missing a valid answer. For each odd candidate \(n\), the algorithm first checks whether \(n\) itself is prime. Only then does it examine all cut positions.
The stopping rule comes directly from the problem statement: there are exactly 11 truncatable primes. So the search is not based on a guessed numerical limit; it terminates when the count reaches 11.
The standard positive example is \(3797\). Its right truncations are
$$3797,\ 379,\ 37,\ 3,$$
and its left truncations are
$$3797,\ 797,\ 97,\ 7.$$
Every number in both chains is prime, so \(3797\) is truncatable.
A useful contrast is \(47\). It is prime, and its left truncation is \(7\), which is prime, but its right truncation is \(4\), which is not prime. So being prime is far from sufficient; both truncation directions must survive every cut.
The implementation uses a direct primality test. Numbers below \(2\) are rejected immediately. Even numbers are prime only when the number is \(2\). For an odd candidate \(n\), the code tries odd divisors \(3,5,7,\dots\) up to the point where \(p \le n/p\), which is equivalent to \(p^2 \le n\). If no divisor is found, the number is prime.
If \(n<10\), the candidate is rejected because single-digit primes are excluded by the problem. Otherwise the decimal representation is converted to a string once. For each cut position, the suffix after the cut and the prefix before the cut are parsed back into integers. Both are sent to the primality test, and the candidate is rejected at the first composite truncation.
This mirrors the mathematical definition exactly: each cut produces one proper suffix and one proper prefix, and both must remain prime.
The search keeps two running values: how many truncatable primes have been found and the sum of those values. Starting from \(11\), it inspects only odd integers. Whenever a candidate passes the truncation test, the count is increased and the candidate is added to the running total. As soon as the count reaches 11, the algorithm returns the sum.
The implementations also include two lightweight sanity checks: \(3797\) must be accepted, while \(47\) must be rejected. Those checks confirm that both truncation directions are being enforced.
For a single integer \(n\), the trial-division primality test costs \(O(\sqrt{n})\) time and \(O(1)\) extra space. If \(n\) has \(k\) digits, the truncatability test performs one primality check on \(n\) itself and then two more for each cut position, for a total of \(2k-1\) primality tests. That gives \(O(k\sqrt{n})\) time for one candidate, with \(k = O(\log n)\).
If \(M\) is the largest odd number examined before the eleventh solution appears, the full search remains practical because only odd numbers are tested and most candidates fail quickly. A clean upper bound is \(O(M^{3/2})\) time for the whole scan with \(O(1)\) auxiliary memory, aside from temporary decimal strings of length \(O(\log M)\). For this problem, that is easily fast enough.
Eine beidseitig abschneidbare Primzahl bleibt prim, wenn man wiederholt Ziffern von links entfernt und ebenso, wenn man wiederholt Ziffern von rechts entfernt. Die einstelligen Primzahlen \(2,3,5,7\) werden dabei ausdrücklich nicht mitgezählt, also beginnt die Suche erst bei mehrstelligen Kandidaten.
Gesucht sind die 11 solchen Zahlen im Dezimalsystem und ihre Summe. Die Implementierungen nutzen die Vorgabe aus der Aufgabe, dass es genau 11 Lösungen gibt; deshalb endet die Suche sofort nach dem elften Treffer. Die erhaltene Summe ist \(748317\).
Hier gibt es keine Rekursion und keine versteckte geschlossene Formel. Der entscheidende mathematische Kern ist die Dezimaldarstellung einer Primzahl und die Invariante, dass jeder echte Präfix und jeder echte Suffix dieser Darstellung wieder eine Primzahl sein muss.
Sei
$$p = d_1 d_2 \cdots d_k$$
die Dezimaldarstellung einer \(k\)-stelligen Primzahl. Für jede Schnittposition \(c=1,2,\dots,k-1\) definieren wir die Rechtstrunkierung und die Linkstrunkierung durch
$$R_c = \left\lfloor \frac{p}{10^c} \right\rfloor,$$
$$L_c = \text{die von } d_{c+1} d_{c+2} \cdots d_k \text{ dargestellte ganze Zahl}.$$
Dann ist \(p\) genau dann abschneidbar, wenn
$$p,\ R_1,\dots,R_{k-1},\ L_1,\dots,L_{k-1}$$
allesamt prim sind. Anders gesagt: Jeder echte Präfix und jeder echte Suffix der Dezimaldarstellung muss prim bleiben. Genau diese Bedingung prüfen die C++-, Python- und Java-Implementierungen.
Einige Ziffern sind von vornherein ausgeschlossen. Die erste Ziffer \(d_1\) muss zu \(\{2,3,5,7\}\) gehören, denn nach genügend vielen Rechtstrunkierungen bleibt nur diese eine Ziffer übrig. Die letzte Ziffer \(d_k\) muss \(3\) oder \(7\) sein: Nach allen Linkstrunkierungen bleibt sie allein stehen, aber eine mehrstellige Primzahl kann nicht auf \(2\) oder \(5\) enden.
Jede innere Ziffer muss aus \(\{1,3,7,9\}\) stammen. Denn jede innere Ziffer wird zur letzten Ziffer eines echten Präfixes, und jedes dieser Präfixe muss prim sein. Eine gerade Ziffer oder eine \(5\) im Inneren würde also zwangsläufig einen zusammengesetzten Präfix erzeugen. Dadurch wird die Menge möglicher Kandidaten sehr klein.
Jede abschneidbare Primzahl dieser Aufgabe hat mindestens zwei Stellen, ist also ungerade und größer als \(10\). Deshalb kann die Suche bei \(11\) beginnen und in Zweierschritten fortlaufen, ohne eine Lösung zu übersehen. Für jeden ungeraden Kandidaten \(n\) prüft der Algorithmus zunächst, ob \(n\) selbst prim ist. Erst danach werden die Schnittpositionen untersucht.
Das Abbruchkriterium kommt direkt aus der Aufgabenstellung: Es existieren genau 11 solcher Zahlen. Die Suche braucht also keine vermutete obere Schranke; sie endet genau dann, wenn der Zähler den Wert 11 erreicht.
Das klassische positive Beispiel ist \(3797\). Seine Rechtstrunkierungen sind
$$3797,\ 379,\ 37,\ 3,$$
und seine Linkstrunkierungen sind
$$3797,\ 797,\ 97,\ 7.$$
Alle Zahlen in beiden Folgen sind prim, also ist \(3797\) abschneidbar.
Zum Vergleich betrachten wir \(47\). Diese Zahl ist prim, und ihre Linkstrunkierung \(7\) ist ebenfalls prim. Aber die Rechtstrunkierung \(4\) ist nicht prim. Daran sieht man, dass reine Primzahleigenschaft nicht genügt; beide Richtungen müssen jeden einzelnen Schnitt überstehen.
Die Implementierung verwendet einen direkten Primzahltest. Zahlen unter \(2\) werden sofort verworfen. Gerade Zahlen sind nur dann prim, wenn die Zahl \(2\) ist. Für einen ungeraden Kandidaten \(n\) werden die ungeraden Teiler \(3,5,7,\dots\) ausprobiert, solange \(p \le n/p\) gilt; das ist äquivalent zu \(p^2 \le n\). Wird kein Teiler gefunden, ist die Zahl prim.
Ist \(n<10\), wird der Kandidat sofort abgelehnt, weil einstellige Primzahlen laut Aufgabe nicht zählen. Andernfalls wird die Dezimaldarstellung einmal in einen String umgewandelt. Für jede Schnittposition werden der Suffix nach dem Schnitt und der Präfix vor dem Schnitt wieder in ganze Zahlen umgewandelt. Beide werden mit dem Primzahltest geprüft, und beim ersten zusammengesetzten Trunkat wird der Kandidat verworfen.
Damit folgt die Implementierung exakt der mathematischen Definition: Jeder Schnitt erzeugt genau einen echten Präfix und genau einen echten Suffix, und beide müssen prim bleiben.
Während der Suche werden zwei Werte fortlaufend gepflegt: die Anzahl bereits gefundener abschneidbarer Primzahlen und ihre Summe. Beginnend bei \(11\) untersucht der Algorithmus nur ungerade Zahlen. Besteht ein Kandidat die Abschneidbarkeitsprüfung, werden Zähler und Summe aktualisiert. Sobald 11 Treffer gefunden wurden, wird die Summe zurückgegeben.
Zusätzlich enthalten die Implementierungen zwei kleine Plausibilitätsprüfungen: \(3797\) muss akzeptiert werden, \(47\) muss verworfen werden. Damit wird abgesichert, dass wirklich beide Abschneiderichtungen geprüft werden.
Für eine einzelne Zahl \(n\) kostet der Primzahltest per Probedivision \(O(\sqrt{n})\) Zeit und \(O(1)\) zusätzlichen Speicher. Hat \(n\) genau \(k\) Stellen, dann führt der Abschneidbarkeitstest einen Primzahltest für \(n\) selbst und danach zwei weitere für jede Schnittposition aus, also insgesamt \(2k-1\) Primzahltests. Daraus folgt \(O(k\sqrt{n})\) Zeit pro Kandidat mit \(k = O(\log n)\).
Bezeichnet \(M\) die größte ungerade Zahl, die vor dem elften Treffer untersucht wird, dann bleibt die Gesamtsuche praktisch, weil nur ungerade Zahlen betrachtet werden und die meisten Kandidaten sehr früh scheitern. Eine saubere obere Schranke ist \(O(M^{3/2})\) Zeit bei \(O(1)\) Hilfsspeicher, abgesehen von temporären Dezimalstrings der Länge \(O(\log M)\). Für diese Aufgabe ist das problemlos schnell genug.
Çift yönlü kesilebilir asal, soldan rakam silmeye devam edildiğinde de sağdan rakam silmeye devam edildiğinde de asal kalmayı sürdüren asal sayıdır. Tek basamaklı asallar \(2,3,5,7\) bu tanıma dahil edilmez; dolayısıyla arama doğrudan çok basamaklı adaylar üzerinde yapılır.
Amaç, onluk sistemde bu özelliğe sahip 11 sayıyı bulup toplamaktır. Uygulamalar, soruda tam olarak 11 tane olduğu bilgisini doğrudan kullanır; bu yüzden arama, on birinci örnek bulunduğu anda biter. Elde edilen toplam \(748317\)'dir.
Bu problemde çözülecek bir rekürans yoktur. Asıl matematiksel nesne, bir asalın onluk gösterimi ve bu gösterimin her öz önekinin ve her öz sonekinin de asal kalması gerektiği değişmezidir.
$$p = d_1 d_2 \cdots d_k$$
biçiminde yazılan \(k\) basamaklı bir asal düşünelim. Her \(c=1,2,\dots,k-1\) kesim konumu için sağdan ve soldan kesmeleri şöyle tanımlayabiliriz:
$$R_c = \left\lfloor \frac{p}{10^c} \right\rfloor,$$
$$L_c = d_{c+1} d_{c+2} \cdots d_k \text{ dizisinin temsil ettiği tamsayı}.$$
O halde \(p\) ancak ve ancak
$$p,\ R_1,\dots,R_{k-1},\ L_1,\dots,L_{k-1}$$
sayilarinin hepsi asal ise kesilebilir asaldır. Yani onluk yazımdaki her öz önek ve her öz sonek asal kalmalıdır. C++, Python ve Java uygulamalarının denetlediği koşul tam olarak budur.
Aramaya başlamadan önce bazı rakamlar zaten elenir. İlk rakam \(d_1\), yeterince sağdan kesme yapıldığında tek başına kalacağı için \(\{2,3,5,7\}\) kümesinde olmalıdır. Son rakam \(d_k\) ise \(3\) ya da \(7\) olmak zorundadır: tüm soldan kesmelerden sonra tek basamaklı asal olarak ayakta kalmalıdır, ama çok basamaklı bir asal \(2\) ya da \(5\) ile bitemez.
İçteki her rakam \(\{1,3,7,9\}\) kümesinden gelmelidir. Çünkü her iç rakam, uygun bir anda bir önekin son basamağı olur ve bu önek asal kalmak zorundadır. İç kısımda çift bir rakam ya da \(5\) bulunması, bu öneklerden birini otomatik olarak bileşik yapar. Bu da geçerli örneklerin neden çok seyrek olduğunu açıklar.
Bu sorudaki her kesilebilir asal en az iki basamaklıdır; dolayısıyla tektir ve \(10\)'dan büyüktür. Bu yüzden arama \(11\)'den başlayıp \(2\) artarak ilerleyebilir; böylece hiçbir çözüm atlanmaz. Her tek aday \(n\) için algoritma önce \(n\)'in kendisinin asal olup olmadığını kontrol eder. Ancak bu test geçerse tüm kesim noktaları incelenir.
Durma ölçütü de doğrudan problem ifadesinden gelir: böyle sayılardan tam 11 tane vardır. Yani programın varsayımsal bir üst sınıra ihtiyacı yoktur; sayaç 11 olduğunda arama biter.
En bilinen olumlu örnek \(3797\)'dir. Bunun sağdan kesmeleri
$$3797,\ 379,\ 37,\ 3,$$
soldan kesmeleri ise
$$3797,\ 797,\ 97,\ 7$$
şeklindedir. Her iki zincirdeki tüm sayılar asal olduğundan \(3797\) kesilebilir asaldır.
Buna karşılık \(47\) asal olmasına rağmen uygun değildir. Soldan kesildiğinde \(7\) elde edilir ve bu asaldır; fakat sağdan kesildiğinde \(4\) elde edilir ve bu asal değildir. Demek ki yalnızca başlangıçta asal olmak yetmez; iki yönlü tüm kesmelerin de asal kalması gerekir.
Uygulama doğrudan bir asallık testi kullanır. \(2\)'den küçük sayılar hemen reddedilir. Çift sayılar ancak sayı \(2\) ise asaldır. Tek bir aday \(n\) için \(3,5,7,\dots\) biçimindeki tek bölenler, \(p \le n/p\) koşulu bozulana kadar denenir; bu koşul \(p^2 \le n\) ile aynıdır. Hiç bölen bulunmazsa sayı asaldır.
Eğer \(n<10\) ise aday doğrudan reddedilir; çünkü tek basamaklı asallar soruda hariç tutulmuştur. Aksi halde sayı bir kez onluk yazıma çevrilir. Her kesim konumunda, kesimden sonraki sonek ve kesimden önceki önek yeniden tamsayıya dönüştürülür. Bu iki sayı asallık testine gönderilir; ilk bileşik truncation görüldüğünde aday elenir.
Böylece uygulama, matematiksel tanımı bire bir izler: her kesim bir öz sonek ve bir öz önek üretir ve ikisinin de asal kalması gerekir.
Arama boyunca iki büyüklük tutulur: bulunan kesilebilir asal sayısı ve bunların toplamı. Başlangıç değeri \(11\) olan tarama yalnızca tek sayılar üzerinde ilerler. Bir aday testi geçtiğinde sayaç bir artırılır ve aday toplama eklenir. Sayaç 11 olduğunda algoritma toplamı döndürür.
Uygulamalarda ayrıca iki küçük sağlamlık kontrolü vardır: \(3797\) kabul edilmelidir, \(47\) ise reddedilmelidir. Bu kontroller iki kesme yönünün de gerçekten zorlandığını doğrular.
Tek bir \(n\) sayısı için deneme bölmesiyle asallık testi \(O(\sqrt{n})\) zaman ve \(O(1)\) ek bellek kullanır. \(n\) sayısının \(k\) basamağı varsa, kesilebilirlik testi \(n\)'in kendisi için bir asallık testi ve her kesim konumu için iki ek asallık testi yapar; toplam sayı \(2k-1\) olur. Dolayısıyla tek adayın maliyeti \(O(k\sqrt{n})\)'dir ve burada \(k = O(\log n)\).
Eğer \(M\), on birinci çözüm görülmeden önce incelenen en büyük tek sayı ise, tüm aramanın maliyeti pratikte düşüktür; çünkü sadece tek sayılar denenir ve çoğu aday çok erken elenir. Temiz bir üst sınır \(O(M^{3/2})\) zamandır. Yardımcı bellek \(O(1)\) düzeyindedir; yalnızca uzunluğu \(O(\log M)\) olan geçici onluk dizgeler oluşur. Bu problem boyutu için yöntem fazlasıyla yeterlidir.
Un primo truncable por ambos lados sigue siendo primo cuando se eliminan cifras sucesivamente por la izquierda y también cuando se eliminan por la derecha. Los primos de una sola cifra \(2,3,5,7\) quedan excluidos, así que la búsqueda se hace solo entre candidatos de varias cifras.
La tarea consiste en encontrar los 11 números con esa propiedad en base 10 y sumar sus valores. Las implementaciones aprovechan que el enunciado garantiza que existen exactamente 11, de modo que la exploración termina en cuanto aparece el undécimo. La suma obtenida es \(748317\).
Aquí no hay una recurrencia que resolver. El objeto matemático central es la expansión decimal de un primo y la condición invariante de que todo prefijo propio y todo sufijo propio de esa expansión también deben ser primos.
Sea
$$p = d_1 d_2 \cdots d_k$$
la representación decimal de un primo de \(k\) cifras. Para cada posición de corte \(c=1,2,\dots,k-1\), definimos la truncación por la derecha y la truncación por la izquierda como
$$R_c = \left\lfloor \frac{p}{10^c} \right\rfloor,$$
$$L_c = \text{el entero representado por } d_{c+1} d_{c+2} \cdots d_k.$$
Entonces \(p\) es truncable exactamente cuando
$$p,\ R_1,\dots,R_{k-1},\ L_1,\dots,L_{k-1}$$
son todos primos. Dicho de otra manera, cada prefijo propio y cada sufijo propio de la cadena decimal debe seguir siendo primo. Esa es justamente la condición que comprueban las implementaciones en C++, Python y Java.
Algunas cifras quedan descartadas antes de empezar. La primera cifra \(d_1\) debe pertenecer a \(\{2,3,5,7\}\), porque después de suficientes truncaciones por la derecha esa cifra queda sola. La última cifra \(d_k\) debe ser \(3\) o \(7\): después de todas las truncaciones por la izquierda también queda sola, pero un primo de varias cifras no puede terminar en \(2\) ni en \(5\).
Toda cifra interior debe estar en \(\{1,3,7,9\}\). Cada cifra interior pasa a ser la última cifra de algún prefijo propio, y ese prefijo tiene que ser primo. Una cifra interior par o igual a \(5\) obligaría a que uno de esos prefijos fuera compuesto. Estas restricciones explican por qué los ejemplos válidos son tan escasos.
Cada primo truncable de este problema tiene al menos dos cifras, así que es impar y mayor que \(10\). Por eso la búsqueda puede arrancar en \(11\) y avanzar de dos en dos sin perder ninguna solución. Para cada candidato impar \(n\), el algoritmo comprueba primero si \(n\) es primo; solo si pasa ese filtro se estudian todos los cortes.
La condición de parada viene directamente del enunciado: existen exactamente 11 primos truncables. No hace falta fijar una cota superior artificial; el proceso termina cuando el contador llega a 11.
El ejemplo positivo clásico es \(3797\). Sus truncaciones por la derecha son
$$3797,\ 379,\ 37,\ 3,$$
y sus truncaciones por la izquierda son
$$3797,\ 797,\ 97,\ 7.$$
Todos los números de ambas cadenas son primos, así que \(3797\) es truncable.
En cambio, \(47\) no sirve. El número \(47\) es primo y su truncación izquierda \(7\) también es prima, pero su truncación derecha \(4\) no lo es. Ser primo al principio no basta; hay que sobrevivir a todos los cortes en ambas direcciones.
La implementación usa una prueba directa de primalidad. Los números menores que \(2\) se rechazan de inmediato. Un número par solo es primo si es exactamente \(2\). Para un candidato impar \(n\), se prueban divisores impares \(3,5,7,\dots\) mientras se cumpla \(p \le n/p\), condición equivalente a \(p^2 \le n\). Si no aparece ningún divisor, el número es primo.
Si \(n<10\), el candidato se descarta al instante porque los primos de una cifra no cuentan. En caso contrario, se convierte una sola vez a su representación decimal como cadena. Para cada posición de corte, se toman el sufijo situado después del corte y el prefijo situado antes del corte, se vuelven a interpretar como enteros y ambos se someten a la prueba de primalidad. En cuanto una truncación resulta compuesta, el candidato queda descartado.
Eso reproduce exactamente la definición matemática: cada corte produce un prefijo propio y un sufijo propio, y los dos deben seguir siendo primos.
La búsqueda mantiene dos acumuladores: cuántos primos truncables se han encontrado y cuál es la suma de todos ellos. Empezando en \(11\), el programa inspecciona únicamente enteros impares. Cuando un candidato supera la prueba, se incrementa el contador y se añade el valor a la suma. En cuanto el contador llega a 11, se devuelve la suma.
Las implementaciones incluyen además dos comprobaciones ligeras: \(3797\) debe aceptarse y \(47\) debe rechazarse. Así se verifica que realmente se están imponiendo las dos direcciones de truncación.
Para un entero \(n\), la prueba de primalidad por división de prueba cuesta \(O(\sqrt{n})\) tiempo y \(O(1)\) memoria adicional. Si \(n\) tiene \(k\) cifras, la prueba completa de truncabilidad realiza una comprobación de primalidad para \(n\) y luego dos más por cada posición de corte, en total \(2k-1\) comprobaciones. Por tanto, el coste por candidato es \(O(k\sqrt{n})\), con \(k = O(\log n)\).
Si \(M\) denota el mayor impar examinado antes de hallar la undécima solución, la búsqueda completa sigue siendo muy razonable porque solo se recorren impares y la mayoría de los candidatos fallan enseguida. Una cota superior limpia es \(O(M^{3/2})\) tiempo y \(O(1)\) memoria auxiliar, salvo cadenas decimales temporales de longitud \(O(\log M)\). Para este problema, ese coste es pequeño.
双向可截素数指的是这样一种素数：不断从左侧删去数字时仍然是素数，不断从右侧删去数字时也仍然是素数。单个数字的素数 \(2,3,5,7\) 不计入答案，所以搜索对象只包含至少两位的候选数。
题目要求找出十进制下全部 11 个这样的数，并求它们的和。实现直接利用题目给出的事实: 这样的数恰好只有 11 个，因此一旦找到第 11 个就可以停止。最终得到的总和是 \(748317\)。
这个问题没有需要推导的递推式。真正的数学核心是一个素数的十进制表示，以及下面这个不变量: 它的每一个真前缀和每一个真后缀都必须仍然是素数。
设
$$p = d_1 d_2 \cdots d_k$$
是一个 \(k\) 位素数的十进制表示。对每个截断位置 \(c=1,2,\dots,k-1\)，定义右截断和左截断为
$$R_c = \left\lfloor \frac{p}{10^c} \right\rfloor,$$
$$L_c = \text{由 } d_{c+1} d_{c+2} \cdots d_k \text{ 表示的整数}.$$
那么 \(p\) 是双向可截素数，当且仅当
$$p,\ R_1,\dots,R_{k-1},\ L_1,\dots,L_{k-1}$$
全部都是素数。换句话说，十进制字符串的每一个真前缀和每一个真后缀都必须保留素性。C++、Python 和 Java 实现检查的正是这一条件。
在真正搜索之前，一些数字已经被排除了。首位 \(d_1\) 必须属于 \(\{2,3,5,7\}\)，因为经过足够多次右截断后最终只剩下这一位。末位 \(d_k\) 必须是 \(3\) 或 \(7\): 经过全部左截断后它也会单独留下，而一个多位素数不可能以 \(2\) 或 \(5\) 结尾。
所有中间位都必须落在 \(\{1,3,7,9\}\) 中。原因是每一个中间位都会成为某个真前缀的最后一位，而这些前缀都必须是素数。如果中间位是偶数或 \(5\)，对应的前缀就会立刻变成合数。这说明可行候选非常稀少。
本题中的可截素数都至少有两位，因此一定是大于 \(10\) 的奇数。所以搜索可以从 \(11\) 开始，并且每次加 \(2\)，不会漏掉任何答案。对于每个奇数候选 \(n\)，算法先判断 \(n\) 自身是否为素数；只有这一关通过后，才会去检查所有截断位置。
停止条件直接来自题目本身: 这样的数恰好只有 11 个。因此程序不需要人为猜测上界，只要计数达到 11 就可以结束。
经典的正例是 \(3797\)。它的右截断链为
$$3797,\ 379,\ 37,\ 3,$$
左截断链为
$$3797,\ 797,\ 97,\ 7.$$
两条链中的每个数都是素数，所以 \(3797\) 满足要求。
反例可以看 \(47\)。\(47\) 本身是素数，左截断得到 \(7\) 也是素数，但右截断得到 \(4\)，而 \(4\) 不是素数。这说明“原数是素数”远远不够，两个方向上的每一次截断都必须保留素性。
实现采用直接的素性判断。小于 \(2\) 的整数立刻判为非素数。偶数只有在数值恰好等于 \(2\) 时才是素数。对于一个奇数候选 \(n\)，代码尝试奇数除数 \(3,5,7,\dots\)，直到条件 \(p \le n/p\) 不再成立；这与 \(p^2 \le n\) 完全等价。如果始终找不到因子，就说明 \(n\) 是素数。
如果 \(n<10\)，实现会直接拒绝它，因为单个数字的素数不算在题目答案里。否则先把 \(n\) 转成十进制字符串。随后对每一个截断位置，分别取截断后的后缀和截断前的前缀，再把它们转回整数，并分别做素性测试。只要某一次截断得到合数，这个候选数就立刻被淘汰。
这与数学定义一一对应: 每个切口都会产生一个真前缀和一个真后缀，两者都必须是素数。
搜索过程中维护两个累计量: 已经找到多少个双向可截素数，以及这些数的总和。程序从 \(11\) 开始，只考察奇数。某个候选通过完整测试后，计数器加一，并把该候选加入总和。计数达到 11 时，算法就返回结果。
实现里还加入了两个轻量级自检: \(3797\) 必须被接受，而 \(47\) 必须被拒绝。这样可以确认代码确实同时检查了左右两个方向的截断。
对单个整数 \(n\) 而言，试除法素性测试的时间复杂度是 \(O(\sqrt{n})\)，额外空间复杂度是 \(O(1)\)。如果 \(n\) 有 \(k\) 位，那么完整的可截性检查会先对 \(n\) 本身做一次素性测试，然后对每个截断位置再做两次，总共是 \(2k-1\) 次素性测试，因此单个候选的代价为 \(O(k\sqrt{n})\)，其中 \(k = O(\log n)\)。
设在找到第 11 个解之前检查到的最大奇数为 \(M\)。由于程序只枚举奇数，而且绝大多数候选会很快失败，整体运行时间仍然很小。一个干净的上界是 \(O(M^{3/2})\) 时间，辅助空间是 \(O(1)\)，另外只会产生长度为 \(O(\log M)\) 的临时十进制字符串。对本题的规模来说，这已经绰绰有余。
Двусторонне усекаемое простое число остается простым, если последовательно удалять цифры слева, и также остается простым, если последовательно удалять цифры справа. Однозначные простые числа \(2,3,5,7\) в ответ не входят, поэтому поиск ведется только среди многозначных кандидатов.
Нужно найти все 11 таких чисел в десятичной системе и вычислить их сумму. Реализации напрямую используют факт из условия, что решений ровно 11, поэтому поиск завершается сразу после нахождения одиннадцатого. Получающаяся сумма равна \(748317\).
Здесь нет рекуррентного соотношения и нет скрытой замкнутой формулы. Главный математический объект - десятичная запись простого числа и инвариант: каждый собственный префикс и каждый собственный суффикс этой записи тоже должен быть простым.
Пусть
$$p = d_1 d_2 \cdots d_k$$
есть десятичная запись \(k\)-значного простого числа. Для каждой позиции разреза \(c=1,2,\dots,k-1\) определим усечение справа и усечение слева так:
$$R_c = \left\lfloor \frac{p}{10^c} \right\rfloor,$$
$$L_c = \text{целое число, записанное цифрами } d_{c+1} d_{c+2} \cdots d_k.$$
Тогда число \(p\) является усекаемым тогда и только тогда, когда
$$p,\ R_1,\dots,R_{k-1},\ L_1,\dots,L_{k-1}$$
все просты. Иными словами, каждый собственный префикс и каждый собственный суффикс десятичной записи должен оставаться простым. Именно это условие и проверяют реализации на C++, Python и Java.
Некоторые цифры исключаются заранее. Первая цифра \(d_1\) должна принадлежать множеству \(\{2,3,5,7\}\), потому что после достаточного числа правых усечений останется только она. Последняя цифра \(d_k\) обязана быть \(3\) или \(7\): после всех левых усечений именно она останется одна, а многозначное простое число не может оканчиваться на \(2\) или \(5\).
Каждая внутренняя цифра должна лежать в \(\{1,3,7,9\}\). Дело в том, что любая внутренняя цифра становится последней цифрой некоторого собственного префикса, а такой префикс обязан быть простым. Если внутри стоит четная цифра или \(5\), один из этих префиксов немедленно окажется составным. Поэтому подходящих чисел очень мало.
Любое усекаемое простое число в этой задаче имеет хотя бы две цифры, а значит, оно нечетно и больше \(10\). Поэтому поиск можно начать с \(11\) и двигаться с шагом \(2\), не пропуская решений. Для каждого нечетного кандидата \(n\) алгоритм сначала проверяет, является ли простым само число \(n\). Только после этого рассматриваются все позиции усечения.
Критерий остановки тоже взят прямо из условия: таких чисел ровно 11. Следовательно, программе не нужна искусственная верхняя граница; поиск заканчивается в тот момент, когда счетчик достигает 11.
Классический положительный пример - число \(3797\). Его правые усечения равны
$$3797,\ 379,\ 37,\ 3,$$
а левые усечения равны
$$3797,\ 797,\ 97,\ 7.$$
Все числа в обеих цепочках просты, значит, \(3797\) действительно подходит.
Для контраста рассмотрим \(47\). Само \(47\) простое, и его левое усечение \(7\) тоже простое. Но правое усечение \(4\) уже не простое. Значит, простоты исходного числа недостаточно; нужно, чтобы оба направления усечения сохраняли простоту на каждом шаге.
Реализация использует прямую проверку простоты. Числа меньше \(2\) немедленно отвергаются. Четное число считается простым только в случае \(2\). Для нечетного кандидата \(n\) перебираются нечетные делители \(3,5,7,\dots\), пока выполняется условие \(p \le n/p\), эквивалентное неравенству \(p^2 \le n\). Если делитель не найден, число простое.
Если \(n<10\), кандидат сразу отвергается, потому что однозначные простые в условии исключены. Иначе число один раз преобразуется в десятичную строку. Для каждой позиции разреза берутся суффикс после разреза и префикс перед разрезом, оба снова переводятся в целые числа и отдельно проверяются на простоту. При первом составном усечении кандидат отбрасывается.
Это полностью повторяет математическое определение: каждый разрез порождает один собственный префикс и один собственный суффикс, и оба должны быть простыми.
Во время поиска поддерживаются две величины: сколько усекаемых простых уже найдено и какова их суммарная сумма. Начиная с \(11\), программа просматривает только нечетные числа. Когда кандидат проходит полную проверку, счетчик увеличивается, а число добавляется к сумме. Как только найдено 11 чисел, алгоритм возвращает итог.
В реализациях есть и две легкие проверочные точки: \(3797\) должно приниматься, а \(47\) должно отвергаться. Это гарантирует, что проверяются оба направления усечения.
Для одного числа \(n\) проверка простоты методом пробного деления занимает \(O(\sqrt{n})\) времени и \(O(1)\) дополнительной памяти. Если у \(n\) \(k\) цифр, полная проверка усекаемости выполняет одну проверку простоты для самого \(n\) и затем еще по две проверки для каждой позиции разреза, всего \(2k-1\) проверок. Поэтому стоимость одного кандидата равна \(O(k\sqrt{n})\), где \(k = O(\log n)\).
Пусть \(M\) - наибольшее нечетное число, просмотренное до появления одиннадцатого решения. Полный поиск остается вполне практичным, потому что рассматриваются только нечетные числа и большинство кандидатов отбрасывается очень рано. Удобная верхняя оценка - \(O(M^{3/2})\) времени и \(O(1)\) вспомогательной памяти, если не считать временных десятичных строк длины \(O(\log M)\). Для этой задачи такого метода более чем достаточно.
العدد الأولي القابل للاقتطاع من الجهتين هو عدد أولي يبقى أوليًا عند حذف الأرقام تباعًا من اليسار، ويبقى أوليًا أيضًا عند حذفها تباعًا من اليمين. الأعداد الأولية ذات الرقم الواحد \(2,3,5,7\) مستبعدة من العد، ولذلك يبدأ البحث من الأعداد متعددة الخانات فقط.
المطلوب هو إيجاد الأعداد الأحد عشر التي تحقق هذه الخاصية في النظام العشري ثم حساب مجموعها. تعتمد التطبيقات مباشرة على حقيقة مذكورة في نص المسألة، وهي أن هذه الأعداد عددها بالضبط 11، ولذلك يتوقف البحث فور العثور على العدد الحادي عشر. المجموع الناتج هو \(748317\).
لا توجد هنا علاقة عودية ولا صيغة مغلقة خفية. الفكرة الرياضية الأساسية هي التمثيل العشري للعدد الأولي، والثابت الذي يجب أن يبقى صحيحًا هو أن كل بادئة حقيقية وكل لاحقة حقيقية لهذا التمثيل يجب أن تكون عددًا أوليًا أيضًا.
لنكتب
$$p = d_1 d_2 \cdots d_k$$
حيث تمثل هذه الصيغة الكتابة العشرية لعدد أولي مكوّن من \(k\) خانات. ولكل موضع قطع \(c=1,2,\dots,k-1\) نعرّف الاقتطاع من اليمين والاقتطاع من اليسار كما يلي:
$$R_c = \left\lfloor \frac{p}{10^c} \right\rfloor,$$
$$L_c = \operatorname{val}(d_{c+1} d_{c+2} \cdots d_k).$$
وعندئذ يكون \(p\) قابلاً للاقتطاع إذا وفقط إذا كانت جميع الأعداد
$$p,\ R_1,\dots,R_{k-1},\ L_1,\dots,L_{k-1}$$
أولية. وبصياغة أخرى: كل بادئة حقيقية وكل لاحقة حقيقية للسلسلة العشرية يجب أن تبقى أولية. وهذا هو الشرط نفسه الذي تتحقق منه تطبيقات C++ وPython وJava.
بعض الخانات مستبعدة قبل بدء البحث أصلًا. الخانة الأولى \(d_1\) يجب أن تنتمي إلى \(\{2,3,5,7\}\)، لأنها تبقى وحدها بعد عدد كاف من الاقتطاعات من اليمين. أما الخانة الأخيرة \(d_k\) فيلزم أن تكون \(3\) أو \(7\)، لأنها تبقى وحدها بعد الاقتطاع الكامل من اليسار، ولأن العدد الأولي متعدد الخانات لا يمكن أن ينتهي بـ \(2\) أو \(5\).
كل خانة داخلية يجب أن تنتمي إلى \(\{1,3,7,9\}\). والسبب أن كل خانة داخلية تصبح في مرحلة ما الخانة الأخيرة لبادئة حقيقية، وهذه البادئة يجب أن تكون أولية. فإذا كانت الخانة الداخلية زوجية أو تساوي \(5\)، فإن إحدى تلك البوادئ ستكون مركبة حتمًا. لهذا السبب تكون الأمثلة الصحيحة نادرة جدًا.
كل عدد أولي قابل للاقتطاع في هذه المسألة له على الأقل خانتان، ولذلك فهو عدد فردي وأكبر من \(10\). لذا يمكن أن يبدأ البحث من \(11\) ويتقدم بمقدار \(2\) في كل مرة من دون أن يفوّت أي حل. ولكل مرشح فردي \(n\)، تفحص الخوارزمية أولًا ما إذا كان \(n\) نفسه أوليًا؛ وبعد النجاح في هذه الخطوة فقط تُفحص جميع مواضع القطع.
أما شرط التوقف فهو مأخوذ مباشرة من نص المسألة: يوجد بالضبط 11 عددًا من هذا النوع. لذلك لا تحتاج الخوارزمية إلى حد أعلى مفترض؛ بل تتوقف حين يصل العداد إلى 11.
المثال الإيجابي الأشهر هو \(3797\). اقتطاعاته من اليمين هي
$$3797,\ 379,\ 37,\ 3,$$
واقتطاعاته من اليسار هي
$$3797,\ 797,\ 97,\ 7.$$
جميع الأعداد في السلسلتين أولية، ولذلك فإن \(3797\) يحقق الخاصية.
أما \(47\) فهو مثال مضاد مفيد. العدد \(47\) أولي، واقتطاعه من اليسار يعطي \(7\) وهو أولي أيضًا، لكن اقتطاعه من اليمين يعطي \(4\)، و\(4\) ليس عددًا أوليًا. وهذا يبين أن أولية العدد الأصلي وحدها لا تكفي؛ بل يجب أن تنجح جميع الاقتطاعات في الاتجاهين.
يستخدم التنفيذ اختبارًا مباشرًا للأولية. أي عدد أصغر من \(2\) يُرفض فورًا. والعدد الزوجي لا يكون أوليًا إلا إذا كان مساويًا لـ \(2\). وبالنسبة إلى مرشح فردي \(n\)، تُجرَّب القواسم الفردية \(3,5,7,\dots\) ما دام الشرط \(p \le n/p\) محققًا، وهذا مكافئ تمامًا للشرط \(p^2 \le n\). وإذا لم يظهر أي قاسم، فالعدد أولي.
إذا كان \(n<10\)، يُرفض المرشح مباشرة لأن الأعداد الأولية ذات الخانة الواحدة غير محسوبة في هذه المسألة. وإلا فيحوَّل العدد مرة واحدة إلى سلسلة عشرية. ثم عند كل موضع قطع يؤخذ اللاحق بعد القطع والبادئة قبل القطع، ويعاد تفسير كل منهما كعدد صحيح، ثم يخضعان لاختبار الأولية. وعند أول اقتطاع غير أولي يُستبعد المرشح فورًا.
بهذا يطابق التنفيذ التعريف الرياضي خطوة بخطوة: كل قطع يولّد بادئة حقيقية ولاحقة حقيقية، ويجب أن تكونا أوليتين معًا.
تحافظ الخوارزمية أثناء البحث على قيمتين: عدد الأعداد الأولية القابلة للاقتطاع التي عُثر عليها حتى الآن، ومجموعها. بدءًا من \(11\)، لا يُفحص إلا الأعداد الفردية. وإذا نجح مرشح ما في الاختبار الكامل، يزاد العداد بمقدار واحد ويضاف هذا المرشح إلى المجموع. وحين يصل العداد إلى 11، تعاد النتيجة النهائية.
تتضمن التطبيقات أيضًا اختبارين صغيرين للتأكد من صحة المنطق: يجب قبول \(3797\)، ويجب رفض \(47\). وهذا يؤكد أن الاتجاهين، اليسار واليمين، يتم فحصهما فعلًا.
بالنسبة إلى عدد واحد \(n\)، فإن اختبار الأولية بالقسمة التجريبية يستهلك زمنًا مقداره \(O(\sqrt{n})\) ومساحة إضافية مقدارها \(O(1)\). وإذا كان \(n\) مكوّنًا من \(k\) خانات، فإن اختبار قابلية الاقتطاع الكامل يجري اختبار أولية واحدًا للعدد نفسه ثم اختبارين إضافيين لكل موضع قطع، أي ما مجموعه \(2k-1\) اختبارًا. ومن ثم تكون كلفة المرشح الواحد \(O(k\sqrt{n})\)، حيث \(k = O(\log n)\).
إذا رمزنا بـ \(M\) إلى أكبر عدد فردي تم فحصه قبل ظهور الحل الحادي عشر، فإن البحث الكامل يبقى عمليًا لأن البرنامج يمر فقط على الأعداد الفردية ولأن معظم المرشحين يسقطون بسرعة كبيرة. ويمكن إعطاء حد علوي نظيف مقداره \(O(M^{3/2})\) زمنًا و\(O(1)\) مساحة مساعدة، باستثناء سلاسل عشرية مؤقتة طولها \(O(\log M)\). وهذا أكثر من كافٍ لحجم هذه المسألة.