Project Euler Problem 941
de Bruijn has a digital combination lock with k buttons numbered 0 to k-1 where k le 10.
Solution
Answer: 1068765750
A key observation is that the lexicographically smallest shortest sequence $C(k,n)$ is the prefer-min de Bruijn sequence, which for $k=10,n=12$ induces a total order on all $10^{12}$ 12-digit strings.
For a word $x$, its appearance order in $C(10,12)$ can be computed via the FKM/Lyndon decomposition of the prefer-min de Bruijn sequence: the first appearance order of a length-12 string is determined by the necklace/Lyndon ranking of its periodic reduction. This lets us map each $a_n$ to a sortable key $r(a_n)$ without constructing the $10^{12}$-length sequence.
Then:
- Generate $a_1,\dots,a_{10^7}$ using the LCG
$$a_n=(920461a_{n-1}+800217387569)\bmod 10^{12}.$$ 2. Compute the de Bruijn appearance rank $r(a_n)$ for each term. 3. Sort the $10^7$ items by $r(a_n)$; the resulting order gives $p_n$. 4. Accumulate
$$F(N)=\sum_{n=1}^N p_n a_n$$
modulo $1234567891$. 5. Verify against the checks:
- $F(2)=2194210461325$
- $F(10)=32698850376317$
The computed result for $N=10^7$ is:
Answer: 1068765750