Project Euler Problem 759
The function f is defined for all positive integers as follows: It can be proven that f(n) is integer for all values of
Solution
Answer: 282771304
By analyzing the recurrence, one finds the key simplification:
$$f(n)=n\cdot \operatorname{popcount}(n)$$
where $\operatorname{popcount}(n)$ is the number of 1s in the binary representation of $n$.
This matches the examples:
- $f(7)=7\cdot 3=21$
- $S(10)=\sum_{i=1}^{10} (i\cdot \operatorname{popcount}(i))^2 = 1530$
- $S(100)=4798445$
So the target becomes
$$S(N)=\sum_{i=1}^{N} i^2 \cdot \operatorname{popcount}(i)^2$$
For $N=10^{16}$, this can be computed efficiently using a binary digit DP with matrix transitions over the moments:
$$1,\ n,\ n^2,\ k,\ k^2,\ nk,\ nk^2,\ n^2k,\ n^2k^2$$
where $k=\operatorname{popcount}(n)$. Fast exponentiation over free suffix bits yields the result in $O(\log N)$.
The computation gives:
Answer: 282771304