We seek the smallest positive integer \(x\) such that the decimal digits of \(x\), \(2x\), \(3x\), \(4x\), \(5x\), and \(6x\) are exactly the same up to reordering. In other words, each multiple from \(2x\) through \(6x\) must be a digit permutation of the original number. The smallest such value is \(142857\), but the point of the problem is to justify why a direct search is so small and why a simple exact test is enough.
The three implementations all rely on one exact invariant: two integers satisfy the condition precisely when their decimal digits have the same multiset. Everything else is a consequence of that observation.
Define the digit signature \(\sigma(n)\) to be the string obtained by sorting the decimal digits of \(n\) into nondecreasing order. Then
$$x \text{ and } y \text{ are digit permutations } \Longleftrightarrow \sigma(x)=\sigma(y).$$
So Problem 52 is equivalent to the system
$$\sigma(x)=\sigma(2x)=\sigma(3x)=\sigma(4x)=\sigma(5x)=\sigma(6x).$$
This formulation is stronger than checking only digit sums or congruences: it remembers the full multiplicity of every decimal digit, including zeros.
If \(x\) has \(d\) decimal digits, then every permutation of its digits also has \(d\) digits. In particular, \(6x\) must still have \(d\) digits. Therefore any \(d\)-digit candidate must satisfy
$$10^{d-1} \le x \le \left\lfloor \frac{10^d-1}{6} \right\rfloor.$$
This is the main structural restriction of the problem. It says that only the first sixth of each \(d\)-digit block can possibly work. For a fixed digit length, the number of candidates is
$$\left\lfloor \frac{10^d-1}{6} \right\rfloor - 10^{d-1} + 1.$$
For \(d=6\), this gives the interval \(100000 \le x \le 166666\), which contains only \(66667\) candidates. The actual implementations do not hard-code this bound, but it explains why the first solution appears in a very narrow region.
Permuting decimal digits preserves their sum, so if \(\sigma(kx)=\sigma(x)\), then \(kx\) and \(x\) have the same digit sum and hence the same residue modulo \(9\). Taking \(k=2\) gives
$$2x \equiv x \pmod 9,$$
so every valid solution must satisfy
$$x \equiv 0 \pmod 9.$$
This is only a necessary condition, not a full characterization. Many multiples of \(9\) still fail the signature test, so the implementations keep the exact sorted-digit comparison rather than relying on weaker filters.
The checkpoint example used by the implementations is \(125874\), because
$$2 \cdot 125874 = 251748,$$
and both numbers have the same sorted signature \(124578\). That shows the basic idea on a single multiple.
The complete solution is
$$x=142857,$$
for which
$$2x=285714,\quad 3x=428571,\quad 4x=571428,\quad 5x=714285,\quad 6x=857142.$$
Sorting the digits of any of these six numbers always gives the same signature \(124578\). Because the search is performed in increasing order, the first successful candidate is automatically the smallest possible answer.
The C++, Python, and Java implementations all follow the same structure. They start at \(x=1\) and test candidates in increasing order. For each candidate, the implementation sorts the digits of \(x\) once, then compares that signature with the sorted digits of \(2x\), \(3x\), and so on up to the chosen upper multiplier. As soon as one comparison fails, the candidate is rejected immediately and the search moves on.
This means the code uses the exact criterion \(\sigma(kx)=\sigma(x)\) directly. It does not build frequency tables, it does not pre-split the search by digit length, and it does not use congruence pruning. The benefit is simplicity: the code is short, and the early break makes the brute-force search fast enough.
All three implementations also include a small built-in validation step. Before solving the main problem, they verify that \(125874\) and \(251748\) really do have the same sorted digits. There is also an optional command-line setting that replaces the default upper multiplier \(6\) by a user-specified value at least \(2\), so the same routine can search for analogous questions such as matching digits for \(2x\) through \(4x\).
Let \(M\) be the largest multiplier being checked and let \(A\) be the first solution for that choice. The implementations test every candidate from \(1\) through \(A\). If \(D\) is the number of decimal digits of \(A\), then each signature computation sorts at most \(D\) characters, so one comparison costs \(O(D \log D)\). In the worst case, a candidate performs \(M\) such signature computations, giving total time
$$O(A\,M\,D\log D).$$
For the default problem, \(M=6\), \(A=142857\), and \(D=6\), so the workload is tiny in practice. The extra space is \(O(D)\) for the temporary digit strings, or constant with respect to the number of candidates.
Gesucht ist die kleinste positive ganze Zahl \(x\), für die die Dezimalziffern von \(x\), \(2x\), \(3x\), \(4x\), \(5x\) und \(6x\) bis auf ihre Reihenfolge genau übereinstimmen. Jedes dieser Vielfachen soll also eine Ziffernpermutation von \(x\) sein. Der kleinste Wert mit dieser Eigenschaft ist \(142857\), aber mathematisch interessant ist vor allem, warum die Suche so klein bleibt und warum ein sehr einfacher exakter Test genügt.
Alle drei Implementierungen beruhen auf genau einem exakten Invarianzbegriff: Zwei Zahlen erfüllen die Bedingung genau dann, wenn ihre Dezimalziffern dieselbe Multimenge bilden. Daraus folgen die übrigen Aussagen des Problems.
Definiere die Ziffernsignatur \(\sigma(n)\) als die Zeichenfolge, die entsteht, wenn man die Dezimalziffern von \(n\) nicht absteigend sortiert. Dann gilt
$$x \text{ und } y \text{ sind Ziffernpermutationen } \Longleftrightarrow \sigma(x)=\sigma(y).$$
Problem 52 ist also äquivalent zu
$$\sigma(x)=\sigma(2x)=\sigma(3x)=\sigma(4x)=\sigma(5x)=\sigma(6x).$$
Diese Formulierung ist stärker als jede reine Quersummen- oder Kongruenzbedingung, weil sie die genaue Häufigkeit jeder einzelnen Dezimalziffer festhält.
Hat \(x\) genau \(d\) Dezimalstellen, dann besitzt jede Permutation seiner Ziffern ebenfalls \(d\) Stellen. Insbesondere muss also auch \(6x\) noch \(d\)-stellig sein. Für jeden \(d\)-stelligen Kandidaten folgt damit
$$10^{d-1} \le x \le \left\lfloor \frac{10^d-1}{6} \right\rfloor.$$
Das ist die wichtigste strukturelle Einschränkung des Problems: Nur das erste Sechstel eines jeden Stellenblocks kann überhaupt funktionieren. Für feste Stellenzahl ist die Anzahl der Kandidaten gleich
$$\left\lfloor \frac{10^d-1}{6} \right\rfloor - 10^{d-1} + 1.$$
Für \(d=6\) erhält man das Intervall \(100000 \le x \le 166666\), also nur \(66667\) Kandidaten. Die Implementierungen kodieren diese Schranke nicht ausdrücklich, aber sie erklärt, warum die erste Lösung in einem sehr schmalen Bereich liegt.
Eine Ziffernpermutation verändert die Quersumme nicht. Wenn also \(\sigma(kx)=\sigma(x)\) gilt, dann haben \(kx\) und \(x\) dieselbe Quersumme und damit denselben Rest modulo \(9\). Für \(k=2\) ergibt sich
$$2x \equiv x \pmod 9,$$
also muss jede Lösung
$$x \equiv 0 \pmod 9$$
erfüllen. Das ist jedoch nur notwendig, nicht hinreichend. Sehr viele Vielfache von \(9\) scheitern trotzdem am exakten Signaturvergleich, weshalb die Implementierungen direkt die sortierten Ziffern vergleichen.
Das in den Implementierungen eingebaute Prüfbeispiel ist \(125874\), denn
$$2 \cdot 125874 = 251748,$$
und beide Zahlen haben dieselbe sortierte Signatur \(124578\). Das demonstriert die Grundidee für einen einzelnen Multiplikator.
Die vollständige Lösung lautet
$$x=142857,$$
mit
$$2x=285714,\quad 3x=428571,\quad 4x=571428,\quad 5x=714285,\quad 6x=857142.$$
Sortiert man die Ziffern einer beliebigen dieser sechs Zahlen, erhält man stets dieselbe Signatur \(124578\). Da die Suche streng aufsteigend erfolgt, ist der erste Treffer automatisch die kleinste mögliche Lösung.
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Sie starten bei \(x=1\) und testen Kandidaten der Reihe nach. Für jedes \(x\) werden die Ziffern einmal sortiert und anschließend mit den sortierten Ziffern von \(2x\), \(3x\) und so weiter bis zum gewählten oberen Multiplikator verglichen. Sobald ein Vergleich fehlschlägt, wird der Kandidat sofort verworfen.
Der Code benutzt also die exakte Bedingung \(\sigma(kx)=\sigma(x)\) unmittelbar. Er baut keine Häufigkeitstabellen, trennt die Suche nicht explizit nach Stellenzahl auf und verwendet auch keine Kongruenzfilter. Der Vorteil ist die Klarheit: Der Algorithmus bleibt sehr kurz, und der frühe Abbruch macht die Brute-Force-Suche schnell genug.
Alle drei Implementierungen enthalten außerdem einen kleinen eingebauten Test. Vor der eigentlichen Suche wird überprüft, dass \(125874\) und \(251748\) tatsächlich dieselben sortierten Ziffern besitzen. Zusätzlich gibt es eine optionale Kommandozeilen-Einstellung, mit der der Standardwert \(6\) durch einen frei gewählten oberen Multiplikator ab \(2\) ersetzt werden kann.
Sei \(M\) der größte geprüfte Multiplikator und \(A\) die erste Lösung für diese Wahl. Die Implementierungen testen alle Kandidaten von \(1\) bis \(A\). Wenn \(D\) die Stellenzahl von \(A\) ist, dann sortiert jede Signaturberechnung höchstens \(D\) Zeichen; ein Vergleich kostet also \(O(D \log D)\). Im schlechtesten Fall benötigt ein Kandidat \(M\) solcher Signaturen, insgesamt also
$$O(A\,M\,D\log D).$$
Für das Standardproblem gilt \(M=6\), \(A=142857\) und \(D=6\), daher ist die Laufzeit in der Praxis sehr klein. Der zusätzliche Speicherbedarf beträgt \(O(D)\) für die temporären Ziffernfolgen und ist damit konstant in Bezug auf die Anzahl der getesteten Kandidaten.
Aranan sayı, \(x\), \(2x\), \(3x\), \(4x\), \(5x\) ve \(6x\) için aynı ondalık rakamların yalnızca farklı sıralarla ortaya çıktığı en küçük pozitif tam sayıdır. Başka bir deyişle \(2x\) ile \(6x\) arasındaki her kat, \(x\)'in rakamlarının bir permütasyonu olmalıdır. Bu özelliği sağlayan en küçük değer \(142857\)'dir; asıl önemli nokta ise neden bu sonucun çok kısa bir tam aramayla bulunabildiğini anlamaktır.
Üç çözümün de dayandığı temel fikir aynıdır: iki sayı koşulu ancak ve ancak ondalık rakamlarının çokluğu aynıysa sağlar. Kodun yaptığı karşılaştırma tam olarak bu matematiksel nesneyi test eder.
\(\sigma(n)\) ile, \(n\)'in ondalık rakamları küçükten büyüğe sıralandığında elde edilen dizgeyi gösterelim. O zaman
$$x \text{ ve } y \text{ rakam permütasyonudur } \Longleftrightarrow \sigma(x)=\sigma(y).$$
Dolayısıyla Problem 52 şu eşitlikler sistemine indirgenir:
$$\sigma(x)=\sigma(2x)=\sigma(3x)=\sigma(4x)=\sigma(5x)=\sigma(6x).$$
Bu test, yalnızca rakam toplamını ya da modüler bir koşulu kontrol etmekten daha güçlüdür; çünkü her rakamın kaç kez geçtiğini eksiksiz biçimde korur.
Eğer \(x\), \(d\) basamaklıysa, rakamlarının her permütasyonu da \(d\) basamaklıdır. Özellikle \(6x\) de hâlâ \(d\) basamaklı olmak zorundadır. Bu yüzden her \(d\) basamaklı aday için
$$10^{d-1} \le x \le \left\lfloor \frac{10^d-1}{6} \right\rfloor$$
olmalıdır. Bu, problemin en önemli yapısal kısıtıdır. Yani her basamak bloğunun yalnızca ilk altıda birlik kısmı aday olabilir. Sabit \(d\) için aday sayısı
$$\left\lfloor \frac{10^d-1}{6} \right\rfloor - 10^{d-1} + 1$$
şeklindedir. \(d=6\) için aralık \(100000 \le x \le 166666\) olur; toplam yalnızca \(66667\) aday vardır. Uygulamalar bu sınırı açıkça kullanmaz, ama ilk çözümün niçin dar bir bölgede bulunduğunu açıklayan matematik budur.
Rakam permütasyonu rakam toplamını değiştirmez. Bu yüzden \(\sigma(kx)=\sigma(x)\) ise, \(kx\) ile \(x\) aynı rakam toplamına ve dolayısıyla mod \(9\) altında aynı kalana sahiptir. \(k=2\) seçilirse
$$2x \equiv x \pmod 9$$
elde edilir ve buradan her geçerli çözüm için
$$x \equiv 0 \pmod 9$$
çıkar. Ancak bu yalnızca gerekli bir koşuldur. \(9\)'un katı olan pek çok sayı tam imza karşılaştırmasını geçemez; bu yüzden uygulamalar daha zayıf filtreler yerine doğrudan sıralanmış rakamları karşılaştırır.
Uygulamaların kullandığı doğrulama örneği \(125874\)'tür; çünkü
$$2 \cdot 125874 = 251748,$$
ve her iki sayının sıralanmış rakam imzası da \(124578\)'dir. Bu, tek bir kat için temel fikri gösterir.
Tam çözüm ise
$$x=142857$$
olup
$$2x=285714,\quad 3x=428571,\quad 4x=571428,\quad 5x=714285,\quad 6x=857142$$
şeklindedir. Bu altı sayının hepsinin sıralanmış rakamları yine \(124578\) verir. Arama artan sırayla yapıldığı için ilk bulunan uygun aday otomatik olarak en küçük çözümdür.
C++, Python ve Java uygulamalarının akışı aynıdır. Arama \(x=1\) ile başlar ve adaylar artan sırayla denenir. Her aday için önce \(x\)'in rakamları sıralanır; sonra bu imza \(2x\), \(3x\) ve seçilen en büyük kata kadar bütün çarpımların sıralanmış rakamlarıyla karşılaştırılır. İlk uyuşmazlıkta aday hemen elenir.
Dolayısıyla kod doğrudan \(\sigma(kx)=\sigma(x)\) koşulunu uygular. Frekans tablosu kurmaz, aramayı basamak sayısına göre bölmez ve modüler eleme kullanmaz. Bunun ödülü sadeliktir: algoritma çok kısadır ve erken çıkış sayesinde kaba kuvvet yaklaşımı pratikte yeterince hızlıdır.
Üç uygulamada da küçük bir yerleşik kontrol bulunur. Ana problem çözülmeden önce \(125874\) ile \(251748\)'in gerçekten aynı sıralanmış rakamlara sahip olduğu doğrulanır. Ayrıca varsayılan üst çarpan \(6\) yerine, en az \(2\) olacak biçimde başka bir üst sınır seçmeye yarayan isteğe bağlı bir komut satırı ayarı da vardır.
\(M\) kontrol edilen en büyük çarpan, \(A\) ise bu seçim için bulunan ilk çözüm olsun. Uygulamalar \(1\)'den \(A\)'ya kadar bütün adayları dener. \(A\)'nın basamak sayısı \(D\) ise, bir imza hesabı en fazla \(D\) karakteri sıraladığı için tek maliyet \(O(D \log D)\) olur. Bir aday en kötü durumda \(M\) imza hesabı yaptığından toplam çalışma süresi
$$O(A\,M\,D\log D)$$
şeklindedir. Varsayılan problemde \(M=6\), \(A=142857\) ve \(D=6\) olduğundan gerçek çalışma süresi çok küçüktür. Ek bellek, geçici rakam dizgeleri için \(O(D)\) olup aday sayısından bağımsızdır.
Hay que encontrar el entero positivo más pequeño \(x\) tal que los dígitos decimales de \(x\), \(2x\), \(3x\), \(4x\), \(5x\) y \(6x\) sean exactamente los mismos salvo por el orden. Es decir, cada múltiplo entre \(2x\) y \(6x\) debe ser una permutación de los dígitos de \(x\). El menor valor que cumple esto es \(142857\), y el interés matemático del problema está en ver por qué una búsqueda directa, bien planteada, basta.
Las tres implementaciones usan el mismo objeto matemático central: la firma ordenada de los dígitos decimales. Esa firma da una condición exacta, no una aproximación.
Sea \(\sigma(n)\) la cadena que resulta de ordenar de menor a mayor los dígitos decimales de \(n\). Entonces
$$x \text{ e } y \text{ son permutaciones de dígitos } \Longleftrightarrow \sigma(x)=\sigma(y).$$
Por tanto, el problema equivale a exigir
$$\sigma(x)=\sigma(2x)=\sigma(3x)=\sigma(4x)=\sigma(5x)=\sigma(6x).$$
Esta formulación conserva toda la información relevante: no solo la suma de los dígitos, sino también cuántas veces aparece cada cifra, incluidos los ceros.
Si \(x\) tiene \(d\) cifras decimales, cualquier permutación de sus cifras también tiene \(d\) cifras. En particular, \(6x\) debe seguir teniendo \(d\) cifras. Por eso todo candidato de \(d\) cifras debe satisfacer
$$10^{d-1} \le x \le \left\lfloor \frac{10^d-1}{6} \right\rfloor.$$
Esta es la restricción estructural más importante del problema: solo el primer sexto de cada bloque de \(d\) cifras puede funcionar. El número exacto de candidatos en ese bloque es
$$\left\lfloor \frac{10^d-1}{6} \right\rfloor - 10^{d-1} + 1.$$
Cuando \(d=6\), la búsqueda relevante queda reducida al intervalo \(100000 \le x \le 166666\), que contiene solo \(66667\) valores. El código no impone esta cota de forma explícita, pero la cota explica por qué la primera solución aparece pronto.
Una permutación de dígitos no altera la suma de los dígitos. Si \(\sigma(kx)=\sigma(x)\), entonces \(kx\) y \(x\) tienen la misma suma de cifras y, por tanto, son congruentes módulo \(9\). Tomando \(k=2\), obtenemos
$$2x \equiv x \pmod 9,$$
de donde se deduce que toda solución válida debe cumplir
$$x \equiv 0 \pmod 9.$$
Esto solo da una condición necesaria. Muchísimos múltiplos de \(9\) no satisfacen la igualdad exacta de firmas, así que las implementaciones conservan la comparación completa de dígitos ordenados.
El ejemplo de verificación incorporado en las implementaciones es \(125874\), porque
$$2 \cdot 125874 = 251748,$$
y ambos números producen la misma firma ordenada \(124578\). Eso muestra la idea básica con un único múltiplo.
La solución completa es
$$x=142857,$$
ya que
$$2x=285714,\quad 3x=428571,\quad 4x=571428,\quad 5x=714285,\quad 6x=857142.$$
En los seis casos, al ordenar los dígitos se obtiene la misma firma \(124578\). Como la búsqueda recorre los enteros en orden creciente, el primer acierto es automáticamente la solución mínima.
Las versiones en C++, Python y Java siguen exactamente el mismo esquema. Empiezan en \(x=1\) y prueban candidatos crecientes. Para cada candidato calculan una vez la firma ordenada de \(x\) y luego la comparan con las firmas ordenadas de \(2x\), \(3x\) y así sucesivamente hasta el multiplicador máximo elegido. En cuanto una comparación falla, el candidato se descarta sin hacer trabajo extra.
El código aplica directamente el criterio exacto \(\sigma(kx)=\sigma(x)\). No usa tablas de frecuencias, no divide la búsqueda por longitud de cifras y no introduce filtros modulares. La ventaja es la simplicidad, y el corte temprano hace que el barrido completo siga siendo muy rápido.
Las tres implementaciones incluyen también una comprobación interna: antes de resolver el problema principal, verifican que \(125874\) y \(251748\) realmente tienen la misma firma de dígitos. Además, aceptan un ajuste opcional de línea de comandos que sustituye el multiplicador superior por defecto \(6\) por otro valor elegido por el usuario, siempre que sea al menos \(2\).
Sea \(M\) el multiplicador máximo y \(A\) la primera solución para ese valor. Las implementaciones prueban todos los candidatos desde \(1\) hasta \(A\). Si \(D\) es el número de cifras de \(A\), cada firma ordena como mucho \(D\) caracteres, así que una comparación cuesta \(O(D \log D)\). En el peor caso, un candidato necesita \(M\) firmas y el tiempo total es
$$O(A\,M\,D\log D).$$
En el problema original, \(M=6\), \(A=142857\) y \(D=6\), por lo que el tiempo real es muy pequeño. El espacio adicional es \(O(D)\) para las cadenas temporales de dígitos, es decir, constante respecto al número de candidatos examinados.
题目要求找到最小的正整数 \(x\)，使得 \(x,2x,3x,4x,5x,6x\) 这六个数在十进制下恰好由同一组数字组成，只是排列顺序不同。换句话说，\(2x\) 到 \(6x\) 都必须是 \(x\) 的数字重排。满足条件的最小值是 \(142857\)。这个问题的关键不在于结果本身，而在于说明为什么一个非常直接的精确搜索就足够了。
三份实现都围绕同一个核心对象展开：把十进制数字排序后得到的“数字签名”。这个签名不是启发式条件，而是与题意完全等价的判定标准。
记 \(\sigma(n)\) 为把 \(n\) 的十进制数字按非降序排列后得到的字符串。那么
$$x \text{ 与 } y \text{ 的数字互为重排 } \Longleftrightarrow \sigma(x)=\sigma(y).$$
因此，Problem 52 可以直接写成
$$\sigma(x)=\sigma(2x)=\sigma(3x)=\sigma(4x)=\sigma(5x)=\sigma(6x).$$
这个条件比只看数位和或者只看模运算更强，因为它完整保留了每个数字出现的次数，包括数字 \(0\) 的次数。
如果 \(x\) 有 \(d\) 位，那么由这些数字重排得到的任何数也必须仍然有 \(d\) 位。因此 \(6x\) 也必须是 \(d\) 位数。于是每个 \(d\) 位候选都必须满足
$$10^{d-1} \le x \le \left\lfloor \frac{10^d-1}{6} \right\rfloor.$$
这是本题最重要的结构约束。它说明每个 \(d\) 位区间里，只有最前面的六分之一有可能成为答案。该区间内候选数的精确个数是
$$\left\lfloor \frac{10^d-1}{6} \right\rfloor - 10^{d-1} + 1.$$
例如 \(d=6\) 时，只需要关注 \(100000 \le x \le 166666\)，总共 \(66667\) 个候选。实现代码并没有显式利用这个界，但这个界解释了为什么第一个解会出现在很小的范围内。
数字重排不会改变各位数字之和。如果 \(\sigma(kx)=\sigma(x)\)，那么 \(kx\) 与 \(x\) 的数位和相同，因此它们模 \(9\) 同余。取 \(k=2\)，就得到
$$2x \equiv x \pmod 9,$$
于是任何合法解都必须满足
$$x \equiv 0 \pmod 9.$$
不过这只是必要条件，不是充分条件。大量 \(9\) 的倍数仍然无法通过完整的数字签名比较，所以实现里保留了更强也更直接的排序判定。
三份实现都内置了一个小检查：因为
$$2 \cdot 125874 = 251748,$$
而这两个数的排序后签名都等于 \(124578\)，所以它们确实互为数字重排。这个例子只展示了一个倍数的情形。
完整答案是
$$x=142857,$$
并且
$$2x=285714,\quad 3x=428571,\quad 4x=571428,\quad 5x=714285,\quad 6x=857142.$$
把这六个数的数字分别排序，得到的都是同一个签名 \(124578\)。由于搜索按自然数递增顺序进行，所以第一个通过检验的候选值一定就是最小解。
C++、Python 和 Java 版本采用完全相同的控制流程。它们从 \(x=1\) 开始逐个尝试候选值。对于每个候选，先计算一次 \(x\) 的排序后数字签名，再把它与 \(2x\)、\(3x\) 直到所选最大倍数的签名逐个比较。一旦某个倍数不匹配，就立刻终止当前候选的检查并继续下一个整数。
因此，实现实际上是在直接测试 \(\sigma(kx)=\sigma(x)\) 这个精确条件。它们没有建立数字频次数组，没有先按位数切分搜索空间，也没有加入模 \(9\) 之类的弱过滤。这样做的好处是代码非常短，而提前退出已经足以保证速度。
在正式求解之前，三份实现都会先验证 \(125874\) 与 \(251748\) 的排序后数字确实一致。除此之外，它们还接受一个可选的命令行设置，用来把默认的最大倍数 \(6\) 改成用户指定的其他值，只要求该值不小于 \(2\)。这样同一套程序也能研究“\(2x\) 到 \(4x\) 是否也重排”这一类变体问题。
设 \(M\) 是要检查的最大倍数，\(A\) 是该设定下找到的第一个解。实现会把所有候选从 \(1\) 一直试到 \(A\)。若 \(A\) 有 \(D\) 位，那么一次数字签名计算最多对 \(D\) 个字符排序，因此其代价为 \(O(D \log D)\)。在最坏情况下，一个候选需要计算 \(M\) 个签名，于是总时间复杂度为
$$O(A\,M\,D\log D).$$
对原题来说，\(M=6\)、\(A=142857\)、\(D=6\)，所以实际运行量非常小。额外空间只需要保存若干临时数字字符串，因此是 \(O(D)\)，相对于候选总数来说可以看作常数级。
Нужно найти наименьшее положительное число \(x\), для которого десятичные цифры чисел \(x\), \(2x\), \(3x\), \(4x\), \(5x\) и \(6x\) совпадают с точностью до перестановки. Иначе говоря, каждое число от \(2x\) до \(6x\) должно быть перестановкой цифр самого \(x\). Наименьшее такое значение равно \(142857\), но смысл задачи в том, чтобы понять, почему достаточно очень простой точной проверки.
Все три реализации используют один и тот же центральный объект: отсортированную подпись десятичных цифр. Эта подпись дает точное и полное условие задачи.
Обозначим через \(\sigma(n)\) строку, полученную сортировкой десятичных цифр числа \(n\) по неубыванию. Тогда
$$x \text{ и } y \text{ являются перестановками цифр } \Longleftrightarrow \sigma(x)=\sigma(y).$$
Следовательно, задача эквивалентна системе
$$\sigma(x)=\sigma(2x)=\sigma(3x)=\sigma(4x)=\sigma(5x)=\sigma(6x).$$
Это условие намного сильнее, чем проверка одной только суммы цифр или сравнений по модулю, потому что оно сохраняет полную кратность каждой цифры.
Если \(x\) имеет \(d\) десятичных цифр, то любая перестановка этих цифр тоже имеет \(d\) цифр. Значит, и число \(6x\) обязано оставаться \(d\)-значным. Поэтому любой \(d\)-значный кандидат должен удовлетворять неравенствам
$$10^{d-1} \le x \le \left\lfloor \frac{10^d-1}{6} \right\rfloor.$$
Это главное структурное ограничение задачи: потенциально подходят только числа из первой шестой части каждого блока фиксированной длины. Точное число кандидатов равно
$$\left\lfloor \frac{10^d-1}{6} \right\rfloor - 10^{d-1} + 1.$$
При \(d=6\) остается интервал \(100000 \le x \le 166666\), то есть всего \(66667\) кандидатов. Реализации явно не кодируют эту границу, но именно она объясняет, почему решение находится быстро.
Перестановка цифр не меняет сумму цифр. Поэтому из \(\sigma(kx)=\sigma(x)\) следует, что \(kx\) и \(x\) имеют одинаковую сумму цифр и, следовательно, одинаковый остаток по модулю \(9\). При \(k=2\) получаем
$$2x \equiv x \pmod 9,$$
то есть любое допустимое решение обязано удовлетворять
$$x \equiv 0 \pmod 9.$$
Это лишь необходимое условие. Большинство кратных \(9\) все равно не проходят точную проверку подписи, поэтому реализации сравнивают именно отсортированные цифры, а не более слабые инварианты.
Встроенный контрольный пример использует число \(125874\), потому что
$$2 \cdot 125874 = 251748,$$
и у обоих чисел одна и та же подпись \(124578\). Это демонстрирует идею на одном множителе.
Полное решение имеет вид
$$x=142857,$$
поскольку
$$2x=285714,\quad 3x=428571,\quad 4x=571428,\quad 5x=714285,\quad 6x=857142.$$
После сортировки цифр каждое из этих шести чисел дает одну и ту же подпись \(124578\). Поскольку поиск идет по возрастанию, первый найденный подходящий кандидат автоматически является минимальным.
Реализации на C++, Python и Java устроены одинаково. Они начинают с \(x=1\) и перебирают кандидаты по возрастанию. Для каждого кандидата один раз вычисляется отсортированная подпись \(x\), после чего она сравнивается с подписями чисел \(2x\), \(3x\) и так далее вплоть до выбранного верхнего множителя. При первом несовпадении текущий кандидат сразу отбрасывается.
То есть программа напрямую использует точный критерий \(\sigma(kx)=\sigma(x)\). В ней нет таблиц частот цифр, нет явного разбиения по числу цифр и нет модульных фильтров. За счет раннего выхода такой прямой перебор остается очень быстрым.
Во всех трех реализациях есть небольшой встроенный тест: перед основным поиском проверяется, что числа \(125874\) и \(251748\) действительно имеют одинаковые отсортированные цифры. Кроме того, предусмотрен необязательный параметр командной строки, который позволяет заменить стандартный верхний множитель \(6\) на любое значение не меньше \(2\).
Пусть \(M\) обозначает максимальный проверяемый множитель, а \(A\) — первое решение для этого значения. Реализации проверяют все числа от \(1\) до \(A\). Если \(A\) имеет \(D\) цифр, то вычисление одной подписи требует сортировки не более чем \(D\) символов, то есть стоит \(O(D \log D)\). В худшем случае на один кандидат приходится \(M\) таких вычислений, а общее время равно
$$O(A\,M\,D\log D).$$
Для исходной задачи \(M=6\), \(A=142857\) и \(D=6\), поэтому на практике время работы очень мало. Дополнительная память составляет \(O(D)\) для временных строк с цифрами и не зависит от числа просмотренных кандидатов.
المطلوب هو إيجاد أصغر عدد صحيح موجب \(x\) بحيث تكون الأرقام العشرية في \(x\) و\(2x\) و\(3x\) و\(4x\) و\(5x\) و\(6x\) هي نفسها تمامًا مع اختلاف الترتيب فقط. أي إن كل مضاعف من \(2x\) إلى \(6x\) يجب أن يكون تبديلًا لأرقام \(x\). أصغر قيمة تحقق ذلك هي \(142857\)، لكن القيمة الحقيقية في المسألة هي فهم لماذا تكفي طريقة بحث مباشرة ودقيقة جدًا.
تعتمد جميع التطبيقات على الفكرة الرياضية نفسها: ترتيب الأرقام العشرية يعطي بصمة رقمية كاملة للعدد. ومتى تطابقت هذه البصمة، كان الشرط محققًا بالضبط.
لنعرّف \(\sigma(n)\) بأنها السلسلة الناتجة من ترتيب أرقام \(n\) العشرية ترتيبًا غير تنازلي، ولنكتب \(x \sim y\) عندما يكون العددان تبديلين لبعضهما في الأرقام. عندئذٍ
$$x \sim y \Longleftrightarrow \sigma(x)=\sigma(y).$$
وبذلك تصبح المسألة مكافئة للنظام
$$\sigma(x)=\sigma(2x)=\sigma(3x)=\sigma(4x)=\sigma(5x)=\sigma(6x).$$
هذه الصياغة أقوى من أي فحص يعتمد فقط على مجموع الأرقام أو على شروط تطابق عددية، لأنها تحفظ عدد مرات ظهور كل رقم حفظًا كاملًا.
إذا كان \(x\) مكوّنًا من \(d\) أرقام عشرية، فإن أي تبديل لأرقامه سيبقى مكوّنًا من \(d\) أرقام. لذلك يجب أن يبقى \(6x\) أيضًا عددًا من \(d\) أرقام. ومن ثم فإن كل مرشح ذي \(d\) أرقام يجب أن يحقق
$$10^{d-1} \le x \le \left\lfloor \frac{10^d-1}{6} \right\rfloor.$$
وهذا هو القيد البنيوي الأهم في المسألة: الجزء الأول فقط من كل كتلة أعداد ذات طول ثابت يمكن أن يحتوي على حل. وعدد المرشحين في هذه الكتلة يساوي
$$\left\lfloor \frac{10^d-1}{6} \right\rfloor - 10^{d-1} + 1.$$
فعندما \(d=6\)، نحصل على المجال \(100000 \le x \le 166666\)، أي \(66667\) مرشحًا فقط. لا تستخدم التطبيقات هذا القيد صراحة، لكنه يوضح لماذا يظهر أول حل في نطاق ضيق جدًا.
تبديل الأرقام لا يغيّر مجموعها. فإذا كان \(\sigma(kx)=\sigma(x)\)، فإن \(kx\) و\(x\) يملكان مجموع الأرقام نفسه، ومن ثم فلهما الباقي نفسه بترديد \(9\). باختيار \(k=2\) نحصل على
$$2x \equiv x \pmod 9,$$
وبالتالي يجب أن يحقق أي حل صحيح
$$x \equiv 0 \pmod 9.$$
لكن هذا شرط لازم فقط وليس كافيًا. فكثير من مضاعفات \(9\) لا تمر عبر اختبار البصمة الرقمية الكامل، ولذلك تعتمد التطبيقات على مقارنة الأرقام المرتبة مباشرة.
مثال التحقق المضمّن في التطبيقات هو \(125874\)، لأن
$$2 \cdot 125874 = 251748,$$
وكلا العددين يعطي البصمة المرتبة نفسها \(124578\). وهذا يشرح الفكرة على مضاعف واحد.
أما الحل الكامل فهو
$$x=142857,$$
إذ إن
$$2x=285714,\quad 3x=428571,\quad 4x=571428,\quad 5x=714285,\quad 6x=857142.$$
وبترتيب أرقام أي واحد من هذه الأعداد الستة نحصل دائمًا على البصمة نفسها \(124578\). وبما أن البحث يسير تصاعديًا، فإن أول مرشح ناجح هو تلقائيًا أصغر حل ممكن.
تنفذ نسخ C++ وPython وJava الخطة نفسها. يبدأ البحث من \(x=1\) ويجري اختبار المرشحين بالترتيب التصاعدي. لكل مرشح تُحسب البصمة المرتبة للعدد \(x\) مرة واحدة، ثم تُقارن ببصمات \(2x\) و\(3x\) وهكذا حتى أكبر مضاعف مطلوب. وعند أول عدم تطابق يُرفض المرشح فورًا ويبدأ اختبار العدد التالي.
إذن فالتنفيذ يطبق الشرط الدقيق \(\sigma(kx)=\sigma(x)\) مباشرة. ولا يستخدم جداول تكرار للأرقام، ولا يقسم البحث مسبقًا بحسب عدد الخانات، ولا يضيف مرشحات أضعف مثل شرط الترديد \(9\). والميزة هنا هي البساطة، بينما يجعل الإنهاء المبكر البحث المباشر سريعًا بما يكفي.
تتضمن التطبيقات الثلاثة خطوة تحقق صغيرة قبل الحل الرئيسي: التأكد من أن \(125874\) و\(251748\) لهما بالفعل الأرقام المرتبة نفسها. كما تقبل إعدادًا اختياريًا من سطر الأوامر يبدل الحد الأعلى الافتراضي \(6\) بقيمة يختارها المستخدم شرط ألا تقل عن \(2\).
لنرمز إلى أكبر مضاعف مفحوص بالرمز \(M\)، وإلى أول حل تم العثور عليه بالرمز \(A\). تقوم التطبيقات باختبار كل المرشحين من \(1\) حتى \(A\). إذا كان \(A\) مكوّنًا من \(D\) أرقام، فإن حساب بصمة واحدة يحتاج إلى ترتيب ما لا يزيد على \(D\) محارف، أي بتكلفة \(O(D \log D)\). وفي أسوأ الأحوال يحتاج المرشح الواحد إلى \(M\) حسابات من هذا النوع، لذلك يكون الزمن الكلي
$$O(A\,M\,D\log D).$$
في المسألة الأصلية لدينا \(M=6\) و\(A=142857\) و\(D=6\)، ولذلك يكون التنفيذ صغير التكلفة عمليًا. أما الذاكرة الإضافية فهي \(O(D)\) فقط من أجل السلاسل المؤقتة للأرقام، أي ثابتة بالنسبة إلى عدد المرشحين الكلي.