For Carmichael's function \(\lambda(m)\), define
$$\mathcal L(n)=\max\{m:\lambda(m) \lt n\}+1.$$
The goal is to find the last nine digits of \(\mathcal L(2\cdot 10^7)\). A direct search over \(m\) is hopelessly large, so the implementation works in the reverse direction: it searches over promising values of a target \(t\) with \(1\le t\lt n\), and for each such \(t\) constructs the largest integer whose Carmichael value divides \(t\).
For a fixed integer \(t\ge 1\), let
$$M(t)=\max\{m:\lambda(m)\mid t\}.$$
Then the original problem becomes
$$\mathcal L(n)-1=\max_{1\le t\lt n} M(t).$$
This reformulation is valid because every integer \(m\) with \(\lambda(m)\lt n\) appears when we choose \(t=\lambda(m)\), and conversely every \(m\) counted by \(M(t)\) satisfies \(\lambda(m)\mid t\lt n\), hence \(\lambda(m)\lt n\).
The construction starts from the standard formulas for prime powers. For an odd prime \(p\),
$$\lambda(p^a)=p^{a-1}(p-1).$$
For powers of \(2\),
$$\lambda(2)=1,\qquad \lambda(4)=2,\qquad \lambda(2^a)=2^{a-2}\quad (a\ge 3).$$
If
$$m=\prod_i p_i^{a_i},$$
then Carmichael's function combines these local contributions by least common multiple:
$$\lambda(m)=\operatorname{lcm}\bigl(\lambda(p_1^{a_1}),\lambda(p_2^{a_2}),\dots\bigr).$$
So the entire problem reduces to understanding which prime powers may occur when \(\lambda(m)\) is forced to divide a chosen value \(t\).
Assume \(p\) is odd and \(p^a\parallel m\). If \(\lambda(m)\mid t\), then in particular
$$\lambda(p^a)=p^{a-1}(p-1)\mid t.$$
Because \(p\) and \(p-1\) are coprime, this forces the two independent divisibility conditions
$$p-1\mid t,\qquad p^{a-1}\mid t.$$
Hence the exponent \(a\) cannot exceed
$$a\le v_p(t)+1,$$
where \(v_p(t)\) is the exponent of \(p\) in the factorization of \(t\). Therefore an odd prime \(p\) can appear at all only when \(p-1\mid t\), and when it does appear its largest admissible power is
$$p^{v_p(t)+1}.$$
This already explains a key feature of the search: divisors of \(t\) of the form \(p-1\) generate possible prime factors \(p\) of the maximizing integer.
The prime \(2\) is different because its Carmichael values do not follow the odd-prime formula. If \(t\) is odd, then \(\lambda(2)=1\mid t\) but \(\lambda(4)=2\nmid t\), so the largest allowed power of \(2\) is just \(2^1\).
If \(v_2(t)=r\ge 1\), then from \(\lambda(2^a)=2^{a-2}\) for \(a\ge 3\) we obtain
$$2^{a-2}\mid t\iff a\le r+2.$$
So the largest admissible exponent of \(2\) is
$$a_2(t)= \begin{cases} 1,& v_2(t)=0,\\ v_2(t)+2,& v_2(t)\ge 1. \end{cases}$$
This is why the implementation always inserts a power of \(2\) first and treats it separately from the odd primes.
Combining the odd-prime rule with the special \(2\)-power rule gives
$$M(t)=2^{a_2(t)}\prod_{\substack{p\text{ odd prime}\\p-1\mid t}} p^{v_p(t)+1}.$$
The code evaluates the same formula in a divisor-based form. Since the condition \(p-1\mid t\) is equivalent to saying that \(d=p-1\) is a divisor of \(t\), we can rewrite it as
$$M(t)=2^{a_2(t)}\prod_{\substack{d\mid t\\d+1\text{ prime}\\d+1\gt 2}} (d+1)^{v_{d+1}(t)+1}.$$
This is exactly why divisor generation is central: each divisor \(d\) gives one potential prime \(d+1\), and if that number is prime it contributes a whole prime power to the product.
The formula for \(M(t)\) shows two ways to make it large.
First, \(t\) should have many divisors, because every divisor \(d\) is a chance that \(d+1\) is prime. Second, \(t\) should contain small prime factors with reasonably large exponents, because the term \(v_p(t)+1\) can raise already-admissible primes to higher powers.
For that reason, the implementation does not scan every integer below \(n\). Instead, it explores a structured family of candidates built from small primes with nonincreasing exponents. This is the same pattern that appears in highly composite style searches: it strongly favors numbers with rich divisor structure, which are exactly the values of \(t\) most likely to maximize \(M(t)\).
To illustrate the method, take \(n=6\). Then we must maximize \(M(t)\) over \(1\le t\lt 6\).
For \(t=1\), only the factor \(2\) is possible, so \(M(1)=2\).
For \(t=2\), we have \(a_2(2)=3\), and the divisor \(2\) yields the prime \(3\). Therefore
$$M(2)=2^3\cdot 3=24.$$
For \(t=3\), there is again no odd prime with \(p-1\mid 3\) except \(p=2\), so \(M(3)=2\).
For \(t=4\), we have \(a_2(4)=4\), and the divisors \(2\) and \(4\) yield the primes \(3\) and \(5\). Hence
$$M(4)=2^4\cdot 3\cdot 5=240.$$
For \(t=5\), no new odd prime appears, so \(M(5)=2\). The maximum is therefore \(240\), which means
$$\mathcal L(6)=240+1=241.$$
This is the small checkpoint verified by the implementations before they tackle the full input.
The C++, Python, and Java implementations all follow the same pipeline. They first build a primality sieve up to \(n\), because every tested number has the form \(d+1\) with \(d\lt t\lt n\).
Next they generate candidate values of \(t\) by depth-first search over products of small primes with nonincreasing exponents and with \(t\lt n\). During this search they keep the factorization of the current candidate, so every divisor of \(t\) can later be reconstructed efficiently.
For one candidate \(t\), the implementation enumerates all divisors of \(t\), starts with the special \(2\)-power contribution, and then checks each number \(d+1\). If \(d+1\) is prime, the corresponding prime power \((d+1)^{v_{d+1}(t)+1}\) is multiplied into the current value of \(M(t)\).
The true integers involved are enormous, so the implementations store two parallel views of each candidate: a logarithmic score for accurate comparison of magnitudes, and the value modulo \(10^9\) for the requested last nine digits. After the best candidate has been found, they return
$$\bigl(\max M(t)+1\bigr)\bmod 10^9,$$
with leading zeros preserved in the final output format when necessary.
Let \(n\) be the input bound, and let \(S\) be the structured set of \(t\)-candidates explored by the search. Building the primality sieve up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory.
For one candidate \(t\), if \(\tau(t)\) denotes its number of divisors, then generating all divisors and scanning them costs \(O(\tau(t))\) time and \(O(\tau(t))\) temporary space. The remaining work per divisor is small: a primality lookup, a short factor-exponent query, a modular exponentiation with a tiny exponent, and one logarithmic accumulation.
Therefore the overall running time is
$$O\left(n\log\log n+\sum_{t\in S}\tau(t)\right),$$
and the memory usage is
$$O\left(n+\max_{t\in S}\tau(t)\right).$$
In practice the dominant cost is not modular arithmetic but the number of divisor-rich candidates explored by the depth-first search.
Für die Carmichael-Funktion \(\lambda(m)\) sei
$$\mathcal L(n)=\max\{m:\lambda(m) \lt n\}+1.$$
Gesucht sind die letzten neun Ziffern von \(\mathcal L(2\cdot 10^7)\). Eine direkte Suche über \(m\) ist viel zu groß. Deshalb arbeitet die Lösung rückwärts: Sie betrachtet vielversprechende Werte \(t\) mit \(1\le t\lt n\) und konstruiert für jedes solche \(t\) die größte Zahl, deren Carmichael-Wert \(t\) teilt.
Für ein festes \(t\ge 1\) definieren wir
$$M(t)=\max\{m:\lambda(m)\mid t\}.$$
Dann gilt
$$\mathcal L(n)-1=\max_{1\le t\lt n} M(t).$$
Das ist korrekt, weil jedes \(m\) mit \(\lambda(m)\lt n\) beim Wert \(t=\lambda(m)\) erfasst wird. Umgekehrt erfüllt jedes von \(M(t)\) erzeugte \(m\) die Bedingung \(\lambda(m)\mid t\lt n\) und damit automatisch \(\lambda(m)\lt n\).
Der Ausgangspunkt sind die Standardformeln für Primzahlpotenzen. Für eine ungerade Primzahl \(p\) gilt
$$\lambda(p^a)=p^{a-1}(p-1).$$
Für Zweierpotenzen gilt
$$\lambda(2)=1,\qquad \lambda(4)=2,\qquad \lambda(2^a)=2^{a-2}\quad (a\ge 3).$$
Ist
$$m=\prod_i p_i^{a_i},$$
dann kombiniert sich die Carmichael-Funktion über das kgV der lokalen Beiträge:
$$\lambda(m)=\operatorname{lcm}\bigl(\lambda(p_1^{a_1}),\lambda(p_2^{a_2}),\dots\bigr).$$
Damit ist das Problem auf die Frage reduziert, welche Primzahlpotenzen in \(m\) vorkommen dürfen, wenn \(\lambda(m)\) ein festes \(t\) teilen soll.
Sei \(p\) ungerade und \(p^a\parallel m\). Aus \(\lambda(m)\mid t\) folgt insbesondere
$$\lambda(p^a)=p^{a-1}(p-1)\mid t.$$
Da \(p\) und \(p-1\) teilerfremd sind, zerfällt das in die beiden Bedingungen
$$p-1\mid t,\qquad p^{a-1}\mid t.$$
Also kann der Exponent \(a\) höchstens
$$a\le v_p(t)+1$$
sein. Eine ungerade Primzahl \(p\) darf also genau dann auftreten, wenn \(p-1\) ein Teiler von \(t\) ist; im Maximum trägt sie dann die Potenz
$$p^{v_p(t)+1}$$
bei. Das erklärt bereits, warum Teiler von \(t\) so wichtig sind: Jeder Teiler der Form \(p-1\) kann einen neuen Primfaktor \(p\) erzeugen.
Für \(p=2\) gilt die ungerade Primzahlformel nicht. Ist \(t\) ungerade, dann ist \(\lambda(2)=1\mid t\), aber \(\lambda(4)=2\nmid t\). In diesem Fall ist also nur \(2^1\) erlaubt.
Ist dagegen \(v_2(t)=r\ge 1\), dann folgt aus \(\lambda(2^a)=2^{a-2}\) für \(a\ge 3\)
$$2^{a-2}\mid t\iff a\le r+2.$$
Der maximale Zweierexponent lautet damit
$$a_2(t)= \begin{cases} 1,& v_2(t)=0,\\ v_2(t)+2,& v_2(t)\ge 1. \end{cases}$$
Deshalb behandelt die Implementierung die Zweierpotenz immer separat und fügt sie vor allen ungeraden Primzahlen ein.
Setzt man die Regel für ungerade Primzahlen mit der Sonderregel für \(2\) zusammen, erhält man
$$M(t)=2^{a_2(t)}\prod_{\substack{p\text{ ungerade Primzahl}\\p-1\mid t}} p^{v_p(t)+1}.$$
Die Implementierung benutzt dieselbe Aussage in einer teilerbasierten Form. Denn \(p-1\mid t\) ist äquivalent dazu, dass \(d=p-1\) ein Teiler von \(t\) ist. Also
$$M(t)=2^{a_2(t)}\prod_{\substack{d\mid t\\d+1\text{ prim}\\d+1\gt 2}} (d+1)^{v_{d+1}(t)+1}.$$
Genau deshalb werden für jedes \(t\) alle Teiler erzeugt und die Zahlen \(d+1\) auf Primzahl-Eigenschaft geprüft.
Die Formel für \(M(t)\) zeigt zwei Hebel, um große Werte zu erhalten.
Erstens soll \(t\) viele Teiler besitzen, denn jeder Teiler \(d\) ist eine Gelegenheit dafür, dass \(d+1\) prim ist. Zweitens soll \(t\) kleine Primfaktoren mit nennenswerten Exponenten besitzen, weil der Term \(v_p(t)+1\) bereits zugelassene Primzahlen auf höhere Potenzen anheben kann.
Darum enumeriert die Implementierung nicht alle Zahlen unterhalb von \(n\). Stattdessen durchsucht sie eine strukturierte Familie aus Produkten kleiner Primzahlen mit nichtzunehmenden Exponenten. Das ist genau das Muster hochteilerreicher Zahlen und konzentriert die Suche auf jene \(t\), die realistisch \(M(t)\) maximieren können.
Zur Veranschaulichung betrachten wir \(n=6\). Dann ist \(M(t)\) für alle \(1\le t\lt 6\) zu maximieren.
Für \(t=1\) ist nur der Faktor \(2\) möglich, also \(M(1)=2\).
Für \(t=2\) gilt \(a_2(2)=3\), und der Teiler \(2\) liefert die Primzahl \(3\). Also
$$M(2)=2^3\cdot 3=24.$$
Für \(t=3\) gibt es außer \(2\) keine ungerade Primzahl mit \(p-1\mid 3\), daher \(M(3)=2\).
Für \(t=4\) gilt \(a_2(4)=4\), und die Teiler \(2\) sowie \(4\) liefern die Primzahlen \(3\) und \(5\). Daher
$$M(4)=2^4\cdot 3\cdot 5=240.$$
Für \(t=5\) entsteht keine neue ungerade Primzahl, also \(M(5)=2\). Das Maximum ist somit \(240\), also
$$\mathcal L(6)=240+1=241.$$
Genau dieser kleine Kontrollwert wird von den Implementierungen vor der eigentlichen Rechnung überprüft.
Die C++-, Python- und Java-Implementierungen benutzen denselben Ablauf. Zuerst bauen sie ein Primzahlsieb bis \(n\) auf, denn jede geprüfte Zahl hat die Form \(d+1\) mit \(d\lt t\lt n\).
Anschließend werden Kandidaten \(t\) per Tiefensuche erzeugt: als Produkte kleiner Primzahlen mit nichtzunehmenden Exponenten und unter der Nebenbedingung \(t\lt n\). Während dieser Suche bleibt die Primfaktorzerlegung des aktuellen Kandidaten erhalten, sodass sich daraus später die komplette Teilerliste effizient rekonstruieren lässt.
Für ein fixes \(t\) enumeriert die Implementierung alle Teiler, setzt zuerst den Beitrag der Zweierpotenz und prüft dann jede Zahl \(d+1\). Ist \(d+1\) prim, so wird die zugehörige Potenz \((d+1)^{v_{d+1}(t)+1}\) in den aktuellen Wert von \(M(t)\) eingemultipliziert.
Da die echten Zahlen sehr groß werden, speichert die Implementierung jeden Kandidaten auf zwei Arten: als logarithmischen Wert zum sicheren Größenvergleich und parallel dazu modulo \(10^9\), um die letzten neun Ziffern zu behalten. Am Ende wird
$$\bigl(\max M(t)+1\bigr)\bmod 10^9$$
ausgegeben, bei Bedarf mit führenden Nullen formatiert.
Sei \(n\) die Schranke der Aufgabe und \(S\) die von der Suche erzeugte strukturierte Kandidatenmenge. Das Primzahlsieb bis \(n\) benötigt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher.
Für einen Kandidaten \(t\) mit \(\tau(t)\) Teilern kostet das Erzeugen und Durchlaufen aller Teiler \(O(\tau(t))\) Zeit und \(O(\tau(t))\) temporären Speicher. Die restliche Arbeit pro Teiler ist klein: ein Primzahl-Lookup, eine kurze Exponentenabfrage aus der Faktorisierung, eine modulare Potenz mit kleinem Exponenten und eine Logarithmus-Akkumulation.
Damit ist die Gesamtlaufzeit
$$O\left(n\log\log n+\sum_{t\in S}\tau(t)\right),$$
und der Speicherbedarf beträgt
$$O\left(n+\max_{t\in S}\tau(t)\right).$$
In der Praxis dominiert also nicht die Modulo-Arithmetik, sondern die Anzahl der teilerreichen Kandidaten, die von der Tiefensuche untersucht werden.
Carmichael fonksiyonu \(\lambda(m)\) için
$$\mathcal L(n)=\max\{m:\lambda(m) \lt n\}+1$$
tanımlanır. Amaç, \(\mathcal L(2\cdot 10^7)\) değerinin son dokuz basamağını bulmaktır. \(m\) üzerinde doğrudan arama yapmak gerçek sınırlar için imkansız olduğundan, çözüm ters yönden gider: \(1\le t\lt n\) olacak umut verici hedef değerler seçilir ve her \(t\) için Carmichael değeri \(t\)'yi bölen en büyük sayı kurulur.
Sabit bir \(t\ge 1\) için
$$M(t)=\max\{m:\lambda(m)\mid t\}$$
tanımını yapalım. O zaman
$$\mathcal L(n)-1=\max_{1\le t\lt n} M(t)$$
olur. Bunun nedeni şudur: \(\lambda(m)\lt n\) koşulunu sağlayan her \(m\), \(t=\lambda(m)\) seçilince bu maksimumun içinde yer alır. Ters yönde, \(M(t)\) ile elde edilen her sayı için \(\lambda(m)\mid t\lt n\) olduğundan yine \(\lambda(m)\lt n\) geçerlidir.
Başlangıç noktası asal kuvvetler için standart formüllerdir. Tek bir tek asal \(p\) için
$$\lambda(p^a)=p^{a-1}(p-1).$$
\(2\) kuvvetlerinde ise
$$\lambda(2)=1,\qquad \lambda(4)=2,\qquad \lambda(2^a)=2^{a-2}\quad (a\ge 3).$$
Eğer
$$m=\prod_i p_i^{a_i}$$
ise, Carmichael fonksiyonu yerel katkıları EKOK ile birleştirir:
$$\lambda(m)=\operatorname{lcm}\bigl(\lambda(p_1^{a_1}),\lambda(p_2^{a_2}),\dots\bigr).$$
Dolayısıyla mesele, sabit bir \(t\) için hangi asal kuvvetlerin \(m\) içine girebileceğini belirlemeye indirgenir.
\(p\) tek asal olsun ve \(p^a\parallel m\) varsayalım. \(\lambda(m)\mid t\) ise özellikle
$$\lambda(p^a)=p^{a-1}(p-1)\mid t$$
olmalıdır. \(p\) ile \(p-1\) aralarında asal olduğundan bu, iki ayrı koşula ayrılır:
$$p-1\mid t,\qquad p^{a-1}\mid t.$$
Buna göre üs için üst sınır
$$a\le v_p(t)+1$$
olur. Demek ki tek bir asal \(p\), ancak \(p-1\) sayısı \(t\)'nin böleni ise ortaya çıkabilir; ortaya çıktığında da en büyük katkısı
$$p^{v_p(t)+1}$$
şeklindedir. Böylece neden \(t\)'nin bölenlerine bakıldığını da görmüş oluruz: \(p-1\) biçimindeki bölenler yeni bir asal \(p\) üretir.
\(p=2\) için formül farklıdır. Eğer \(t\) tek ise \(\lambda(2)=1\mid t\) olur, ama \(\lambda(4)=2\nmid t\) olduğu için izin verilen en büyük \(2\) kuvveti sadece \(2^1\)'dir.
Eğer \(v_2(t)=r\ge 1\) ise, \(a\ge 3\) için \(\lambda(2^a)=2^{a-2}\) bağıntısından
$$2^{a-2}\mid t\iff a\le r+2$$
elde edilir. Bu nedenle izin verilen en büyük \(2\) üssü
$$a_2(t)= \begin{cases} 1,& v_2(t)=0,\\ v_2(t)+2,& v_2(t)\ge 1 \end{cases}$$
olur. Uygulama da bu yüzden önce \(2\)-kuvvetini ekler ve tek asalları daha sonra işler.
Tek asallar için bulunan kuralı \(2\) özel durumu ile birleştirince
$$M(t)=2^{a_2(t)}\prod_{\substack{p\text{ tek asal}\\p-1\mid t}} p^{v_p(t)+1}$$
elde edilir. Kod aynı bağıntıyı bölenler üzerinden uygular. Çünkü \(p-1\mid t\) demek, \(d=p-1\) sayısının \(t\)'nin bir böleni olması demektir. Böylece
$$M(t)=2^{a_2(t)}\prod_{\substack{d\mid t\\d+1\text{ asal}\\d+1\gt 2}} (d+1)^{v_{d+1}(t)+1}$$
şeklinde de yazabiliriz. Kodun her aday \(t\) için tüm bölenleri üretip \(d+1\) sayısını asal testiyle kontrol etmesinin nedeni tam olarak budur.
\(M(t)\) formülü büyük değere ulaşmanın iki ana yolunu gösterir.
Birincisi, \(t\) çok bölenli olmalıdır; çünkü her bölen \(d\), \(d+1\)'in asal olma ihtimali üzerinden yeni bir asal çarpan doğurabilir. İkincisi, \(t\) küçük asalların makul üslerini taşımalıdır; çünkü \(v_p(t)+1\) terimi, zaten izinli olan asalların kuvvetini büyütür.
Bu yüzden uygulama \(n\)'den küçük her sayıyı tek tek denemez. Bunun yerine, küçük asalların azalmayan değil azalan veya eşit üs düzeniyle kurulan yapılandırılmış bir aday ailesini DFS ile dolaşır. Bu desen, çok bölenli sayılarda görülen klasik yapıdır ve tam da büyük \(M(t)\) üretme potansiyeli en yüksek değerleri hedefler.
Yöntemi göstermek için \(n=6\) alalım. Bu durumda \(1\le t\lt 6\) için \(M(t)\) değerlerinin en büyüğünü arıyoruz.
\(t=1\) için yalnızca \(2\) mümkündür, dolayısıyla \(M(1)=2\).
\(t=2\) için \(a_2(2)=3\) olur ve bölen \(2\), asal \(3\)'ü üretir. O halde
$$M(2)=2^3\cdot 3=24.$$
\(t=3\) için \(p-1\mid 3\) koşulunu sağlayan yeni bir tek asal çıkmaz, bu yüzden \(M(3)=2\).
\(t=4\) için \(a_2(4)=4\) olur; bölenler \(2\) ve \(4\), sırasıyla \(3\) ve \(5\) asallarını verir. Dolayısıyla
$$M(4)=2^4\cdot 3\cdot 5=240.$$
\(t=5\) için yine yeni bir tek asal gelmez, yani \(M(5)=2\). Maksimum değer \(240\) olduğundan
$$\mathcal L(6)=240+1=241$$
bulunur. Bu değer, tam girişe geçmeden önce uygulamanın doğruladığı küçük kontroldür.
C++, Python ve Java uygulamalarının üçü de aynı akışı izler. Önce \(n\)'ye kadar bir asal süzgeci kurulur; çünkü test edilen tüm sayılar \(d\lt t\lt n\) olacak şekilde \(d+1\) biçimindedir.
Daha sonra aday \(t\) değerleri, küçük asalların azalmayan değil azalan üs düzeniyle kurulan çarpımları olarak derinlik öncelikli aramayla üretilir ve her zaman \(t\lt n\) koşulu korunur. Arama sırasında mevcut adayın asal çarpanlara ayrılışı elde tutulduğu için, sonradan bu adayın tüm bölenleri verimli biçimde üretilebilir.
Sabit bir \(t\) için uygulama önce tüm bölenleri çıkarır, ardından özel \(2\)-kuvvet katkısını ekler ve her \(d+1\) sayısını asal olup olmadığı açısından sınar. Eğer \(d+1\) asal ise, ilgili kuvvet \((d+1)^{v_{d+1}(t)+1}\) o adayın \(M(t)\) değerine çarpılır.
Gerçek sayılar çok büyüdüğü için uygulama her adayı iki farklı görünümle taşır: büyüklük karşılaştırması için logaritmik değer ve istenen son dokuz basamak için \(10^9\) modundaki değer. Arama bittiğinde
$$\bigl(\max M(t)+1\bigr)\bmod 10^9$$
döndürülür; gerekirse çıktı baştaki sıfırlar korunarak biçimlendirilir.
\(n\) giriş sınırı, \(S\) ise DFS'nin gezdiği yapılandırılmış aday kümesi olsun. \(n\)'ye kadar asal süzgeci kurmak \(O(n\log\log n)\) zaman ve \(O(n)\) bellek gerektirir.
\(t\) adayının bölen sayısı \(\tau(t)\) ise, tüm bölenleri üretmek ve dolaşmak \(O(\tau(t))\) zaman ve \(O(\tau(t))\) geçici bellek ister. Bölen başına kalan iş küçüktür: asal sorgusu, kısa bir üs sorgusu, küçük üslerle modüler üs alma ve bir log toplamı.
Bu nedenle toplam çalışma süresi
$$O\left(n\log\log n+\sum_{t\in S}\tau(t)\right),$$
toplam bellek kullanımı ise
$$O\left(n+\max_{t\in S}\tau(t)\right)$$
olur. Pratikte asıl maliyet modüler aritmetik değil, DFS'nin incelediği çok bölenli aday sayısıdır.
Para la función de Carmichael \(\lambda(m)\), se define
$$\mathcal L(n)=\max\{m:\lambda(m) \lt n\}+1.$$
Hay que obtener los últimos nueve dígitos de \(\mathcal L(2\cdot 10^7)\). Buscar directamente sobre \(m\) es inviable, así que la solución trabaja hacia atrás: toma valores candidatos \(t\) con \(1\le t\lt n\) y, para cada uno, construye el mayor entero cuyo valor de Carmichael divide a \(t\).
Para un entero fijo \(t\ge 1\), definimos
$$M(t)=\max\{m:\lambda(m)\mid t\}.$$
Entonces el problema original se reescribe como
$$\mathcal L(n)-1=\max_{1\le t\lt n} M(t).$$
La equivalencia es inmediata: cualquier \(m\) con \(\lambda(m)\lt n\) aparece al elegir \(t=\lambda(m)\), y a la inversa todo entero contado por \(M(t)\) cumple \(\lambda(m)\mid t\lt n\), luego también satisface \(\lambda(m)\lt n\).
El punto de partida son las fórmulas estándar sobre potencias primas. Para un primo impar \(p\),
$$\lambda(p^a)=p^{a-1}(p-1).$$
Para las potencias de \(2\),
$$\lambda(2)=1,\qquad \lambda(4)=2,\qquad \lambda(2^a)=2^{a-2}\quad (a\ge 3).$$
Si
$$m=\prod_i p_i^{a_i},$$
entonces la función de Carmichael combina esas contribuciones locales mediante el mínimo común múltiplo:
$$\lambda(m)=\operatorname{lcm}\bigl(\lambda(p_1^{a_1}),\lambda(p_2^{a_2}),\dots\bigr).$$
Por tanto, todo el problema se reduce a decidir qué potencias primas pueden aparecer en \(m\) cuando imponemos \(\lambda(m)\mid t\).
Supongamos que \(p\) es impar y que \(p^a\parallel m\). Si \(\lambda(m)\mid t\), entonces en particular
$$\lambda(p^a)=p^{a-1}(p-1)\mid t.$$
Como \(p\) y \(p-1\) son coprimos, esto obliga a cumplir las dos condiciones
$$p-1\mid t,\qquad p^{a-1}\mid t.$$
Así, el exponente \(a\) no puede exceder
$$a\le v_p(t)+1,$$
donde \(v_p(t)\) denota la valuación de \(p\) en la factorización de \(t\). En consecuencia, un primo impar \(p\) solo puede aparecer cuando \(p-1\mid t\), y su mayor contribución posible es
$$p^{v_p(t)+1}.$$
Esto explica por qué los divisores de \(t\) son tan importantes: los divisores de la forma \(p-1\) generan nuevos primos candidatos \(p\).
El primo \(2\) debe tratarse aparte. Si \(t\) es impar, entonces \(\lambda(2)=1\mid t\), pero \(\lambda(4)=2\nmid t\), de modo que la mayor potencia admisible es solamente \(2^1\).
Si \(v_2(t)=r\ge 1\), entonces usando \(\lambda(2^a)=2^{a-2}\) para \(a\ge 3\) obtenemos
$$2^{a-2}\mid t\iff a\le r+2.$$
Por ello, el exponente máximo permitido de \(2\) es
$$a_2(t)= \begin{cases} 1,& v_2(t)=0,\\ v_2(t)+2,& v_2(t)\ge 1. \end{cases}$$
Esta es la razón por la que la implementación empieza siempre incorporando la potencia de \(2\) y la separa del tratamiento de los primos impares.
Uniendo la regla de los primos impares con la regla especial de \(2\), se llega a
$$M(t)=2^{a_2(t)}\prod_{\substack{p\text{ primo impar}\\p-1\mid t}} p^{v_p(t)+1}.$$
El programa evalúa exactamente la misma expresión en forma basada en divisores. Como \(p-1\mid t\) equivale a decir que \(d=p-1\) es un divisor de \(t\), también podemos escribir
$$M(t)=2^{a_2(t)}\prod_{\substack{d\mid t\\d+1\text{ primo}\\d+1\gt 2}} (d+1)^{v_{d+1}(t)+1}.$$
Por eso la enumeración de divisores es central: cada divisor \(d\) produce un candidato \(d+1\), y si ese número es primo aporta toda una potencia prima al producto final.
La fórmula de \(M(t)\) muestra dos maneras de hacerlo crecer.
Primero, conviene que \(t\) tenga muchos divisores, porque cada divisor \(d\) es una oportunidad de que \(d+1\) sea primo. Segundo, conviene que \(t\) tenga factores primos pequeños con exponentes apreciables, porque el término \(v_p(t)+1\) permite elevar aún más las potencias primas ya admisibles.
Por eso las implementaciones no recorren todos los enteros menores que \(n\). En su lugar, exploran una familia estructurada de candidatos formada por productos de primos pequeños con exponentes no crecientes. Es el patrón típico de los números muy ricos en divisores y concentra la búsqueda justo en los valores de \(t\) con más posibilidades de maximizar \(M(t)\).
Tomemos \(n=6\). Debemos maximizar \(M(t)\) para \(1\le t\lt 6\).
Para \(t=1\), solo puede aparecer el factor \(2\), de modo que \(M(1)=2\).
Para \(t=2\), se tiene \(a_2(2)=3\), y el divisor \(2\) genera el primo \(3\). Por tanto
$$M(2)=2^3\cdot 3=24.$$
Para \(t=3\), no aparece ningún primo impar nuevo con \(p-1\mid 3\), así que \(M(3)=2\).
Para \(t=4\), se tiene \(a_2(4)=4\), y los divisores \(2\) y \(4\) generan los primos \(3\) y \(5\). Entonces
$$M(4)=2^4\cdot 3\cdot 5=240.$$
Para \(t=5\), no surge ningún primo impar adicional, luego \(M(5)=2\). El máximo es \(240\), así que
$$\mathcal L(6)=240+1=241.$$
Ese es precisamente el pequeño valor de control que verifican las implementaciones antes de resolver la instancia grande.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero construyen una criba de primalidad hasta \(n\), porque todos los números que se ponen a prueba tienen la forma \(d+1\) con \(d\lt t\lt n\).
Después generan candidatos \(t\) mediante una búsqueda en profundidad sobre productos de primos pequeños con exponentes no crecientes y con la restricción \(t\lt n\). Durante esa búsqueda se conserva la factorización del candidato actual, lo que permite reconstruir todos sus divisores de manera eficiente.
Para un \(t\) fijo, la implementación enumera todos sus divisores, incorpora primero la contribución especial de la potencia de \(2\) y luego examina cada número \(d+1\). Si \(d+1\) es primo, se multiplica la potencia correspondiente \((d+1)^{v_{d+1}(t)+1}\) dentro del valor actual de \(M(t)\).
Como los enteros verdaderos son enormes, las implementaciones almacenan dos representaciones de cada candidato: una puntuación logarítmica para comparar tamaños con seguridad y el valor módulo \(10^9\) para conservar exactamente los últimos nueve dígitos. Al final devuelven
$$\bigl(\max M(t)+1\bigr)\bmod 10^9,$$
formateado con ceros iniciales cuando hace falta.
Sea \(n\) la cota de entrada y \(S\) el conjunto estructurado de candidatos \(t\) explorados por la búsqueda. La criba de primalidad hasta \(n\) cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria.
Para un candidato \(t\), si \(\tau(t)\) es su número de divisores, generar y recorrer todos esos divisores cuesta \(O(\tau(t))\) tiempo y \(O(\tau(t))\) espacio temporal. El trabajo restante por divisor es pequeño: una consulta a la criba, una búsqueda corta del exponente en la factorización, una potenciación modular con exponente pequeño y una suma logarítmica.
Por tanto, el tiempo total es
$$O\left(n\log\log n+\sum_{t\in S}\tau(t)\right),$$
y el uso total de memoria es
$$O\left(n+\max_{t\in S}\tau(t)\right).$$
En la práctica, el coste dominante no es la aritmética modular, sino el número de candidatos ricos en divisores que la búsqueda en profundidad llega a examinar.
对 Carmichael 函数 \(\lambda(m)\)，定义
$$\mathcal L(n)=\max\{m:\lambda(m) \lt n\}+1.$$
题目要求求出 \(\mathcal L(2\cdot 10^7)\) 的后九位。若直接枚举 \(m\)，规模会大得无法接受，因此实现采用“反向构造”的思路：不直接猜 \(m\)，而是枚举满足 \(1\le t\lt n\) 的一些有希望的目标值 \(t\)，并对每个 \(t\) 构造满足 \(\lambda(m)\mid t\) 的最大整数。
对固定的 \(t\ge 1\)，定义
$$M(t)=\max\{m:\lambda(m)\mid t\}.$$
那么原问题就变成
$$\mathcal L(n)-1=\max_{1\le t\lt n} M(t).$$
这个改写是完全合理的。因为任意满足 \(\lambda(m)\lt n\) 的整数 \(m\)，在取 \(t=\lambda(m)\) 时一定会被覆盖；反过来，凡是计入 \(M(t)\) 的整数都满足 \(\lambda(m)\mid t\lt n\)，所以同样必然满足 \(\lambda(m)\lt n\)。换句话说，我们可以先研究“给定一个可整除目标 \(t\) 时，最大能拼出多大的 \(m\)”这个问题，再对所有 \(t\lt n\) 取最大值。
关键起点是 Carmichael 函数在素数幂上的标准表达式。对奇素数 \(p\)，有
$$\lambda(p^a)=p^{a-1}(p-1).$$
对 \(2\) 的幂，情况稍有不同：
$$\lambda(2)=1,\qquad \lambda(4)=2,\qquad \lambda(2^a)=2^{a-2}\quad (a\ge 3).$$
如果
$$m=\prod_i p_i^{a_i},$$
那么整体的 Carmichael 值由各个局部值取最小公倍数得到：
$$\lambda(m)=\operatorname{lcm}\bigl(\lambda(p_1^{a_1}),\lambda(p_2^{a_2}),\dots\bigr).$$
因此，问题的核心不在于直接计算大量 \(\lambda(m)\)，而在于反过来分析：若要求 \(\lambda(m)\) 整除某个给定的 \(t\)，那么 \(m\) 的各个素数幂最多可以取到多大。
设 \(p\) 是奇素数，并且 \(p^a\parallel m\)。若要求 \(\lambda(m)\mid t\)，那么至少要有
$$\lambda(p^a)=p^{a-1}(p-1)\mid t.$$
由于 \(p\) 与 \(p-1\) 互素，这等价于两条彼此独立的条件：
$$p-1\mid t,\qquad p^{a-1}\mid t.$$
于是指数 \(a\) 受到上界
$$a\le v_p(t)+1$$
的限制，其中 \(v_p(t)\) 表示 \(t\) 的素因子分解里 \(p\) 的指数。因此，一个奇素数 \(p\) 只有在 \(p-1\mid t\) 时才可能出现在最大化的 \(m\) 中；一旦可以出现，它能贡献的最大幂次就是
$$p^{v_p(t)+1}.$$
这一步揭示了为什么“枚举 \(t\) 的所有约数”如此关键：每个形如 \(p-1\) 的约数都可能对应出一个可用的素数 \(p\)。
素数 \(2\) 不能直接套用奇素数公式。如果 \(t\) 是奇数，那么 \(\lambda(2)=1\mid t\)，但 \(\lambda(4)=2\nmid t\)，所以此时 \(m\) 中最多只能放入 \(2^1\)。
如果 \(v_2(t)=r\ge 1\)，则由 \(a\ge 3\) 时的公式 \(\lambda(2^a)=2^{a-2}\) 可知
$$2^{a-2}\mid t\iff a\le r+2.$$
因此，\(2\) 在最大乘积中可取到的最高指数为
$$a_2(t)= \begin{cases} 1,& v_2(t)=0,\\ v_2(t)+2,& v_2(t)\ge 1. \end{cases}$$
这也是实现里总是先单独放入一个 \(2\) 的贡献，再去处理奇素数的原因。
把奇素数的规则和 \(2\) 的特殊规则合在一起，就得到
$$M(t)=2^{a_2(t)}\prod_{\substack{p\text{ 为奇素数}\\p-1\mid t}} p^{v_p(t)+1}.$$
实现中采用的是完全等价的“约数视角”。因为 \(p-1\mid t\) 等价于存在约数 \(d=p-1\) 且 \(d\mid t\)，所以还可以写成
$$M(t)=2^{a_2(t)}\prod_{\substack{d\mid t\\d+1\text{ 为素数}\\d+1\gt 2}} (d+1)^{v_{d+1}(t)+1}.$$
这条公式几乎就是代码本身的数学版描述：先生成 \(t\) 的全部约数，对每个约数 \(d\) 检查 \(d+1\) 是否是素数；如果是，就把对应的素数幂乘进去。
从 \(M(t)\) 的公式可以直接看出两种增大结果的方法。
第一，\(t\) 应该有很多约数，因为每个约数 \(d\) 都给了 \(d+1\) 成为素数的机会，也就给了结果中新增一个素因子的机会。第二，\(t\) 里应该带有一些小素数的较高指数，因为 \(v_p(t)+1\) 会把已经允许出现的素数 \(p\) 再往更高次方提升。
因此，实现并没有暴力扫描所有小于 \(n\) 的整数，而是只搜索一种非常有针对性的候选形状：由小素数构成、指数按非增顺序排列的乘积。这正是“高约数密度”数常见的结构，和高度合成数的构造思路非常接近。对于本题，这种结构化搜索能够集中火力检查最有希望把 \(M(t)\) 做大的那些 \(t\)。
用一个很小的例子来看整个过程。取 \(n=6\)，那么只需比较 \(1\le t\lt 6\) 的 \(M(t)\)。
当 \(t=1\) 时，只能放入 \(2\)，所以 \(M(1)=2\)。
当 \(t=2\) 时，有 \(a_2(2)=3\)，并且约数 \(2\) 给出素数 \(3\)，因此
$$M(2)=2^3\cdot 3=24.$$
当 \(t=3\) 时，没有新的奇素数满足 \(p-1\mid 3\)，所以 \(M(3)=2\)。
当 \(t=4\) 时，有 \(a_2(4)=4\)，而约数 \(2\) 和 \(4\) 分别对应素数 \(3\) 与 \(5\)，于是
$$M(4)=2^4\cdot 3\cdot 5=240.$$
当 \(t=5\) 时，也不会产生新的奇素数，所以 \(M(5)=2\)。综上最大值是 \(240\)，因此
$$\mathcal L(6)=240+1=241.$$
这正是实现中用于自检的小样例结果。
C++、Python 和 Java 三个实现采用的是同一套流程。第一步是建立到 \(n\) 为止的素数筛，因为所有被测试的数都形如 \(d+1\)，其中 \(d\lt t\lt n\)。
第二步是用深度优先搜索生成候选 \(t\)。这些候选并不是任意整数，而是小素数乘积，并且指数按照非增顺序排列，同时始终保持 \(t\lt n\)。搜索过程中会一直保留当前候选的素因子分解，这样之后就能高效地重建出它的全部约数。
对某个固定的 \(t\)，实现先枚举所有约数，先加入 \(2\) 的特殊贡献，然后对每个约数 \(d\) 检查 \(d+1\) 是否为素数。若 \(d+1\) 是素数，就把 \((d+1)^{v_{d+1}(t)+1}\) 乘到当前候选值里，也就是把公式中的对应因子真正落实到计算中。
由于真正的整数会变得极大，实现并不会只保存一个普通整数值，而是同时维护两种表示方式：一种是对数和，用来稳定地比较不同候选谁更大；另一种是模 \(10^9\) 的值，用来最终输出后九位。搜索结束后返回
$$\bigl(\max M(t)+1\bigr)\bmod 10^9,$$
必要时再补前导零，使输出始终是九位格式。
设输入上界为 \(n\)，深度优先搜索真正访问到的候选集合为 \(S\)。构建到 \(n\) 的素数筛需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间。
对一个候选 \(t\)，若其约数个数为 \(\tau(t)\)，那么生成并扫描全部约数需要 \(O(\tau(t))\) 时间和 \(O(\tau(t))\) 的临时空间。每个约数上的其余工作都比较轻量：一次筛表查询、一次很短的指数读取、一次小指数模幂，以及一次对数累加。
因此总时间复杂度为
$$O\left(n\log\log n+\sum_{t\in S}\tau(t)\right),$$
总空间复杂度为
$$O\left(n+\max_{t\in S}\tau(t)\right).$$
实际运行中，主导成本并不是模运算，而是深度优先搜索究竟要检查多少个“约数很多”的候选 \(t\)。
Для функции Кармайкла \(\lambda(m)\) задаётся
$$\mathcal L(n)=\max\{m:\lambda(m) \lt n\}+1.$$
Нужно найти последние девять цифр числа \(\mathcal L(2\cdot 10^7)\). Прямой перебор по \(m\) здесь нереалистичен, поэтому решение идёт в обратную сторону: перебирает перспективные значения \(t\) с \(1\le t\lt n\) и для каждого такого \(t\) строит наибольшее число, у которого значение функции Кармайкла делит \(t\).
Для фиксированного \(t\ge 1\) введём
$$M(t)=\max\{m:\lambda(m)\mid t\}.$$
Тогда исходная задача переписывается в виде
$$\mathcal L(n)-1=\max_{1\le t\lt n} M(t).$$
Это эквивалентно исходному определению: всякое \(m\) с условием \(\lambda(m)\lt n\) появляется при выборе \(t=\lambda(m)\), а всякое число, учтённое в \(M(t)\), автоматически удовлетворяет \(\lambda(m)\mid t\lt n\), то есть тоже имеет \(\lambda(m)\lt n\).
Основа решения — стандартные формулы для степеней простых. Для нечётного простого \(p\) имеем
$$\lambda(p^a)=p^{a-1}(p-1).$$
Для степеней двойки действует особая формула:
$$\lambda(2)=1,\qquad \lambda(4)=2,\qquad \lambda(2^a)=2^{a-2}\quad (a\ge 3).$$
Если
$$m=\prod_i p_i^{a_i},$$
то общее значение \(\lambda(m)\) получается как НОК локальных вкладов:
$$\lambda(m)=\operatorname{lcm}\bigl(\lambda(p_1^{a_1}),\lambda(p_2^{a_2}),\dots\bigr).$$
Поэтому главная задача состоит в том, чтобы понять: при фиксированном \(t\) какие степени простых вообще могут входить в максимально возможное \(m\), если требуется \(\lambda(m)\mid t\).
Пусть \(p\) — нечётный простой и \(p^a\parallel m\). Если \(\lambda(m)\mid t\), то обязательно
$$\lambda(p^a)=p^{a-1}(p-1)\mid t.$$
Так как числа \(p\) и \(p-1\) взаимно просты, это равносильно двум независимым условиям
$$p-1\mid t,\qquad p^{a-1}\mid t.$$
Следовательно, показатель \(a\) ограничен сверху:
$$a\le v_p(t)+1,$$
где \(v_p(t)\) обозначает показатель простого \(p\) в разложении \(t\). Значит, нечётный простой \(p\) может появиться только тогда, когда \(p-1\) делит \(t\), и в этом случае его максимальный вклад равен
$$p^{v_p(t)+1}.$$
Именно отсюда возникает идея перебора делителей \(t\): делитель вида \(p-1\) автоматически указывает на допустимый простой множитель \(p\).
Для простого \(2\) формула отличается от нечётного случая. Если \(t\) нечётно, то \(\lambda(2)=1\mid t\), но \(\lambda(4)=2\nmid t\), поэтому максимально возможна лишь степень \(2^1\).
Если \(v_2(t)=r\ge 1\), то из формулы \(\lambda(2^a)=2^{a-2}\) при \(a\ge 3\) следует
$$2^{a-2}\mid t\iff a\le r+2.$$
Следовательно, максимальный показатель двойки равен
$$a_2(t)= \begin{cases} 1,& v_2(t)=0,\\ v_2(t)+2,& v_2(t)\ge 1. \end{cases}$$
Именно поэтому в реализации вклад степени двойки обрабатывается первым и отдельно от всех нечётных простых.
Объединяя правило для нечётных простых с особым правилом для \(2\), получаем
$$M(t)=2^{a_2(t)}\prod_{\substack{p\text{ — нечётный простой}\\p-1\mid t}} p^{v_p(t)+1}.$$
В программе та же идея реализована в эквивалентной форме через делители. Так как условие \(p-1\mid t\) равносильно тому, что \(d=p-1\) является делителем \(t\), можно записать
$$M(t)=2^{a_2(t)}\prod_{\substack{d\mid t\\d+1\text{ простое}\\d+1\gt 2}} (d+1)^{v_{d+1}(t)+1}.$$
Именно поэтому для каждого кандидата \(t\) строится полный список делителей, а затем проверяется простота всех чисел вида \(d+1\).
Формула для \(M(t)\) сразу показывает два способа сделать результат большим.
Во-первых, \(t\) должно иметь много делителей, потому что каждый делитель \(d\) даёт шанс, что число \(d+1\) окажется простым и добавит новый множитель в итоговое произведение. Во-вторых, \(t\) выгодно иметь разложение с небольшими простыми и достаточно большими показателями, потому что множитель \(v_p(t)+1\) позволяет повысить степень уже допустимых простых.
Поэтому реализации не перебирают все числа меньше \(n\). Вместо этого они обходят структурированное семейство кандидатов, состоящих из произведений малых простых с невозрастающими показателями. Это классический шаблон для чисел с очень большим количеством делителей и именно он концентрирует поиск на тех \(t\), которые реально способны максимизировать \(M(t)\).
Рассмотрим маленький пример с \(n=6\). Нужно максимизировать \(M(t)\) для всех \(1\le t\lt 6\).
При \(t=1\) возможен только множитель \(2\), значит \(M(1)=2\).
При \(t=2\) имеем \(a_2(2)=3\), а делитель \(2\) даёт простой \(3\). Поэтому
$$M(2)=2^3\cdot 3=24.$$
При \(t=3\) новых нечётных простых с условием \(p-1\mid 3\) не появляется, значит \(M(3)=2\).
При \(t=4\) получаем \(a_2(4)=4\), а делители \(2\) и \(4\) дают простые \(3\) и \(5\). Следовательно,
$$M(4)=2^4\cdot 3\cdot 5=240.$$
При \(t=5\) новых нечётных простых снова нет, так что \(M(5)=2\). Максимум равен \(240\), а значит
$$\mathcal L(6)=240+1=241.$$
Это именно тот контрольный пример, который реализации используют перед полной задачей.
Реализации на C++, Python и Java используют один и тот же алгоритм. Сначала строится решето простоты до \(n\), поскольку все проверяемые числа имеют вид \(d+1\) при \(d\lt t\lt n\).
Затем значения \(t\) генерируются поиском в глубину как произведения малых простых с невозрастающими показателями при условии \(t\lt n\). Во время этого поиска сохраняется факторизация текущего кандидата, так что затем из неё можно быстро восстановить полный список делителей.
Для фиксированного \(t\) программа перечисляет все делители, сначала добавляет особый вклад степени двойки, а затем рассматривает каждое число \(d+1\). Если \(d+1\) оказывается простым, соответствующая степень \((d+1)^{v_{d+1}(t)+1}\) умножается в текущее значение \(M(t)\).
Так как реальные числа получаются огромными, реализации ведут два представления каждого кандидата: логарифмическую оценку для корректного сравнения размеров и значение по модулю \(10^9\) для сохранения последних девяти цифр. После завершения поиска возвращается
$$\bigl(\max M(t)+1\bigr)\bmod 10^9,$$
причём при необходимости результат форматируется с ведущими нулями.
Пусть \(n\) — входная граница, а \(S\) — структурированное множество кандидатов \(t\), которое реально просматривает поиск. Построение решета до \(n\) требует \(O(n\log\log n)\) времени и \(O(n)\) памяти.
Для одного кандидата \(t\), если \(\tau(t)\) — число его делителей, то генерация и просмотр всех делителей занимает \(O(\tau(t))\) времени и \(O(\tau(t))\) временной памяти. Остальная работа на один делитель мала: одна проверка по решету, короткий запрос показателя простого, быстрое модульное возведение в степень и одно накопление логарифма.
Итоговая трудоёмкость равна
$$O\left(n\log\log n+\sum_{t\in S}\tau(t)\right),$$
а потребление памяти равно
$$O\left(n+\max_{t\in S}\tau(t)\right).$$
На практике основную цену платит не модульная арифметика, а количество богатых делителями кандидатов, которые успевает рассмотреть поиск в глубину.
لدالة كارمايكل \(\lambda(m)\) نعرّف
$$\mathcal L(n)=\max\{m:\lambda(m) \lt n\}+1.$$
المطلوب هو إيجاد آخر تسعة أرقام من \(\mathcal L(2\cdot 10^7)\). التعداد المباشر على قيم \(m\) غير عملي إطلاقًا، لذلك تعمل الخوارزمية بالعكس: تختار قيمًا مرشحة \(t\) بحيث \(1\le t\lt n\)، ثم تبني لكل \(t\) أكبر عدد ممكن يحقق الشرط \(\lambda(m)\mid t\).
لأي \(t\ge 1\) نعرّف
$$M(t)=\max\{m:\lambda(m)\mid t\}.$$
وعندئذ تصبح المسألة الأصلية
$$\mathcal L(n)-1=\max_{1\le t\lt n} M(t).$$
هذه الصياغة مكافئة تمامًا للتعريف الأصلي، لأن كل عدد \(m\) يحقق \(\lambda(m)\lt n\) يظهر تلقائيًا عندما نأخذ \(t=\lambda(m)\)، وبالعكس فإن كل عدد يدخل في \(M(t)\) يحقق \(\lambda(m)\mid t\lt n\)، ومن ثم يحقق أيضًا \(\lambda(m)\lt n\).
نقطة البداية هي الصيغ المعروفة لقوى الأعداد الأولية. إذا كان \(p\) أوليًا فرديًا فإن
$$\lambda(p^a)=p^{a-1}(p-1).$$
أما لقوى \(2\) فلدينا
$$\lambda(2)=1,\qquad \lambda(4)=2,\qquad \lambda(2^a)=2^{a-2}\quad (a\ge 3).$$
وإذا كان
$$m=\prod_i p_i^{a_i},$$
فإن قيمة \(\lambda(m)\) الكلية تتكوّن بأخذ المضاعف المشترك الأصغر للقيم المحلية:
$$\lambda(m)=\operatorname{lcm}\bigl(\lambda(p_1^{a_1}),\lambda(p_2^{a_2}),\dots\bigr).$$
إذًا جوهر المسألة هو تحديد أي قوى أولية يمكن أن تدخل في أكبر \(m\) ممكن عندما نفرض أن \(\lambda(m)\) تقسم قيمة ثابتة \(t\).
افترض أن \(p\) أولي فردي وأن \(p^a\parallel m\). إذا كان \(\lambda(m)\mid t\)، فلابد خصوصًا من تحقق
$$\lambda(p^a)=p^{a-1}(p-1)\mid t.$$
وبما أن \(p\) و\(p-1\) أوليان فيما بينهما، فإن هذا الشرط ينفصل إلى شرطين مستقلين:
$$p-1\mid t,\qquad p^{a-1}\mid t.$$
ومن ثم لا يمكن أن يتجاوز الأس \(a\) القيمة
$$a\le v_p(t)+1,$$
حيث \(v_p(t)\) هو أس \(p\) في تحليل \(t\). لذلك لا يظهر الأولي الفردي \(p\) أصلًا إلا إذا كان \(p-1\) قاسمًا لـ \(t\)، وإذا ظهر فإن أكبر مساهمة له هي
$$p^{v_p(t)+1}.$$
وهنا تظهر أهمية قواسم \(t\): فكل قاسم من الشكل \(p-1\) يستطيع أن يولّد عاملًا أوليًا جديدًا \(p\) في العدد الأعظمي المطلوب.
الأولي \(2\) لا يتبع القاعدة نفسها. فإذا كان \(t\) فرديًا فإن \(\lambda(2)=1\mid t\)، ولكن \(\lambda(4)=2\nmid t\)، ولذلك لا يُسمح إلا بالقوة \(2^1\).
أما إذا كان \(v_2(t)=r\ge 1\)، فإن الصيغة \(\lambda(2^a)=2^{a-2}\) عندما \(a\ge 3\) تعطي
$$2^{a-2}\mid t\iff a\le r+2.$$
إذن أكبر أس مسموح به للعدد \(2\) هو
$$a_2(t)= \begin{cases} 1,& v_2(t)=0,\\ v_2(t)+2,& v_2(t)\ge 1. \end{cases}$$
ولهذا تبدأ الخوارزمية دائمًا بإضافة مساهمة قوة \(2\) على نحو منفصل قبل فحص بقية الأعداد الأولية الفردية.
عند جمع قاعدة الأعداد الأولية الفردية مع الحالة الخاصة لـ \(2\) نحصل على
$$M(t)=2^{a_2(t)}\prod_{\substack{p\text{ odd prime}\\p-1\mid t}} p^{v_p(t)+1}.$$
وتستخدم الشيفرات الصيغة نفسها ولكن بصياغة تعتمد على القواسم. فشرط \(p-1\mid t\) مكافئ لوجود قاسم \(d=p-1\) من قواسم \(t\)، ولذلك يمكن كتابة
$$M(t)=2^{a_2(t)}\prod_{\substack{d\mid t\\d+1\text{ prime}\\d+1\gt 2}} (d+1)^{v_{d+1}(t)+1}.$$
وهذا يفسر مباشرة لماذا تقوم الخوارزمية بتوليد جميع قواسم \(t\) ثم اختبار ما إذا كان \(d+1\) عددًا أوليًا: فكل قاسم ناجح يضيف قوة أولية كاملة إلى حاصل الضرب.
تكشف صيغة \(M(t)\) عن طريقتين لزيادة القيمة النهائية.
الأولى أن يكون لـ \(t\) عدد كبير من القواسم، لأن كل قاسم \(d\) يمثل فرصة لأن يكون \(d+1\) أوليًا، وبالتالي فرصة لإضافة عامل أولي جديد. والثانية أن يحتوي \(t\) على قوى جيدة من الأعداد الأولية الصغيرة، لأن الحد \(v_p(t)+1\) يسمح برفع القوى المسموح بها إلى مراتب أعلى.
لهذا السبب لا تفحص الشيفرات كل عدد أصغر من \(n\). بدلًا من ذلك، تستكشف عائلة منظمة من المرشحين مبنية من أعداد أولية صغيرة وبأسس غير متزايدة. هذا هو النمط المعتاد للأعداد ذات الكثافة العالية من القواسم، وهو بالضبط ما يجعل هذه القيم من \(t\) أكثر المرشحين قدرة على تعظيم \(M(t)\).
لنأخذ المثال الصغير \(n=6\). عندئذ يجب مقارنة \(M(t)\) لكل \(1\le t\lt 6\).
عندما \(t=1\)، لا يظهر إلا العامل \(2\)، لذلك \(M(1)=2\).
عندما \(t=2\)، يكون \(a_2(2)=3\)، والقاسم \(2\) يعطي الأولي \(3\)، ومن ثم
$$M(2)=2^3\cdot 3=24.$$
عندما \(t=3\)، لا يظهر أي أولي فردي جديد يحقق \(p-1\mid 3\)، ولذلك \(M(3)=2\).
عندما \(t=4\)، يكون \(a_2(4)=4\)، والقاسمان \(2\) و\(4\) يعطيان الأوليين \(3\) و\(5\)، وبالتالي
$$M(4)=2^4\cdot 3\cdot 5=240.$$
وعندما \(t=5\)، لا نحصل على أولي فردي إضافي، ومن ثم \(M(5)=2\). إذًا القيمة العظمى هي \(240\)، وبالتالي
$$\mathcal L(6)=240+1=241.$$
وهذه هي قيمة التحقق الصغيرة التي تعتمد عليها الشيفرات قبل الانتقال إلى المدخل الكامل.
التنفيذات في C++ وPython وJava تتبع السلسلة نفسها من الخطوات. أولًا تبني غربالًا للأولية حتى \(n\)، لأن كل عدد يُختبر لاحقًا يكون على الصورة \(d+1\) حيث \(d\lt t\lt n\).
بعد ذلك تُولِّد قيم \(t\) المرشحة ببحث عمق أولًا على أعداد مكوّنة من ضرب أعداد أولية صغيرة بأسس غير متزايدة، مع الحفاظ دائمًا على الشرط \(t\lt n\). وخلال هذا البحث يجري الاحتفاظ بتحليل \(t\) إلى عوامله الأولية حتى يمكن إعادة بناء قائمة قواسمه بسرعة عند تقييمه.
عند تقييم قيمة ثابتة \(t\)، تُولَّد جميع القواسم، ثم تُضاف مساهمة قوة \(2\) الخاصة، ثم يُفحص كل عدد من الشكل \(d+1\). فإذا كان \(d+1\) أوليًا، تُضرب القوة المقابلة \((d+1)^{v_{d+1}(t)+1}\) في القيمة الحالية لـ \(M(t)\).
ولأن الأعداد الحقيقية هائلة، لا تعتمد الشيفرة على تمثيل عددي مباشر واحد، بل تحتفظ بصورتين لكل مرشح: قيمة لوغاريتمية لمقارنة الأحجام بدقة، وقيمة بترديد \(10^9\) للاحتفاظ بآخر تسعة أرقام. وبعد انتهاء البحث تعيد
$$\bigl(\max M(t)+1\bigr)\bmod 10^9,$$
مع تنسيق يحافظ على الأصفار البادئة عند الحاجة.
لنرمز إلى حد الإدخال بـ \(n\)، وإلى مجموعة المرشحين التي يمر عليها البحث فعلًا بالرمز \(S\). بناء غربال الأولية حتى \(n\) يحتاج إلى \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة.
وبالنسبة إلى مرشح واحد \(t\)، إذا كان عدد قواسمه هو \(\tau(t)\)، فإن توليد هذه القواسم كلها ومسحها يكلف \(O(\tau(t))\) زمنًا و\(O(\tau(t))\) مساحة مؤقتة. أما العمل الباقي لكل قاسم فصغير: مراجعة في الغربال، واستخراج قصير للأس، وحساب أس معياري بأس صغير، ثم إضافة لوغاريتمية.
لذلك تكون الكلفة الكلية
$$O\left(n\log\log n+\sum_{t\in S}\tau(t)\right),$$
أما الذاكرة الكلية فتكون
$$O\left(n+\max_{t\in S}\tau(t)\right).$$
عمليًا، ليست الحسابات المعيارية هي العامل المهيمن، بل عدد المرشحين ذوي القواسم الكثيرة الذين يصل إليهم بحث العمق أولًا.