We are told that \(1487, 4817, 8147\) is a three-term arithmetic progression of four-digit primes, and that all three numbers are permutations of the same four digits. The task is to find the other four-digit prime progression with the same property and concatenate its three terms into one 12-digit integer.
The crucial point is that two conditions must hold at the same time: the numbers must lie in arithmetic progression, and they must belong to the same digit-permutation class. The successful solution comes from organizing the search around that shared digit structure instead of generating permutations blindly.
The implementations treat the problem as a search over four-digit primes. For each prime \(p\), the digits are sorted into a canonical key, and primes with the same key are collected together. Inside one such class, a three-term arithmetic progression is easy to test.
Define the digit signature of a four-digit number \(p\) by sorting its decimal digits in nondecreasing order. If we write this signature as \(\sigma(p)\), then
$$\sigma(p)=\text{sorted digits of }p.$$
Two four-digit numbers are permutations of one another exactly when they have the same signature. So the search space naturally splits into classes
$$G_s=\{p:\ 1000 \le p \le 9999,\ p \text{ is prime},\ \sigma(p)=s\}.$$
Any valid answer must lie entirely inside one class \(G_s\). That turns the original problem into a much smaller collection of subproblems: for each signature class of primes, determine whether it contains a three-term arithmetic progression.
Suppose a class \(G_s\) is sorted increasingly, and choose two elements \(a<b\) from it. If they are the first two terms of a three-term arithmetic progression, then the third term is forced:
$$b-a=d,\qquad c=b+d=2b-a.$$
So there is no need to guess all three numbers independently. For every pair \((a,b)\) inside one signature class, compute \(c=2b-a\) and check whether \(c\) is also in the same class. If it is, then all required properties are already satisfied:
$$a,\ b,\ c \in G_s \implies \text{all three are four-digit primes with the same digits.}$$
The only extra bound worth checking is \(c \le 9999\), because the progression must stay among four-digit numbers.
Sharing a digit signature means sharing the same digit sum. Therefore every number in a fixed class \(G_s\) is congruent modulo \(9\). If \(a,b,c\) all belong to one class, then
$$a \equiv b \equiv c \pmod 9,$$
so any common difference \(d\) in a valid progression must satisfy
$$d \equiv 0 \pmod 9.$$
There is another immediate restriction: every four-digit prime is odd, so the difference between any two of them in an arithmetic progression must be even. Hence every valid common difference is a multiple of both \(2\) and \(9\), and therefore
$$18 \mid d.$$
The code does not explicitly use this divisibility test, but it explains why such progressions are rare and why a simple grouped search finishes quickly.
The famous example belongs to the signature class \(\sigma=1478\). Inside that class we have
$$1487,\ 4817,\ 8147,$$
and indeed
$$4817-1487=3330,\qquad 8147-4817=3330.$$
The same search also finds the other class with the required structure, namely \(\sigma=2699\). In that class,
$$2969,\ 6299,\ 9629$$
are all prime, all use the same digits, and form the arithmetic progression
$$6299-2969=3330,\qquad 9629-6299=3330.$$
Concatenating these three terms gives the required 12-digit result \(296962999629\).
The C++, Python, and Java implementations iterate through every integer from \(1000\) to \(9999\). Each candidate is tested for primality by trial division: even numbers are handled immediately, and odd divisors are checked only up to \(\sqrt{n}\). Every surviving prime is then sent to the grouping phase.
For each four-digit prime, the decimal digits are sorted to form the canonical signature. A map from signature to list of primes collects all primes with the same multiset of digits. This is the implementation form of the mathematical classes \(G_s\).
Each group with at least three elements is sorted. The implementation scans all pairs \(a<b\) in that group, computes \(c=2b-a\), discards the pair if \(c\) leaves the four-digit range, and otherwise checks whether \(c\) is still in the same group. Once a valid triple is found, the known example beginning with \(1487\) is skipped, and the remaining triple is concatenated in order \(abc\).
Because the search is performed inside a prime-only group, the membership test for \(c\) automatically confirms the prime condition and the permutation condition at the same time. That is why the code stays short while still matching the mathematics exactly.
Let \(R=9000\) be the number of four-digit integers checked. The primality phase uses trial division, so its worst-case running time is \(O(R\sqrt{9999})\), which is tiny at this scale. Sorting four digits is constant-time work, so grouping the primes adds only linear overhead in the number of primes found.
If the signature classes are \(G_1,G_2,\dots\), the progression search costs
$$\sum_i \binom{|G_i|}{2}$$
pair checks, plus a membership lookup for the computed third term. In the C++ and Java implementations that lookup is logarithmic in the class size after sorting; in the Python implementation it is linear in the class size, but the classes are so small that the practical cost is still negligible. Memory usage is \(O(P)\), where \(P\) is the number of four-digit primes stored across all groups.
Gegeben ist, dass \(1487, 4817, 8147\) eine dreigliedrige arithmetische Folge aus vierstelligen Primzahlen bildet und dass alle drei Zahlen Permutationen derselben vier Ziffern sind. Gesucht ist die andere vierstellige Primzahlfolge mit derselben Eigenschaft; anschließend sollen ihre drei Glieder zu einer einzigen 12-stelligen Zahl verkettet werden.
Entscheidend ist, dass zwei Bedingungen gleichzeitig erfüllt sein müssen: Die Zahlen müssen in arithmetischer Progression liegen und zugleich zur selben Ziffern-Permutationsklasse gehören. Deshalb organisiert die Lösung die Suche nach gemeinsamen Ziffern und nicht nach beliebigen Permutationen.
Die Implementierungen betrachten alle vierstelligen Primzahlen. Zu jeder Primzahl \(p\) wird eine kanonische Ziffernsignatur gebildet, indem ihre Dezimalziffern sortiert werden. Primzahlen mit derselben Signatur werden zusammengefasst. Innerhalb einer solchen Klasse lässt sich eine dreigliedrige arithmetische Folge direkt testen.
Definiere die Signatur einer vierstelligen Zahl \(p\), indem ihre Ziffern aufsteigend sortiert werden. Schreiben wir diese Signatur als \(\sigma(p)\), so gilt
$$\sigma(p)=\text{sortierte Ziffern von }p.$$
Zwei vierstellige Zahlen sind genau dann Permutationen voneinander, wenn sie dieselbe Signatur besitzen. Daher zerfällt der Suchraum in Klassen
$$G_s=\{p:\ 1000 \le p \le 9999,\ p \text{ ist prim},\ \sigma(p)=s\}.$$
Jede gültige Lösung muss vollständig in einer einzigen Klasse \(G_s\) liegen. Damit reduziert sich das Problem auf viele kleine Teilprobleme: Enthält eine bestimmte Signaturklasse eine dreigliedrige arithmetische Folge?
Sei \(G_s\) aufsteigend sortiert, und wähle zwei Elemente \(a<b\) daraus. Wenn sie die ersten beiden Glieder einer dreigliedrigen arithmetischen Folge sind, dann ist das dritte Glied eindeutig festgelegt:
$$b-a=d,\qquad c=b+d=2b-a.$$
Man muss also nicht alle drei Zahlen getrennt raten. Für jedes Paar \((a,b)\) in einer Signaturklasse berechnet man \(c=2b-a\) und prüft, ob \(c\) ebenfalls in derselben Klasse liegt. Ist das der Fall, dann sind alle Bedingungen sofort erfüllt:
$$a,\ b,\ c \in G_s \implies \text{alle drei sind vierstellige Primzahlen mit denselben Ziffern.}$$
Zusätzlich genügt die einfache Schranke \(c \le 9999\), damit die Folge im Bereich der vierstelligen Zahlen bleibt.
Gleiche Ziffernsignatur bedeutet gleiche Ziffernsumme. Damit sind alle Zahlen in einer festen Klasse \(G_s\) modulo \(9\) kongruent. Für \(a,b,c\) aus derselben Klasse gilt also
$$a \equiv b \equiv c \pmod 9,$$
und daher muss jede gemeinsame Differenz \(d\) in einer gültigen Folge die Bedingung
$$d \equiv 0 \pmod 9$$
erfüllen. Außerdem ist jede vierstellige Primzahl ungerade, also muss die Differenz in einer arithmetischen Folge gerade sein. Zusammen folgt
$$18 \mid d.$$
Diese Teilbarkeitsaussage wird im Code nicht explizit verwendet, beschreibt aber gut, warum nur sehr wenige Paare überhaupt infrage kommen.
Das bekannte Beispiel gehört zur Signaturklasse \(\sigma=1478\). Dort liegen
$$1487,\ 4817,\ 8147$$
und tatsächlich gilt
$$4817-1487=3330,\qquad 8147-4817=3330.$$
Dieselbe Suche findet auch die andere Klasse mit der verlangten Struktur, nämlich \(\sigma=2699\). In dieser Klasse bilden
$$2969,\ 6299,\ 9629$$
eine Folge von Primzahlen mit denselben Ziffern und mit
$$6299-2969=3330,\qquad 9629-6299=3330.$$
Die gesuchte Verkettung lautet daher \(296962999629\).
Die C++-, Python- und Java-Implementierungen durchlaufen jede ganze Zahl von \(1000\) bis \(9999\). Jede Kandidatenzahl wird durch Probedivision auf Primzahl getestet: Gerade Zahlen werden sofort behandelt, und bei ungeraden Zahlen werden nur ungerade Teiler bis \(\sqrt{n}\) geprüft. Jede gefundene Primzahl geht anschließend in die Gruppierung ein.
Für jede vierstellige Primzahl werden die Dezimalziffern sortiert, um die kanonische Signatur zu erzeugen. Eine Abbildung von Signatur auf Liste der Primzahlen sammelt so alle Zahlen mit demselben Ziffernmultimengensatz. Genau das ist die Implementierung der mathematischen Klassen \(G_s\).
Jede Gruppe mit mindestens drei Elementen wird sortiert. Dann betrachtet die Implementierung alle Paare \(a<b\) in dieser Gruppe, berechnet \(c=2b-a\), verwirft den Fall bei \(c>9999\) und prüft sonst, ob \(c\) ebenfalls in der Gruppe enthalten ist. Sobald eine gültige Dreierfolge gefunden wird, wird das bekannte Beispiel mit Anfang \(1487\) übersprungen und die andere Folge als Verkettung \(abc\) ausgegeben.
Weil die Suche innerhalb einer reinen Primzahlgruppe erfolgt, bestätigt der Mitgliedschaftstest für \(c\) zugleich die Primzahligkeit und die Permutationseigenschaft. Genau deshalb bleibt der Code knapp und ist dennoch mathematisch vollständig.
Sei \(R=9000\) die Zahl der überprüften vierstelligen ganzen Zahlen. Die Primzahlphase benutzt Probedivision und hat daher im schlimmsten Fall Laufzeit \(O(R\sqrt{9999})\); bei dieser Problemgröße ist das sehr klein. Das Sortieren von genau vier Ziffern ist konstante Arbeit, sodass die Gruppierung nur linearen Zusatzaufwand in der Anzahl der gefundenen Primzahlen verursacht.
Bezeichnen \(G_1,G_2,\dots\) die Signaturklassen, dann kostet die Suche nach arithmetischen Folgen
$$\sum_i \binom{|G_i|}{2}$$
Paarprüfungen plus einen Mitgliedschaftstest für den berechneten dritten Term. In C++ und Java ist diese Suche nach dem Sortieren logarithmisch in der Klassengröße; in Python linear in der Klassengröße. Da die Klassen aber sehr klein sind, bleibt der praktische Aufwand vernachlässigbar. Der Speicherbedarf ist \(O(P)\), wobei \(P\) die Zahl der gespeicherten vierstelligen Primzahlen ist.
\(1487, 4817, 8147\) dizisinin dört basamaklı asal sayılardan oluşan bir üç terimli aritmetik dizi olduğu ve bu üç sayının aynı dört rakamın permütasyonları olduğu veriliyor. İstenen şey, aynı özelliğe sahip diğer dört basamaklı asal diziyi bulmak ve üç terimi yan yana yazarak 12 basamaklı tek bir sayı elde etmek.
Burada aynı anda sağlanması gereken iki koşul vardır: sayılar hem aritmetik dizide olmalı hem de aynı rakam sınıfına ait olmalıdır. Bu yüzden çözüm, tüm permütasyonları üretmek yerine ortak rakam yapısını temel alarak arama yapar.
Uygulamalar problemi dört basamaklı asallar üzerinde bir arama olarak kurar. Her asal \(p\) için rakamlar sıralanarak tekil bir imza elde edilir; aynı imzaya sahip asal sayılar aynı gruba konur. Bir grubun içinde üç terimli aritmetik dizi testi çok doğrudan hale gelir.
Dört basamaklı bir \(p\) sayısının basamak imzasını, ondalık rakamlarını küçükten büyüğe sıralayarak tanımlayalım. Bunu \(\sigma(p)\) ile gösterirsek
$$\sigma(p)=\text{\(p\) sayısının sıralanmış rakamları}$$
olur. İki dört basamaklı sayı, ancak ve ancak imzaları aynıysa birbirinin rakam permütasyonudur. Böylece arama uzayı
$$G_s=\{p:\ 1000 \le p \le 9999,\ p \text{ asaldır},\ \sigma(p)=s\}$$
sınıflarına ayrılır. Geçerli bir çözümün tamamı tek bir \(G_s\) sınıfının içinde bulunmak zorundadır. Yani asıl soru, her imza sınıfı için şu hale gelir: Bu sınıfta üç terimli bir aritmetik dizi var mı?
\(G_s\) sınıfı artan sırada yazılsın ve içinden \(a<b\) olmak üzere iki eleman seçilsin. Bunlar üç terimli bir aritmetik dizinin ilk iki terimiyse üçüncü terim zorunlu olarak
$$b-a=d,\qquad c=b+d=2b-a$$
şeklindedir. Dolayısıyla üç sayıyı ayrı ayrı tahmin etmeye gerek yoktur. Aynı imza sınıfındaki her \((a,b)\) çifti için \(c=2b-a\) hesaplanır ve \(c\)'nin yine aynı sınıfta olup olmadığına bakılır. Eğer varsa
$$a,\ b,\ c \in G_s \implies \text{üçü de aynı rakamlı dört basamaklı asallardır.}$$
Böylece tek ek sınır kontrolü \(c \le 9999\) şartıdır; çünkü dizi dört basamaklı sayılar içinde kalmalıdır.
Aynı imzaya sahip sayılar aynı rakam toplamına sahiptir. Bu nedenle sabit bir \(G_s\) sınıfındaki tüm sayılar \(9\) modunda denktir. Eğer \(a,b,c\) aynı sınıftaysa
$$a \equiv b \equiv c \pmod 9$$
olur; dolayısıyla ortak fark \(d\) için
$$d \equiv 0 \pmod 9$$
gerekir. Ayrıca dört basamaklı her asal tektir, bu yüzden aritmetik dizideki ortak farkın çift olması gerekir. İki koşul birlikte
$$18 \mid d$$
sonucunu verir. Kod bu gözlemi açıkça kullanmaz, ama neden çok az sayıda adayın başarılı olduğunu iyi açıklar.
Bilinen örnek \(\sigma=1478\) imza sınıfındadır. Bu sınıfta
$$1487,\ 4817,\ 8147$$
bulunur ve gerçekten
$$4817-1487=3330,\qquad 8147-4817=3330$$
eşitlikleri sağlanır. Aynı arama, istenen diğer sınıfı da bulur: \(\sigma=2699\). Bu sınıfta
$$2969,\ 6299,\ 9629$$
hem asaldır hem de aynı rakamların permütasyonlarıdır; ayrıca
$$6299-2969=3330,\qquad 9629-6299=3330.$$
Üç terim yan yana yazılınca istenen sayı \(296962999629\) olur.
C++, Python ve Java uygulamaları \(1000\) ile \(9999\) arasındaki her tam sayıyı dolaşır. Her aday için asal testi deneme bölmesiyle yapılır: çift sayılar hemen ele alınır, tek sayılar için ise yalnızca \(\sqrt{n}\)'e kadar tek bölenler denenir. Asal çıkan sayılar bir sonraki aşamaya gönderilir.
Her dört basamaklı asalın rakamları sıralanır ve kanonik imza elde edilir. İmzadan asal listesine giden bir eşleme, aynı rakam çoklu kümesine sahip bütün asalları aynı yerde toplar. Matematikteki \(G_s\) sınıfları kodda tam olarak bu yapıya karşılık gelir.
En az üç elemanlı her grup sıralanır. Sonra grup içindeki bütün \(a<b\) çiftleri gezilir, \(c=2b-a\) hesaplanır, \(c>9999\) ise aday atılır, aksi halde \(c\)'nin grupta bulunup bulunmadığı kontrol edilir. Geçerli bir üçlü bulunduğunda \(1487\) ile başlayan bilinen örnek atlanır ve diğer üçlü \(abc\) biçiminde birleştirilir.
Arama yalnızca asal sayılardan oluşan bir grup içinde yapıldığı için, \(c\)'nin grupta bulunması hem asal olma koşulunu hem de rakam permütasyonu koşulunu aynı anda doğrular. Bu yüzden uygulama kısa ama tam olarak probleme uygundur.
\(R=9000\) tane dört basamaklı tam sayı kontrol edilir. Asal testi deneme bölmesi kullandığı için en kötü durumda maliyet \(O(R\sqrt{9999})\) olur; bu problem boyutunda bu son derece küçüktür. Dört rakamı sıralamak sabit zamanlı olduğundan, gruplama aşaması bulunan asal sayılar sayısında doğrusal ek maliyet getirir.
İmza sınıfları \(G_1,G_2,\dots\) olsun. Aritmetik dizi araması
$$\sum_i \binom{|G_i|}{2}$$
adet çift kontrolü yapar ve her çift için hesaplanan üçüncü terim için bir üyelik sorgusu yürütür. C++ ve Java sürümlerinde bu sorgu, sıralamadan sonra sınıf boyutuna göre logaritmiktir; Python sürümünde sınıf boyutuna göre doğrusaldır. Fakat sınıflar çok küçük olduğu için pratikte bu fark önemsizdir. Bellek kullanımı, depolanan dört basamaklı asal sayılar sayısı \(P\) için \(O(P)\) düzeyindedir.
Se nos dice que \(1487, 4817, 8147\) forma una progresión aritmética de tres números primos de cuatro cifras, y que los tres números son permutaciones de las mismas cuatro cifras. La tarea consiste en encontrar la otra progresión de primos de cuatro cifras con esa propiedad y concatenar sus tres términos para obtener un único entero de 12 cifras.
Las dos restricciones importantes son simultáneas: los números deben estar en progresión aritmética y además deben pertenecer a la misma clase de permutación de dígitos. Por eso la solución no intenta generar todas las permutaciones posibles, sino que organiza la búsqueda por estructura digital compartida.
Las implementaciones recorren los primos de cuatro cifras. Para cada primo \(p\), ordenan sus dígitos y usan esa cadena ordenada como firma canónica. Los primos con la misma firma se agrupan juntos. Dentro de una clase así, comprobar una progresión aritmética de longitud tres es muy sencillo.
Definimos la firma digital de un número de cuatro cifras \(p\) ordenando sus dígitos decimales de menor a mayor. Si llamamos \(\sigma(p)\) a esa firma, entonces
$$\sigma(p)=\text{dígitos ordenados de }p.$$
Dos números de cuatro cifras son permutaciones uno del otro exactamente cuando tienen la misma firma. Así, el espacio de búsqueda se divide en clases
$$G_s=\{p:\ 1000 \le p \le 9999,\ p \text{ es primo},\ \sigma(p)=s\}.$$
Cualquier solución válida debe quedar completamente dentro de una sola clase \(G_s\). El problema original se reduce entonces a una colección de preguntas más pequeñas: para cada firma, decidir si la clase correspondiente contiene una progresión aritmética de tres términos.
Supongamos que una clase \(G_s\) está ordenada en forma creciente y tomamos dos elementos \(a<b\) de ella. Si son los dos primeros términos de una progresión aritmética de longitud tres, el tercer término queda forzado:
$$b-a=d,\qquad c=b+d=2b-a.$$
Por tanto, no hace falta adivinar las tres cifras a la vez. Para cada par \((a,b)\) dentro de una misma clase de firma, se calcula \(c=2b-a\) y se verifica si \(c\) también pertenece a la misma clase. Si ocurre eso, entonces ya se cumplen todas las condiciones:
$$a,\ b,\ c \in G_s \implies \text{los tres son primos de cuatro cifras con los mismos dígitos.}$$
La única cota adicional necesaria es \(c \le 9999\), para asegurarse de que la progresión siga dentro del rango de cuatro cifras.
Tener la misma firma implica tener la misma suma de dígitos. Por eso, todos los números de una clase fija \(G_s\) son congruentes módulo \(9\). Si \(a,b,c\) pertenecen a la misma clase, entonces
$$a \equiv b \equiv c \pmod 9,$$
de modo que la diferencia común \(d\) de una progresión válida debe satisfacer
$$d \equiv 0 \pmod 9.$$
Además, todo primo de cuatro cifras es impar, así que la diferencia entre términos consecutivos de la progresión debe ser par. Combinando ambas observaciones obtenemos
$$18 \mid d.$$
El código no utiliza esta divisibilidad como poda explícita, pero sí explica por qué sobreviven tan pocos candidatos.
El ejemplo conocido pertenece a la clase \(\sigma=1478\). En esa clase aparecen
$$1487,\ 4817,\ 8147,$$
y en efecto
$$4817-1487=3330,\qquad 8147-4817=3330.$$
La misma búsqueda encuentra la otra clase con la estructura pedida, la de firma \(\sigma=2699\). Allí
$$2969,\ 6299,\ 9629$$
son todos primos, usan las mismas cifras y verifican
$$6299-2969=3330,\qquad 9629-6299=3330.$$
Al concatenarlos se obtiene el resultado buscado: \(296962999629\).
Las implementaciones en C++, Python y Java recorren todos los enteros desde \(1000\) hasta \(9999\). Cada candidato se somete a una prueba de primalidad por división tentativa: los pares se resuelven de inmediato y, para los impares, solo se ensayan divisores impares hasta \(\sqrt{n}\). Los números que superan esta prueba pasan a la fase de agrupación.
Para cada primo de cuatro cifras, se ordenan sus dígitos y se obtiene una firma canónica. Un mapa desde la firma hacia una lista de primos reúne todos los primos con el mismo multiconjunto de dígitos. Esa estructura es la realización directa de las clases matemáticas \(G_s\).
Cada grupo con al menos tres elementos se ordena. Luego la implementación examina todos los pares \(a<b\) del grupo, calcula \(c=2b-a\), descarta el caso si \(c>9999\) y, en caso contrario, comprueba si \(c\) sigue perteneciendo al mismo grupo. Cuando aparece una terna válida, se omite el ejemplo conocido que empieza en \(1487\) y se concatena la otra terna en el orden \(abc\).
Como la comprobación se hace dentro de un grupo formado solo por primos, verificar que \(c\) pertenece al grupo confirma al mismo tiempo la primalidad y la condición de permutación. Esa es la razón por la que la implementación es breve y, sin embargo, matemáticamente exacta.
Sea \(R=9000\) el número de enteros de cuatro cifras inspeccionados. La fase de primalidad usa división tentativa, así que su coste en el peor caso es \(O(R\sqrt{9999})\), muy pequeño para este tamaño de entrada. Ordenar cuatro dígitos es trabajo constante, por lo que la agrupación añade solo un coste lineal en el número de primos encontrados.
Si \(G_1,G_2,\dots\) son las clases de firma, la búsqueda de progresiones requiere
$$\sum_i \binom{|G_i|}{2}$$
comprobaciones de pares, más una búsqueda de pertenencia para el tercer término calculado. En C++ y Java esa búsqueda es logarítmica en el tamaño del grupo una vez ordenado; en Python es lineal en el tamaño del grupo. Como los grupos son muy pequeños, el coste práctico sigue siendo insignificante. El uso de memoria es \(O(P)\), donde \(P\) es el número de primos de cuatro cifras almacenados en todos los grupos.
题目先给出一个已知例子：\(1487, 4817, 8147\) 是三个四位素数，既构成等差数列，又互为同一组数字的排列。要求找出另一个满足同样条件的四位素数三项等差数列，并把三项按顺序拼接成一个 12 位整数。
这个问题的关键不只是“找素数”，而是要同时满足两个结构条件：一是三项必须成等差，二是三项必须来自同一个数字排列类。真正高效的做法不是对每个素数暴力生成全部排列，而是先按数字结构分组，再在每个小组内部寻找等差关系。
三份实现都把问题看成对四位素数的有组织搜索。对每个素数 \(p\)，先把十进制数字排序，得到一个标准化的“数字签名”；拥有同一签名的素数被放进同一组。这样一来，排列条件被编码进分组本身，剩下的工作就是在组内寻找三项等差数列。
定义四位数 \(p\) 的数字签名 \(\sigma(p)\) 为：把它的十进制数字按从小到大排序后得到的结果，即
$$\sigma(p)=\text{\(p\) 的数字排序结果}.$$
两个四位数互为数字排列，当且仅当它们有相同的签名。因此搜索空间自然分解为若干类
$$G_s=\{p:\ 1000 \le p \le 9999,\ p \text{ 是素数},\ \sigma(p)=s\}.$$
任何合法答案都必须完整地落在某个单独的 \(G_s\) 中。于是原问题被改写成许多小问题：对每个数字签名 \(s\)，对应的素数组 \(G_s\) 是否含有一个三项等差数列？
设某个类 \(G_s\) 已按从小到大排序，取其中两个元素 \(a<b\)。如果它们是一个三项等差数列的前两项，那么第三项就被唯一确定为
$$b-a=d,\qquad c=b+d=2b-a.$$
因此不需要同时猜三个数。对同一签名类里的每一对 \((a,b)\)，只要计算 \(c=2b-a\)，再检查 \(c\) 是否仍在这个类中即可。如果 \(c\) 也属于 \(G_s\)，那么排列条件和素数条件已经自动满足：
$$a,\ b,\ c \in G_s \implies \text{三者都是同一数字集合的四位素数。}$$
唯一还要显式检查的是 \(c \le 9999\)，因为题目只允许四位数。
同一个数字签名意味着相同的数字和，所以同一类 \(G_s\) 中的所有数模 \(9\) 同余。若 \(a,b,c\) 来自同一类，则有
$$a \equiv b \equiv c \pmod 9,$$
因此合法等差数列的公差 \(d\) 必须满足
$$d \equiv 0 \pmod 9.$$
另一方面，所有四位素数都是奇数，所以等差数列的公差还必须是偶数。两条条件合并起来得到
$$18 \mid d.$$
实现并没有把这条整除性质单独写成剪枝规则，但它很好地解释了为什么真正可能成功的候选对非常少。
已知例子属于签名 \(\sigma=1478\) 这一类，其中有
$$1487,\ 4817,\ 8147,$$
并且
$$4817-1487=3330,\qquad 8147-4817=3330.$$
同样的搜索方法还会找到另一个满足要求的签名类，即 \(\sigma=2699\)。在这个类里，
$$2969,\ 6299,\ 9629$$
都是素数，数字完全相同，只是顺序不同，而且
$$6299-2969=3330,\qquad 9629-6299=3330.$$
因此题目要求拼接得到的结果就是 \(296962999629\)。这个例子同时说明了为什么“先分组、再找等差”正是最贴合题意的数学建模。
C++、Python 和 Java 实现都会遍历 \(1000\) 到 \(9999\) 之间的每个整数。对每个候选值，先做试除素性判断：偶数单独处理，奇数只检查到 \(\sqrt{n}\) 为止的奇除数。通过测试的数字被视为四位素数，并送入下一步。
每个四位素数的十进制数字都会被排序，形成标准签名。随后，用“签名 \(\rightarrow\) 素数列表”的映射把拥有同一数字多重集的素数聚到一起。这正是数学中 \(G_s\) 类的程序化表示。
每个元素个数至少为 3 的分组都会先排序。然后实现遍历组内所有 \(a<b\) 的成对选择，计算 \(c=2b-a\)。若 \(c>9999\)，这对候选直接丢弃；否则检查 \(c\) 是否还在同一组中。一旦找到合法三元组，就跳过已知的 \(1487,4817,8147\)，并把另一个三元组按 \(abc\) 顺序拼接输出。
因为组内原本就只保存四位素数，所以“\(c\) 是否在同一组中”这一条测试，实际上同时验证了三件事：\(c\) 是四位数、\(c\) 是素数、\(c\) 与前两项拥有相同数字。这样程序很短，但与数学条件完全一致。
设 \(R=9000\) 是被检查的四位整数个数。素性测试使用试除法，因此最坏情况下这一阶段的复杂度为 \(O(R\sqrt{9999})\)。在本题规模下，这个代价非常小。每个素数只需要对 4 个数字排序，所以分组阶段对找到的素数个数只增加线性级别的开销。
若各个签名类记为 \(G_1,G_2,\dots\)，则等差搜索的成对检查总数为
$$\sum_i \binom{|G_i|}{2}.$$
此外，每一对还需要对第三项做一次成员查询。C++ 和 Java 版本在排序后的组中使用对数级别的查找；Python 版本对列表做线性成员测试。不过这些组都很小，所以实际运行时间仍然几乎可以忽略。内存使用量为 \(O(P)\)，其中 \(P\) 是所有分组中存储的四位素数总数。
Известно, что \(1487, 4817, 8147\) образуют арифметическую прогрессию из трёх четырёхзначных простых чисел, причём все три числа являются перестановками одних и тех же цифр. Нужно найти другую такую же прогрессию из четырёхзначных простых и записать подряд её три члена, получив одно 12-значное число.
Сложность задачи в том, что одновременно должны выполняться два условия: числа должны образовывать арифметическую прогрессию и принадлежать одному классу цифровых перестановок. Поэтому правильная стратегия состоит не в переборе всех перестановок, а в группировке простых по общему цифровому инварианту.
Во всех трёх реализациях задача рассматривается как поиск по четырёхзначным простым числам. Для каждого простого \(p\) его цифры сортируются, и эта отсортированная запись используется как каноническая сигнатура. Простые с одинаковой сигнатурой собираются в одну группу. После этого проверка трёхчленной арифметической прогрессии внутри одной группы становится очень простой.
Определим цифровую сигнатуру четырёхзначного числа \(p\) как результат сортировки его десятичных цифр по возрастанию. Обозначая её через \(\sigma(p)\), получаем
$$\sigma(p)=\text{отсортированные цифры числа }p.$$
Два четырёхзначных числа являются перестановками друг друга тогда и только тогда, когда их сигнатуры совпадают. Значит, пространство поиска естественно разбивается на классы
$$G_s=\{p:\ 1000 \le p \le 9999,\ p \text{ простое},\ \sigma(p)=s\}.$$
Любое допустимое решение целиком лежит внутри одного класса \(G_s\). Тем самым исходная задача распадается на набор меньших задач: содержит ли данный сигнатурный класс трёхчленную арифметическую прогрессию?
Пусть класс \(G_s\) отсортирован по возрастанию, и из него выбраны два элемента \(a<b\). Если это первые два члена трёхчленной арифметической прогрессии, то третий член определяется однозначно:
$$b-a=d,\qquad c=b+d=2b-a.$$
Поэтому не нужно угадывать все три числа сразу. Для каждой пары \((a,b)\) внутри одного класса достаточно вычислить \(c=2b-a\) и проверить, принадлежит ли \(c\) тому же самому классу. Если принадлежит, то все нужные свойства автоматически выполнены:
$$a,\ b,\ c \in G_s \implies \text{все три являются четырёхзначными простыми с теми же цифрами.}$$
Дополнительно достаточно проверить лишь условие \(c \le 9999\), чтобы прогрессия не выходила за пределы четырёхзначных чисел.
Одинаковая сигнатура означает одинаковую сумму цифр. Следовательно, все числа одного класса \(G_s\) сравнимы по модулю \(9\):
$$a \equiv b \equiv c \pmod 9.$$
Значит, общая разность \(d\) любой допустимой прогрессии обязана удовлетворять условию
$$d \equiv 0 \pmod 9.$$
Кроме того, все четырёхзначные простые нечётны, а значит разность между соседними членами арифметической прогрессии должна быть чётной. Вместе это даёт
$$18 \mid d.$$
Эта делимость не используется в коде как отдельная оптимизация, но она хорошо объясняет, почему подходящих кандидатов оказывается очень мало.
Известный пример принадлежит классу с сигнатурой \(\sigma=1478\). Внутри него находятся
$$1487,\ 4817,\ 8147,$$
и действительно
$$4817-1487=3330,\qquad 8147-4817=3330.$$
Тот же самый поиск находит и второй нужный класс, а именно \(\sigma=2699\). В нём числа
$$2969,\ 6299,\ 9629$$
тоже простые, являются перестановками одних и тех же цифр и удовлетворяют
$$6299-2969=3330,\qquad 9629-6299=3330.$$
Именно поэтому искомая конкатенация равна \(296962999629\).
Реализации на C++, Python и Java перебирают каждое целое число от \(1000\) до \(9999\). Для каждого кандидата выполняется проверка простоты методом пробных делений: чётные числа обрабатываются сразу, а для нечётных проверяются только нечётные делители вплоть до \(\sqrt{n}\). Все числа, прошедшие этот тест, передаются на этап группировки.
У каждого найденного четырёхзначного простого сортируются цифры, после чего получается каноническая сигнатура. Отображение вида «сигнатура \(\rightarrow\) список простых» собирает вместе все простые с одинаковым мультимножеством цифр. Это и есть программная форма математических классов \(G_s\).
Каждая группа как минимум из трёх элементов сортируется. Затем реализация перебирает все пары \(a<b\) внутри группы, вычисляет \(c=2b-a\), отбрасывает случай при \(c>9999\) и в противном случае проверяет, лежит ли \(c\) в том же списке. Когда находится корректная тройка, известный пример, начинающийся с \(1487\), пропускается, а другая тройка склеивается в порядке \(abc\).
Так как поиск идёт внутри группы, содержащей только простые числа, проверка принадлежности \(c\) одновременно подтверждает и простоту, и условие на перестановку цифр. Именно поэтому код остаётся коротким, но полностью соответствует математике задачи.
Пусть \(R=9000\) обозначает количество проверяемых четырёхзначных целых чисел. Этап проверки простоты использует пробные деления, поэтому его худшая асимптотика равна \(O(R\sqrt{9999})\), что для данного диапазона очень мало. Сортировка ровно четырёх цифр занимает константное время, так что группировка добавляет лишь линейную по числу найденных простых стоимость.
Если сигнатурные классы обозначить через \(G_1,G_2,\dots\), то поиск прогрессий требует
$$\sum_i \binom{|G_i|}{2}$$
проверок пар и одного запроса на принадлежность для вычисленного третьего члена. В версиях на C++ и Java этот поиск после сортировки логарифмический по размеру класса; в версии на Python он линейный по размеру класса. Поскольку сами классы малы, практическое время работы в любом случае ничтожно. Память имеет порядок \(O(P)\), где \(P\) — число сохранённых четырёхзначных простых во всех группах.
المعطى أن \(1487, 4817, 8147\) تشكل متتابعة حسابية من ثلاثة أعداد أولية مكوّنة من أربع خانات، وأن الأعداد الثلاثة هي تبديلات لنفس الأرقام الأربع. المطلوب هو إيجاد المتتابعة الأخرى من الأعداد الأولية ذات الأربع خانات التي تحقق الخاصية نفسها، ثم ضم حدودها الثلاثة بالترتيب للحصول على عدد واحد من 12 خانة.
جوهر المسألة هو اجتماع شرطين معًا: لا بد أن تكون الأعداد في متتابعة حسابية، ولا بد أيضًا أن تنتمي إلى الفئة نفسها من حيث ترتيب الأرقام. لذلك لا يعتمد الحل على توليد جميع التبديلات الممكنة، بل على تجميع الأعداد بحسب البنية الرقمية المشتركة ثم البحث داخل كل مجموعة.
تتعامل التطبيقات مع المسألة باعتبارها بحثًا منظمًا بين الأعداد الأولية ذات الأربع خانات. لكل عدد أولي \(p\)، تُرتَّب أرقامه العشرية للحصول على توقيع رقمي معياري، ثم تُجمع الأعداد الأولية ذات التوقيع نفسه في قائمة واحدة. عندئذ يصبح اختبار وجود متتابعة حسابية من ثلاثة حدود داخل المجموعة أمرًا مباشرًا.
نعرّف التوقيع الرقمي للعدد ذي الأربع خانات \(p\) بأنه الناتج عن ترتيب أرقامه تصاعديًا. وإذا رمزنا إلى هذا التوقيع بـ \(\sigma(p)\)، فيمكن كتابة الفكرة رمزيًا على الصورة
$$\sigma(p)=\operatorname{sort}(p).$$
ويكون عددان من أربع خانات تبديلين لبعضهما البعض إذا وفقط إذا امتلكا التوقيع نفسه. لذلك ينقسم فضاء البحث طبيعيًا إلى فئات من الشكل
$$G_s=\{p\in \mathbb{P}:\ 1000 \le p \le 9999,\ \sigma(p)=s\}.$$
وأي حل صحيح لا بد أن يقع بالكامل داخل فئة واحدة \(G_s\). وهكذا تتحول المسألة الأصلية إلى أسئلة أصغر: هل تحتوي فئة توقيع معينة على متتابعة حسابية من ثلاثة حدود أم لا؟
افترض أن عناصر الفئة \(G_s\) مرتبة تصاعديًا، واختر عنصرين \(a<b\) منها. إذا كانا الحدين الأولين في متتابعة حسابية من ثلاثة حدود، فإن الحد الثالث يصبح محددًا حتميًا وفق العلاقة
$$b-a=d,\qquad c=b+d=2b-a.$$
إذًا لسنا بحاجة إلى تخمين الأعداد الثلاثة دفعة واحدة. لكل زوج \((a,b)\) داخل الفئة نفسها نحسب \(c=2b-a\)، ثم نتحقق مما إذا كان \(c\) موجودًا في الفئة نفسها. وإذا تحقق ذلك فمجرد وجود
$$a,\ b,\ c \in G_s$$
يعني أن الأعداد الثلاثة أولية من أربع خانات ولها الأرقام نفسها.
ويبقى فقط أن نضمن الشرط \(c \le 9999\) حتى لا تخرج المتتابعة من نطاق الأعداد ذات الأربع خانات.
امتلاك التوقيع نفسه يعني امتلاك مجموع الأرقام نفسه. لذلك تكون جميع الأعداد داخل الفئة \(G_s\) متطابقة بترديد \(9\). فإذا كانت \(a,b,c\) في الفئة نفسها، فلدينا
$$a \equiv b \equiv c \pmod 9,$$
ومن ثم يجب أن يحقق الفرق المشترك \(d\) في أي متتابعة صحيحة الشرط
$$d \equiv 0 \pmod 9.$$
ومن جهة أخرى، كل عدد أولي ذي أربع خانات هو عدد فردي، ولذلك يجب أن يكون الفرق بين حدين متتالين في المتتابعة الحسابية عددًا زوجيًا. وبدمج الشرطين نحصل على
$$18 \mid d.$$
لا تستخدم الشيفرة هذه القابلية للقسمة كاختصار مستقل، لكنها تفسر جيدًا لماذا لا ينجح إلا عدد قليل جدًا من الأزواج المرشحة.
المثال المعروف ينتمي إلى فئة التوقيع \(\sigma=1478\). داخل هذه الفئة نجد
$$1487,\ 4817,\ 8147,$$
وبالفعل
$$4817-1487=3330,\qquad 8147-4817=3330.$$
وبالبحث نفسه نعثر على الفئة الأخرى المطلوبة، وهي فئة التوقيع \(\sigma=2699\). في هذه الفئة تكون الأعداد
$$2969,\ 6299,\ 9629$$
كلها أولية، وتستخدم الأرقام نفسها، كما تحقق
$$6299-2969=3330,\qquad 9629-6299=3330.$$
وبذلك يكون العدد الناتج عن ضم الحدود الثلاثة هو \(296962999629\).
تقوم تطبيقات C++ وPython وJava بالمرور على كل عدد صحيح من \(1000\) إلى \(9999\). ولكل عدد مرشح، يُجرى اختبار أولية بالقسمة التجريبية: تُعالج الأعداد الزوجية مباشرة، أما الأعداد الفردية فلا يُفحص منها إلا القواسم الفردية حتى \(\sqrt{n}\). وكل عدد ينجح في هذا الاختبار ينتقل إلى مرحلة التجميع.
تُرتب أرقام كل عدد أولي ذي أربع خانات للحصول على توقيع معياري. ثم تُستخدم بنية ربط من التوقيع إلى قائمة الأعداد الأولية لتجميع جميع الأعداد التي تمتلك مجموعة الأرقام نفسها. وهذا هو التمثيل البرمجي المباشر للفئات الرياضية \(G_s\).
كل مجموعة تحتوي على ثلاثة عناصر على الأقل تُرتب تصاعديًا. بعد ذلك تمر الشيفرة على جميع الأزواج \(a<b\) داخل المجموعة، وتحسب \(c=2b-a\)، وتهمل الحالة إذا كان \(c>9999\)، وإلا فتتحقق من وجود \(c\) في المجموعة نفسها. وعندما تُعثر على ثلاثية صحيحة، يُتجاوز المثال المعروف الذي يبدأ بـ \(1487\)، ثم تُضم الثلاثية الأخرى بالترتيب \(abc\).
ولأن البحث يجري داخل مجموعة تحتوي أصلًا على أعداد أولية فقط، فإن مجرد التحقق من وجود \(c\) داخل المجموعة يؤكد في الوقت نفسه شرط الأولية وشرط تبديل الأرقام. ولهذا تبقى الشيفرة قصيرة مع أنها تمثل الفكرة الرياضية بدقة كاملة.
إذا رمزنا بعدد الأعداد الصحيحة ذات الأربع خانات المفحوصة بـ \(R=9000\)، فإن مرحلة اختبار الأولية بالقسمة التجريبية تمتلك في أسوأ حالة تعقيدًا من رتبة \(O(R\sqrt{9999})\)، وهو صغير جدًا في هذا النطاق. أما ترتيب أربعة أرقام فقط فهو كلفة ثابتة، لذا فإن مرحلة التجميع تضيف كلفة خطية في عدد الأعداد الأولية التي تم العثور عليها.
إذا كانت فئات التوقيع هي \(G_1,G_2,\dots\)، فإن البحث عن المتتابعات يحتاج إلى
$$\sum_i \binom{|G_i|}{2}$$
من فحوص الأزواج، إضافة إلى استعلام انتماء واحد للحد الثالث المحسوب. في نسختي C++ وJava يكون هذا الاستعلام لوغاريتميًا في حجم المجموعة بعد ترتيبها، بينما يكون خطيًا في حجم المجموعة في نسخة Python. لكن أحجام المجموعات صغيرة جدًا، لذلك يبقى الزمن العملي مهملاً. أما الذاكرة فرتبتها \(O(P)\)، حيث \(P\) هو عدد الأعداد الأولية ذات الأربع خانات المخزنة عبر جميع المجموعات.