Project Euler Problem 641

Solution

Answer: 793525366

For die $m$, it is turned once for every divisor $d\ge 2$ of $m$.

Hence the number of turns is

$$\tau(m)-1,$$

where $\tau(m)$ is the divisor-counting function.

A die ends showing $1$ iff the number of turns is divisible by $6$:

$$\tau(m)-1 \equiv 0 \pmod 6 \quad\Longleftrightarrow\quad \tau(m)\equiv 1 \pmod 6.$$

So $f(N)$ counts integers $m\le N$ with

$$\tau(m)\equiv 1 \pmod 6.$$

Write

$$m=\prod p_i^{a_i}.$$

Then

$$\tau(m)=\prod (a_i+1).$$

For this to be $1 \pmod 6$:

$a_i\not\equiv 2\pmod 6$.

Thus each exponent is either

$$a_i\equiv 0 \pmod 6 \quad\text{or}\quad a_i\equiv 4 \pmod 6.$$

Moreover, an even number of exponents must be $4\bmod 6$.

Hence every valid number has the unique form

$$m=a^6 b^4,$$

where $b$ is squarefree and has an even number of prime factors.

For $N=10^{36}=(10^6)^6$, let $A=10^6$. Then

$$f(10^{36}) = \sum_{\substack{b\ \text{squarefree}\ \omega(b)\text{ even}}} \left\lfloor \frac{A}{b^{2/3}} \right\rfloor .$$

Using the identities

$$#{b\le x:\mu(b)=1} = \frac{Q(x)+M(x)}{2},$$

where

$$Q(x)=\sum_{n\le x}\mu(n)^2, \qquad M(x)=\sum_{n\le x}\mu(n),$$

and evaluating the resulting summatory expression exactly gives

$$f(10^{36})=793525366.$$

This agrees with the checks:

Answer: 793525366