We seek the integer \(n\) with \(1 \lt n \lt 10^7\) such that \(\varphi(n)\) is a digit permutation of \(n\) and the quotient \(n/\varphi(n)\) is as small as possible. Here \(\varphi(n)\) counts the integers \(1 \le k \le n\) that are coprime to \(n\).
The C++, Python, and Java implementations do not rely on a narrow guess such as "the answer must be semiprime". Instead they compute \(\varphi(n)\) exactly for every \(n\) below the limit, test the digit-permutation condition exactly, and keep the candidate with the smallest ratio.
The key mathematics is the factor formula for Euler's totient function and the observation that it can be turned into a sieve. Once every totient value is available, Problem 70 becomes a direct scan over all \(n \lt 10^7\).
If the distinct prime divisors of \(n\) are \(p_1,\dots,p_r\), then
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
This comes from counting the integers in \(\{1,2,\dots,n\}\) that are not divisible by any prime factor of \(n\). Each factor \((1-1/p)\) removes the fraction ruled out by the prime \(p\), and only distinct prime divisors matter.
Equivalently, if \(n=p_1^{a_1}\cdots p_r^{a_r}\), then
$$\varphi(n)=p_1^{a_1-1}(p_1-1)\cdots p_r^{a_r-1}(p_r-1).$$
Initialize an array with \(\phi(m)=m\) for every \(m\). When a prime \(p\) is encountered, every multiple \(j\) of \(p\) must receive the factor \((1-1/p)\), so the update is
$$\phi(j)\leftarrow \phi(j)\left(1-\frac1p\right)=\phi(j)-\frac{\phi(j)}{p}.$$
The key invariant is that after all primes up to \(P\) have been processed,
$$\phi(j)=j\prod_{\substack{q\mid j\\ q\le P}}\left(1-\frac1q\right).$$
Once the last prime divisor of \(j\) has been handled, this becomes exactly \(\varphi(j)\). The update is also an integer step: when the factor for \(p\) is applied, the current value still contains an unremoved factor of \(p\), so \(\phi(j)/p\) is integral at that moment.
The prime test inside the sieve is just as simple. If \(\phi(i)=i\) when the loop reaches \(i\), then no smaller prime has touched it, so \(i\) is prime. Every composite number would already have been reduced by its smallest prime divisor.
The problem asks whether \(n\) and \(\varphi(n)\) use exactly the same decimal digits with the same multiplicities. That is a multiset condition, not an arithmetic identity.
One way to test it is to sort both decimal strings and compare the results. Another is to count how many times each digit \(0,1,\dots,9\) appears and compare the two count vectors. The implementations use both styles: sorting in Python and Java, and a digit-frequency count in C++. Different mechanics, same mathematical test.
Once a candidate passes the digit test, we must decide whether its ratio is better than the best ratio seen so far. For positive quantities,
$$\frac{a}{b} \lt \frac{c}{d}\qquad\Longleftrightarrow\qquad ad \lt cb.$$
So the ratio comparison can be done by cross-multiplication instead of repeated division. This keeps the ordering exact. The C++ and Python implementations use this integer comparison directly, while the Java implementation evaluates the quotient numerically.
This small example mirrors the full method. Start with \(\phi(21)=21\). The prime divisors of 21 are 3 and 7, so the sieve performs
$$21 \xrightarrow{\,p=3\,} 21-\frac{21}{3}=14 \xrightarrow{\,p=7\,} 14-\frac{14}{7}=12.$$
Hence \(\varphi(21)=12\), which matches the product formula
$$\varphi(21)=21\left(1-\frac13\right)\left(1-\frac17\right)=12.$$
The digits of 21 and 12 are the same multiset \(\{1,2\}\), so 21 is a valid candidate. On the restricted range \(n \lt 100\), it is the best one, which makes it a convenient sanity check for the sieve and the ratio comparison. A larger sample from the problem statement is \(87109\), whose totient is \(79180\); the same digit-multiset test accepts that pair as well.
The C++, Python, and Java implementations all follow the same two-phase structure: first build every totient value below the limit with a sieve, then sweep once through the completed table looking for valid permutations and the minimum ratio.
An array of length \(10^7\) is filled with its own indices. The main loop scans upward from 2. Whenever an entry is still equal to its index, that number is prime, so every multiple of it is updated by the rule \(\phi(j)\leftarrow \phi(j)-\phi(j)/p\). After this phase, the array holds \(\varphi(n)\) for every \(n\) in the search range.
The second loop visits each \(n\ge 2\), retrieves its precomputed totient, and checks whether the decimal digits match as a multiset. The C++ implementation uses a 10-entry digit counter, while the Python and Java implementations sort the decimal representations before comparing them.
Whenever a valid permutation is found, the implementation compares its ratio against the current best and updates the stored answer if the new ratio is smaller. Because all totient values are already known, this final phase is a simple linear scan with no recursion, no backtracking, and no number-theoretic guesswork beyond the sieve itself.
Let \(N=10^7\). The totient sieve has the same harmonic-over-primes behavior as other prime sieves and runs in \(O(N\log\log N)\) time. The final scan is \(O(N)\) candidates, with a digit test that is constant-time in practice because numbers below \(10^7\) have at most seven decimal digits. Written asymptotically, that test is \(O(d)\) with digit counts or \(O(d\log d)\) with sorting, where \(d\le 7\).
The memory usage is \(O(N)\) for the totient table. That linear table is the dominant space cost in all three languages, and it is exactly what allows the search to stay exhaustive while still remaining fast enough for the stated limit.
Gesucht ist die ganze Zahl \(n\) mit \(1 \lt n \lt 10^7\), für die \(\varphi(n)\) eine Ziffernpermutation von \(n\) ist und der Quotient \(n/\varphi(n)\) minimal wird. Dabei zählt \(\varphi(n)\) die Zahlen \(1 \le k \le n\), die zu \(n\) teilerfremd sind.
Die C++-, Python- und Java-Implementierungen verlassen sich nicht auf eine enge Vermutung wie "die Lösung muss halbprim sein". Stattdessen berechnen sie \(\varphi(n)\) für jedes \(n\) unter der Schranke exakt, prüfen die Ziffernpermutation direkt und behalten den Kandidaten mit dem kleinsten Verhältnis.
Die zentrale Mathematik besteht aus der Produktformel für Eulers Totientfunktion und der Beobachtung, dass sie sich in ein Sieb umwandeln lässt. Sobald alle Totientwerte vorliegen, ist Problem 70 nur noch ein exakter Durchlauf über alle \(n \lt 10^7\).
Seien \(p_1,\dots,p_r\) die verschiedenen Primteiler von \(n\). Dann gilt
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
Diese Formel entsteht, indem man aus \(\{1,2,\dots,n\}\) genau die Zahlen entfernt, die durch mindestens einen Primteiler von \(n\) teilbar sind. Jeder Faktor \((1-1/p)\) entfernt den durch \(p\) verbotenen Anteil, und nur die verschiedenen Primteiler spielen eine Rolle.
Schreibt man \(n=p_1^{a_1}\cdots p_r^{a_r}\), so ist äquivalent
$$\varphi(n)=p_1^{a_1-1}(p_1-1)\cdots p_r^{a_r-1}(p_r-1).$$
Man initialisiert ein Feld mit \(\phi(m)=m\) für jedes \(m\). Sobald eine Primzahl \(p\) erreicht wird, muss jedes Vielfache \(j\) den Faktor \((1-1/p)\) erhalten. Die Aktualisierung lautet also
$$\phi(j)\leftarrow \phi(j)\left(1-\frac1p\right)=\phi(j)-\frac{\phi(j)}{p}.$$
Die entscheidende Invariante lautet: Nachdem alle Primzahlen bis \(P\) verarbeitet sind, gilt
$$\phi(j)=j\prod_{\substack{q\mid j\\ q\le P}}\left(1-\frac1q\right).$$
Sobald der letzte Primteiler von \(j\) bearbeitet wurde, ist dieser Wert genau \(\varphi(j)\). Der Schritt bleibt ganzzahlig, weil beim Verarbeiten von \(p\) im aktuellen Wert noch ein nicht entfernter Faktor \(p\) steckt, also ist \(\phi(j)/p\) in diesem Moment tatsächlich eine ganze Zahl.
Auch der Primzahltest im Sieb ist direkt. Falls \(\phi(i)=i\) gilt, wenn die Schleife bei \(i\) ankommt, dann hat keine kleinere Primzahl diesen Eintrag verändert, also ist \(i\) prim. Jede zusammengesetzte Zahl wäre bereits durch ihren kleinsten Primteiler reduziert worden.
Gefragt ist nicht, ob \(n\) und \(\varphi(n)\) nahe beieinander liegen, sondern ob beide dieselben Dezimalziffern mit denselben Häufigkeiten besitzen. Das ist eine Bedingung über Multimengen von Ziffern.
Man kann dafür beide Dezimaldarstellungen sortieren und vergleichen. Alternativ kann man zählen, wie oft jede Ziffer \(0,1,\dots,9\) vorkommt, und die beiden Häufigkeitsvektoren vergleichen. Die Implementierungen verwenden beide Varianten: Sortieren in Python und Java, Ziffernhäufigkeiten in C++.
Hat ein Kandidat den Zifferntest bestanden, muss nur noch entschieden werden, ob sein Verhältnis besser ist als das bisher beste. Für positive Größen gilt
$$\frac{a}{b} \lt \frac{c}{d}\qquad\Longleftrightarrow\qquad ad \lt cb.$$
Man kann den Vergleich also per Kreuzmultiplikation statt per wiederholter Division durchführen. Dadurch bleibt die Ordnung exakt. Die C++- und Python-Implementierungen machen genau das, während die Java-Implementierung den Quotienten numerisch auswertet.
Dieses kleine Beispiel spiegelt das vollständige Verfahren wider. Zunächst ist \(\phi(21)=21\). Die Primteiler von 21 sind 3 und 7, also führt das Sieb die Schritte
$$21 \xrightarrow{\,p=3\,} 21-\frac{21}{3}=14 \xrightarrow{\,p=7\,} 14-\frac{14}{7}=12.$$
Damit ist \(\varphi(21)=12\), im Einklang mit der Produktformel
$$\varphi(21)=21\left(1-\frac13\right)\left(1-\frac17\right)=12.$$
Die Zahlen 21 und 12 besitzen dieselbe Ziffernmultimenge \(\{1,2\}\), also ist 21 ein gültiger Kandidat. Im eingeschränkten Bereich \(n \lt 100\) ist es sogar der beste, weshalb dieser Fall ein nützlicher Plausibilitätstest für Sieb und Quotientenvergleich ist. Ein größeres Beispiel aus der Aufgabenstellung ist \(87109\) mit Totient \(79180\); auch dieses Paar besteht denselben Zifferntest.
Die C++-, Python- und Java-Implementierungen folgen alle derselben Zweiphasenstruktur: zuerst werden mit einem Sieb sämtliche Totientwerte unterhalb der Schranke berechnet, danach wird die fertige Tabelle einmal nach gültigen Permutationen und dem kleinsten Quotienten abgesucht.
Ein Array der Länge \(10^7\) wird zunächst mit seinen eigenen Indizes gefüllt. Dann läuft die Hauptschleife von 2 aufwärts. Immer wenn ein Eintrag noch gleich seinem Index ist, handelt es sich um eine Primzahl, und alle Vielfachen werden mit der Regel \(\phi(j)\leftarrow \phi(j)-\phi(j)/p\) aktualisiert. Nach dieser Phase enthält das Feld für jedes \(n\) im Suchbereich den Wert \(\varphi(n)\).
Die zweite Schleife besucht jedes \(n\ge 2\), liest den vorberechneten Totientwert und prüft, ob beide Dezimaldarstellungen dieselbe Ziffernmultimenge haben. Die C++-Implementierung benutzt dazu einen Zähler mit 10 Einträgen; Python und Java sortieren die Dezimaldarstellungen vor dem Vergleich.
Sobald eine gültige Permutation gefunden ist, vergleicht die Implementierung deren Quotienten mit dem bisher besten und ersetzt die gespeicherte Antwort nur bei echtem Fortschritt. Weil alle Totientwerte bereits vorliegen, ist diese Schlussphase ein einfacher linearer Durchlauf ohne Rekursion, ohne Backtracking und ohne zusätzliche Zahlentheorie jenseits des Siebs.
Sei \(N=10^7\). Das Totientsieb hat dasselbe harmonische Verhalten über die Primzahlen wie andere Primzahlsiebe und läuft in \(O(N\log\log N)\) Zeit. Der abschließende Durchlauf betrachtet \(O(N)\) Kandidaten, und der Zifferntest ist praktisch konstant, weil Zahlen unter \(10^7\) höchstens sieben Dezimalstellen besitzen. Asymptotisch ist dieser Test \(O(d)\) bei Ziffernzählung oder \(O(d\log d)\) bei Sortierung, mit \(d\le 7\).
Der Speicherverbrauch beträgt \(O(N)\) für die Totienttabelle. Diese lineare Tabelle dominiert den Platzbedarf in allen drei Sprachen und ist genau der Grund, warum die Suche vollständig bleiben kann und für die vorgegebene Schranke dennoch schnell genug ist.
\(1 \lt n \lt 10^7\) aralığında, \(\varphi(n)\) değeri \(n\) sayısının rakamlarının bir permütasyonu olan ve aynı zamanda \(n/\varphi(n)\) oranını en küçük yapan \(n\) aranıyor. Burada \(\varphi(n)\), \(1 \le k \le n\) aralığında \(n\) ile aralarında asal olan sayıların sayısıdır.
C++, Python ve Java uygulamaları "cevap mutlaka iki asalın çarpımıdır" gibi dar bir tahmine yaslanmaz. Bunun yerine sınırın altındaki her \(n\) için \(\varphi(n)\) değerini tam olarak hesaplar, rakam-permütasyonu koşulunu doğrudan test eder ve en küçük oranı veren adayı saklar.
Ana fikir, Euler totient fonksiyonunun çarpım formülünü bir eleğe dönüştürmektir. Bütün totient değerleri hazır olunca Problem 70, \(n \lt 10^7\) için yapılan tam bir taramaya dönüşür.
\(n\)'yi bölen farklı asallar \(p_1,\dots,p_r\) olsun. O zaman
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
Bu formül, \(\{1,2,\dots,n\}\) içinden \(n\)'nin asal bölenlerinden en az birine bölünen sayıları elemekten gelir. Her \((1-1/p)\) çarpanı, \(p\) yüzünden elenen oranı çıkarır; yalnızca farklı asal bölenler önemlidir.
Eşdeğer biçimde, \(n=p_1^{a_1}\cdots p_r^{a_r}\) ise
$$\varphi(n)=p_1^{a_1-1}(p_1-1)\cdots p_r^{a_r-1}(p_r-1).$$
Başlangıçta her \(m\) için \(\phi(m)=m\) olacak şekilde bir dizi kurulur. Bir asal \(p\) görüldüğünde, \(p\)'nin her katı \(j\), \((1-1/p)\) çarpanını almalıdır. Bu yüzden güncelleme
$$\phi(j)\leftarrow \phi(j)\left(1-\frac1p\right)=\phi(j)-\frac{\phi(j)}{p}$$
şeklindedir. Temel değişmez şudur: \(P\)'ye kadar olan tüm asallar işlendiğinde
$$\phi(j)=j\prod_{\substack{q\mid j\\ q\le P}}\left(1-\frac1q\right).$$
\(j\)'nin son asal böleni de işlendiğinde bu değer tam olarak \(\varphi(j)\) olur. Üstelik işlem gerçekten tam sayılıdır; çünkü \(p\) için güncelleme yapılırken mevcut değerin içinde henüz kaldırılmamış bir \(p\) çarpanı bulunur, dolayısıyla \(\phi(j)/p\) o anda tam sayıdır.
Eleğin içindeki asal testi de buradan gelir. Döngü \(i\)'ye ulaştığında hâlâ \(\phi(i)=i\) ise, bu değere daha küçük hiçbir asal dokunmamıştır; o halde \(i\) asaldır. Bileşik bir sayı, en küçük asal böleni işlendiğinde çoktan küçülmüş olurdu.
Sorulan şey, \(n\) ile \(\varphi(n)\)'nin birbirine sayısal olarak yakın olması değil; ondalık yazımlarında aynı rakamların aynı sayıda bulunmasıdır. Yani kontrol edilmesi gereken nesne, rakamların çoklu kümesidir.
Bunu test etmenin bir yolu iki ondalık gösterimi sıralayıp karşılaştırmaktır. Başka bir yol, \(0,1,\dots,9\) rakamlarının her birinin kaç kez geçtiğini sayıp iki frekans vektörünü karşılaştırmaktır. Uygulamalar iki yöntemi de kullanır: Python ve Java sıralama yapar, C++ ise rakam sayacı tutar.
Bir aday rakam testini geçtiğinde, oranının mevcut en iyi orandan küçük olup olmadığına bakmak gerekir. Pozitif nicelikler için
$$\frac{a}{b} \lt \frac{c}{d}\qquad\Longleftrightarrow\qquad ad \lt cb.$$
Bu yüzden karşılaştırma, tekrar tekrar bölme yapmak yerine çapraz çarpma ile yapılabilir. Böylece sıralama tam olarak korunur. C++ ve Python uygulamaları bunu doğrudan tam sayılarla yapar; Java uygulaması ise oranı sayısal olarak hesaplar.
Bu küçük örnek, tüm yöntemi aynen yansıtır. Başlangıçta \(\phi(21)=21\) olur. 21'in asal bölenleri 3 ve 7 olduğundan elek şu adımları uygular:
$$21 \xrightarrow{\,p=3\,} 21-\frac{21}{3}=14 \xrightarrow{\,p=7\,} 14-\frac{14}{7}=12.$$
Dolayısıyla \(\varphi(21)=12\) elde edilir; bu, çarpım formülüyle de aynıdır:
$$\varphi(21)=21\left(1-\frac13\right)\left(1-\frac17\right)=12.$$
21 ve 12 sayıları aynı rakam çokluğuna, yani \(\{1,2\}\)'ye sahiptir. Böylece 21 geçerli bir aday olur. Daraltılmış \(n \lt 100\) aralığında en iyi değer de budur; bu yüzden hem eleği hem de oran karşılaştırmasını doğrulamak için çok kullanışlı bir küçük örnektir. Soru metnindeki daha büyük örnek \(87109\) için de \(\varphi(87109)=79180\) olup aynı rakam testi başarıyla geçilir.
C++, Python ve Java uygulamalarının hepsi aynı iki aşamalı yapıyı izler: önce sınırın altındaki bütün totient değerleri bir elek ile üretilir, sonra hazır tablo bir kez taranarak geçerli permütasyonlar ve en küçük oran bulunur.
Uzunluğu \(10^7\) olan bir dizi kendi indisleriyle doldurulur. Ana döngü 2'den başlayarak yukarı gider. Bir giriş hâlâ kendi indisine eşitse bu sayı asaldır; bu durumda tüm katları \(\phi(j)\leftarrow \phi(j)-\phi(j)/p\) kuralıyla güncellenir. Aşamanın sonunda dizideki her giriş, arama aralığındaki ilgili \(\varphi(n)\) değerini taşır.
İkinci döngü \(n\ge 2\) olan her sayıyı ziyaret eder, önceden hesaplanmış totient değerini alır ve ondalık rakamların çoklu küme olarak eşleşip eşleşmediğini kontrol eder. C++ uygulaması 10 elemanlı bir rakam sayacı kullanır; Python ve Java uygulamaları karşılaştırmadan önce ondalık gösterimleri sıralar.
Geçerli bir permütasyon bulunduğunda uygulama bu adayın oranını o ana kadarki en iyi oranla karşılaştırır ve yalnızca yeni oran daha küçükse saklanan cevabı değiştirir. Bütün totient değerleri zaten hazır olduğundan, bu son aşama özyineleme, geri izleme ya da ek sayı kuramı numaraları içermeyen basit doğrusal bir taramadır.
\(N=10^7\) olsun. Totient eleği, asal sayılar üzerindeki harmonik toplam davranışı nedeniyle \(O(N\log\log N)\) zamanda çalışır. Son tarama \(O(N)\) aday inceler; rakam testi ise pratikte sabittir, çünkü \(10^7\)'den küçük sayılar en fazla yedi basamaklıdır. Asimptotik olarak bu test, frekans sayımı ile \(O(d)\), sıralama ile \(O(d\log d)\) olur ve burada \(d\le 7\)'dir.
Bellek kullanımı, totient tablosu için \(O(N)\)'dir. Üç dilde de baskın alan maliyeti bu doğrusal tablodur ve tam da bu yapı sayesinde arama hem eksiksiz kalır hem de verilen sınır için yeterince hızlı olur.
Se busca el entero \(n\) con \(1 \lt n \lt 10^7\) tal que \(\varphi(n)\) sea una permutación decimal de \(n\) y, entre todos esos casos, el cociente \(n/\varphi(n)\) sea mínimo. Aquí \(\varphi(n)\) cuenta los enteros \(1 \le k \le n\) que son coprimos con \(n\).
Las implementaciones en C++, Python y Java no dependen de una conjetura estrecha como "la respuesta tiene que ser semiprima". En cambio, calculan \(\varphi(n)\) exactamente para todo \(n\) por debajo del límite, comprueban de forma exacta la condición de permutación de dígitos y conservan el candidato con la razón más pequeña.
La idea central es la fórmula por factores de la función totiente de Euler y el hecho de que puede convertirse en un tamiz. Una vez disponibles todos los valores de totiente, el Problema 70 se reduce a recorrer de forma directa todos los \(n \lt 10^7\).
Si \(p_1,\dots,p_r\) son los divisores primos distintos de \(n\), entonces
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
La fórmula sale de contar los enteros de \(\{1,2,\dots,n\}\) que no son divisibles por ninguno de los factores primos de \(n\). Cada factor \((1-1/p)\) elimina la fracción descartada por el primo \(p\), y solo importan los divisores primos distintos.
De manera equivalente, si \(n=p_1^{a_1}\cdots p_r^{a_r}\), entonces
$$\varphi(n)=p_1^{a_1-1}(p_1-1)\cdots p_r^{a_r-1}(p_r-1).$$
Se inicializa un arreglo con \(\phi(m)=m\) para cada \(m\). Cuando aparece un primo \(p\), todo múltiplo \(j\) de \(p\) debe recibir el factor \((1-1/p)\), así que la actualización es
$$\phi(j)\leftarrow \phi(j)\left(1-\frac1p\right)=\phi(j)-\frac{\phi(j)}{p}.$$
La invariante clave dice que, después de procesar todos los primos hasta \(P\), se cumple
$$\phi(j)=j\prod_{\substack{q\mid j\\ q\le P}}\left(1-\frac1q\right).$$
Cuando ya se han tratado todos los divisores primos de \(j\), esa expresión coincide exactamente con \(\varphi(j)\). Además, la actualización es entera: al aplicar el factor correspondiente a \(p\), el valor actual todavía conserva un factor \(p\) que no se ha eliminado, de modo que \(\phi(j)/p\) es entero en ese instante.
El test de primalidad dentro del tamiz nace de la misma observación. Si \(\phi(i)=i\) cuando el bucle llega a \(i\), entonces ningún primo menor ha modificado esa entrada y, por tanto, \(i\) es primo. Todo número compuesto ya habría sido reducido por su menor divisor primo.
El problema no pide cercanía numérica entre \(n\) y \(\varphi(n)\); pide que sus escrituras decimales contengan exactamente los mismos dígitos con las mismas multiplicidades. Eso es una condición sobre multiconjuntos de dígitos.
Puede comprobarse ordenando ambas cadenas decimales y comparando el resultado. También puede hacerse contando cuántas veces aparece cada dígito \(0,1,\dots,9\) y comparando los dos vectores de frecuencias. Las implementaciones usan las dos variantes: Python y Java ordenan, mientras que C++ utiliza un contador de dígitos.
Una vez que un candidato supera la prueba de dígitos, hay que decidir si su cociente es mejor que el mejor visto hasta ese momento. Para cantidades positivas,
$$\frac{a}{b} \lt \frac{c}{d}\qquad\Longleftrightarrow\qquad ad \lt cb.$$
Así, la comparación puede hacerse mediante multiplicación cruzada en lugar de divisiones repetidas. Eso conserva el orden exacto. Las implementaciones en C++ y Python usan esta comparación entera, mientras que la implementación en Java evalúa el cociente de forma numérica.
Este caso pequeño reproduce el método completo. Se empieza con \(\phi(21)=21\). Como los divisores primos de 21 son 3 y 7, el tamiz realiza
$$21 \xrightarrow{\,p=3\,} 21-\frac{21}{3}=14 \xrightarrow{\,p=7\,} 14-\frac{14}{7}=12.$$
Por tanto \(\varphi(21)=12\), en acuerdo con la fórmula producto
$$\varphi(21)=21\left(1-\frac13\right)\left(1-\frac17\right)=12.$$
Los números 21 y 12 tienen el mismo multiconjunto de dígitos \(\{1,2\}\), así que 21 es un candidato válido. En el rango reducido \(n \lt 100\) es, de hecho, el mejor, y por eso sirve como verificación manual muy útil del tamiz y de la comparación de razones. Un ejemplo mayor tomado del enunciado es \(87109\), cuyo totiente es \(79180\); ese par también supera exactamente el mismo test de dígitos.
Las implementaciones en C++, Python y Java siguen la misma estructura de dos fases: primero construyen todos los valores de totiente por debajo del límite con un tamiz, y después recorren una sola vez la tabla terminada para localizar las permutaciones válidas y la razón mínima.
Se llena un arreglo de longitud \(10^7\) con sus propios índices. El bucle principal avanza desde 2. Cada vez que una entrada sigue siendo igual a su índice, ese número es primo, y entonces todos sus múltiplos se actualizan con la regla \(\phi(j)\leftarrow \phi(j)-\phi(j)/p\). Al terminar esta fase, el arreglo contiene \(\varphi(n)\) para cada \(n\) del rango de búsqueda.
El segundo bucle visita cada \(n\ge 2\), recupera su totiente precalculado y comprueba si ambas escrituras decimales coinciden como multiconjuntos de dígitos. La implementación en C++ usa un contador de 10 posiciones; las implementaciones en Python y Java ordenan antes de comparar.
Cada vez que aparece una permutación válida, la implementación compara su razón con la mejor razón actual y actualiza la respuesta solo si la nueva es menor. Como todos los valores de totiente ya están disponibles, esta fase final es un barrido lineal sencillo, sin recursión, sin retroceso y sin trucos aritméticos adicionales más allá del tamiz.
Sea \(N=10^7\). El tamiz de totientes tiene el mismo comportamiento armónico sobre los primos que otros tamices y se ejecuta en \(O(N\log\log N)\). El barrido final inspecciona \(O(N)\) candidatos, y la prueba de dígitos es constante en la práctica porque los números menores que \(10^7\) tienen como máximo siete cifras decimales. Asintóticamente, esa prueba es \(O(d)\) con conteo de frecuencias o \(O(d\log d)\) con ordenación, donde \(d\le 7\).
El uso de memoria es \(O(N)\) por la tabla de totientes. Esa tabla lineal es el coste espacial dominante en los tres lenguajes y es justamente lo que permite mantener una búsqueda exhaustiva sin perder rendimiento para el límite dado.
我们要在 \(1 \lt n \lt 10^7\) 的范围内找到一个整数 \(n\)，使得 \(\varphi(n)\) 与 \(n\) 具有完全相同的十进制数字，只是顺序不同，并且在所有这样的候选中，比例 \(n/\varphi(n)\) 最小。这里 \(\varphi(n)\) 表示从 \(1\) 到 \(n\) 中与 \(n\) 互素的整数个数。
C++、Python 和 Java 的实现都没有先假设答案必须是什么形状，例如“答案一定是两个素数的乘积”。它们采用的是完全穷举但经过优化的路线：先一次性算出所有 \(n\) 的 totient 值，再逐个检查数字排列条件，最后保留比例最小的那个候选。
这道题真正关键的数学对象是欧拉函数的乘积公式，以及这个公式如何自然地转化成一个筛法。一旦 \(\varphi(n)\) 对所有 \(n \lt 10^7\) 都已经准备好，剩下的工作就只是一次严格而直接的扫描。
设 \(n\) 的不同素因子是 \(p_1,\dots,p_r\)，则有
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
这个公式的含义是：在 \(\{1,2,\dots,n\}\) 里，把那些能被 \(n\) 的某个素因子整除的数全部剔除。每个因子 \((1-1/p)\) 都对应“剔除能被 \(p\) 整除的那一部分”，而且只需要关心不同的素因子。
如果把 \(n\) 写成 \(n=p_1^{a_1}\cdots p_r^{a_r}\)，也可以写成
$$\varphi(n)=p_1^{a_1-1}(p_1-1)\cdots p_r^{a_r-1}(p_r-1).$$
先建立一个数组，对每个 \(m\) 初始化 \(\phi(m)=m\)。当筛到某个素数 \(p\) 时，它的每个倍数 \(j\) 都必须乘上 \((1-1/p)\)，因此更新规则就是
$$\phi(j)\leftarrow \phi(j)\left(1-\frac1p\right)=\phi(j)-\frac{\phi(j)}{p}.$$
这里的核心不变量是：当所有不超过 \(P\) 的素数都处理完成以后，数组中有
$$\phi(j)=j\prod_{\substack{q\mid j\\ q\le P}}\left(1-\frac1q\right).$$
一旦 \(j\) 的最后一个素因子也被处理到，这个值就恰好等于真正的 \(\varphi(j)\)。而且这个更新始终是整数运算，因为在处理素数 \(p\) 时，当前值中仍然保留着尚未消掉的因子 \(p\)，所以 \(\phi(j)/p\) 在那一刻一定是整数。
筛法中的素数判定也来自同一个思路。如果循环走到 \(i\) 时仍有 \(\phi(i)=i\)，说明没有任何更小的素数修改过它，因此 \(i\) 必定是素数。反过来，任意合数都会在它最小的素因子被处理时提前被改小。
题目要求的不是 \(n\) 和 \(\varphi(n)\) 在数值上接近，而是它们的十进制表示中，每个数字出现的次数完全相同。也就是说，需要比较的是数字的多重集，而不是数值本身。
一种做法是把两个十进制字符串分别排序后比较；另一种做法是统计数字 \(0,1,\dots,9\) 的出现次数，然后比较两个频率向量。几个实现正好覆盖了这两种思路：Python 和 Java 采用排序，C++ 采用数字计数。虽然实现方式不同，但数学条件完全一致。
当一个候选通过数字测试以后，下一步是判断它的比例是否优于当前最优解。对于正数，
$$\frac{a}{b} \lt \frac{c}{d}\qquad\Longleftrightarrow\qquad ad \lt cb.$$
因此没有必要反复做浮点除法，直接做交叉相乘就能得到完全精确的顺序关系。C++ 和 Python 的实现采用了这种整数比较；Java 的实现则直接计算浮点比例。无论写法如何，目标都一样，就是保留最小的 \(n/\varphi(n)\)。
这个小例子能完整展示整个方法。开始时 \(\phi(21)=21\)。因为 21 的素因子是 3 和 7，筛法会依次执行
$$21 \xrightarrow{\,p=3\,} 21-\frac{21}{3}=14 \xrightarrow{\,p=7\,} 14-\frac{14}{7}=12.$$
于是 \(\varphi(21)=12\)。这和乘积公式完全一致：
$$\varphi(21)=21\left(1-\frac13\right)\left(1-\frac17\right)=12.$$
21 与 12 的数字多重集同为 \(\{1,2\}\)，所以 21 是一个合法候选。在缩小版范围 \(n \lt 100\) 内，它正是最优值，因此非常适合用来手工检查筛法与比例比较是否正确。题面给出的较大例子 \(87109\) 也一样，\(\varphi(87109)=79180\)，数字测试同样通过。
C++、Python 和 Java 的实现都遵循同一个两阶段结构：先用筛法构造出所有 totient 值，再对这张完整表做一次线性扫描，找出满足排列条件且比例最小的 \(n\)。
程序先分配一个长度为 \(10^7\) 的数组，并把每个位置初始化成自己的下标。主循环从 2 开始向上扫描。每当某个位置仍然等于自身下标，就说明这个数是素数，于是把它的所有倍数按 \(\phi(j)\leftarrow \phi(j)-\phi(j)/p\) 的规则更新。这个阶段结束以后，数组的第 \(n\) 项就已经是 \(\varphi(n)\)。
接下来程序遍历每个 \(n\ge 2\)，读取预先算好的 \(\varphi(n)\)，再检查两者的十进制数字是否作为多重集相同。C++ 实现使用 10 个槽位的数字计数器；Python 和 Java 实现则先排序再比较。
一旦遇到合法候选，程序就把它的比例与当前记录的最优比例进行比较。如果新比例更小，就更新答案。因为所有 totient 值在前一阶段已经全部准备完毕，所以这一阶段只是简单的线性扫描，不需要递归，不需要回溯，也不需要额外的数论猜测。
设 \(N=10^7\)。totient 筛法和其他素数筛一样，具有按素数求和的调和型复杂度，因此时间复杂度为 \(O(N\log\log N)\)。最后的扫描处理 \(O(N)\) 个候选，而每次数字比较在实际中几乎是常数时间，因为小于 \(10^7\) 的数最多只有七位十进制数字。若用渐近记号表示，数字计数法是 \(O(d)\)，排序法是 \(O(d\log d)\)，其中 \(d\le 7\)。
空间复杂度是 \(O(N)\)，主要由存放全部 totient 值的线性数组构成。在三种语言里，最大的内存开销都是这张表；也正是因为先付出这一线性空间成本，整个搜索才能保持完全穷举，同时又足够快。
Нужно найти такое целое число \(n\), что \(1 \lt n \lt 10^7\), значение \(\varphi(n)\) является перестановкой цифр числа \(n\), а отношение \(n/\varphi(n)\) минимально среди всех таких случаев. Здесь \(\varphi(n)\) обозначает количество чисел \(1 \le k \le n\), взаимно простых с \(n\).
Реализации на C++, Python и Java не опираются на узкую гипотезу вроде "ответ обязательно полупростой". Вместо этого они точно вычисляют \(\varphi(n)\) для каждого \(n\) ниже предела, напрямую проверяют условие перестановки цифр и сохраняют кандидат с наименьшим отношением.
Главная математика здесь состоит из произведения для функции Эйлера и из того факта, что его можно превратить в сито. Когда все значения totient уже построены, задача 70 сводится к точному проходу по всем \(n \lt 10^7\).
Пусть \(p_1,\dots,p_r\) - различные простые делители числа \(n\). Тогда
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
Эта формула получается, если из множества \(\{1,2,\dots,n\}\) убрать все числа, которые делятся хотя бы на один простой делитель \(n\). Каждый множитель \((1-1/p)\) убирает долю, запрещённую простым \(p\), и важны только различные простые делители.
Эквивалентно, если \(n=p_1^{a_1}\cdots p_r^{a_r}\), то
$$\varphi(n)=p_1^{a_1-1}(p_1-1)\cdots p_r^{a_r-1}(p_r-1).$$
Сначала создаётся массив с начальным значением \(\phi(m)=m\) для каждого \(m\). Когда встречается простое число \(p\), каждый его кратный \(j\) должен получить множитель \((1-1/p)\), поэтому выполняется обновление
$$\phi(j)\leftarrow \phi(j)\left(1-\frac1p\right)=\phi(j)-\frac{\phi(j)}{p}.$$
Ключевая инварианта такова: после обработки всех простых чисел до \(P\) включительно выполнено
$$\phi(j)=j\prod_{\substack{q\mid j\\ q\le P}}\left(1-\frac1q\right).$$
Как только обработан последний простой делитель числа \(j\), это выражение становится точным значением \(\varphi(j)\). Более того, шаг всегда целочисленный: в момент обработки простого \(p\) текущее значение ещё содержит неубранный множитель \(p\), поэтому \(\phi(j)/p\) тогда обязательно целое.
Отсюда же возникает проверка простоты внутри сита. Если при достижении числа \(i\) всё ещё выполняется \(\phi(i)=i\), значит никакое меньшее простое не меняло этот элемент, следовательно, \(i\) простое. Любое составное число уже было бы уменьшено своим наименьшим простым делителем.
Задача не спрашивает, близки ли \(n\) и \(\varphi(n)\) по величине. Она спрашивает, состоят ли их десятичные записи из одних и тех же цифр с одними и теми же кратностями. То есть нужно сравнить мультимножества цифр.
Это можно сделать, отсортировав обе десятичные строки и сравнив результат. Можно и иначе: посчитать, сколько раз встречается каждая цифра \(0,1,\dots,9\), и сравнить два вектора частот. Реализации используют оба подхода: Python и Java сортируют, а C++ считает частоты цифр.
После того как кандидат прошёл цифровой тест, остаётся решить, меньше ли его отношение текущего лучшего. Для положительных чисел верно
$$\frac{a}{b} \lt \frac{c}{d}\qquad\Longleftrightarrow\qquad ad \lt cb.$$
Значит, сравнение можно выполнять перекрёстным умножением, не прибегая каждый раз к делению. Это сохраняет точный порядок. В реализациях на C++ и Python используется именно такое целочисленное сравнение, а реализация на Java вычисляет отношение напрямую в вещественном виде.
Этот небольшой пример полностью повторяет работу общего метода. В начале \(\phi(21)=21\). Простые делители 21 равны 3 и 7, поэтому сито выполняет шаги
$$21 \xrightarrow{\,p=3\,} 21-\frac{21}{3}=14 \xrightarrow{\,p=7\,} 14-\frac{14}{7}=12.$$
Следовательно, \(\varphi(21)=12\), что совпадает и с формулой произведения
$$\varphi(21)=21\left(1-\frac13\right)\left(1-\frac17\right)=12.$$
Числа 21 и 12 имеют одно и то же мультимножество цифр \(\{1,2\}\), поэтому 21 является допустимым кандидатом. На сокращённом диапазоне \(n \lt 100\) это даже лучший ответ, так что этот случай удобно использовать как ручную проверку сита и сравнения отношений. Более крупный пример из условия задачи - \(87109\), для которого \(\varphi(87109)=79180\); эта пара проходит тот же цифровой тест.
Все реализации на C++, Python и Java имеют одну и ту же двухфазную структуру: сначала с помощью сита строятся все значения totient ниже предела, а затем готовая таблица один раз просматривается в поиске допустимых перестановок и минимального отношения.
Массив длины \(10^7\) сначала заполняется собственными индексами. Главный цикл идёт вверх от 2. Если значение по-прежнему равно индексу, число простое, и все его кратные обновляются по правилу \(\phi(j)\leftarrow \phi(j)-\phi(j)/p\). После этой фазы массив уже содержит \(\varphi(n)\) для каждого \(n\) из диапазона поиска.
Во втором проходе рассматривается каждое \(n\ge 2\), берётся заранее вычисленное значение \(\varphi(n)\), после чего проверяется совпадение десятичных цифр как мультимножества. Реализация на C++ использует счётчик из 10 ячеек; реализации на Python и Java сортируют десятичные записи перед сравнением.
Как только найдена допустимая перестановка, её отношение сравнивается с текущим лучшим, и сохранённый ответ обновляется только при строгом улучшении. Поскольку все значения totient уже известны, этот заключительный этап представляет собой обычный линейный проход без рекурсии, без возвратов назад и без дополнительных эвристик.
Пусть \(N=10^7\). Сито totient обладает тем же гармоническим поведением по простым числам, что и другие решета, и работает за \(O(N\log\log N)\). Финальный проход проверяет \(O(N)\) кандидатов, а цифровой тест практически является константным, потому что числа меньше \(10^7\) имеют не более семи десятичных цифр. В асимптотической записи это \(O(d)\) при подсчёте частот или \(O(d\log d)\) при сортировке, где \(d\le 7\).
Потребление памяти равно \(O(N)\) из-за таблицы totient. Именно этот линейный массив является главным пространственным расходом во всех трёх языках, и именно он делает возможным полный перебор, который всё ещё остаётся быстрым при заданном ограничении.
نريد إيجاد العدد الصحيح \(n\) بحيث \(1 \lt n \lt 10^7\)، وتكون \(\varphi(n)\) إعادة ترتيب لأرقام \(n\) نفسها، ويكون الكسر \(n/\varphi(n)\) أصغر ما يمكن بين جميع هذه الحالات. وتمثل \(\varphi(n)\) عدد الأعداد من \(1\) إلى \(n\) التي تكون أولية نسبياً مع \(n\).
تنفيذات C++ وPython وJava لا تبدأ بفرضية ضيقة مثل "لا بد أن يكون الجواب حاصل ضرب عددين أوليين". بل تحسب \(\varphi(n)\) بدقة لكل \(n\) تحت الحد، ثم تختبر شرط تبديل الأرقام مباشرة، ثم تحتفظ بالمرشح الذي يحقق أصغر نسبة.
الفكرة الرياضية الأساسية هنا هي صيغة الضرب لدالة أويلر، ثم تحويل هذه الصيغة إلى غربال. وبعد أن تصبح كل قيم totient جاهزة، تتحول المسألة إلى مسح مباشر لكل \(n \lt 10^7\).
إذا كانت القواسم الأولية المميزة للعدد \(n\) هي \(p_1,\dots,p_r\)، فإن
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
هذه الصيغة تأتي من عد الأعداد في المجموعة \(\{1,2,\dots,n\}\) التي لا تقبل القسمة على أي قاسم أولي من قواسم \(n\). كل عامل \((1-1/p)\) يزيل النسبة المستبعدة بسبب العدد الأولي \(p\)، ولا نحتاج إلا إلى القواسم الأولية المختلفة.
وبصورة مكافئة، إذا كتبنا \(n=p_1^{a_1}\cdots p_r^{a_r}\)، فإن
$$\varphi(n)=p_1^{a_1-1}(p_1-1)\cdots p_r^{a_r-1}(p_r-1).$$
نبدأ بمصفوفة تحقق \(\phi(m)=m\) لكل \(m\). وعندما نصل إلى عدد أولي \(p\)، فإن كل مضاعف \(j\) له يجب أن يحصل على العامل \((1-1/p)\)، ولذلك يكون التحديث
$$\phi(j)\leftarrow \phi(j)\left(1-\frac1p\right)=\phi(j)-\frac{\phi(j)}{p}.$$
الثابت الأساسي هنا هو أنه بعد معالجة جميع الأعداد الأولية حتى \(P\)، يصبح لدينا
$$\phi(j)=j\prod_{\substack{q\mid j\\ q\le P}}\left(1-\frac1q\right).$$
وعندما تُعالَج آخر قسمة أولية تخص \(j\)، تتحول هذه القيمة بالضبط إلى \(\varphi(j)\). كما أن خطوة التحديث تبقى صحيحة على مستوى الأعداد الصحيحة، لأن القيمة الحالية عند معالجة \(p\) ما زالت تحتوي على عامل \(p\) لم يُزل بعد، ولذلك تكون \(\phi(j)/p\) عدداً صحيحاً في تلك اللحظة.
ومن هنا أيضاً تأتي طريقة كشف الأعداد الأولية داخل الغربال. فإذا وصلنا إلى \(i\) وما زالت \(\phi(i)=i\)، فهذا يعني أن أي عدد أولي أصغر لم يعدل هذه الخانة، وبالتالي يكون \(i\) أولياً. أما العدد المركب فكان لا بد أن يتغير مسبقاً عند معالجة أصغر قاسم أولي له.
المسألة لا تطلب أن يكون \(n\) قريباً عددياً من \(\varphi(n)\)، بل تطلب أن يكون التمثيل العشري لكليهما مؤلفاً من الأرقام نفسها وبالتكرارات نفسها. أي أن الشيء الذي نقارنه هو متعدد مجموعة الأرقام.
يمكن تنفيذ هذا الاختبار بترتيب السلسلتين العشريتين ثم مقارنتهما، أو بعدّ مرات ظهور كل رقم من \(0\) إلى \(9\) ثم مقارنة متجهي التكرار. التنفيذات تستخدم الطريقتين: Python وJava ترتبان الأرقام، بينما يستخدم C++ عداداً لتكرار الأرقام.
بعد أن ينجح المرشح في اختبار الأرقام، يبقى أن نقرر هل نسبته أفضل من أفضل نسبة حالية. وللكميات الموجبة لدينا
$$\frac{a}{b} \lt \frac{c}{d}\qquad\Longleftrightarrow\qquad ad \lt cb.$$
إذن يمكن إجراء المقارنة بالضرب التبادلي من غير حاجة إلى القسمة المتكررة، وهذا يحافظ على الترتيب الدقيق. تنفيذات C++ وPython تستخدم هذه المقارنة الصحيحة مباشرة، أما تنفيذ Java فيحسب النسبة عددياً.
هذا المثال الصغير يطابق المنهج الكامل تماماً. في البداية \(\phi(21)=21\). وبما أن القواسم الأولية لـ 21 هي 3 و7، فإن الغربال ينفذ
$$21 \xrightarrow{\,p=3\,} 21-\frac{21}{3}=14 \xrightarrow{\,p=7\,} 14-\frac{14}{7}=12.$$
ومن ثم نحصل على \(\varphi(21)=12\)، وهذا يوافق أيضاً صيغة الضرب:
$$\varphi(21)=21\left(1-\frac13\right)\left(1-\frac17\right)=12.$$
العددان 21 و12 يملكان متعدد مجموعة الأرقام نفسه \(\{1,2\}\)، لذلك يكون 21 مرشحاً صالحاً. وفي النطاق المصغر \(n \lt 100\) يكون هذا هو أفضل جواب، ولذلك فهو فحص يدوي ممتاز لصحة الغربال وطريقة مقارنة النسب. كما أن المثال الأكبر الوارد في نص المسألة هو \(87109\)، وتحقّق له \(\varphi(87109)=79180\)، ويجتاز الزوج الاختبار الرقمي نفسه.
كل من تنفيذات C++ وPython وJava يتبع البنية نفسها ذات المرحلتين: أولاً بناء جميع قيم totient تحت الحد باستخدام غربال، ثم المرور مرة واحدة على الجدول المكتمل للعثور على التبديلات الصحيحة وأصغر نسبة.
تُملأ مصفوفة بطول \(10^7\) بقيم فهارسها نفسها. ثم تمشي الحلقة الرئيسية من 2 إلى الأعلى. وكلما بقيت خانة مساوية لفهرسها، كان ذلك العدد أولياً، فتُحدَّث كل مضاعفاته وفق القاعدة \(\phi(j)\leftarrow \phi(j)-\phi(j)/p\). وبعد نهاية هذه المرحلة تصبح كل خانة حاوية للقيمة \(\varphi(n)\) الموافقة لها.
تمر الحلقة الثانية على كل \(n\ge 2\)، وتقرأ قيمة \(\varphi(n)\) المحسوبة مسبقاً، ثم تتحقق من أن التمثيلين العشريين متطابقان كمتعدد مجموعة من الأرقام. يستخدم تنفيذ C++ عداداً من 10 خانات، بينما يرتب تنفيذا Python وJava التمثيلين قبل المقارنة.
كلما ظهر تبديل صالح، تُقارَن نسبته بأفضل نسبة محفوظة حتى تلك اللحظة، ولا يُحدَّث الجواب إلا إذا كانت النسبة الجديدة أصغر حقاً. ولأن جميع قيم totient أصبحت جاهزة مسبقاً، فإن هذه المرحلة الأخيرة ليست أكثر من مسح خطي بسيط، بلا استدعاء ذاتي، وبلا رجوع خلفي، وبلا افتراضات إضافية تتجاوز الغربال نفسه.
لنكتب \(N=10^7\). يعمل غربال totient بزمن \(O(N\log\log N)\)، لأنه يملك السلوك التوافقي نفسه فوق الأعداد الأولية الذي نراه في الغربالات المعروفة. أما المسح النهائي فيفحص \(O(N)\) مرشحاً، واختبار الأرقام ثابت عملياً لأن الأعداد الأصغر من \(10^7\) لا تتجاوز سبع خانات عشرية. وبالترميز التقاربي يكون الاختبار \(O(d)\) عند استخدام العد، أو \(O(d\log d)\) عند استخدام الفرز، حيث \(d\le 7\).
أما الذاكرة فهي \(O(N)\) بسبب جدول totient. وهذا الجدول الخطي هو الكلفة المهيمنة في اللغات الثلاث، وهو بالضبط ما يسمح بأن يبقى البحث شاملاً من دون أن يصبح بطيئاً عند هذا الحد.