Project Euler Problem 728

Solution

Answer: 709874991

Let the configuration space be vectors in $\mathbb F_2^n$, where $1$ means “tail” and $0$ means “head”.

A move flips $k$ consecutive coins on the circle, so the move vectors are cyclic shifts of

$$(1,1,\dots,1,0,\dots,0)$$

with $k$ consecutive $1$’s.

Thus the solvable states form the span of these vectors, and therefore

$$F(n,k)=2^{\operatorname{rank}(M_{n,k})},$$

where $M_{n,k}$ is the circulant matrix generated by

$$f(x)=1+x+\cdots+x^{k-1}.$$

Over $\mathbb F_2$, the rank of a circulant matrix is

$$\operatorname{rank}(M_{n,k}) = n-\deg\gcd(x^n-1,f(x)).$$

Using the factorisation structure in characteristic $2$, one obtains

$$\deg\gcd(x^n-1,f(x)) = \begin{cases} \gcd(n,k), & v_2(n)<v_2(k),\[4pt] \gcd(n,k)-1, & v_2(n)\ge v_2(k). \end{cases}$$

Hence

$$F(n,k)= \begin{cases} 2^{,n-\gcd(n,k)}, & v_2(n)<v_2(k),\[4pt] 2^{,n-\gcd(n,k)+1}, & v_2(n)\ge v_2(k). \end{cases}$$

This matches the examples:

Reorganising the double sum by $d=\gcd(n,k)$ and writing $n=dm$ gives

$$S(N) = \sum_{m\le N} c(m)\sum_{d\le N/m} 2^{d(m-1)},$$

where

$$c(m)= \begin{cases} 2, & m=1,\ 2\varphi(m), & m\text{ even},\ \dfrac{3}{2}\varphi(m), & m>1\text{ odd}. \end{cases}$$

A sieve for $\varphi$ up to $10^7$ together with precomputed powers of $2$ evaluates the sum efficiently modulo $10^9+7$.

The computation gives

$$S(10^7)\equiv 709874991 \pmod{1,000,000,007}.$$

Answer: 709874991