Project Euler Problem 912

Project Euler Problem 912

Solution

Answer: 674045136

Let valid binary strings be those with no occurrence of 111.

The sequence $s_n$ is the increasing list of positive integers whose binary representations are valid.

We need

$$F(N)=\sum_{\substack{1\le n\le N\ s_n\text{ odd}}} n^2.$$

A number is odd iff its binary representation ends in 1, so the problem reduces to tracking the positions of valid strings ending in 1.

A convenient way to solve this is with a recursive automaton over the last two bits:

• State = last two bits seen.
• Append 0 or 1 unless that would create 111.

For every recursively generated block of strings, we store:

• $L$: number of strings in the block
• $C$: number of odd strings
• $S_1$: sum of positions of odd strings within the block
• $S_2$: sum of squared positions of odd strings within the block

When concatenating two blocks $A$ then $B$:

$$\begin{aligned} S_1 &= S_{1,A} + (S_{1,B}+L_A C_B),\ S_2 &= S_{2,A} + \left(S_{2,B}+2L_A S_{1,B}+L_A^2 C_B\right). \end{aligned}$$

Using memoized recursion over binary lengths, and then taking the first $10^{16}$ valid numbers, the computation reproduces the check value

$$F(10)=199$$

and finally gives

$$F(10^{16}) \equiv 674045136 \pmod{10^9+7}.$$

Answer: 674045136