WARNING: The text below provides a guidance for a Project Euler problem.

  • If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.

  • If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.

  • If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.

  • Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.




















A long row of dice

Striping the problem of its dicey narrative, the task boils down to finding the value of the following function :

where is the divisor function, that is a function that counts the number of positive divisors. We now turn to characterise numbers for which it is the case that . For this, recall the standard formula (when we know the prime factorization of ):

Assuming that , we immediately see that none of the can be 0, 2, 3, or 4 (by simply looking at this equation modulo 2, 3) modulo 6. Each thus gives remainder 1 or 5 = -1, and each gives remainder 0 or 4 modulo 6. Moreover, the number of ’s giving remainder -1 must be even. Going back to the prime factorization of number , we may rewrite it as:

and pulling together the sixth powers:

Here now comes the crucial observation: to construct an integer satisfying the above relation, the first chunk can be taken to be any integer for which the Möbius function (this comes straight from the definition of the Möbius function). Afterwards the first chunk, , can be set to be an arbitrary integer! For a fixed value of , there will be hence possible values for among . This yields a feasible formula for :

The following piece of compact Julia code gives answer in a (somehow) reasonable time. The bottleneck here is the unnecessary computation of all of the values of the Möbius function.

n = 10^9
μ = ones(n)
result = floor(n^(2/3))
for i = 2:n
    if μ[i] == 1
        μ[i:i:n] *= -i
        μ[i*i:i*i:n] = 0
    end
    if # <REMOVED>
        result += floor((n/i)^(2/3))
    end
end