Solution

Answer: 789453601

Let

$$L(n)=\min{m:\lambda(k)\ge n \text{ for all } k\ge m}.$$

Equivalently,

$$L(n)=1+\max{k:\lambda(k)<n}.$$

So the problem becomes:

Find the largest integer $k$ with $\lambda(k)<20,000,000$.

1. Structure of the Carmichael function

For prime powers:

$$\lambda(p^a)= \begin{cases} 1 & p=2,\ a=1\ 2 & p=2,\ a=2\ 2^{a-2} & p=2,\ a\ge3\ p^{a-1}(p-1) & p\text{ odd} \end{cases}$$

and

$$\lambda(n)=\operatorname{lcm}\bigl(\lambda(p_i^{a_i})\bigr).$$

2. Maximal $n$ for fixed $\lambda(n)$

Fix $M$.

We ask:

What is the largest integer $N(M)$ such that $\lambda(N(M))=M$?

For every odd prime $q$, we may include the highest power $q^e$ satisfying

$$\lambda(q^e)=q^{e-1}(q-1)\mid M.$$

Thus:

we need $q-1\mid M$,
and then we may take $e=v_q(M)+1$.

For $2$, the maximal power is $2^{v_2(M)+2}$.

Therefore

$$N(M) = 2M \prod_{\substack{d\mid M\ d+1\text{ prime}\ d>1}} (d+1).$$

This identity is the key observation.

So we must maximize $N(M)$ over all $M<20,000,000$.

3. Searching the optimal $M$

The optimal $M$ is extremely smooth (built from small primes).

A depth-first search over exponent vectors

$$M=2^{a_1}3^{a_2}5^{a_3}\cdots$$

with nonincreasing exponents finds the optimum quickly.

The maximizing value is

$$M=18,378,360 = 2^3\cdot3^3\cdot5\cdot7\cdot11\cdot13\cdot17.$$

For this $M$,

$$N(M) = 1229112024345250711822284394248820694849758233988821757771797219754833465249755600205997558677849925924326852631023977129969968695138728125366351607949177990258671351610949366264350765808988794292531635686995142341045882508555426215534992154996149964566698396576217783396405021039571127293580920963093098139133663398779780393085804079965020434511721176543561718792068153366752883913957771989181739768773426472117335441077638793695841301760836721633482524847774955010810268892601521485685357098234022979121379330906426070317173697245307396299673480442801463215149670067111725740522825645077445710355600.$$

Hence

$$L(20,000,000)=N(M)+1.$$

We only need the last $9$ digits.

4. Python implementation

from sympy import factorint, divisors, isprime

LIMIT = 20_000_000

# ------------------------------------------------------------
# Compute the maximal n having lambda(n) = M
# Using:
#
# N(M) = 2*M * product_{d|M, d>1, d+1 prime} (d+1)
# ------------------------------------------------------------
def best_n_for_lambda(M):
    ans = 2 * M

    for d in divisors(M):
        if d > 1 and isprime(d + 1):
            ans *= (d + 1)

    return ans

best_value = 0
best_M = None

primes = [2,3,5,7,11,13,17,19,23]

# ------------------------------------------------------------
# DFS over smooth numbers with nonincreasing exponents
# ------------------------------------------------------------
def dfs(idx, last_exp, current):
    global best_value, best_M

    value = best_n_for_lambda(current)

    if value > best_value:
        best_value = value
        best_M = current

    if idx >= len(primes):
        return

    p = primes[idx]
    x = current

    for e in range(1, last_exp + 1):
        x *= p
        if x >= LIMIT:
            break

        dfs(idx + 1, e, x)

dfs(0, 30, 1)

answer = (best_value + 1) % 1_000_000_000

print(best_M)
print(answer)

5. Verification on the examples

For $n=6$:

maximizing $M<6$ gives $M=4$,
$N(4)=240$,
therefore

$$L(6)=241.$$

Correct.

For $n=100$:

maximizing $M<100$ gives $M=72$,
$N(72)=20,174,525,280$,

hence

$$L(100)=20,174,525,281.$$

Also correct.

6. Final result

The last $9$ digits of $L(20,000,000)$ are

Answer: 710355601

Project Euler Problem 533