For a positive integer \(n\), Euler's totient \(\varphi(n)\) counts how many integers from \(1\) to \(n\) are coprime to \(n\). The task is to find the value of \(n \le 1{,}000{,}000\) that maximizes the ratio \(n/\varphi(n)\).
A brute-force scan over all integers is unnecessary. The decisive observation is that the ratio can be rewritten entirely in terms of the distinct prime divisors of \(n\), and that turns the search into a short product of consecutive primes.
The full derivation comes from Euler's product formula for the totient function and from a simple exchange argument on prime factors.
If
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
then the totient function satisfies
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
Therefore
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{1}{1-\frac{1}{p}}=\prod_{p\mid n}\frac{p}{p-1}.$$
This identity is the key invariant of the problem. The exponents \(a_i\) disappear completely, so the ratio depends only on which primes divide \(n\), not on how many times they divide it. For example, \(6=2\cdot 3\) and \(12=2^2\cdot 3\) both have ratio \(3\).
Because the ratio ignores multiplicities, increasing the exponent of an existing prime makes \(n\) larger without improving \(n/\varphi(n)\). That means an optimal value can always be chosen squarefree:
$$n=p_1p_2\cdots p_k.$$
Under the constraint \(n \le L\), spending part of the size budget on \(p^2,p^3,\dots\) is wasteful. It is always better to reserve that budget for introducing a new prime divisor, because a new prime contributes a fresh factor \(p/(p-1)\) greater than 1.
For primes \(p<q\), we have
$$\frac{p}{p-1} > \frac{q}{q-1}.$$
So smaller primes improve the ratio more than larger primes do. Suppose a squarefree candidate contains \(q\) but omits a smaller prime \(p\). Replace \(q\) by \(p\) and define
$$m=n\frac{p}{q}.$$
Then \(m<n\), while
$$\frac{m}{\varphi(m)}=\frac{n}{\varphi(n)}\cdot \frac{p/(p-1)}{q/(q-1)} > \frac{n}{\varphi(n)}.$$
So any maximizer that uses a larger prime must also use every smaller prime. The prime divisors of the optimum therefore form an initial segment of the primes:
$$2,3,5,7,\dots,p_k.$$
The product of the first \(k\) primes is called a primorial, so the answer is the largest primorial that does not exceed the limit.
Start from 1 and multiply consecutive primes:
$$2,\quad 2\cdot 3=6,\quad 6\cdot 5=30,\quad 30\cdot 7=210,\quad 210\cdot 11=2310,$$
$$2310\cdot 13=30030,\qquad 30030\cdot 17=510510,\qquad 510510\cdot 19=9699690.$$
The product through \(17\) is still below \(1{,}000{,}000\), but multiplying by \(19\) overshoots the bound. Therefore
$$\boxed{510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17}$$
is the maximizing value.
A smaller comparison shows why the proof works. Moving from \(6\) to \(12\) only increases the exponent of \(2\), so the ratio stays at \(3\). Moving from \(6\) to \(30\) introduces the new prime \(5\), so the ratio is multiplied by \(5/4\) and rises to \(15/4\).
The C++, Python, and Java implementations follow the proof directly instead of computing totients for every integer up to the limit. They first generate a short list of primes with a sieve. For the Project Euler bound, sieving up to \(100\) is more than enough, because the relevant prime chain stops at \(19\).
They then keep a running product and multiply by primes in increasing order. As soon as the next multiplication would exceed the chosen limit, the loop stops, and the current product is returned. At every stage that product is exactly the largest primorial still allowed by the bound.
The implementations also support a configurable limit and include a small checkpoint: when the limit is \(10\), the best value is \(6\). No totient table, divisor scan, or search over all candidates is needed, because the mathematics has already reduced the problem to a handful of prime multiplications.
Within this implementation, prime generation is done only up to \(100\), so the sieve cost is effectively constant, both in time and in memory. After that, the multiplication loop touches only the first few primes and stops once the next prime would cross the limit.
For the specific bound \(1{,}000{,}000\), the loop only needs the primes \(2,3,5,7,11,13,17,19\), so the overall computation is tiny. In practical terms, both runtime and memory usage are constant for this problem.
Für eine positive ganze Zahl \(n\) zählt Eulers Phi-Funktion \(\varphi(n)\), wie viele Zahlen von \(1\) bis \(n\) teilerfremd zu \(n\) sind. Gesucht ist der Wert von \(n \le 1{,}000{,}000\), für den das Verhältnis \(n/\varphi(n)\) maximal wird.
Ein vollständiges Durchprobieren aller Zahlen bis eine Million ist nicht nötig. Der entscheidende Punkt ist, dass sich das Verhältnis ausschließlich über die verschiedenen Primteiler von \(n\) ausdrücken lässt. Danach bleibt nur noch ein kurzes Produkt aufeinanderfolgender Primzahlen.
Die gesamte Herleitung beruht auf der Produktformel für die Totientfunktion und auf einem einfachen Austauschargument für Primfaktoren.
Ist
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
dann gilt
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
Also folgt
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{1}{1-\frac{1}{p}}=\prod_{p\mid n}\frac{p}{p-1}.$$
Das ist die zentrale Invariante der Aufgabe. Die Exponenten \(a_i\) verschwinden vollständig. Das Verhältnis hängt also nur davon ab, welche Primzahlen \(n\) teilen, nicht davon, mit welcher Potenz sie auftreten. Deshalb haben etwa \(6=2\cdot 3\) und \(12=2^2\cdot 3\) beide das Verhältnis \(3\).
Da Vielfachheiten im Verhältnis gar nicht vorkommen, vergrößert eine höhere Potenz eines bereits vorhandenen Primfaktors nur \(n\), ohne \(n/\varphi(n)\) zu verbessern. Ein Optimum kann daher immer quadratfrei gewählt werden:
$$n=p_1p_2\cdots p_k.$$
Unter der Schranke \(n \le L\) ist es also verschwendet, Größe in \(p^2,p^3,\dots\) zu investieren. Viel sinnvoller ist es, diese Größe für einen neuen Primteiler zu verwenden, denn jeder neue Primteiler liefert einen zusätzlichen Faktor \(p/(p-1)\), der größer als 1 ist.
Für Primzahlen \(p<q\) gilt
$$\frac{p}{p-1} > \frac{q}{q-1}.$$
Kleine Primzahlen verbessern das Verhältnis also stärker als große. Angenommen, eine quadratfreie Kandidatenzahl enthält \(q\), aber eine kleinere Primzahl \(p\) fehlt. Ersetze \(q\) durch \(p\) und setze
$$m=n\frac{p}{q}.$$
Dann ist \(m<n\), aber zugleich
$$\frac{m}{\varphi(m)}=\frac{n}{\varphi(n)}\cdot \frac{p/(p-1)}{q/(q-1)} > \frac{n}{\varphi(n)}.$$
Jeder Maximierer, der eine größere Primzahl benutzt, muss also auch alle kleineren benutzen. Die Primteiler des Optimums bilden deshalb ein Anfangsstück der Primzahlen:
$$2,3,5,7,\dots,p_k.$$
Das Produkt der ersten \(k\) Primzahlen heißt Primorial. Gesucht ist also das größte Primorial, das die Schranke nicht überschreitet.
Man beginnt bei 1 und multipliziert nacheinander mit Primzahlen:
$$2,\quad 2\cdot 3=6,\quad 6\cdot 5=30,\quad 30\cdot 7=210,\quad 210\cdot 11=2310,$$
$$2310\cdot 13=30030,\qquad 30030\cdot 17=510510,\qquad 510510\cdot 19=9699690.$$
Bis \(17\) bleibt das Produkt unter \(1{,}000{,}000\), mit \(19\) wird die Schranke überschritten. Daher ist
$$\boxed{510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17}$$
die gesuchte Zahl.
Ein kleineres Beispiel zeigt denselben Mechanismus. Von \(6\) zu \(12\) wird nur der Exponent von \(2\) erhöht, also bleibt das Verhältnis bei \(3\). Von \(6\) zu \(30\) kommt dagegen die neue Primzahl \(5\) hinzu, wodurch sich das Verhältnis mit \(5/4\) multipliziert und auf \(15/4\) steigt.
Die Implementierungen in C++, Python und Java folgen diesem Beweis direkt, anstatt Totienten für alle Zahlen bis zur Schranke zu berechnen. Zuerst erzeugen sie mit einem Sieb eine kurze Primzahlliste. Für die Project-Euler-Schranke reicht ein Sieb bis \(100\) mehr als aus, weil die relevante Kette bereits bei \(19\) endet.
Anschließend wird ein laufendes Produkt geführt, das der Reihe nach mit Primzahlen multipliziert wird. Sobald die nächste Multiplikation die gewählte Schranke überschreiten würde, stoppt die Schleife und gibt das aktuelle Produkt zurück. Dieses Produkt ist in jedem Moment genau das größte noch erlaubte Primorial.
Die Implementierungen unterstützen außerdem eine konfigurierbare Schranke und enthalten einen kleinen Kontrolltest: Für die Schranke \(10\) ist das beste Ergebnis \(6\). Eine Totienttabelle oder ein Durchlauf über alle Kandidaten ist nicht nötig, weil die Mathematik die Suche bereits auf wenige Primzahlmultiplikationen reduziert hat.
In dieser Lösung werden Primzahlen nur bis \(100\) erzeugt, daher ist der Aufwand des Siebs sowohl zeitlich als auch speicherseitig effektiv konstant. Danach betrachtet die Multiplikationsschleife nur die ersten wenigen Primzahlen und stoppt, sobald die nächste Primzahl die Schranke sprengen würde.
Für die konkrete Schranke \(1{,}000{,}000\) werden nur die Primzahlen \(2,3,5,7,11,13,17,19\) benötigt. Praktisch sind Laufzeit und Speicherverbrauch für diese Aufgabe also konstant.
Pozitif bir \(n\) tamsayısı için Euler totient fonksiyonu \(\varphi(n)\), \(1\) ile \(n\) arasındaki ve \(n\) ile aralarında asal olan sayıların sayısını verir. Soruda, \(n \le 1{,}000{,}000\) koşulu altında \(n/\varphi(n)\) oranını en büyük yapan \(n\) değeri istenir.
Bir milyona kadar bütün sayıları tek tek denemek gerekmiyor. Asıl fikir, bu oranın yalnızca \(n\)'in farklı asal bölenleri cinsinden yazılabilmesi ve böylece aramanın art arda asal sayıların kısa bir çarpımına indirgenmesidir.
Tüm çözüm, totient fonksiyonunun çarpım formülüne ve asal çarpanlar üzerinde yapılan basit bir değiş-tokuş argümanına dayanır.
Eğer
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
ise
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)$$
olur. Buradan
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{1}{1-\frac{1}{p}}=\prod_{p\mid n}\frac{p}{p-1}$$
elde edilir. Bu özdeşlik problemin temel değişmezidir. Üsler \(a_i\) tamamen yok olur; yani oran, bir asalın kaç kez geçtiğine değil, yalnızca hangi asalların \(n\)'i böldüğüne bağlıdır. Örneğin \(6=2\cdot 3\) ve \(12=2^2\cdot 3\) için oran aynı şekilde \(3\) olur.
Oran çoklukları görmediği için, mevcut bir asalın üssünü büyütmek \(n\)'i artırır ama \(n/\varphi(n)\) değerini yükseltmez. Bu yüzden en iyi aday her zaman karesiz seçilebilir:
$$n=p_1p_2\cdots p_k.$$
\(n \le L\) kısıtı altında \(p^2,p^3,\dots\) gibi kuvvetlere yer ayırmak boşa harcamadır. Aynı büyüklük bütçesini yeni bir asal bölen eklemek için kullanmak daha iyidir; çünkü yeni asal, orana \(p/(p-1)\) biçiminde 1'den büyük yeni bir çarpan kazandırır.
\(p<q\) olan asal sayılar için
$$\frac{p}{p-1} > \frac{q}{q-1}$$
geçerlidir. Yani küçük asallar oranı büyük asal sayılardan daha fazla iyileştirir. Şimdi karesiz bir adayın \(q\) asalını içerdiğini, ama ondan küçük bir \(p\) asalını içermediğini varsayalım. \(q\) yerine \(p\) yazıp
$$m=n\frac{p}{q}$$
tanımını yapalım. O zaman \(m<n\) olur ve aynı zamanda
$$\frac{m}{\varphi(m)}=\frac{n}{\varphi(n)}\cdot \frac{p/(p-1)}{q/(q-1)} > \frac{n}{\varphi(n)}$$
elde edilir. Demek ki daha büyük bir asalı kullanan her maksimum aday, ondan küçük bütün asalları da içermek zorundadır. Böylece optimumun asal bölenleri şu biçimde bir başlangıç parçası oluşturur:
$$2,3,5,7,\dots,p_k.$$
İlk \(k\) asalın çarpımına primorial denir. Dolayısıyla aranan cevap, sınırı aşmayan en büyük primorialdir.
1'den başlayıp ardışık asallarla çarpalım:
$$2,\quad 2\cdot 3=6,\quad 6\cdot 5=30,\quad 30\cdot 7=210,\quad 210\cdot 11=2310,$$
$$2310\cdot 13=30030,\qquad 30030\cdot 17=510510,\qquad 510510\cdot 19=9699690.$$
\(17\)'ye kadar olan çarpım hâlâ \(1{,}000{,}000\)'in altındadır; fakat \(19\) ile çarpınca sınır aşılır. Bu yüzden
$$\boxed{510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17}$$
maksimumu veren değerdir.
Daha küçük bir karşılaştırma, mantığı açıkça gösterir. \(6\)'dan \(12\)'ye geçmek yalnızca \(2\)'nin üssünü artırır; oran yine \(3\) kalır. Ama \(6\)'dan \(30\)'a geçmek yeni asal \(5\)'i ekler; bu da oranı \(5/4\) ile çarpar ve değeri \(15/4\)'e çıkarır.
C++, Python ve Java uygulamaları, tüm sayılar için totient hesaplamak yerine bu ispatı doğrudan uygular. Önce kısa bir asal listesi üretmek için bir elek kurarlar. Project Euler sınırı için \(100\)'e kadar elemek fazlasıyla yeterlidir; çünkü belirleyici asal zinciri zaten \(19\)'da durur.
Daha sonra artan sıradaki asallarla çarpılan bir yürüyen çarpım tutulur. Bir sonraki çarpım seçilen limiti aşacaksa döngü durur ve mevcut çarpım döndürülür. Her adımda bu değer, sınır altında kalan en büyük primorialdir.
Uygulamalar ayrıca ayarlanabilir bir üst sınır kabul eder ve küçük bir kontrol de içerir: limit \(10\) olduğunda en iyi değer \(6\) olmalıdır. Totient tablosu kurmaya, bölen taramaya veya tüm adayları denemeye gerek yoktur; çünkü matematik problemi zaten birkaç asal çarpımına indirmiştir.
Bu çözümde asal üretimi yalnızca \(100\)'e kadar yapıldığı için, eleğin zaman ve bellek maliyeti pratikte sabittir. Ardından gelen çarpım döngüsü sadece ilk birkaç asala bakar ve bir sonraki asal limiti aşınca durur.
Özel olarak \(1{,}000{,}000\) sınırı için yalnızca \(2,3,5,7,11,13,17,19\) asalları gerekir. Bu problemde çalışma süresi ve bellek kullanımı pratik olarak sabittir.
Para un entero positivo \(n\), la función totiente de Euler \(\varphi(n)\) cuenta cuántos enteros entre \(1\) y \(n\) son coprimos con \(n\). La tarea consiste en encontrar el valor de \(n \le 1{,}000{,}000\) que maximiza la razón \(n/\varphi(n)\).
No hace falta recorrer uno por uno todos los enteros hasta un millón. La observación decisiva es que la razón puede escribirse únicamente en función de los divisores primos distintos de \(n\), y eso reduce toda la búsqueda a un producto corto de primos consecutivos.
Toda la derivación se apoya en la fórmula producto de la función totiente y en un argumento de intercambio muy simple sobre los factores primos.
Si
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
entonces
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
Por tanto,
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{1}{1-\frac{1}{p}}=\prod_{p\mid n}\frac{p}{p-1}.$$
Esta es la invariante central del problema. Los exponentes \(a_i\) desaparecen por completo, así que la razón depende solo de qué primos dividen a \(n\), no de cuántas veces lo hacen. Por ejemplo, \(6=2\cdot 3\) y \(12=2^2\cdot 3\) tienen la misma razón, igual a \(3\).
Como la razón ignora las multiplicidades, aumentar el exponente de un primo que ya está presente hace crecer \(n\) sin mejorar \(n/\varphi(n)\). Por eso siempre se puede elegir un óptimo libre de cuadrados:
$$n=p_1p_2\cdots p_k.$$
Bajo la restricción \(n \le L\), gastar parte del tamaño permitido en \(p^2,p^3,\dots\) es un desperdicio. Es mejor reservar ese margen para introducir un primo nuevo, porque cada primo nuevo aporta un factor fresco \(p/(p-1)\) mayor que 1.
Si \(p<q\) son primos, entonces
$$\frac{p}{p-1} > \frac{q}{q-1}.$$
Los primos pequeños mejoran la razón más que los grandes. Supongamos ahora que un candidato libre de cuadrados contiene \(q\), pero no contiene un primo menor \(p\). Sustituyamos \(q\) por \(p\) y definamos
$$m=n\frac{p}{q}.$$
Entonces \(m<n\), mientras que
$$\frac{m}{\varphi(m)}=\frac{n}{\varphi(n)}\cdot \frac{p/(p-1)}{q/(q-1)} > \frac{n}{\varphi(n)}.$$
Así, cualquier máximo que use un primo grande también debe usar todos los primos más pequeños. Los divisores primos del óptimo forman por tanto un segmento inicial de la sucesión de primos:
$$2,3,5,7,\dots,p_k.$$
El producto de los primeros \(k\) primos se llama primorial. En consecuencia, la respuesta es el mayor primorial que no supera el límite.
Partimos de 1 y multiplicamos por primos consecutivos:
$$2,\quad 2\cdot 3=6,\quad 6\cdot 5=30,\quad 30\cdot 7=210,\quad 210\cdot 11=2310,$$
$$2310\cdot 13=30030,\qquad 30030\cdot 17=510510,\qquad 510510\cdot 19=9699690.$$
El producto hasta \(17\) sigue estando por debajo de \(1{,}000{,}000\), pero al multiplicar por \(19\) ya se supera la cota. Por lo tanto,
$$\boxed{510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17}$$
es el valor que maximiza la razón.
Una comparación pequeña muestra el mismo mecanismo. Pasar de \(6\) a \(12\) solo aumenta el exponente de \(2\), así que la razón sigue siendo \(3\). Pasar de \(6\) a \(30\) introduce el primo nuevo \(5\), de modo que la razón se multiplica por \(5/4\) y sube hasta \(15/4\).
Las implementaciones en C++, Python y Java siguen exactamente esta prueba en lugar de calcular \(\varphi(n)\) para todos los enteros hasta el límite. Primero generan una lista corta de primos mediante un tamiz. Para la cota de Project Euler, tamizar hasta \(100\) es más que suficiente, porque la cadena relevante de primos ya se detiene en \(19\).
Después mantienen un producto acumulado y lo van multiplicando por primos en orden creciente. En cuanto la siguiente multiplicación superaría el límite elegido, el bucle se detiene y devuelve el producto actual. En cada instante, ese producto es precisamente el mayor primorial permitido por la cota.
Las implementaciones también aceptan un límite configurable e incluyen una comprobación pequeña: cuando el límite es \(10\), el mejor valor debe ser \(6\). No hace falta construir una tabla de totientes, recorrer divisores ni explorar todos los candidatos, porque la matemática ya redujo el problema a unas pocas multiplicaciones de primos.
En esta solución, la generación de primos solo llega hasta \(100\), por lo que el costo del tamiz es, en la práctica, constante tanto en tiempo como en memoria. Después, el bucle de multiplicación examina solo los primeros pocos primos y termina cuando el siguiente haría rebasar el límite.
Para la cota concreta \(1{,}000{,}000\), únicamente intervienen los primos \(2,3,5,7,11,13,17,19\). En términos prácticos, el tiempo de ejecución y la memoria son constantes para este problema.
对于正整数 \(n\)，欧拉函数 \(\varphi(n)\) 表示区间 \(1\) 到 \(n\) 中与 \(n\) 互质的整数个数。题目要求在 \(n \le 1{,}000{,}000\) 的条件下，找出使比值 \(n/\varphi(n)\) 最大的那个 \(n\)。
这道题并不需要把一百万以内的所有整数逐个检查。关键在于：这个比值可以完全改写成只和 \(n\) 的不同素因子有关的形式。一旦看清这一点，搜索就从大范围枚举压缩成了连续素数的短乘积。
整个推导建立在欧拉函数的乘积公式之上，同时再配合一个关于素因子的交换论证。
如果
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
那么欧拉函数满足
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
于是立刻得到
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{1}{1-\frac{1}{p}}=\prod_{p\mid n}\frac{p}{p-1}.$$
这就是本题最核心的不变量。指数 \(a_i\) 在公式里完全消失了，因此比值只和哪些素数整除 \(n\) 有关，而和这些素数出现多少次无关。比如 \(6=2\cdot 3\) 与 \(12=2^2\cdot 3\) 的比值都等于 \(3\)。
由于比值根本不看重数，提高某个已经出现的素数的指数，只会让 \(n\) 变大，却不会提高 \(n/\varphi(n)\)。因此最优解总可以取成平方自由数：
$$n=p_1p_2\cdots p_k.$$
在 \(n \le L\) 这一限制下，把规模预算浪费在 \(p^2,p^3,\dots\) 上是没有意义的。更好的做法是用同样的预算去引入一个新的素因子，因为每引入一个新素数，目标比值都会额外乘上一个大于 1 的因子 \(p/(p-1)\)。
对于两个素数 \(p<q\)，有
$$\frac{p}{p-1} > \frac{q}{q-1}.$$
这说明小素数对比值的提升比大素数更强。现在设某个平方自由候选数包含素数 \(q\)，却没有包含更小的素数 \(p\)。把 \(q\) 换成 \(p\)，定义
$$m=n\frac{p}{q}.$$
那么 \(m<n\)，同时还有
$$\frac{m}{\varphi(m)}=\frac{n}{\varphi(n)}\cdot \frac{p/(p-1)}{q/(q-1)} > \frac{n}{\varphi(n)}.$$
也就是说，如果一个最大化候选已经用到了较大的素数，那么它就不可能漏掉任何更小的素数。于是最优解的素因子一定构成素数序列的一个前缀：
$$2,3,5,7,\dots,p_k.$$
前 \(k\) 个素数的乘积通常称为 primorial，因此本题的答案就是不超过上界的最大 primorial。
从 1 开始，依次乘上连续素数：
$$2,\quad 2\cdot 3=6,\quad 6\cdot 5=30,\quad 30\cdot 7=210,\quad 210\cdot 11=2310,$$
$$2310\cdot 13=30030,\qquad 30030\cdot 17=510510,\qquad 510510\cdot 19=9699690.$$
乘到 \(17\) 为止还没有超过 \(1{,}000{,}000\)，但再乘上下一个素数 \(19\) 就会越界。因此最大值对应的整数就是
$$\boxed{510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17}.$$
再看一个更小的比较也能看出同样的规律。把 \(6\) 变成 \(12\)，只是把素数 \(2\) 的指数从 1 提高到 2，所以比值仍然是 \(3\)。而把 \(6\) 变成 \(30\) 时，引入了新的素数 \(5\)，比值就会额外乘上 \(5/4\)，从 \(3\) 提升到 \(15/4\)。
C++、Python 和 Java 的实现都直接照着上面的数学结论来做，而不是对每个整数都显式计算一次欧拉函数。它们先用筛法生成一小段素数表。对于 Project Euler 这道题的上界来说，筛到 \(100\) 已经绰绰有余，因为真正会用到的关键素数链在 \(19\) 就结束了。
随后，程序维护一个滚动乘积，按从小到大的顺序依次乘上素数。一旦发现再乘下一个素数就会超过给定上界，循环立即停止，当前乘积就是答案。因为在整个过程中，这个乘积始终都是仍然不超界的最大 primorial。
这些实现还支持可配置的上界，并带有一个很小的自检：当上界是 \(10\) 时，最优值应该是 \(6\)。由于数学证明已经把问题压缩成几次素数乘法，所以根本不需要建立 totient 表、扫描所有因子，或者遍历所有候选整数。
在这份实现里，筛素数只做到 \(100\)，因此筛法的时间和空间成本在实际中都可以视为常数。之后的乘法循环只会访问前几个素数，并在下一个素数即将使乘积超界时停止。
对本题的 \(1{,}000{,}000\) 上界来说，程序真正涉及的只有 \(2,3,5,7,11,13,17,19\) 这些素数。因此在实际意义上，这道题的运行时间和内存消耗都是常数量级。
Для положительного целого числа \(n\) функция Эйлера \(\varphi(n)\) считает, сколько чисел от \(1\) до \(n\) взаимно просты с \(n\). Требуется найти такое \(n \le 1{,}000{,}000\), для которого отношение \(n/\varphi(n)\) максимально.
Полный перебор всех чисел до миллиона здесь не нужен. Ключевое наблюдение состоит в том, что это отношение можно выразить только через различные простые делители числа \(n\). После этого задача сводится к короткому произведению последовательных простых чисел.
Вся цепочка рассуждений опирается на произведение Эйлера для функции \(\varphi\) и на простое перестановочное рассуждение для простых множителей.
Если
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
то
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
Следовательно,
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{1}{1-\frac{1}{p}}=\prod_{p\mid n}\frac{p}{p-1}.$$
Это главный инвариант задачи. Показатели \(a_i\) полностью исчезают, так что отношение определяется только тем, какие простые делители входят в \(n\), а не тем, с какими степенями они входят. Например, у чисел \(6=2\cdot 3\) и \(12=2^2\cdot 3\) отношение одинаково и равно \(3\).
Раз отношение не зависит от кратности простого делителя, увеличение степени уже присутствующего простого числа лишь увеличивает \(n\), не улучшая \(n/\varphi(n)\). Поэтому оптимум всегда можно выбрать квадратсвободным:
$$n=p_1p_2\cdots p_k.$$
При ограничении \(n \le L\) тратить часть допустимого размера на \(p^2,p^3,\dots\) бессмысленно. Намного лучше использовать этот запас на новый простой делитель, потому что каждый новый простой множитель добавляет в целевое отношение новый множитель \(p/(p-1)\), который больше 1.
Для простых \(p<q\) выполняется
$$\frac{p}{p-1} > \frac{q}{q-1}.$$
То есть меньшие простые улучшают отношение сильнее, чем большие. Предположим, что некоторый квадратсвободный кандидат содержит \(q\), но не содержит меньший простой \(p\). Заменим \(q\) на \(p\) и определим
$$m=n\frac{p}{q}.$$
Тогда \(m<n\), а также
$$\frac{m}{\varphi(m)}=\frac{n}{\varphi(n)}\cdot \frac{p/(p-1)}{q/(q-1)} > \frac{n}{\varphi(n)}.$$
Значит, любой максимизатор, в котором встречается более крупный простой, обязан содержать и все меньшие простые. Следовательно, простые делители оптимума образуют начальный отрезок последовательности простых:
$$2,3,5,7,\dots,p_k.$$
Произведение первых \(k\) простых называется примориалом. Поэтому ответом является наибольший примориал, не превосходящий заданный предел.
Начнем с 1 и будем последовательно умножать на простые числа:
$$2,\quad 2\cdot 3=6,\quad 6\cdot 5=30,\quad 30\cdot 7=210,\quad 210\cdot 11=2310,$$
$$2310\cdot 13=30030,\qquad 30030\cdot 17=510510,\qquad 510510\cdot 19=9699690.$$
Произведение до \(17\) еще не превосходит \(1{,}000{,}000\), а умножение на следующий простой \(19\) уже выводит нас за предел. Поэтому
$$\boxed{510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17}$$
и есть искомое число.
Тот же механизм виден на меньших примерах. Переход от \(6\) к \(12\) лишь увеличивает степень простого числа \(2\), поэтому отношение остается равным \(3\). А переход от \(6\) к \(30\) вводит новый простой \(5\), и отношение дополнительно умножается на \(5/4\), поднимаясь до \(15/4\).
Реализации на C++, Python и Java напрямую следуют этому доказательству, вместо того чтобы вычислять значения \(\varphi(n)\) для всех чисел до предела. Сначала они строят короткий список простых чисел с помощью решета. Для границы из задачи Project Euler решета до \(100\) более чем достаточно, потому что существенная цепочка простых заканчивается уже на \(19\).
После этого поддерживается текущее произведение, которое по очереди умножается на простые числа в возрастающем порядке. Как только следующее умножение должно превысить выбранный предел, цикл останавливается и возвращает текущее значение. На каждом шаге это значение и есть наибольший примориал, еще допустимый по условию.
Реализации также принимают настраиваемую верхнюю границу и содержат небольшую проверку: при пределе \(10\) правильным ответом должно быть \(6\). Ни таблица значений функции Эйлера, ни перебор делителей, ни просмотр всех кандидатов не нужны, потому что математика уже сократила задачу до нескольких умножений простых чисел.
В этой реализации простые числа генерируются только до \(100\), поэтому стоимость решета по времени и памяти на практике постоянна. Затем цикл умножения рассматривает лишь первые несколько простых и заканчивается, как только следующий простой превысит границу.
Для конкретного предела \(1{,}000{,}000\) реально используются только простые числа \(2,3,5,7,11,13,17,19\). Поэтому в практическом смысле и время работы, и расход памяти для этой задачи постоянны.
بالنسبة إلى عدد صحيح موجب \(n\)، فإن دالة أويلر \(\varphi(n)\) تحسب عدد الأعداد من \(1\) إلى \(n\) التي تكون أولية نسبيًا مع \(n\). المطلوب هو إيجاد قيمة \(n \le 1{,}000{,}000\) التي تجعل النسبة \(n/\varphi(n)\) أكبر ما يمكن.
لا حاجة إلى فحص كل الأعداد حتى مليون واحدًا واحدًا. الفكرة الحاسمة هي أن هذه النسبة يمكن كتابتها بالكامل بدلالة القواسم الأولية المختلفة لـ \(n\) فقط، وعندها تتحول المسألة إلى حاصل ضرب قصير لأعداد أولية متتالية.
يعتمد الاشتقاق كله على صيغة أويلر الضربية لدالة \(\varphi\)، وعلى حجة استبدال بسيطة بين العوامل الأولية.
إذا كان
$$n=\prod_{i=1}^{k} p_i^{a_i},$$
فإن
$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$
ومن ثم
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{1}{1-\frac{1}{p}}=\prod_{p\mid n}\frac{p}{p-1}.$$
هذه هي الفكرة الثابتة الأساسية في المسألة. الأسس \(a_i\) تختفي تمامًا من الصيغة، ولذلك فالنسبة لا تعتمد إلا على معرفة أي الأعداد الأولية تقسم \(n\)، ولا تعتمد على عدد مرات ظهور كل واحد منها. ولهذا نجد مثلًا أن \(6=2\cdot 3\) و\(12=2^2\cdot 3\) يعطيان النسبة نفسها، وهي \(3\).
بما أن النسبة لا ترى التكرارات، فإن زيادة أس عدد أولي موجود بالفعل تجعل \(n\) أكبر من غير أن تحسن \(n/\varphi(n)\). لذلك يمكن دائمًا اختيار حل أمثل خاليًا من المربعات:
$$n=p_1p_2\cdots p_k.$$
تحت القيد \(n \le L\)، فإن صرف جزء من حجم العدد على \(p^2,p^3,\dots\) لا يحقق أي فائدة. الأفضل هو استخدام هذا المجال لإدخال قاسم أولي جديد، لأن كل عدد أولي جديد يضيف عاملًا جديدًا من الشكل \(p/(p-1)\) وهو أكبر من 1.
إذا كان \(p<q\) عددين أوليين، فإن
$$\frac{p}{p-1} > \frac{q}{q-1}.$$
وهذا يعني أن العدد الأولي الأصغر يحسن النسبة أكثر من العدد الأولي الأكبر. لنفترض الآن أن مرشحًا خاليًا من المربعات يحتوي على \(q\) لكنه لا يحتوي على عدد أولي أصغر منه هو \(p\). لنستبدل \(q\) بـ \(p\)، ولنعرف
$$m=n\frac{p}{q}.$$
عندئذٍ يكون \(m<n\)، وفي الوقت نفسه
$$\frac{m}{\varphi(m)}=\frac{n}{\varphi(n)}\cdot \frac{p/(p-1)}{q/(q-1)} > \frac{n}{\varphi(n)}.$$
إذن أي قيمة تعطي الحد الأقصى وتستخدم عددًا أوليًا أكبر، لا بد أن تستخدم أيضًا كل الأعداد الأولية الأصغر منه. ومن ثم فإن القواسم الأولية للحل الأمثل تشكل مقطعًا ابتدائيًا من متتالية الأعداد الأولية:
$$2,3,5,7,\dots,p_k.$$
وحاصل ضرب أول \(k\) أعداد أولية يسمى primorial. لذلك فالإجابة هي أكبر primorial لا يتجاوز الحد المعطى.
نبدأ من 1 ونضرب تباعًا في الأعداد الأولية المتتالية:
$$2,\quad 2\cdot 3=6,\quad 6\cdot 5=30,\quad 30\cdot 7=210,\quad 210\cdot 11=2310,$$
$$2310\cdot 13=30030,\qquad 30030\cdot 17=510510,\qquad 510510\cdot 19=9699690.$$
يظل حاصل الضرب حتى \(17\) أقل من \(1{,}000{,}000\)، لكن الضرب في \(19\) يتجاوز الحد مباشرة. لذلك تكون القيمة المثلى هي
$$\boxed{510510=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17}.$$
ويمكن رؤية الفكرة نفسها على مثال أصغر. الانتقال من \(6\) إلى \(12\) لا يضيف عددًا أوليًا جديدًا، بل يزيد فقط أس \(2\)، لذلك تبقى النسبة \(3\). أما الانتقال من \(6\) إلى \(30\) فيضيف العدد الأولي \(5\)، فتُضرب النسبة في \(5/4\) وتصبح \(15/4\).
تتبع تطبيقات C++ وPython وJava هذا البرهان مباشرة بدلًا من حساب \(\varphi(n)\) لكل عدد حتى الحد الأعلى. فهي تبدأ أولًا بتوليد قائمة قصيرة من الأعداد الأولية باستخدام منخل. وبالنسبة إلى حد Project Euler، فإن التوليد حتى \(100\) أكثر من كافٍ، لأن السلسلة الحاسمة تتوقف عند \(19\).
بعد ذلك تحتفظ الشيفرة بحاصل ضرب جارٍ، وتضربه في الأعداد الأولية بترتيب تصاعدي. وما إن يصبح الضرب في العدد الأولي التالي متجاوزًا للحد المختار، حتى تتوقف الحلقة ويُعاد حاصل الضرب الحالي. وفي كل مرحلة يكون هذا الحاصل هو أكبر primorial ما زال مسموحًا به تحت القيد.
كما تدعم التطبيقات حدًا علويًا قابلًا للتغيير، وتحتوي على فحص صغير أيضًا: عندما يكون الحد \(10\)، يجب أن تكون أفضل قيمة هي \(6\). لا حاجة إلى بناء جدول totient، ولا إلى فحص جميع القواسم أو جميع المرشحين، لأن التحليل الرياضي اختزل المسألة إلى بضع عمليات ضرب فقط.
في هذا الحل لا يُولَّد من الأعداد الأولية إلا ما يصل إلى \(100\)، ولهذا تكون كلفة المنخل في الزمن والذاكرة ثابتة عمليًا. وبعد ذلك لا تمر حلقة الضرب إلا على عدد قليل جدًا من الأعداد الأولية قبل أن تتوقف عند أول تجاوز للحد.
وعند الحد المحدد \(1{,}000{,}000\)، لا يلزم فعليًا سوى الأعداد الأولية \(2,3,5,7,11,13,17,19\). لذلك فإن زمن التنفيذ واستهلاك الذاكرة في هذه المسألة ثابتان من الناحية العملية.