Project Euler Problem 520

Project Euler Problem 520

Solution

Answer: 238413705

Let a digit’s count parity determine validity:

• Odd digits ${1,3,5,7,9}$: if present, must occur an odd number of times.
• Even digits ${0,2,4,6,8}$: if present, must occur an even number of times.

We count all valid positive integers with at most $n$ digits.

A direct DP on digit-count parities would use $3^{10}=59049$ states (for each digit: absent / odd count / even count). The key simplification is symmetry:

• The five odd digits are interchangeable.
• The four nonzero even digits are interchangeable.
• Digit $0$ must be separated because of the leading-zero restriction.

So the state is compressed to:

$$(z,a,b,c,d,e,f)$$

where:

• $z\in{0,1,2}$: state of digit $0$

(absent / odd count / even count)

• $a,b,c$: numbers of odd digits in states

absent / odd / even, with $a+b+c=5$

• $d,e,f$: numbers of nonzero even digits in states

absent / odd / even, with $d+e+f=4$

This reduces the automaton to only 945 states.

We then:

1. Build the transition graph (10 possible appended digits).
2. Compute $Q(n)$ for the first few thousand terms by DP.
3. Verify:

• $Q(7)=287975$
• $Q(100)\bmod 1000000123=123864868$

4. Use Berlekamp–Massey to derive a linear recurrence for $Q(n)$ (order 22).
5. Evaluate $Q(2^u)$ for $1\le u\le39$ using fast linear recurrence exponentiation.

The resulting value is:

Answer: 238413705