We seek 10-digit pandigital numbers \(d_1d_2\cdots d_{10}\) that use each digit from 0 through 9 exactly once, with \(d_1 \neq 0\). The special condition is imposed on the seven overlapping 3-digit windows beginning at positions 2 through 8.
If we define
$$w_i = 100d_{i+1} + 10d_{i+2} + d_{i+3}\qquad (1 \le i \le 7)$$
and
$$(p_1,p_2,\dots,p_7) = (2,3,5,7,11,13,17),$$
then the required property is
$$w_i \equiv 0 \pmod{p_i}\qquad \text{for every } i=1,2,\dots,7.$$
The task is to sum all pandigital numbers satisfying these seven congruences simultaneously.
The problem is a finite constraint filter on the set of pandigital arrangements. The useful mathematics is not a recurrence or a generating function, but the structure created by the seven sliding windows and the divisibility rules attached to them.
The windows are
$$d_2d_3d_4,\ d_3d_4d_5,\ d_4d_5d_6,\ d_5d_6d_7,\ d_6d_7d_8,\ d_7d_8d_9,\ d_8d_9d_{10}.$$
They overlap by two digits each time, so a choice made in the middle of the number affects several tests at once. For example, \(d_6\) appears in the windows checked against 5, 7, and 11, while \(d_8\) appears in the windows checked against 11, 13, and 17. That overlap is the central mathematical object in the problem: the divisibility conditions are local, but they are chained together.
Several restrictions can be read off before examining any full candidate. Since \(w_1=d_2d_3d_4\) is divisible by 2, the last digit of that window must be even, so \(d_4\) is even. Since \(w_3=d_4d_5d_6\) is divisible by 5, its last digit must be 0 or 5, so
$$d_6 \in \{0,5\}.$$
Since \(w_2=d_3d_4d_5\) is divisible by 3, its digit sum must be divisible by 3, hence
$$d_3 + d_4 + d_5 \equiv 0 \pmod{3}.$$
These are not separate side facts. Because the windows overlap, a decision forced by one prime immediately feeds into later primes. This is why valid pandigital numbers are very rare even though the raw search space is only \(10!\).
The checkpoint example used by the implementations is
$$1406357289.$$
Its seven windows are
$$406,\ 063,\ 635,\ 357,\ 572,\ 728,\ 289.$$
Now check them against the prime list in order:
$$406 \equiv 0 \pmod{2},\quad 63 \equiv 0 \pmod{3},\quad 635 \equiv 0 \pmod{5},$$
$$357 \equiv 0 \pmod{7},\quad 572 \equiv 0 \pmod{11},\quad 728 \equiv 0 \pmod{13},\quad 289 \equiv 0 \pmod{17}.$$
The block \(063\) is perfectly valid here: it is the value of the digits in positions 3 through 5, and numerically it equals 63. This example shows exactly what the predicate tests and why the windows must be interpreted positionally rather than as standalone decimal strings.
No recurrence is needed because every candidate can be checked independently. There are exactly
$$10! = 3{,}628{,}800$$
pandigital arrangements of the ten digits. The implementation simply evaluates the seven-window predicate on each arrangement, rejecting those with leading zero because they are not 10-digit numbers. Even in the worst case this means only \(7 \cdot 10!\) modular checks, which is a modest amount of work for modern hardware.
The C++, Python, and Java implementations all follow the same high-level algorithm: enumerate every arrangement of the digits 0 through 9, test the substring divisibility property, and add the numeric value of each valid arrangement to a running total.
The compiled implementations begin from the ordered digit sequence 0123456789 and move through the arrangements in lexicographic order. The Python implementation asks the standard permutation iterator for all arrangements of the same ten digits. In every case, uniqueness of digits is automatic because the generator itself produces permutations.
For each candidate, the implementation first checks whether the first digit is zero. If so, the candidate is rejected immediately. Otherwise it builds the seven window values \(w_1,\dots,w_7\) directly from adjacent digits and compares them with the fixed prime list \((2,3,5,7,11,13,17)\). The candidate is accepted only if all seven congruences hold.
Whenever a candidate passes the predicate, the full 10-digit value is converted to an integer and added to the running total. Before the complete sweep begins, the implementations also perform small sanity checks: the known valid example \(1406357289\) must pass, while an obvious non-example such as \(1234567890\) must fail. Those checkpoints ensure that the divisibility test is wired to the correct positions and primes.
The search visits all \(10!\) permutations, so the running time is \(O(10!)\). More concretely, it examines 3,628,800 candidates, and each candidate requires only constant work: one leading-zero test, seven 3-digit constructions, and seven modular reductions in the worst case.
The extra memory usage is \(O(1)\) beyond the current candidate and the running total. The C++ and Java versions mutate a small in-memory digit container in place, while the Python version receives candidates lazily from the permutation iterator, so none of the implementations stores the full search space.
Gesucht sind 10-stellige pandigitale Zahlen \(d_1d_2\cdots d_{10}\), in denen jede Ziffer von 0 bis 9 genau einmal vorkommt und \(d_1 \neq 0\) gilt. Die besondere Bedingung betrifft sieben überlappende 3-stellige Fenster, die bei den Positionen 2 bis 8 beginnen.
Definiert man
$$w_i = 100d_{i+1} + 10d_{i+2} + d_{i+3}\qquad (1 \le i \le 7)$$
und
$$(p_1,p_2,\dots,p_7) = (2,3,5,7,11,13,17),$$
dann lautet die Bedingung
$$w_i \equiv 0 \pmod{p_i}\qquad \text{fur alle } i=1,2,\dots,7.$$
Gesucht ist die Summe aller pandigitalen Zahlen, die alle sieben Kongruenzen gleichzeitig erfullen.
Das Problem ist eine endliche Filteraufgabe auf der Menge aller pandigitalen Anordnungen. Der mathematische Kern ist keine Rekursion, sondern die Struktur der sieben gleitenden Fenster und der dazugehorigen Teilbarkeitsbedingungen.
Die Fenster sind
$$d_2d_3d_4,\ d_3d_4d_5,\ d_4d_5d_6,\ d_5d_6d_7,\ d_6d_7d_8,\ d_7d_8d_9,\ d_8d_9d_{10}.$$
Jeweils zwei Ziffern werden von einem Fenster zum nachsten weitergereicht. Dadurch beeinflusst eine Entscheidung in der Mitte der Zahl mehrere Tests gleichzeitig. So liegt \(d_6\) in den Fenstern fur 5, 7 und 11, wahrend \(d_8\) in den Fenstern fur 11, 13 und 17 vorkommt. Genau diese Uberlappung macht die Aufgabe interessant: lokale Teilbarkeitsregeln sind zu einer Kette gekoppelt.
Einige Einschrankungen folgen sofort. Weil \(w_1=d_2d_3d_4\) durch 2 teilbar ist, muss die letzte Ziffer dieses Fensters gerade sein, also ist \(d_4\) gerade. Weil \(w_3=d_4d_5d_6\) durch 5 teilbar ist, muss seine letzte Ziffer 0 oder 5 sein, also
$$d_6 \in \{0,5\}.$$
Weil \(w_2=d_3d_4d_5\) durch 3 teilbar ist, muss auch die Ziffernsumme durch 3 teilbar sein:
$$d_3 + d_4 + d_5 \equiv 0 \pmod{3}.$$
Diese Beobachtungen sind nicht bloB dekorativ. Wegen der Uberlappung eines Fensters mit dem nachsten wird eine durch eine Primzahl erzwungene Wahl sofort in weitere Bedingungen hineingetragen. Deshalb bleiben am Ende nur sehr wenige zulassige Zahlen ubrig.
Das in den Implementierungen verwendete Positivbeispiel ist
$$1406357289.$$
Die sieben Fenster lauten
$$406,\ 063,\ 635,\ 357,\ 572,\ 728,\ 289.$$
Prüft man sie der Reihe nach gegen \(2,3,5,7,11,13,17\), so erhalt man
$$406 \equiv 0 \pmod{2},\quad 63 \equiv 0 \pmod{3},\quad 635 \equiv 0 \pmod{5},$$
$$357 \equiv 0 \pmod{7},\quad 572 \equiv 0 \pmod{11},\quad 728 \equiv 0 \pmod{13},\quad 289 \equiv 0 \pmod{17}.$$
Der Block \(063\) ist hier vollig legitim: positionsbezogen ist er das Fenster aus den Stellen 3 bis 5, numerisch ist sein Wert 63. Genau so interpretiert die Implementierung die Teilstrings.
Eine Rekursion ist nicht notig, weil jeder Kandidat unabhangig von allen anderen gepruft werden kann. Es gibt insgesamt
$$10! = 3{,}628{,}800$$
Permutationen der zehn Ziffern. Die Implementierung testet einfach jede davon, verwirft Anordnungen mit fuhrender Null und wendet dann die sieben Fensterprufungen an. Selbst im schlechtesten Fall sind das nur \(7 \cdot 10!\) Modulo-Tests und damit eine gut beherrschbare Rechenarbeit.
Die C++-, Python- und Java-Implementierungen folgen demselben Grundschema: alle Anordnungen der Ziffern 0 bis 9 erzeugen, die Teilbarkeitsbedingung fur die sieben Teilstrings prufen und den numerischen Wert jeder gultigen Anordnung zu einer Summe addieren.
Die kompilierten Implementierungen starten bei der sortierten Ziffernfolge 0123456789 und gehen sie lexikographisch durch. Die Python-Implementierung verwendet den Standard-Permutationsiterator fur dieselben zehn Ziffern. In allen drei Sprachen ist damit automatisch sichergestellt, dass jede Ziffer genau einmal vorkommt.
Fur jeden Kandidaten wird zuerst gepruft, ob die erste Ziffer 0 ist. Falls ja, wird er sofort verworfen. Andernfalls werden die sieben Werte \(w_1,\dots,w_7\) direkt aus benachbarten Ziffern aufgebaut und gegen die feste Primliste \((2,3,5,7,11,13,17)\) getestet. Nur wenn alle sieben Kongruenzen stimmen, gilt die Zahl als Treffer.
Besteht ein Kandidat alle Tests, wird der volle 10-stellige Wert in eine Ganzzahl umgewandelt und zur laufenden Summe addiert. Vor der eigentlichen Vollsuche werden auBerdem kleine Kontrolltests ausgefuhrt: Das bekannte Beispiel \(1406357289\) muss akzeptiert werden, wahrend ein offensichtliches Gegenbeispiel wie \(1234567890\) abgelehnt werden muss. Damit wird uberpruft, dass die Fenster und Primzahlen an den richtigen Positionen verwendet werden.
Die Laufzeit ist \(O(10!)\), weil alle \(10!\) Permutationen besucht werden. Konkret sind das 3.628.800 Kandidaten, und jeder Kandidat verursacht nur konstanten Aufwand: einen Test auf fuhrende Null sowie im schlimmsten Fall sieben 3-stellige Konstruktionen und sieben Modulo-Operationen.
Der Zusatzspeicher ist \(O(1)\) abgesehen vom aktuellen Kandidaten und der laufenden Summe. C++ und Java verandern einen kleinen Ziffernpuffer direkt im Speicher, wahrend Python die Kandidaten lazily vom Permutationsiterator erhalt. Keine der Implementierungen speichert also den gesamten Suchraum.
Aranan sayilar, \(d_1d_2\cdots d_{10}\) bicimindeki 10 basamakli pandijital sayilardir; 0'dan 9'a kadar her rakam tam bir kez kullanilir ve \(d_1 \neq 0\) olmalidir. Ozel kosul, 2. basamaktan 8. basamaga kadar baslayan yedi adet ortusen 3 basamakli pencere uzerindedir.
Eger asagidaki tanimlari yaparsak
$$w_i = 100d_{i+1} + 10d_{i+2} + d_{i+3}\qquad (1 \le i \le 7)$$
ve
$$(p_1,p_2,\dots,p_7) = (2,3,5,7,11,13,17)$$
tanimlarini yaparsak gereken kosul
$$w_i \equiv 0 \pmod{p_i}\qquad \text{tum } i=1,2,\dots,7 \text{ icin}$$
olur. Gorev, bu yedi kosulu ayni anda saglayan tum pandijital sayilarin toplamini bulmaktir.
Bu problem, pandijital dizilimler uzerinde calisan sonlu bir kisit filtresidir. Esas matematiksel nesne bir ozyineleme degil; yedi kayar pencerenin yapisi ve bu pencerelere bagli bolunebilme kosullaridir.
Pencereler sunlardir:
$$d_2d_3d_4,\ d_3d_4d_5,\ d_4d_5d_6,\ d_5d_6d_7,\ d_6d_7d_8,\ d_7d_8d_9,\ d_8d_9d_{10}.$$
Her yeni pencere bir oncekiyle iki rakam paylasir. Bu nedenle sayinin orta kisimlarinda verilen tek bir karar birden fazla testi ayni anda etkiler. Ornegin \(d_6\), 5, 7 ve 11 ile kontrol edilen pencerelerde yer alir; \(d_8\) ise 11, 13 ve 17 ile test edilen pencerelerde gorunur. Problemin kilit fikri tam olarak budur: kosullar yereldir ama birbirine zincir gibi baglanmistir.
Bazi kisitlar tam sayiyi gormeden bile cikartilabilir. \(w_1=d_2d_3d_4\) sayisi 2'ye bolunebildigi icin bu pencerenin son rakami cift olmalidir; dolayisiyla \(d_4\) cifttir. \(w_3=d_4d_5d_6\) sayisi 5'e bolunebildigi icin son rakam 0 ya da 5 olmalidir; yani
$$d_6 \in \{0,5\}.$$
\(w_2=d_3d_4d_5\) sayisinin 3'e bolunebilmesi icin rakamlar toplami da 3'e bolunmelidir:
$$d_3 + d_4 + d_5 \equiv 0 \pmod{3}.$$
Bu gozlemler yalnizca ek bilgi degildir. Pencereler ortustugu icin bir asaldan gelen zorunluluk hemen sonraki pencerelere tasinir. Bu da gecerli sayilarin neden son derece seyrek oldugunu aciklar.
Uygulamalarda dogrulama icin kullanilan pozitif ornek
$$1406357289$$
sayisidir. Bunun yedi penceresi
$$406,\ 063,\ 635,\ 357,\ 572,\ 728,\ 289$$
olur. Bunlari sirasiyla \(2,3,5,7,11,13,17\) ile test edersek
$$406 \equiv 0 \pmod{2},\quad 63 \equiv 0 \pmod{3},\quad 635 \equiv 0 \pmod{5},$$
$$357 \equiv 0 \pmod{7},\quad 572 \equiv 0 \pmod{11},\quad 728 \equiv 0 \pmod{13},\quad 289 \equiv 0 \pmod{17}$$
elde edilir. Buradaki \(063\) blogu tamamen gecerlidir; bu, 3. ile 5. konumlar arasindaki rakamlardan olusan pencerenin sayisal degeridir ve 63'e esit oldugu icin 3'e tam bolunur. Kod da tam olarak bu yorumu kullanir.
Her aday birbirinden bagimsiz test edilebildigi icin bir ozyineleme ya da karmaşik bir dinamik program gerekmiyor. On rakamin toplam
$$10! = 3{,}628{,}800$$
adet permutasyonu vardir. Uygulama bunlarin hepsini dener, basta sifir olanlari 10 basamakli olmadiklari icin eler ve kalanlarda yedi pencere testini uygular. En kotu durumda bile yalnizca \(7 \cdot 10!\) adet mod alma islemi gerekir.
C++, Python ve Java uygulamalari ayni yuksek seviyeli yontemi izler: 0'dan 9'a kadar rakamlarin butun dizilislerini uret, alt dize bolunebilme ozelligini kontrol et ve gecerli olan her 10 basamakli sayiyi toplama ekle.
Derlenen uygulamalar sirali rakam dizisi 0123456789 ile baslar ve dizilimleri leksikografik sirayla gezer. Python uygulamasi ise ayni on rakam icin standart permutasyon uretecini kullanir. Uretici zaten permutasyon verdigi icin rakamlarin benzersizligi otomatik olarak saglanir.
Her aday icin once ilk rakamin sifir olup olmadigina bakilir. Sifirsa aday hemen reddedilir. Degilse yedi pencere degeri \(w_1,\dots,w_7\), komsu rakamlardan dogrudan kurulur ve sabit asal listesi \((2,3,5,7,11,13,17)\) ile tek tek test edilir. Yalnizca yedi kosulun tamamini saglayan aday kabul edilir.
Bir aday tum testleri gecerse, tum 10 basamakli degeri tam sayiya cevrilir ve calisan toplama eklenir. Tam tarama baslamadan once kucuk mantik kontrolleri de yapilir: bilinen gecerli ornek \(1406357289\) kabul edilmelidir; acikca yanlis bir ornek olan \(1234567890\) ise reddedilmelidir. Bu kontroller pencere konumlarinin ve asal listesinin dogru yerlere baglandigini gosterir.
Zaman karmasikligi \(O(10!)\)'dir cunku tum \(10!\) permutasyonlar gezilir. Daha somut olarak 3.628.800 aday incelenir ve her aday icin sabit maliyet vardir: bir basta sifir kontrolu, en kotu durumda yedi adet 3 basamakli sayi kurma ve yedi adet mod alma.
Ek bellek kullanimı, mevcut aday ve calisan toplam disinda \(O(1)\)'dir. C++ ve Java surumleri kucuk bir rakam tamponunu yerinde degistirir; Python ise adaylari permutasyon uretecinden tek tek alir. Bu nedenle hicbiri tum arama uzayini bellekte tutmaz.
Buscamos numeros pandigitales de 10 cifras \(d_1d_2\cdots d_{10}\) en los que cada digito de 0 a 9 aparece exactamente una vez y ademas \(d_1 \neq 0\). La condicion especial recae sobre siete ventanas superpuestas de tres cifras que empiezan en las posiciones 2 hasta 8.
Si definimos
$$w_i = 100d_{i+1} + 10d_{i+2} + d_{i+3}\qquad (1 \le i \le 7)$$
y
$$(p_1,p_2,\dots,p_7) = (2,3,5,7,11,13,17),$$
la propiedad pedida es
$$w_i \equiv 0 \pmod{p_i}\qquad \text{para todo } i=1,2,\dots,7.$$
La tarea consiste en sumar todos los numeros pandigitales que satisfacen simultaneamente esas siete congruencias.
El problema es un filtro finito sobre el conjunto de todas las disposiciones pandigitales. La idea matematica central no es una recurrencia, sino la estructura de las siete ventanas deslizantes y las reglas de divisibilidad asociadas a cada una.
Las ventanas son
$$d_2d_3d_4,\ d_3d_4d_5,\ d_4d_5d_6,\ d_5d_6d_7,\ d_6d_7d_8,\ d_7d_8d_9,\ d_8d_9d_{10}.$$
Cada ventana comparte dos cifras con la siguiente. Por eso una decision en la zona central del numero afecta varias pruebas a la vez. Por ejemplo, \(d_6\) participa en las ventanas comprobadas con 5, 7 y 11, mientras que \(d_8\) aparece en las comprobadas con 11, 13 y 17. Ese encadenamiento es el objeto matematico importante del problema: las condiciones son locales, pero estan enlazadas.
Se pueden obtener varias restricciones antes de analizar un candidato completo. Como \(w_1=d_2d_3d_4\) es divisible por 2, la ultima cifra de esa ventana debe ser par, asi que \(d_4\) es par. Como \(w_3=d_4d_5d_6\) es divisible por 5, su ultima cifra debe ser 0 o 5; por tanto
$$d_6 \in \{0,5\}.$$
Ademas, \(w_2=d_3d_4d_5\) es divisible por 3 si y solo si la suma de sus cifras tambien lo es, de modo que
$$d_3 + d_4 + d_5 \equiv 0 \pmod{3}.$$
Estas observaciones no son simples adornos. Debido al solapamiento de las ventanas, una condicion forzada por un primo se propaga inmediatamente a las comprobaciones vecinas. Esa es la razon de que las soluciones validas sean tan escasas.
El ejemplo positivo usado por las implementaciones es
$$1406357289.$$
Sus siete ventanas son
$$406,\ 063,\ 635,\ 357,\ 572,\ 728,\ 289.$$
Si se comparan en orden con \(2,3,5,7,11,13,17\), se obtiene
$$406 \equiv 0 \pmod{2},\quad 63 \equiv 0 \pmod{3},\quad 635 \equiv 0 \pmod{5},$$
$$357 \equiv 0 \pmod{7},\quad 572 \equiv 0 \pmod{11},\quad 728 \equiv 0 \pmod{13},\quad 289 \equiv 0 \pmod{17}.$$
El bloque \(063\) es totalmente valido aqui: representa las cifras de las posiciones 3 a 5 y su valor numerico es 63. El predicado de la implementacion trabaja exactamente con esa interpretacion posicional.
No hace falta una recurrencia porque cada candidato se verifica de forma independiente. Existen exactamente
$$10! = 3{,}628{,}800$$
permutaciones de las diez cifras. La implementacion recorre todas, descarta las que empiezan por cero porque no son numeros de 10 cifras, y despues aplica la prueba de las siete ventanas. Incluso en el peor caso solo hay \(7 \cdot 10!\) operaciones modulares, una cantidad perfectamente manejable.
Las implementaciones en C++, Python y Java siguen el mismo esquema general: enumerar todas las disposiciones de las cifras 0 a 9, comprobar la propiedad de divisibilidad sobre las subcadenas y sumar el valor numerico de cada disposicion valida.
Las versiones compiladas parten de la secuencia ordenada 0123456789 y avanzan por las disposiciones en orden lexicografico. La version de Python pide todas las permutaciones al iterador estandar del lenguaje. En todos los casos, la unicidad de las cifras queda garantizada por la propia generacion de permutaciones.
Para cada candidato se comprueba primero si la primera cifra es cero. Si lo es, el candidato se rechaza sin hacer mas trabajo. En caso contrario, se construyen los siete valores \(w_1,\dots,w_7\) a partir de cifras consecutivas y se contrastan con la lista fija de primos \((2,3,5,7,11,13,17)\). Solo si las siete congruencias son ciertas el numero se considera valido.
Cuando un candidato supera todas las pruebas, el numero completo de 10 cifras se convierte a entero y se anade al acumulado. Antes del recorrido total, las implementaciones tambien ejecutan comprobaciones pequenas: el ejemplo conocido \(1406357289\) debe aceptarse, mientras que un contraejemplo evidente como \(1234567890\) debe rechazarse. Eso confirma que las posiciones de las ventanas y el orden de los primos son correctos.
El tiempo de ejecucion es \(O(10!)\) porque se visitan las \(10!\) permutaciones posibles. En terminos concretos, se examinan 3.628.800 candidatos y cada uno requiere trabajo constante: una prueba de cero inicial y, en el peor caso, siete construcciones de numeros de tres cifras junto con siete reducciones modulares.
La memoria extra es \(O(1)\) aparte del candidato actual y la suma acumulada. C++ y Java modifican en sitio un pequeno contenedor de cifras, mientras que Python recibe los candidatos de manera perezosa desde el iterador de permutaciones. Ninguna implementacion almacena todo el espacio de busqueda.
题目要求寻找所有 10 位的 0 到 9 全数字数 \(d_1d_2\cdots d_{10}\)。这里“全数字”表示 0 到 9 每个数字恰好使用一次，而且 \(d_1 \neq 0\)，否则它就不是一个真正的 10 位数。特殊条件落在从第 2 位到第 8 位开始的七个长度为 3 的重叠窗口上。
若定义
$$w_i = 100d_{i+1} + 10d_{i+2} + d_{i+3}\qquad (1 \le i \le 7)$$
以及
$$(p_1,p_2,\dots,p_7) = (2,3,5,7,11,13,17),$$
那么题目的要求就是
$$w_i \equiv 0 \pmod{p_i}\qquad \text{对每个 } i=1,2,\dots,7 \text{ 都成立。}$$
最终目标是把所有同时满足这七个同余条件的全数字数加总起来。
这道题本质上是在有限候选集合上做约束筛选。核心数学对象不是递推式，也不是生成函数，而是七个滑动三位窗口之间的重叠结构，以及每个窗口对应的整除条件。
这七个窗口依次是
$$d_2d_3d_4,\ d_3d_4d_5,\ d_4d_5d_6,\ d_5d_6d_7,\ d_6d_7d_8,\ d_7d_8d_9,\ d_8d_9d_{10}.$$
相邻两个窗口会共享两位数字，因此某一位数字的选择会同时影响多个素数条件。例如 \(d_6\) 同时出现在对 5、7、11 的检查中，\(d_8\) 同时出现在对 11、13、17 的检查中。正因为这些窗口不是彼此独立的，题目才会形成一条连续传播的约束链，而不是七个互不相关的小测试。
在没有枚举完整候选之前，就已经可以得到一些强约束。因为 \(w_1=d_2d_3d_4\) 必须被 2 整除，所以这个窗口的末位必须是偶数，于是 \(d_4\) 一定是偶数。因为 \(w_3=d_4d_5d_6\) 必须被 5 整除，所以末位只能是 0 或 5，也就是
$$d_6 \in \{0,5\}.$$
再由于 \(w_2=d_3d_4d_5\) 必须被 3 整除，其数位和也必须被 3 整除，因此
$$d_3 + d_4 + d_5 \equiv 0 \pmod{3}.$$
这些结论并不是可有可无的附带观察。由于窗口重叠，一个素数给出的限制会立刻影响到后续窗口，所以真正满足全部条件的数字会极少。
实现中用来做正向校验的已知样例是
$$1406357289.$$
它对应的七个窗口是
$$406,\ 063,\ 635,\ 357,\ 572,\ 728,\ 289.$$
按照题目给定的素数顺序 \(2,3,5,7,11,13,17\) 逐一检查，就得到
$$406 \equiv 0 \pmod{2},\quad 63 \equiv 0 \pmod{3},\quad 635 \equiv 0 \pmod{5},$$
$$357 \equiv 0 \pmod{7},\quad 572 \equiv 0 \pmod{11},\quad 728 \equiv 0 \pmod{13},\quad 289 \equiv 0 \pmod{17}.$$
其中 \(063\) 这一块尤其值得说明。它表示第 3 位到第 5 位形成的窗口，数值上等于 63，因此完全可以通过对 3 的整除检查。也就是说，窗口是按位置截取后再解释成整数，而不是要求它在通常十进制写法中不能有前导零。
因为每个候选都可以独立判断，所以这里不需要递推或动态规划。十个数字的全排列一共只有
$$10! = 3{,}628{,}800$$
种。实现直接遍历这些排列，先排除首位为 0 的情况，然后对其余候选执行七次窗口检查。即使按最坏情况估计，也不过是 \(7 \cdot 10!\) 次模运算，规模完全可控。
C++、Python 和 Java 三个实现采用的是同一个高层思路：枚举数字 0 到 9 的所有排列，测试子串整除性质，把通过测试的 10 位数累加到总和里。
两个编译型实现从排好序的数字序列 0123456789 出发，按字典序逐个访问排列。Python 实现则使用语言自带的排列迭代器惰性地产生所有排列。由于候选本身就是排列，所以“每个数字只出现一次”这一要求天然满足。
对每个候选，程序首先检查首位是否为 0；若是，则立刻拒绝。否则就从相邻数字中直接构造出 \(w_1,\dots,w_7\) 这七个三位数，并按固定素数表 \((2,3,5,7,11,13,17)\) 依次做模检查。只有全部七项都通过，候选才被视为有效。
一旦某个候选通过所有测试，程序就把完整的 10 位值转成整数并加入运行总和。在开始完整枚举之前，实现还会做两项小型校验：已知有效的样例 \(1406357289\) 必须通过，而明显无效的 \(1234567890\) 必须失败。这样可以确认窗口位置和素数顺序都没有写错。
时间复杂度是 \(O(10!)\)，因为程序访问了全部 \(10!\) 个排列。更具体地说，一共检查 3,628,800 个候选，而每个候选只需要常数时间：一次首位零判断，以及最坏情况下七次三位数构造和七次取模运算。
额外空间复杂度为 \(O(1)\)，除了当前候选和累计和之外不再需要按搜索规模增长的存储。C++ 与 Java 在一个很小的数字容器上原地推进排列，Python 则从迭代器中逐个接收候选，因此三种实现都不会把整个搜索空间存入内存。
Нужно найти все 10-значные панцифровые числа \(d_1d_2\cdots d_{10}\), в которых каждая цифра от 0 до 9 используется ровно один раз и при этом \(d_1 \neq 0\). Особое условие задается на семи перекрывающихся трехзначных окнах, начинающихся со 2-й по 8-ю позиции.
Если определить
$$w_i = 100d_{i+1} + 10d_{i+2} + d_{i+3}\qquad (1 \le i \le 7)$$
и
$$(p_1,p_2,\dots,p_7) = (2,3,5,7,11,13,17),$$
то требуемое свойство имеет вид
$$w_i \equiv 0 \pmod{p_i}\qquad \text{для каждого } i=1,2,\dots,7.$$
Нужно просуммировать все панцифровые числа, для которых выполняются все семь сравнений одновременно.
Эта задача представляет собой конечную фильтрацию по множеству панцифровых перестановок. Главная математика здесь связана не с рекуррентной формулой, а со структурой семи скользящих окон и делимостью каждого окна на свой простой делитель.
Рассматриваются окна
$$d_2d_3d_4,\ d_3d_4d_5,\ d_4d_5d_6,\ d_5d_6d_7,\ d_6d_7d_8,\ d_7d_8d_9,\ d_8d_9d_{10}.$$
Каждое следующее окно наследует две цифры от предыдущего. Поэтому выбор одной цифры в середине числа влияет сразу на несколько проверок. Например, \(d_6\) участвует в окнах, которые проверяются на делимость на 5, 7 и 11, а \(d_8\) появляется в окнах для 11, 13 и 17. Именно эта связность делает условие жестким: локальные проверки сшиваются в единую цепочку ограничений.
Некоторые ограничения можно выписать заранее. Так как \(w_1=d_2d_3d_4\) делится на 2, последняя цифра этого окна должна быть четной, значит \(d_4\) обязательно четная. Так как \(w_3=d_4d_5d_6\) делится на 5, его последняя цифра должна быть 0 или 5, то есть
$$d_6 \in \{0,5\}.$$
Кроме того, \(w_2=d_3d_4d_5\) делится на 3 тогда и только тогда, когда сумма его цифр делится на 3, поэтому
$$d_3 + d_4 + d_5 \equiv 0 \pmod{3}.$$
Эти выводы важны не сами по себе, а потому, что они сразу распространяются по соседним окнам. Ограничение, навязанное одной простой делимостью, автоматически влияет на следующие проверки. Поэтому допустимых чисел остается очень мало.
В реализациях для контрольной проверки используется известный правильный пример
$$1406357289.$$
Его семь окон равны
$$406,\ 063,\ 635,\ 357,\ 572,\ 728,\ 289.$$
Если проверять их последовательно на делимость на \(2,3,5,7,11,13,17\), то получится
$$406 \equiv 0 \pmod{2},\quad 63 \equiv 0 \pmod{3},\quad 635 \equiv 0 \pmod{5},$$
$$357 \equiv 0 \pmod{7},\quad 572 \equiv 0 \pmod{11},\quad 728 \equiv 0 \pmod{13},\quad 289 \equiv 0 \pmod{17}.$$
Блок \(063\) здесь полностью допустим: это просто число, составленное из цифр на позициях 3, 4 и 5, и его значение равно 63. Именно так реализация и интерпретирует подстроки: сначала берутся нужные позиции, потом из них собирается целое число.
Рекурсия не требуется, потому что каждый кандидат проверяется независимо. Всего имеется
$$10! = 3{,}628{,}800$$
перестановок десяти цифр. Реализация проходит по всем этим перестановкам, отбрасывает варианты с ведущим нулем и для остальных выполняет семь проверок окон. Даже в худшем случае это только \(7 \cdot 10!\) операций взятия по модулю, что вполне подъемно.
Реализации на C++, Python и Java используют один и тот же общий алгоритм: перечислить все перестановки цифр от 0 до 9, проверить свойство подстрочной делимости и прибавить числовое значение каждой подходящей перестановки к накопленной сумме.
Компилируемые версии стартуют с упорядоченной последовательности 0123456789 и идут по перестановкам в лексикографическом порядке. Python-версия получает их от стандартного итератора перестановок. Во всех трех случаях уникальность цифр обеспечивается самим способом генерации.
Для каждого кандидата сначала проверяется, не равна ли первая цифра нулю. Если равна, кандидат сразу отбрасывается. Иначе из соседних цифр строятся семь значений \(w_1,\dots,w_7\), после чего они по порядку проверяются на делимость на фиксированный список простых чисел \((2,3,5,7,11,13,17)\). Кандидат принимается только тогда, когда выполнены все семь условий.
Если кандидат проходит все тесты, полное 10-значное число переводится в целый тип и добавляется к текущей сумме. Перед основным полным перебором реализации выполняют и маленькие проверки корректности: известный пример \(1406357289\) обязан проходить, а очевидно неверный \(1234567890\) обязан проваливаться. Это подтверждает, что окна и список простых чисел привязаны к правильным позициям.
Временная сложность равна \(O(10!)\), потому что рассматриваются все \(10!\) перестановок. В более конкретных терминах это 3 628 800 кандидатов, и для каждого нужен лишь постоянный объем работы: одна проверка на ведущий ноль и, в худшем случае, семь построений трехзначного числа и семь операций по модулю.
Дополнительная память имеет порядок \(O(1)\), если не считать текущий кандидат и накопленную сумму. В C++ и Java небольшой контейнер цифр изменяется на месте, а в Python кандидаты поступают лениво из итератора. Полный поисковый простор в памяти не хранится.
المطلوب هو إيجاد جميع الأعداد البانديجيتال ذات العشر خانات \(d_1d_2\cdots d_{10}\)، حيث تُستخدم الأرقام من 0 إلى 9 مرة واحدة فقط، مع الشرط \(d_1 \neq 0\) حتى يكون العدد مكوَّنًا فعلاً من عشر خانات. الخاصية المميزة تقع على سبع نوافذ متداخلة طول كل منها ثلاث خانات وتبدأ من الموضع الثاني حتى الموضع الثامن.
إذا عرَّفنا
$$w_i = 100d_{i+1} + 10d_{i+2} + d_{i+3}\qquad (1 \le i \le 7)$$
وعرَّفنا أيضًا
$$(p_1,p_2,\dots,p_7) = (2,3,5,7,11,13,17),$$
فإن الشرط المطلوب هو
$$w_i \equiv 0 \pmod{p_i}\qquad (i=1,2,\dots,7).$$
والمهمة النهائية هي جمع كل الأعداد البانديجيتال التي تحقق هذه العلاقات السبعة في وقت واحد.
هذه المسألة هي عملية ترشيح منتهية على مجموعة جميع الترتيبات البانديجيتال الممكنة. الفكرة الرياضية الأساسية ليست علاقة عودية، بل بنية النوافذ السبعة المنزلقة وطريقة انتقال قيود القسمة من نافذة إلى النافذة التالية بسبب التداخل.
النوافذ هي
$$d_2d_3d_4,\ d_3d_4d_5,\ d_4d_5d_6,\ d_5d_6d_7,\ d_6d_7d_8,\ d_7d_8d_9,\ d_8d_9d_{10}.$$
كل نافذة تشترك مع التالية في رقمين، ولذلك فإن اختيار رقم واحد في وسط العدد يؤثر في عدة اختبارات دفعة واحدة. على سبيل المثال، يظهر \(d_6\) في النوافذ التي تُفحص مع 5 و7 و11، بينما يظهر \(d_8\) في النوافذ التي تُفحص مع 11 و13 و17. هذه السلسلة من الاعتماد المتبادل هي الشيء الرياضي المهم في المسألة: القيود محلية، لكنها ليست مستقلة.
يمكن استخراج بعض القيود قبل فحص أي مرشح كامل. بما أن \(w_1=d_2d_3d_4\) قابل للقسمة على 2، فلا بد أن تكون آخر خانة فيه زوجية، أي إن \(d_4\) زوجي. وبما أن \(w_3=d_4d_5d_6\) قابل للقسمة على 5، فلا بد أن تكون خانته الأخيرة 0 أو 5، أي
$$d_6 \in \{0,5\}.$$
ولأن \(w_2=d_3d_4d_5\) قابل للقسمة على 3، فلا بد أن يكون مجموع أرقامه قابلًا للقسمة على 3 أيضًا، وبالتالي
$$d_3 + d_4 + d_5 \equiv 0 \pmod{3}.$$
هذه ليست ملاحظات تجميلية، بل قيود تنتشر مباشرة عبر النوافذ المتداخلة. فالشرط الذي يفرضه عدد أولي واحد يضيق المجال فورًا في الشروط المجاورة، ولهذا تصبح الأعداد الصحيحة المقبولة نادرة جدًا.
المثال الصحيح الذي تستخدمه التطبيقات كفحص مرجعي هو
$$1406357289.$$
ونوافذه السبعة هي
$$406,\ 063,\ 635,\ 357,\ 572,\ 728,\ 289.$$
وعند فحصها بالترتيب مع \(2,3,5,7,11,13,17\) نحصل على
$$406 \equiv 0 \pmod{2},\quad 63 \equiv 0 \pmod{3},\quad 635 \equiv 0 \pmod{5},$$
$$357 \equiv 0 \pmod{7},\quad 572 \equiv 0 \pmod{11},\quad 728 \equiv 0 \pmod{13},\quad 289 \equiv 0 \pmod{17}.$$
والكتلة \(063\) صالحة تمامًا هنا؛ فهي تمثل الخانات من الموضع الثالث إلى الموضع الخامس، وقيمتها العددية هي 63. هذا يوضح أن الاختبار يعمل على نوافذ موضعية ثم يحولها إلى أعداد صحيحة، لا على سلاسل عشرية مستقلة يمنع فيها الصفر البادئ.
لا نحتاج إلى علاقة عودية لأن كل مرشح يمكن اختباره مستقلًا عن غيره. عدد ترتيبات الأرقام العشرة يساوي
$$10! = 3{,}628{,}800$$
فقط. لذلك تقوم التطبيقات بزيارة كل ترتيب، وتستبعد ما يبدأ بصفر لأنه ليس عددًا من عشر خانات، ثم تطبق اختبارات النوافذ السبعة على الباقي. وحتى في أسوأ الأحوال لا نحتاج إلا إلى \(7 \cdot 10!\) عملية باقية قسمة.
تتبع تطبيقات C++ وPython وJava الفكرة العامة نفسها: توليد جميع ترتيبات الأرقام من 0 إلى 9، وفحص خاصية القسمة على السلاسل الفرعية، ثم جمع القيمة العددية لكل ترتيب صحيح.
تبدأ النسختان المترجمتان من السلسلة المرتبة 0123456789 وتنتقلان عبر جميع الترتيبات بترتيب معجمي. أما نسخة Python فتستخدم مولد التبديلات القياسي في اللغة. وفي الحالات كلها تكون خاصية "كل رقم يظهر مرة واحدة" مضمونة تلقائيًا لأن ما يُنتج هو تبديلات فعلية.
لكل مرشح، تفحص التطبيقات أولًا ما إذا كانت الخانة الأولى صفرًا. إذا كان الأمر كذلك يُرفض المرشح فورًا. وإلا تُبنى القيم \(w_1,\dots,w_7\) مباشرة من الخانات المتجاورة، ثم تُفحص على القائمة الثابتة \((2,3,5,7,11,13,17)\) بالترتيب. لا يُقبل المرشح إلا إذا نجح في الاختبارات السبعة كلها.
إذا اجتاز المرشح كل الاختبارات، تُحوَّل القيمة الكاملة ذات العشر خانات إلى عدد صحيح وتُضاف إلى المجموع الجاري. وقبل بدء المسح الكامل، تُجرى أيضًا فحوص صغيرة للتأكد من صحة المنطق: المثال المعروف \(1406357289\) يجب أن يمر، بينما المثال الواضح \(1234567890\) يجب أن يفشل. هذا يؤكد أن مواقع النوافذ وترتيب الأعداد الأولية مستخدمة كما ينبغي.
زمن التنفيذ هو \(O(10!)\) لأن التطبيق يزور جميع التبديلات وعددها \(10!\). وبصورة أكثر تحديدًا، يجري فحص 3,628,800 مرشح، ولكل مرشح كلفة ثابتة فقط: اختبار واحد للصفر البادئ، ثم في أسوأ حالة سبع عمليات بناء لأعداد من ثلاث خانات وسبع عمليات باقي قسمة.
أما الذاكرة الإضافية فهي \(O(1)\) باستثناء المرشح الحالي والمجموع الجاري. في C++ وJava يتم تعديل حاوية صغيرة من الخانات في المكان نفسه، وفي Python تصل الترتيبات واحدًا واحدًا من المولد. لذلك لا يحتفظ أي تنفيذ بكل فضاء البحث في الذاكرة.