We seek the smallest prime \(p\) for which there exists a non-empty set of digit positions such that replacing all of those positions by the same digit \(r\in\{0,\dots,9\}\) produces eight primes. The chosen positions do not need to be adjacent, but every replacement uses one common digit across all chosen positions.
The standard example \(56**3\) shows the phenomenon: replacing the two middle zeros in \(56003\) by \(0,1,\dots,9\) produces seven primes. Problem 51 asks for the first family whose prime count reaches eight.
The C++, Python, and Java implementations treat the problem as a search over decimal patterns. For a fixed prime, the decisive mathematical objects are a target digit, a non-empty subset of the positions carrying that digit, and the replacement digit applied to all of those positions at once.
Write the prime \(p\) in decimal as \(a_0a_1\dots a_{k-1}\). For a digit \(\tau\in\{0,\dots,9\}\), let
$$P_\tau=\{i:a_i=\tau\}.$$
If \(M\subseteq P_\tau\) is non-empty and \(r\in\{0,\dots,9\}\), define the candidate \(N_r(p,\tau,M)\) by
$$b_i(r)=\begin{cases} r, & i\in M,\\ a_i, & i\notin M. \end{cases}$$
Then \(N_r(p,\tau,M)\) is the integer with digits \(b_0(r)b_1(r)\dots b_{k-1}(r)\). If \(0\in M\) and \(r=0\), the result has a leading zero and is discarded. The prime family attached to \((p,\tau,M)\) is therefore
$$F(p,\tau,M)=\{N_r(p,\tau,M):0\le r\le 9,\ N_r(p,\tau,M)\text{ is valid and prime}\}.$$
The problem becomes: find the smallest prime \(p\) for which \(|F(p,\tau,M)|\ge 8\) for some \(\tau\) and some non-empty \(M\).
If a prime \(p\) belongs to a valid family, then one of the ten replacements must reproduce \(p\) itself. In that replacement, every selected position receives the same digit. Therefore the selected positions in \(p\) must already contain one common digit. This proves that every family containing \(p\) can be recovered by choosing one digit value already present in \(p\) and then choosing a non-empty subset of the positions where that digit occurs.
That observation exactly matches the implementations: they first collect all positions of each decimal digit and then enumerate only non-empty subsets inside those groups. No valid family containing the current prime is missed by doing so.
For fixed \((p,\tau,M)\), there are only ten possible replacements, so the family size is just
$$|F(p,\tau,M)|=\sum_{r=0}^{9} I_r,$$
where \(I_r=1\) if \(N_r(p,\tau,M)\) is a valid prime and \(I_r=0\) otherwise.
The same replacement pattern can be rediscovered from several members of the same family. To avoid accepting a later member, define
$$m(p,\tau,M)=\min F(p,\tau,M).$$
The implementations accept the current prime only when both \(|F(p,\tau,M)|\) reaches the required family size and \(p=m(p,\tau,M)\). Because primes are scanned in increasing order, the first accepted prime is automatically the smallest prime that belongs to any qualifying family.
Take \(p=56003\). The digit \(0\) appears at positions \(2\) and \(3\), so choose \(\tau=0\) and \(M=\{2,3\}\). Then every candidate has the form
$$N_r=56rr3.$$
The ten replacements are 56003, 56113, 56223, 56333, 56443, 56553, 56663, 56773, 56883, and 56993. Among them, 56223, 56553, and 56883 are composite, while the other seven are prime. Hence
$$|F(56003,0,\{2,3\})|=7.$$
This is the family cited in the problem statement, and it illustrates the exact object that the implementations enumerate for every prime.
If the digit \(\tau\) appears \(m_\tau\) times in a \(k\)-digit prime, then there are \(2^{m_\tau}-1\) non-empty subsets of \(P_\tau\). So the total number of replacement masks checked for that prime is
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr),$$
where digits with \(m_\tau=0\) contribute nothing. Since the position sets \(P_0,\dots,P_9\) partition the \(k\) digit positions, we have
$$\sum_{\tau=0}^{9} m_\tau=k$$
and the counted subsets are only a portion of all non-empty subsets of the \(k\) positions, so
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\le 2^k-1.$$
Each such mask generates exactly ten candidate numbers. That is why exhaustive search is practical once primality tests are cheap.
The C++, Python, and Java implementations first build a sieve up to a configurable limit. Any candidate within that range is tested by direct table lookup. If a candidate lies above the sieve range, the implementations fall back to ordinary trial division up to \(\sqrt{n}\), so correctness does not depend on the sieve alone.
Primes are scanned in increasing order, starting from 11. For each prime, the implementation records every position occupied by each decimal digit. For each digit group it loops through all non-empty subsets, substitutes replacement digits \(0\) through \(9\), discards leading-zero cases, and counts how many resulting values are prime.
While processing one subset, the implementation also tracks the smallest prime produced anywhere in that family. A prime is returned only if the family size reaches the requested target and the current prime is itself the smallest prime in that family. This prevents the same family from being reported again from a larger member.
The built-in checkpoint uses the smaller target family size 6. In that easier setting, the first accepted prime is \(13\), obtained by replacing the leading digit in the sequence \(13,23,33,\dots,93\) while rejecting \(03\) because of the leading zero.
Let \(L\) be the sieve limit. Building the sieve costs \(O(L\log\log L)\) time and \(O(L)\) memory. After that, the search phase iterates over primes \(p\le L\).
If \(p\) has \(k\) digits and digit multiplicities \(m_0,\dots,m_9\), then the family-generation work for that one prime is
$$O\!\left(10\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\right),$$
because every admissible subset is tried against the ten replacement digits. Since this sum is at most \(2^k-1\), the per-prime search cost is bounded by \(O(10\cdot 2^k)\). Under the default search limit, \(k\le 7\), so the exponential factor stays tiny. Inside the sieve range, each primality test is \(O(1)\); outside it, the fallback test is \(O(\sqrt{n})\).
In practice the method is fast because the digit length remains small and the search space is tightly constrained by the repeated-digit structure.
Gesucht ist die kleinste Primzahl \(p\), für die es eine nichtleere Menge von Ziffernpositionen gibt, sodass das gleichzeitige Ersetzen all dieser Positionen durch dieselbe Ziffer \(r\in\{0,\dots,9\}\) genau genommen eine Familie mit acht Primzahlen erzeugt. Die gewählten Stellen müssen nicht benachbart sein, aber jede Ersetzung benutzt an allen gewählten Stellen dieselbe neue Ziffer.
Das bekannte Beispiel \(56**3\) zeigt das Prinzip: Ersetzt man in \(56003\) die beiden mittleren Nullen durch \(0,1,\dots,9\), erhält man sieben Primzahlen. Problem 51 fragt nach der ersten Familie, deren Primzahlanzahl auf acht steigt.
Die Implementierungen in C++, Python und Java behandeln die Aufgabe als Suche über Dezimalmuster. Für eine feste Primzahl sind die entscheidenden mathematischen Objekte eine Zielziffer, eine nichtleere Teilmenge der Positionen mit genau dieser Ziffer und die gemeinsame Ersatzziffer, die auf alle diese Positionen zugleich gesetzt wird.
Schreibe die Primzahl \(p\) in Dezimalschreibweise als \(a_0a_1\dots a_{k-1}\). Für eine Ziffer \(\tau\in\{0,\dots,9\}\) sei
$$P_\tau=\{i:a_i=\tau\}.$$
Ist \(M\subseteq P_\tau\) nichtleer und \(r\in\{0,\dots,9\}\), dann wird der Kandidat \(N_r(p,\tau,M)\) durch
$$b_i(r)=\begin{cases} r, & i\in M,\\ a_i, & i\notin M \end{cases}$$
definiert. \(N_r(p,\tau,M)\) ist also die Zahl mit den Ziffern \(b_0(r)b_1(r)\dots b_{k-1}(r)\). Falls \(0\in M\) und \(r=0\) gilt, entsteht eine führende Null; dieser Fall wird verworfen. Die zu \((p,\tau,M)\) gehörige Primfamilie ist daher
$$F(p,\tau,M)=\{N_r(p,\tau,M):0\le r\le 9,\ N_r(p,\tau,M)\text{ ist gültig und prim}\}.$$
Damit lautet die Aufgabe: Finde die kleinste Primzahl \(p\), für die \(|F(p,\tau,M)|\ge 8\) für irgendein \(\tau\) und irgendein nichtleeres \(M\) gilt.
Wenn eine Primzahl \(p\) zu einer gültigen Familie gehört, dann muss eine der zehn Ersetzungen \(p\) selbst wieder erzeugen. In genau dieser Ersetzung bekommen alle ausgewählten Positionen dieselbe Ziffer. Also müssen diese Positionen in \(p\) bereits dieselbe Ziffer tragen. Daraus folgt: Jede Familie, die \(p\) enthält, lässt sich wiederfinden, indem man eine in \(p\) vorkommende Ziffer auswählt und dann eine nichtleere Teilmenge ihrer Positionen nimmt.
Genau das tun die Implementierungen: Zuerst werden die Positionen jeder Dezimalziffer gesammelt, dann werden nur nichtleere Teilmengen innerhalb dieser Gruppen enumeriert. Dadurch geht keine gültige Familie verloren, die die aktuelle Primzahl enthält.
Für festes \((p,\tau,M)\) gibt es nur zehn mögliche Ersetzungen, also ist die Familiengröße einfach
$$|F(p,\tau,M)|=\sum_{r=0}^{9} I_r,$$
wobei \(I_r=1\) ist, wenn \(N_r(p,\tau,M)\) eine gültige Primzahl ist, und \(I_r=0\) sonst.
Dasselbe Muster kann von mehreren Mitgliedern derselben Familie aus erneut auftauchen. Um nicht versehentlich ein späteres Mitglied zu akzeptieren, definiert man
$$m(p,\tau,M)=\min F(p,\tau,M).$$
Die Implementierungen akzeptieren die aktuelle Primzahl nur dann, wenn sowohl \(|F(p,\tau,M)|\) die geforderte Größe erreicht als auch \(p=m(p,\tau,M)\) gilt. Da die Primzahlen in aufsteigender Reihenfolge durchsucht werden, ist die erste akzeptierte Primzahl automatisch die kleinste Primzahl irgendeiner qualifizierenden Familie.
Nimm \(p=56003\). Die Ziffer \(0\) steht an den Positionen \(2\) und \(3\), also wählen wir \(\tau=0\) und \(M=\{2,3\}\). Dann haben alle Kandidaten die Form
$$N_r=56rr3.$$
Die zehn Ersetzungen lauten 56003, 56113, 56223, 56333, 56443, 56553, 56663, 56773, 56883 und 56993. Davon sind 56223, 56553 und 56883 zusammengesetzt; die übrigen sieben Zahlen sind prim. Also gilt
$$|F(56003,0,\{2,3\})|=7.$$
Das ist genau die Familie aus der Aufgabenstellung und zugleich das exakte Suchobjekt, das die Implementierungen für jede Primzahl erzeugen.
Wenn die Ziffer \(\tau\) in einer \(k\)-stelligen Primzahl genau \(m_\tau\) Mal vorkommt, gibt es \(2^{m_\tau}-1\) nichtleere Teilmengen von \(P_\tau\). Die Gesamtzahl der getesteten Ersetzungsmasken für diese Primzahl ist also
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr),$$
wobei Ziffern mit \(m_\tau=0\) nichts beitragen. Da die Mengen \(P_0,\dots,P_9\) die \(k\) Stellen partitionieren, gilt
$$\sum_{\tau=0}^{9} m_\tau=k$$
und die gezählten Teilmengen sind nur ein Teil aller nichtleeren Teilmengen der \(k\) Stellen. Daher folgt
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\le 2^k-1.$$
Jede dieser Masken erzeugt genau zehn Kandidaten. Gerade deshalb ist eine vollständige Suche praktikabel, sobald Primzahltests billig genug sind.
Die Implementierungen in C++, Python und Java bauen zunächst ein Sieb bis zu einer konfigurierbaren Grenze auf. Jeder Kandidat innerhalb dieses Bereichs wird per Tabellenzugriff geprüft. Liegt ein Kandidat oberhalb der Siebgrenze, wird auf gewöhnliche Probedivision bis \(\sqrt{n}\) zurückgegriffen. Die Korrektheit hängt also nicht allein vom Sieb ab.
Die Primzahlen werden aufsteigend ab 11 durchlaufen. Für jede Primzahl speichert die Implementierung alle Positionen jeder Dezimalziffer. Für jede solche Zifferngruppe werden alle nichtleeren Teilmengen betrachtet, danach die Ersatzziffern \(0\) bis \(9\) eingesetzt, Fälle mit führender Null verworfen und die verbleibenden Primzahlen gezählt.
Während eine Teilmenge geprüft wird, merkt sich die Implementierung zugleich die kleinste Primzahl, die irgendwo in dieser Familie entsteht. Eine Primzahl wird nur dann zurückgegeben, wenn die Familiengröße den Zielwert erreicht und die aktuelle Primzahl selbst die kleinste Primzahl der Familie ist. So wird dieselbe Familie nicht noch einmal über ein größeres Mitglied gemeldet.
Der eingebaute Kontrolltest benutzt die kleinere Zielgröße 6. In diesem einfacheren Fall ist die erste akzeptierte Primzahl \(13\), erzeugt durch Ersetzen der führenden Ziffer in der Folge \(13,23,33,\dots,93\), wobei \(03\) wegen der führenden Null ausgeschlossen wird.
Sei \(L\) die Siebgrenze. Der Aufbau des Siebs benötigt \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher. Danach iteriert die Suchphase über die Primzahlen \(p\le L\).
Hat \(p\) genau \(k\) Stellen und Ziffernhäufigkeiten \(m_0,\dots,m_9\), dann beträgt der Aufwand der Familienerzeugung für diese eine Primzahl
$$O\!\left(10\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\right),$$
denn jede zulässige Teilmenge wird mit allen zehn Ersatzziffern ausprobiert. Da diese Summe höchstens \(2^k-1\) ist, ist der Aufwand pro Primzahl durch \(O(10\cdot 2^k)\) beschränkt. Unter der voreingestellten Suchgrenze gilt \(k\le 7\), also bleibt der exponentielle Faktor sehr klein. Innerhalb des Siebbereichs kostet ein Primzahltest \(O(1)\), außerhalb davon \(O(\sqrt{n})\).
Praktisch ist das Verfahren schnell, weil die Stellenzahl klein bleibt und der Suchraum durch die Struktur der wiederholten Ziffern stark eingeschränkt ist.
Aranan şey, bazı basamak konumları seçilip bu konumların hepsi aynı rakam \(r\in\{0,\dots,9\}\) ile değiştirildiğinde sekiz asal üreten en küçük asal sayı \(p\)'dir. Seçilen konumların bitişik olması gerekmez; önemli olan, seçilen bütün konumlara aynı yeni rakamın yazılmasıdır.
Bilinen \(56**3\) örneği bu yapıyı gösterir: \(56003\) sayısındaki iki orta sıfır, \(0,1,\dots,9\) ile değiştirilince yedi asal elde edilir. Problem 51, asal sayısı sekize ulaşan ilk aileyi sorar.
C++, Python ve Java uygulamaları problemi ondalık örüntüler üzerinde bir arama olarak kuruyor. Sabit bir asal için belirleyici matematiksel nesneler şunlardır: hedef rakam, bu rakamın bulunduğu konumların boş olmayan bir alt kümesi ve bu konumların tamamına aynı anda uygulanan tek bir yerine koyma rakamı.
Asal sayı \(p\)'yi ondalık yazımda \(a_0a_1\dots a_{k-1}\) olarak yazalım. \(\tau\in\{0,\dots,9\}\) için
$$P_\tau=\{i:a_i=\tau\}$$
olsun. \(M\subseteq P_\tau\) boş değilse ve \(r\in\{0,\dots,9\}\) ise, \(N_r(p,\tau,M)\) adayı
$$b_i(r)=\begin{cases} r, & i\in M,\\ a_i, & i\notin M \end{cases}$$
ile tanımlanır. Yani \(N_r(p,\tau,M)\), basamakları \(b_0(r)b_1(r)\dots b_{k-1}(r)\) olan sayıdır. Eğer \(0\in M\) ve \(r=0\) ise başta sıfır oluşur; bu aday geçersiz sayılır. Buna göre \((p,\tau,M)\) için asal aile
$$F(p,\tau,M)=\{N_r(p,\tau,M):0\le r\le 9,\ N_r(p,\tau,M)\text{ geçerli ve asal}\}$$
şeklindedir. Problem artık şuna dönüşür: \(|F(p,\tau,M)|\ge 8\) eşitsizliğini sağlayan bir \(\tau\) ve boş olmayan bir \(M\) için en küçük asal \(p\)'yi bul.
Bir asal \(p\) geçerli bir ailenin üyesiyse, on adet değiştirme seçeneğinden biri \(p\)'nin kendisini yeniden üretmek zorundadır. O durumda seçilen bütün konumlara aynı rakam yazılmış olur. Demek ki \(p\)'nin içinde o seçilmiş konumların hepsi zaten aynı rakamı taşımalıdır. Bu nedenle \(p\)'yi içeren her aile, \(p\)'de zaten bulunan bir rakamı seçip onun bulunduğu konumların boş olmayan bir alt kümesini almakla yeniden elde edilebilir.
Uygulamaların yaptığı tam olarak budur: önce her rakamın geçtiği konumlar toplanır, sonra yalnızca bu grupların içindeki boş olmayan alt kümeler denenir. Böylece mevcut asalı içeren hiçbir geçerli aile kaçırılmaz.
Sabit \((p,\tau,M)\) için yalnızca on farklı değiştirme vardır; dolayısıyla aile büyüklüğü
$$|F(p,\tau,M)|=\sum_{r=0}^{9} I_r$$
olur. Burada \(I_r=1\), eğer \(N_r(p,\tau,M)\) geçerli bir asal ise; aksi halde \(I_r=0\).
Aynı değiştirme deseni, aynı ailenin birden fazla üyesinden tekrar keşfedilebilir. Daha büyük bir aile üyesini yanlışlıkla kabul etmemek için
$$m(p,\tau,M)=\min F(p,\tau,M)$$
tanımını yaparız. Uygulamalar, ancak hem \(|F(p,\tau,M)|\) istenen eşik değere ulaşıyorsa hem de \(p=m(p,\tau,M)\) ise mevcut asalı kabul eder. Asallar artan sırada tarandığı için, ilk kabul edilen asal otomatik olarak böyle bir aileye ait en küçük asaldır.
\(p=56003\) alınsın. \(0\) rakamı 2 ve 3. konumlarda bulunduğu için \(\tau=0\) ve \(M=\{2,3\}\) seçilir. Bu durumda her aday
$$N_r=56rr3$$
biçimindedir. On aday 56003, 56113, 56223, 56333, 56443, 56553, 56663, 56773, 56883 ve 56993 olur. Bunlardan 56223, 56553 ve 56883 bileşiktir; kalan yedisi asaldır. Dolayısıyla
$$|F(56003,0,\{2,3\})|=7.$$
Bu, soru metnindeki ailedir ve uygulamaların her asal için tam olarak hangi nesneyi taradığını açık biçimde gösterir.
Eğer \(\tau\) rakamı \(k\) basamaklı bir asal içinde \(m_\tau\) kez geçiyorsa, \(P_\tau\)'nun boş olmayan alt kümelerinin sayısı \(2^{m_\tau}-1\) olur. O halde bu asal için denenmiş değiştirme maskesi sayısı
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)$$
kadardır; burada \(m_\tau=0\) olan rakamlar katkı yapmaz. \(P_0,\dots,P_9\) kümeleri bütün basamak konumlarını ayırdığı için
$$\sum_{\tau=0}^{9} m_\tau=k$$
ve sayılan alt kümeler, \(k\) konumun tüm boş olmayan alt kümelerinin yalnızca bir kısmıdır. Bu yüzden
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\le 2^k-1$$
olur. Her maske tam olarak on aday üretir. Asallık sorguları ucuz hale geldiğinde tam aramanın pratik olmasının nedeni budur.
C++, Python ve Java uygulamaları önce ayarlanabilir bir üst sınıra kadar elek kurar. Bu aralığın içindeki her aday doğrudan tablo bakışıyla sınanır. Elek sınırının üstündeki adaylar için ise \(\sqrt{n}\)'e kadar klasik deneme bölmesi kullanılır. Dolayısıyla doğruluk yalnızca eleğe bağlı değildir.
Asallar 11'den başlayarak artan sırada gezilir. Her asal için, her ondalık rakamın geçtiği bütün konumlar kaydedilir. Sonra her rakam grubu içindeki boş olmayan alt kümeler denenir, yerine koyma rakamları \(0\) ile \(9\) arasında değiştirilir, başta sıfır oluşturan adaylar elenir ve kalanların kaçı asal diye sayılır.
Bir alt küme test edilirken uygulama aynı zamanda o ailenin içinde üretilen en küçük asalı da izler. Bir asal ancak aile büyüklüğü hedefe ulaşıyorsa ve mevcut asal o ailenin en küçük asalıysa döndürülür. Böylece aynı aile daha büyük bir üyeden ikinci kez raporlanmaz.
Uygulamalardaki yerleşik kontrol noktası daha küçük hedef olan 6'yı kullanır. Bu daha kolay durumda ilk kabul edilen asal \(13\)'tür; bu da \(13,23,33,\dots,93\) dizisinde baştaki rakam değiştirilerek elde edilir ve \(03\) baştaki sıfır nedeniyle reddedilir.
\(L\) elek sınırı olsun. Eleği kurmanın maliyeti \(O(L\log\log L)\) zaman ve \(O(L)\) bellektir. Bundan sonra arama aşaması \(p\le L\) olan asallar üzerinde ilerler.
Eğer \(p\), \(k\) basamaklıysa ve rakam çoklukları \(m_0,\dots,m_9\) ise, yalnız bu asal için aile üretim maliyeti
$$O\!\left(10\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\right)$$
olur; çünkü her geçerli alt küme on farklı yerine koyma rakamıyla denenir. Bu toplam en fazla \(2^k-1\) olduğundan, asal başına maliyet \(O(10\cdot 2^k)\) ile sınırlıdır. Varsayılan arama aralığında \(k\le 7\) olduğu için bu üstel çarpan küçüktür. Elek içindeki asallık testleri \(O(1)\), dışarıdaki yedek testler ise \(O(\sqrt{n})\) maliyetlidir.
Pratikte yöntem hızlıdır; çünkü basamak sayısı küçük kalır ve arama uzayı tekrarlanan rakam yapısı sayesinde çok sıkı biçimde daralır.
Buscamos el primo más pequeño \(p\) para el cual existe un conjunto no vacío de posiciones decimales tal que, al reemplazar todas esas posiciones por el mismo dígito \(r\in\{0,\dots,9\}\), se obtienen ocho números primos. Las posiciones elegidas no tienen que ser contiguas, pero cada reemplazo usa un único dígito común en todas ellas.
El ejemplo clásico \(56**3\) muestra el fenómeno: al reemplazar en \(56003\) sus dos ceros centrales por \(0,1,\dots,9\), aparecen siete primos. El Problema 51 pide la primera familia cuyo conteo primo alcanza ocho.
Las implementaciones en C++, Python y Java tratan el problema como una búsqueda sobre patrones decimales. Para un primo fijo, los objetos matemáticos decisivos son un dígito objetivo, un subconjunto no vacío de las posiciones donde aparece ese dígito y el dígito de reemplazo que se escribe simultáneamente en todas esas posiciones.
Escribamos el primo \(p\) en decimal como \(a_0a_1\dots a_{k-1}\). Para un dígito \(\tau\in\{0,\dots,9\}\), definimos
$$P_\tau=\{i:a_i=\tau\}.$$
Si \(M\subseteq P_\tau\) es no vacío y \(r\in\{0,\dots,9\}\), el candidato \(N_r(p,\tau,M)\) queda dado por
$$b_i(r)=\begin{cases} r, & i\in M,\\ a_i, & i\notin M \end{cases}$$
y \(N_r(p,\tau,M)\) es el entero con dígitos \(b_0(r)b_1(r)\dots b_{k-1}(r)\). Si \(0\in M\) y \(r=0\), aparece un cero inicial y el candidato se descarta. La familia prima asociada a \((p,\tau,M)\) es entonces
$$F(p,\tau,M)=\{N_r(p,\tau,M):0\le r\le 9,\ N_r(p,\tau,M)\text{ es válido y primo}\}.$$
Así, la tarea consiste en encontrar el primo más pequeño \(p\) para el cual \(|F(p,\tau,M)|\ge 8\) para alguna elección de \(\tau\) y de un \(M\) no vacío.
Si un primo \(p\) pertenece a una familia válida, una de las diez sustituciones debe reconstruir exactamente a \(p\). En esa sustitución, todas las posiciones elegidas reciben el mismo dígito. Por lo tanto, esas posiciones en \(p\) ya tienen que contener un mismo dígito. Eso demuestra que toda familia que contiene a \(p\) puede recuperarse eligiendo un dígito ya presente en \(p\) y luego un subconjunto no vacío de las posiciones donde aparece.
Eso es exactamente lo que hacen las implementaciones: primero agrupan las posiciones por dígito decimal y luego enumeran solo subconjuntos no vacíos dentro de cada grupo. Con esa restricción no se pierde ninguna familia válida que contenga al primo actual.
Para un \((p,\tau,M)\) fijo solo existen diez reemplazos posibles, así que el tamaño de la familia es
$$|F(p,\tau,M)|=\sum_{r=0}^{9} I_r,$$
donde \(I_r=1\) si \(N_r(p,\tau,M)\) es un primo válido y \(I_r=0\) en caso contrario.
El mismo patrón puede reaparecer desde varios miembros de una misma familia. Para evitar aceptar un miembro posterior, definimos
$$m(p,\tau,M)=\min F(p,\tau,M).$$
Las implementaciones aceptan el primo actual solo cuando \(|F(p,\tau,M)|\) alcanza el tamaño requerido y además \(p=m(p,\tau,M)\). Como los primos se recorren en orden creciente, el primer primo aceptado es automáticamente el menor primo que pertenece a cualquier familia válida.
Tomemos \(p=56003\). El dígito \(0\) aparece en las posiciones \(2\) y \(3\), así que elegimos \(\tau=0\) y \(M=\{2,3\}\). Entonces cada candidato tiene la forma
$$N_r=56rr3.$$
Los diez reemplazos son 56003, 56113, 56223, 56333, 56443, 56553, 56663, 56773, 56883 y 56993. Entre ellos, 56223, 56553 y 56883 son compuestos, mientras que los otros siete son primos. Por tanto,
$$|F(56003,0,\{2,3\})|=7.$$
Ésta es precisamente la familia mencionada en el enunciado y muestra con claridad el objeto matemático que enumeran las implementaciones.
Si el dígito \(\tau\) aparece \(m_\tau\) veces en un primo de \(k\) cifras, entonces existen \(2^{m_\tau}-1\) subconjuntos no vacíos de \(P_\tau\). Por consiguiente, el número total de máscaras de reemplazo probadas para ese primo es
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr),$$
donde los dígitos con \(m_\tau=0\) no aportan nada. Como \(P_0,\dots,P_9\) forman una partición de las \(k\) posiciones decimales, tenemos
$$\sum_{\tau=0}^{9} m_\tau=k$$
y los subconjuntos contados son solo una parte de todos los subconjuntos no vacíos de esas \(k\) posiciones. De ahí se obtiene
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\le 2^k-1.$$
Cada una de esas máscaras genera exactamente diez candidatos. Por eso una búsqueda exhaustiva resulta viable una vez que las consultas de primalidad son baratas.
Las implementaciones en C++, Python y Java construyen primero un cribado hasta un límite configurable. Cualquier candidato dentro de ese rango se comprueba con una simple consulta a la tabla. Si un candidato queda por encima del rango del cribado, las implementaciones recurren a división de prueba hasta \(\sqrt{n}\), de modo que la corrección no depende solo del cribado.
Los primos se recorren en orden creciente a partir de 11. Para cada primo, la implementación registra todas las posiciones ocupadas por cada dígito decimal. Luego, para cada grupo de un mismo dígito, prueba todos los subconjuntos no vacíos, sustituye los dígitos de reemplazo \(0\) a \(9\), descarta los casos con cero inicial y cuenta cuántos valores resultantes son primos.
Mientras examina un subconjunto, la implementación también mantiene el primo más pequeño producido en esa familia. Solo devuelve el primo actual si el tamaño de la familia alcanza el objetivo pedido y si el propio primo actual es el menor primo de esa familia. Así se evita informar dos veces la misma familia desde un miembro más grande.
La comprobación interna usa el objetivo más pequeño de tamaño 6. En ese caso más simple, el primer primo aceptado es \(13\), obtenido al reemplazar la cifra inicial en la secuencia \(13,23,33,\dots,93\), descartando \(03\) por el cero inicial.
Sea \(L\) el límite del cribado. Construir el cribado cuesta \(O(L\log\log L)\) tiempo y \(O(L)\) memoria. Después, la fase de búsqueda itera sobre primos \(p\le L\).
Si \(p\) tiene \(k\) cifras y multiplicidades de dígitos \(m_0,\dots,m_9\), entonces el trabajo de generación de familias para ese primo es
$$O\!\left(10\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\right),$$
porque cada subconjunto admisible se prueba con los diez dígitos de reemplazo. Como esa suma está acotada por \(2^k-1\), el costo por primo queda acotado por \(O(10\cdot 2^k)\). Bajo el límite de búsqueda por defecto, \(k\le 7\), así que el factor exponencial sigue siendo pequeño. Dentro del rango del cribado, cada prueba de primalidad es \(O(1)\); fuera de él, la prueba auxiliar cuesta \(O(\sqrt{n})\).
En la práctica, el método es rápido porque la longitud decimal se mantiene reducida y el espacio de búsqueda queda muy restringido por la estructura de dígitos repetidos.
我们要找的是最小的素数 \(p\)：存在一个非空的数位位置集合，把这些位置同时替换成同一个数字 \(r\in\{0,\dots,9\}\) 之后，得到的有效结果中恰好能出现至少八个素数。被替换的位置不要求相邻，但一次替换必须在所有选中位置上使用同一个数字。
题目里著名的 \(56**3\) 例子说明了这种结构：把 \(56003\) 中间两个零同时替换成 \(0,1,\dots,9\)，会得到七个素数。第 51 题要求的是第一个把这个素数族规模提升到八的情形。
C++、Python 和 Java 三个实现都没有把问题写成复杂的数论变换，而是把它看成一种十进制模式搜索。对一个固定素数来说，真正重要的数学对象只有三个：一个目标数字、这个数字出现位置中的一个非空子集，以及写入这些位置的公共替换数字。
把素数 \(p\) 的十进制表示写成 \(a_0a_1\dots a_{k-1}\)。对任意数字 \(\tau\in\{0,\dots,9\}\)，定义
$$P_\tau=\{i:a_i=\tau\}.$$
如果 \(M\subseteq P_\tau\) 非空，并且 \(r\in\{0,\dots,9\}\)，那么候选数 \(N_r(p,\tau,M)\) 由下式给出：
$$b_i(r)=\begin{cases} r, & i\in M,\\ a_i, & i\notin M \end{cases}$$
也就是说，\(N_r(p,\tau,M)\) 的数位就是 \(b_0(r)b_1(r)\dots b_{k-1}(r)\)。如果最高位被选中，也就是 \(0\in M\)，并且又取 \(r=0\)，那么结果会出现前导零，这种候选必须丢弃。因此，与 \((p,\tau,M)\) 对应的素数族就是
$$F(p,\tau,M)=\{N_r(p,\tau,M):0\le r\le 9,\ N_r(p,\tau,M)\text{ 合法且为素数}\}.$$
于是原题被改写成：寻找最小的素数 \(p\)，使得对某个 \(\tau\) 和某个非空 \(M\) 有 \(|F(p,\tau,M)|\ge 8\)。
这是实现中最关键的正确性理由之一。如果某个素数 \(p\) 属于一个有效替换族，那么十种替换里必然有一种会把这个族还原回 \(p\) 本身。可是在那一次替换中，所有被选中的位置都被写成同一个数字。于是，\(p\) 在这些位置上原本也必须全都是同一个数字。
这说明：任何包含 \(p\) 的有效家族，都可以通过“先选 \(p\) 中已经出现的某个数字，再从它的出现位置里选一个非空子集”来重建。也正因为如此，三个实现都会先按数字分组，再只在同一数字的那些位置内部枚举非空子集。这样做不会漏掉任何包含当前素数的合法家族。
对固定的 \((p,\tau,M)\)，只存在十个候选替换，所以家族大小直接写成
$$|F(p,\tau,M)|=\sum_{r=0}^{9} I_r,$$
其中 \(I_r=1\) 表示 \(N_r(p,\tau,M)\) 是一个合法素数，\(I_r=0\) 表示不是。
同一个替换模式可能会从这个家族中的多个素数重新被发现。为了避免把较大的成员误当成答案，代码实际上追踪的是
$$m(p,\tau,M)=\min F(p,\tau,M).$$
只有当家族大小达到目标，而且当前素数本身就是这个家族里的最小素数，即 \(p=m(p,\tau,M)\) 时，程序才接受它。由于素数是按从小到大的顺序扫描的，所以第一个被接受的素数，自动就是题目要求的最小答案。
取 \(p=56003\)。数字 \(0\) 出现在位置 \(2\) 和 \(3\)，于是选择 \(\tau=0\) 与 \(M=\{2,3\}\)。这时所有候选都具有同样的模板
$$N_r=56rr3.$$
十个替换结果分别是 56003、56113、56223、56333、56443、56553、56663、56773、56883、56993。其中 56223、56553、56883 是合数，其余七个都是素数，因此
$$|F(56003,0,\{2,3\})|=7.$$
这正是题目描述中的例子，也清楚地展示了实现真正枚举的对象是什么：不是任意改数，而是“固定未改位置，只让同一批位置共同取遍 0 到 9”。
如果数字 \(\tau\) 在一个 \(k\) 位素数中出现了 \(m_\tau\) 次，那么 \(P_\tau\) 的非空子集个数就是 \(2^{m_\tau}-1\)。因此，对这个素数需要检查的替换掩码总数为
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr),$$
其中没有出现的数字满足 \(m_\tau=0\)，自然不贡献任何项。由于 \(P_0,\dots,P_9\) 正好把全部 \(k\) 个数位位置划分开，所以
$$\sum_{\tau=0}^{9} m_\tau=k.$$
而这些被统计的子集，只是所有 \(k\) 个位置的非空子集中的一部分，因此还可以得到上界
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\le 2^k-1.$$
每一个这样的掩码只需要再试十个替换数字，所以只要素性判断足够快，彻底枚举就是现实可行的。
C++、Python 和 Java 三个实现都会先构造一个到可配置上界为止的筛表。落在这个范围内的候选数，素性判断就是一次表查询。如果候选数超出了筛表范围，程序就退回到经典的试除法，一直检查到 \(\sqrt{n}\)。因此，算法的正确性不依赖于“答案一定在筛表里”，筛表只是为了加速。
程序从 11 开始按升序扫描素数。对每个素数，它会记录十个数字各自出现在哪些位置上。然后对每一个数字组，枚举其中所有非空子集，把替换数字 \(0\) 到 \(9\) 逐一写入这些位置，过滤掉产生前导零的情况，再统计留下来的候选中有多少是素数。
在处理某个位置子集时，实现同时维护这个家族里出现过的最小素数。只有当家族规模达到了目标值，而且当前正在扫描的素数恰好就是这个家族的最小素数时，程序才返回它。这样就不会先遇到一个较大的家族成员并提前结束。
代码自带的检查点使用的是更小的目标家族大小 6。在这个较容易的版本里，最先被接受的素数是 \(13\)：它来自于序列 \(13,23,33,\dots,93\) 中首位数字的统一替换，而 \(03\) 因为有前导零被排除。
记筛表上界为 \(L\)。构造筛表需要 \(O(L\log\log L)\) 时间和 \(O(L)\) 空间。完成这一步之后，搜索阶段在所有 \(p\le L\) 的素数上进行。
如果某个素数 \(p\) 有 \(k\) 位，各个数字的出现次数是 \(m_0,\dots,m_9\)，那么仅这个素数对应的家族生成工作量为
$$O\!\left(10\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\right),$$
因为每一个合法子集都要对十个替换数字各试一次。该和式最多为 \(2^k-1\)，所以单个素数的搜索代价可以界为 \(O(10\cdot 2^k)\)。在默认的搜索范围下，\(k\le 7\)，因此这个指数因子非常小。筛表内的素性判断是 \(O(1)\)，超出筛表时则退化为 \(O(\sqrt{n})\) 的试除。
实际运行很快，原因就在于十进制位数很小，而且搜索空间并不是“所有改法”，而是被重复数字结构严格限制住的一小批模式。
Нужно найти наименьшее простое число \(p\), для которого существует непустой набор позиций цифр, такой что одновременная замена всех этих позиций одной и той же цифрой \(r\in\{0,\dots,9\}\) дает семейство из как минимум восьми простых чисел. Выбранные позиции не обязаны быть соседними, но в каждом варианте замены во все выбранные места записывается одна общая цифра.
Классический пример \(56**3\) показывает сам механизм: если в \(56003\) заменить два средних нуля на \(0,1,\dots,9\), получится семь простых чисел. В задаче 51 требуется первая семья, в которой число простых достигает восьми.
Реализации на C++, Python и Java рассматривают задачу как перебор десятичных шаблонов. Для фиксированного простого числа главными математическими объектами становятся целевая цифра, непустое подмножество ее позиций и цифра замены, которая записывается во все эти позиции одновременно.
Запишем простое число \(p\) в десятичном виде как \(a_0a_1\dots a_{k-1}\). Для цифры \(\tau\in\{0,\dots,9\}\) положим
$$P_\tau=\{i:a_i=\tau\}.$$
Если \(M\subseteq P_\tau\) непусто и \(r\in\{0,\dots,9\}\), то кандидат \(N_r(p,\tau,M)\) задается формулой
$$b_i(r)=\begin{cases} r, & i\in M,\\ a_i, & i\notin M \end{cases}$$
и представляет собой число с цифрами \(b_0(r)b_1(r)\dots b_{k-1}(r)\). Если \(0\in M\) и \(r=0\), возникает ведущий ноль, и такой кандидат отбрасывается. Поэтому семейство простых, связанное с \((p,\tau,M)\), равно
$$F(p,\tau,M)=\{N_r(p,\tau,M):0\le r\le 9,\ N_r(p,\tau,M)\text{ корректно и простое}\}.$$
Тем самым задача сводится к поиску наименьшего простого \(p\), для которого найдутся \(\tau\) и непустое \(M\) с условием \(|F(p,\tau,M)|\ge 8\).
Если простое число \(p\) принадлежит допустимому семейству, то одна из десяти замен обязана восстановить само число \(p\). В этой замене все выбранные позиции получают одну и ту же цифру. Следовательно, в самом числе \(p\) на всех выбранных позициях уже должна стоять одна и та же цифра. Отсюда следует важный вывод: любое семейство, содержащее \(p\), можно восстановить, выбрав одну цифру, уже присутствующую в \(p\), и затем непустое подмножество позиций, где она стоит.
Именно это и делают реализации: сначала собирают позиции каждой цифры, а затем перебирают только непустые подмножества внутри таких групп. Никакое корректное семейство, содержащее текущий простой, при этом не теряется.
Для фиксированного \((p,\tau,M)\) существует лишь десять вариантов замены, поэтому размер семейства равен
$$|F(p,\tau,M)|=\sum_{r=0}^{9} I_r,$$
где \(I_r=1\), если \(N_r(p,\tau,M)\) является корректным простым числом, и \(I_r=0\) в противном случае.
Один и тот же шаблон может повторно встретиться при рассмотрении разных членов одного семейства. Чтобы не принять более поздний элемент, вводится величина
$$m(p,\tau,M)=\min F(p,\tau,M).$$
Реализации принимают текущий простой только тогда, когда размер семейства достигает нужного порога и одновременно \(p=m(p,\tau,M)\). Поскольку перебор идет по простым в возрастающем порядке, первый принятый простой автоматически является наименьшим простым, принадлежащим какому-либо подходящему семейству.
Возьмем \(p=56003\). Цифра \(0\) стоит на позициях \(2\) и \(3\), значит, выбираем \(\tau=0\) и \(M=\{2,3\}\). Тогда каждый кандидат имеет вид
$$N_r=56rr3.$$
Десять замен дают числа 56003, 56113, 56223, 56333, 56443, 56553, 56663, 56773, 56883 и 56993. Среди них 56223, 56553 и 56883 составные, а остальные семь простые. Следовательно,
$$|F(56003,0,\{2,3\})|=7.$$
Это именно тот пример, который приведен в условии, и он точно показывает тот математический объект, который перебирают реализации.
Если цифра \(\tau\) встречается в \(k\)-значном простом числе \(m_\tau\) раз, то число непустых подмножеств множества \(P_\tau\) равно \(2^{m_\tau}-1\). Значит, полное число масок замены, проверяемых для данного простого, равно
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr),$$
причем цифры с \(m_\tau=0\) ничего не добавляют. Так как множества \(P_0,\dots,P_9\) разбивают все \(k\) позиций числа, выполняется
$$\sum_{\tau=0}^{9} m_\tau=k.$$
А поскольку подсчитанные подмножества составляют лишь часть всех непустых подмножеств \(k\) позиций, получаем верхнюю оценку
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\le 2^k-1.$$
Каждая такая маска порождает ровно десять кандидатов. Поэтому полный перебор оказывается вполне практичным, как только проверка простоты выполняется быстро.
Реализации на C++, Python и Java сначала строят решето до настраиваемого предела. Любой кандидат внутри этого диапазона проверяется простым обращением к таблице. Если кандидат выходит за пределы решета, программа переходит к обычному пробному делению до \(\sqrt{n}\). Поэтому корректность алгоритма не зависит только от решета.
Простые числа просматриваются в возрастающем порядке, начиная с 11. Для каждого простого реализация записывает все позиции, на которых встречается каждая десятичная цифра. Затем для каждой такой группы перебираются все непустые подмножества, подставляются цифры замены от \(0\) до \(9\), отбрасываются случаи с ведущим нулем и считается, сколько получившихся чисел являются простыми.
Во время проверки конкретного подмножества реализация также отслеживает наименьший простой, появившийся внутри этого семейства. Текущее простое возвращается только тогда, когда размер семейства достигает целевого значения и само текущее простое является минимальным простым этого семейства. Это не дает одной и той же семье быть сообщенной повторно через более крупный элемент.
Встроенная контрольная проверка использует меньшую целевую величину 6. В этом более простом варианте первым принятым простым оказывается \(13\): оно получается заменой ведущей цифры в последовательности \(13,23,33,\dots,93\), а число \(03\) исключается из-за ведущего нуля.
Пусть \(L\) обозначает предел решета. Построение решета требует \(O(L\log\log L)\) времени и \(O(L)\) памяти. После этого поисковая фаза перебирает простые \(p\le L\).
Если у простого \(p\) ровно \(k\) цифр, а количества вхождений цифр равны \(m_0,\dots,m_9\), то работа по генерации семейств для этого простого имеет порядок
$$O\!\left(10\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\right),$$
потому что каждое допустимое подмножество проверяется на всех десяти цифрах замены. Так как эта сумма не превосходит \(2^k-1\), стоимость на один простой ограничена величиной \(O(10\cdot 2^k)\). При стандартном пределе поиска \(k\le 7\), поэтому экспоненциальный множитель остается маленьким. Внутри диапазона решета каждая проверка простоты стоит \(O(1)\), а вне его запасной тест стоит \(O(\sqrt{n})\).
На практике алгоритм работает быстро именно потому, что число разрядов мало, а пространство поиска сильно сжато структурой повторяющихся цифр.
نبحث عن أصغر عدد أولي \(p\) توجد له مجموعة غير فارغة من مواضع الأرقام بحيث إن استبدال جميع هذه المواضع بالرقم نفسه \(r\in\{0,\dots,9\}\) ينتج عائلة تحتوي على ثمانية أعداد أولية على الأقل. المواضع المختارة لا يلزم أن تكون متجاورة، لكن كل محاولة استبدال تستخدم رقمًا واحدًا مشتركًا في جميع تلك المواضع.
المثال الشهير \(56**3\) يوضح الفكرة: إذا استبدلنا الصفرين الأوسطين في \(56003\) بالأرقام \(0,1,\dots,9\) نحصل على سبعة أعداد أولية. المطلوب في المسألة 51 هو أول عائلة يرتفع فيها عدد الأعداد الأولية إلى ثمانية.
تعامل تطبيقات C++ وPython وJava المسألة على أنها بحث في أنماط عشرية. وبالنسبة إلى عدد أولي ثابت، فالعناصر الرياضية الحاسمة هي: رقم مستهدف، ومجموعة جزئية غير فارغة من المواضع التي يظهر فيها هذا الرقم، ثم رقم بديل واحد يُكتب في جميع تلك المواضع معًا.
لنكتب العدد الأولي \(p\) بصيغته العشرية على الشكل \(a_0a_1\dots a_{k-1}\). ولكل رقم \(\tau\in\{0,\dots,9\}\) نعرّف
$$P_\tau=\{i:a_i=\tau\}.$$
إذا كانت \(M\subseteq P_\tau\) غير فارغة وكان \(r\in\{0,\dots,9\}\)، فإن المرشح \(N_r(p,\tau,M)\) يُعطى بالعلاقة
$$b_i(r)=\begin{cases} r, & i\in M,\\ a_i, & i\notin M \end{cases}$$
أي إن \(N_r(p,\tau,M)\) هو العدد الذي أرقامه \(b_0(r)b_1(r)\dots b_{k-1}(r)\). وإذا كان \(0\in M\) وأخذنا \(r=0\)، يظهر صفر بادئ فيصبح المرشح غير صالح ويُستبعد. لذلك تكون عائلة الأعداد الأولية المرتبطة بالثلاثي \((p,\tau,M)\) هي
$$F(p,\tau,M)=\{N_r(p,\tau,M):0\le r\le 9,\ N_r(p,\tau,M)\text{ is valid and prime}\}.$$
وبذلك تصبح المهمة هي إيجاد أصغر عدد أولي \(p\) بحيث يوجد \(\tau\) ومجموعة غير فارغة \(M\) يحققان \(|F(p,\tau,M)|\ge 8\).
إذا كان العدد الأولي \(p\) عضوًا في عائلة صحيحة، فلا بد أن تكون إحدى عمليات الاستبدال العشر قد أعادت إنتاج \(p\) نفسه. وفي تلك العملية تُكتب القيمة نفسها في جميع المواضع المختارة. إذن لا بد أن تكون هذه المواضع في \(p\) أصلًا حاملة للرقم نفسه. ومن هنا نحصل على المبرر الأساسي: كل عائلة تحتوي على \(p\) يمكن استعادتها باختيار رقم موجود بالفعل في \(p\)، ثم اختيار مجموعة جزئية غير فارغة من المواضع التي يظهر فيها ذلك الرقم.
وهذا يطابق ما تفعله التطبيقات حرفيًا: فهي تجمع مواضع كل رقم على حدة، ثم تعدد فقط المجموعات الجزئية غير الفارغة داخل كل مجموعة متجانسة. وبهذا لا تضيع أي عائلة صحيحة تحتوي على العدد الأولي الجاري فحصه.
بالنسبة إلى ثلاثي ثابت \((p,\tau,M)\)، يوجد فقط عشرة استبدالات ممكنة، ومن ثم فإن حجم العائلة يساوي
$$|F(p,\tau,M)|=\sum_{r=0}^{9} I_r,$$
حيث \(I_r=1\) إذا كان \(N_r(p,\tau,M)\) عددًا أوليًا صالحًا، و\(I_r=0\) في غير ذلك.
قد يُعاد اكتشاف النمط نفسه انطلاقًا من عدة أعضاء في العائلة الواحدة. ولمنع قبول عضو متأخر، نعرّف
$$m(p,\tau,M)=\min F(p,\tau,M).$$
لا تقبل التطبيقات العدد الأولي الحالي إلا إذا بلغ حجم العائلة الحد المطلوب، وكان \(p=m(p,\tau,M)\) في الوقت نفسه. وبما أن الأعداد الأولية تُفحص تصاعديًا، فإن أول عدد يُقبل يكون تلقائيًا أصغر عدد أولي ينتمي إلى أي عائلة مؤهلة.
لنأخذ \(p=56003\). الرقم \(0\) يظهر في الموضعين \(2\) و\(3\)، لذا نختار \(\tau=0\) و\(M=\{2,3\}\). عندئذ يأخذ كل مرشح الصورة
$$N_r=56rr3.$$
والاستبدالات العشرة هي: 56003 و56113 و56223 و56333 و56443 و56553 و56663 و56773 و56883 و56993. من بين هذه القيم تكون 56223 و56553 و56883 أعدادًا مركبة، بينما القيم السبع الأخرى أولية. لذلك
$$|F(56003,0,\{2,3\})|=7.$$
وهذه هي العائلة المذكورة في نص المسألة، وهي توضح بدقة الكائن الرياضي الذي تعدده التطبيقات لكل عدد أولي.
إذا كان الرقم \(\tau\) يظهر \(m_\tau\) مرة في عدد أولي مكوَّن من \(k\) خانات، فإن عدد المجموعات الجزئية غير الفارغة من \(P_\tau\) هو \(2^{m_\tau}-1\). ولذلك يكون عدد أقنعة الاستبدال التي تُفحص لهذا العدد الأولي
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr),$$
ولا تضيف الأرقام ذات \(m_\tau=0\) شيئًا. وبما أن المجموعات \(P_0,\dots,P_9\) تقسم الخانات \(k\) كلها، فلدينا
$$\sum_{\tau=0}^{9} m_\tau=k.$$
كما أن هذه المجموعات الجزئية المعدودة ليست إلا جزءًا من جميع المجموعات الجزئية غير الفارغة لخانات العدد، ومن ثم نحصل على الحد
$$\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\le 2^k-1.$$
وكل قناع من هذه الأقنعة يولد عشرة مرشحين فقط. ولهذا يصبح الفحص الشامل عمليًا ما دامت اختبارات الأولية سريعة.
تبني تطبيقات C++ وPython وJava أولًا غربالًا حتى حد قابل للضبط. وأي مرشح يقع داخل هذا المجال يُفحص عبر قراءة مباشرة من الجدول. وإذا تجاوز المرشح مجال الغربال، تعود التطبيقات إلى القسمة التجريبية المعتادة حتى \(\sqrt{n}\). ولهذا فإن صحة الحل لا تعتمد على الغربال وحده.
تُفحص الأعداد الأولية بترتيب تصاعدي بدءًا من 11. ولكل عدد أولي تسجل التطبيقات جميع المواضع التي يظهر فيها كل رقم عشري. ثم، داخل كل مجموعة لرقم واحد، تُجرَّب جميع المجموعات الجزئية غير الفارغة، وتُستبدل الأرقام من \(0\) إلى \(9\)، وتُرفض الحالات التي تنتج صفرًا بادئًا، ثم يُحصى عدد القيم الأولية الناتجة.
أثناء فحص مجموعة جزئية معينة، يتابع التنفيذ أيضًا أصغر عدد أولي نتج داخل تلك العائلة. ولا يُعاد العدد الأولي الحالي إلا إذا وصل حجم العائلة إلى الهدف المطلوب، وكان هذا العدد هو أصغر عدد أولي في تلك العائلة. وبهذا لا تُبلَّغ العائلة نفسها مرة ثانية انطلاقًا من عضو أكبر.
تستخدم نقطة التحقق المضمَّنة هدفًا أصغر هو 6. وفي هذا الإصدار الأسهل يكون أول عدد أولي مقبول هو \(13\)، وذلك عبر استبدال الخانة الأولى في المتتالية \(13,23,33,\dots,93\)، مع استبعاد \(03\) لأنه يحوي صفرًا بادئًا.
لنرمز إلى حد الغربال بـ \(L\). بناء الغربال يكلف \(O(L\log\log L)\) زمنًا و\(O(L)\) ذاكرة. بعد ذلك تمر مرحلة البحث على جميع الأعداد الأولية \(p\le L\).
إذا كان للعدد الأولي \(p\) عدد خانات يساوي \(k\)، وكانت تكرارات الأرقام هي \(m_0,\dots,m_9\)، فإن تكلفة توليد العائلات لهذا العدد وحده تساوي
$$O\!\left(10\sum_{\tau=0}^{9}\bigl(2^{m_\tau}-1\bigr)\right),$$
لأن كل مجموعة جزئية مسموحة تُفحص مع الأرقام العشرة البديلة. وبما أن هذا المجموع لا يتجاوز \(2^k-1\)، فإن تكلفة البحث لكل عدد أولي محصورة بـ \(O(10\cdot 2^k)\). وتحت حد البحث الافتراضي يكون \(k\le 7\)، لذلك يبقى العامل الأسي صغيرًا جدًا. وداخل مجال الغربال تكون كل عملية فحص أولية من رتبة \(O(1)\)، وخارجه تصبح من رتبة \(O(\sqrt{n})\).
عمليًا تكون الطريقة سريعة لأن عدد الخانات صغير، ولأن فضاء البحث ليس عامًا بل مقيّد بشدة ببنية الأرقام المتكررة.