Detailed mathematical approach

Problem Summary

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\).

Mathematical Approach

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\).

Step 1: Carmichael Values on Prime Powers

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\).

Step 2: Maximal Exponent of an Odd Prime for Fixed \(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.

Step 3: The Special Role of \(2\)

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.

Step 4: Closed Formula for the Largest Integer with \(\lambda(m)\mid t\)

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.

Step 5: Why the Search Focuses on Divisor-Rich \(t\)

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)\).

Step 6: Worked Example \(\mathcal L(6)=241\)

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=533
2. Carmichael function: Wikipedia — Carmichael function
3. Prime factorization and valuations: Wikipedia — \(p\)-adic valuation
4. Divisor function: Wikipedia — Divisor function
5. Highly composite number: Wikipedia — Highly composite number