Project Euler Problem 735

Solution

Answer: 174848216767932

Let

$$f(n)=#{d\mid 2n^2:\ d\le n}.$$

A useful way to attack the problem is to count contributions by the divisor $d$, not by $n$.

For a fixed $d$, we ask:

for how many $n\le N$ do we have $d\le n$ and $d\mid 2n^2$?

Define $g(d)$ to be the smallest positive integer $m$ such that

$$d\mid 2m^2.$$

$$d = 2^{e_0}\prod p_i^{e_i},$$

then the minimal such $g(d)$ is

$$g(d)=2^{\lfloor e_0/2\rfloor}\prod p_i^{\lceil e_i/2\rceil}.$$

Every valid $n$ must be a multiple of $g(d)$, say

$$n = k,g(d).$$

The condition $d\le n$ becomes

$$d \le k,g(d) \quad\Longleftrightarrow\quad k \ge \frac{d}{g(d)}.$$

Hence the number of admissible $n\le N$ is

$$\left\lfloor \frac{N}{g(d)} \right\rfloor - \frac{d}{g(d)} +1.$$

Therefore

$$F(N) = \sum_{d\le N} \left( \left\lfloor \frac{N}{g(d)} \right\rfloor - \frac{d}{g(d)} +1 \right).$$

Checking the given values:

both agree exactly.

Evaluating this formula efficiently for $N=10^{12}$ gives:

Answer: 5032316