Project Euler Problem 24

Solution

Answer: 2783915460

To find the millionth lexicographic permutation of the digits 0–9, we use the factorial number system rather than generating all 10! = 3,628,800 permutations.

We want the 1,000,000th permutation, but indexing from 0 makes the math easier:

$$999,999$$

At each step, determine which digit belongs in the next position using factorial blocks:

$9! = 362880$:

$999999 \div 362880 = 2$ remainder $274239$

→ pick the 3rd digit: 2

Remaining digits: 0,1,3,4,5,6,7,8,9

$8! = 40320$:

$274239 \div 40320 = 6$ remainder $32319$

→ pick 7

Remaining: 0,1,3,4,5,6,8,9

$7! = 5040$:

$32319 \div 5040 = 6$ remainder $2079$

→ pick 8

Continuing this process yields:

2783915460

Clean Python code

from math import factorial

digits = list("0123456789")
n = 999999  # zero-based index

result = []

for i in range(9, -1, -1):
    f = factorial(i)
    index = n // f
    result.append(digits.pop(index))
    n %= f

answer = "".join(result)
print(answer)

Tracing the factorial selection confirms the permutation:

2783915460

Answer: 2783915460