Detailed mathematical approach

Problem Summary

For each positive integer \(n\), define

$a(n)=\#\left\{d\in\mathbb{Z}_{>0}: d\mid 2n^2,\ d\le n\right\}.$

The problem asks for

$F(N)=\sum_{n=1}^{N} a(n).$

A brute-force method would test every \(d\le n\) for every \(n\le N\), which is far too slow for the large target value. The successful approach is to count admissible pairs \((n,d)\) in a structured way, then compress the remaining sums with Möbius inversion and quotient-block floor sums.

Mathematical Approach

Instead of viewing the problem as a separate divisor search for each \(n\), we count all valid pairs \((n,d)\) at once.

Step 1: Recast the Problem as a Pair Count

By definition, \(F(N)\) counts pairs \((n,d)\) such that

$1\le n\le N,\qquad d\mid 2n^2,\qquad d\le n.$

So we may write

$F(N)=\#\left\{(n,d):1\le n\le N,\ d\mid 2n^2,\ d\le n\right\}.$

The inequality \(d\le n\) and the divisibility condition interact naturally with \(\gcd(n,d)\), so that is the right quantity to isolate first.

Step 2: Split Off the Common GCD

For any counted pair, set

$g=\gcd(n,d),\qquad n=g\,m,\qquad d=g\,u,\qquad \gcd(m,u)=1.$

Because \(d\le n\), we immediately have

$u\le m.$

Also, from \(d\mid 2n^2\) we get

$g\,u \mid 2g^2m^2,$

and after dividing by \(g\),

$u\mid 2g\,m^2.$

Since \(\gcd(u,m)=1\), every prime factor of \(u\) must come from \(2g\), so in fact

$u\mid 2g.$

That condition leads to two natural cases: \(u\) odd and \(u\) even.

Step 3: The Odd Branch

If \(u\) is odd, then \(u\mid 2g\) forces \(u\mid g\). Write

$g=u\,t.$

Substituting back gives

$d=u^2t,\qquad n=u\,m\,t,\qquad \gcd(m,u)=1,\qquad m\ge u.$

For fixed \(u\) and \(m\), the parameter \(t\) can be any positive integer with \(u m t\le N\), so it contributes

$\left\lfloor\frac{N}{u m}\right\rfloor$

choices. Therefore the odd contribution is

$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{\substack{m\ge u\\ \gcd(m,u)=1}}\left\lfloor\frac{N}{u m}\right\rfloor.$

The range \(u\le \sqrt N\) is automatic because \(n=u m t\ge u^2\).

Step 4: The Even Branch

If \(u\) is even, write

$u=2w.$

Then \(u\mid 2g\) becomes \(w\mid g\), so we may set

$g=w\,t.$

Now

$d=2w^2t,\qquad n=w\,m\,t,\qquad \gcd(m,2w)=1,\qquad m\ge 2w.$

The condition \(\gcd(m,2w)=1\) means in particular that \(m\) must be odd, and also \(\gcd(m,w)=1\). For fixed \(w\) and \(m\), the number of possible \(t\) is

$\left\lfloor\frac{N}{w m}\right\rfloor.$

So the even contribution is

$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{m\ge 2w\\ m\text{ odd}\\ \gcd(m,w)=1}}\left\lfloor\frac{N}{w m}\right\rfloor.$

Again the range follows from \(n=wmt\ge 2w^2\). The full answer is simply

$F(N)=C_{\mathrm{odd}}(N)+C_{\mathrm{even}}(N).$

Step 5: Remove Coprimality with Möbius Inversion

The remaining obstacle is the condition \(\gcd(m,u)=1\) or \(\gcd(m,w)=1\). This is handled with the Möbius function:

$[\gcd(x,y)=1]=\sum_{d\mid \gcd(x,y)} \mu(d).$

Applying this to the odd branch gives

$C_{\mathrm{odd}}(N)=\sum_{\substack{u\le \sqrt N\\u\text{ odd}}}\ \sum_{d\mid u}^{\mathrm{sqfree}}\mu(d)\sum_{r\ge \lceil u/d\rceil}\left\lfloor\frac{\left\lfloor N/(ud)\right\rfloor}{r}\right\rfloor.$

Here \(d\) runs over the squarefree divisors of \(u\), and we rewrote \(m=d r\).

For the even branch, only odd squarefree divisors matter because \(m\) is already odd. That yields

$C_{\mathrm{even}}(N)=\sum_{w\le \sqrt{N/2}}\ \sum_{\substack{d\mid w\\ d\text{ odd}}}^{\mathrm{sqfree}}\mu(d)\sum_{\substack{r\ge \lceil 2w/d\rceil\\ r\text{ odd}}}\left\lfloor\frac{\left\lfloor N/(wd)\right\rfloor}{r}\right\rfloor.$

These are exactly the two families of sums evaluated by the implementation.

Step 6: Convert the Odd-Denominator Sum into Two Standard Floor Sums

Define the tail floor sum

$\operatorname{FS}(X,L)=\sum_{m=L}^{X}\left\lfloor\frac{X}{m}\right\rfloor.$

Then the odd-denominator version is obtained by subtracting the even denominators:

$\sum_{\substack{m\ge L\\ m\text{ odd}}}\left\lfloor\frac{X}{m}\right\rfloor=\operatorname{FS}(X,L)-\operatorname{FS}\left(\left\lfloor\frac{X}{2}\right\rfloor,\left\lceil\frac{L}{2}\right\rceil\right).$

This identity is the key to turning the even branch into the same kind of floor-sum object as the odd branch. The implementation then evaluates \(\operatorname{FS}(X,L)\) in quotient blocks, using the fact that \(\left\lfloor X/m\right\rfloor\) is constant on long intervals.

Worked Example: \(F(15)=63\)

The implementation checks the small value \(F(15)=63\). Using the branch formulas, we can see why.

For the odd branch, \(u\le \sqrt{15}\), so \(u=1\) or \(u=3\).

When \(u=1\), every \(m\ge 1\) is coprime to \(1\), so

$\sum_{m=1}^{15}\left\lfloor\frac{15}{m}\right\rfloor=45.$

When \(u=3\), we need \(m\ge 3\), \(\gcd(m,3)=1\), and \(\left\lfloor 15/(3m)\right\rfloor>0\). Only \(m=4,5\) contribute, giving

$\left\lfloor\frac{15}{12}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=1+1=2.$

Hence

$C_{\mathrm{odd}}(15)=45+2=47.$

For the even branch, \(w\le \sqrt{15/2}\), so \(w=1,2\).

When \(w=1\), the odd integers \(m\ge 2\) that contribute are \(3,5,7,9,11,13,15\), so

$\left\lfloor\frac{15}{3}\right\rfloor+\left\lfloor\frac{15}{5}\right\rfloor+\left\lfloor\frac{15}{7}\right\rfloor+\left\lfloor\frac{15}{9}\right\rfloor+\left\lfloor\frac{15}{11}\right\rfloor+\left\lfloor\frac{15}{13}\right\rfloor+\left\lfloor\frac{15}{15}\right\rfloor=14.$

When \(w=2\), we need odd \(m\ge 4\), and only \(m=5,7\) contribute:

$\left\lfloor\frac{15}{10}\right\rfloor+\left\lfloor\frac{15}{14}\right\rfloor=1+1=2.$

Thus

$C_{\mathrm{even}}(15)=14+2=16,$

and finally

$F(15)=47+16=63.$

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical decomposition. The optimized computation first determines the two outer ranges, \(\lfloor\sqrt N\rfloor\) for the odd branch and \(\lfloor\sqrt{N/2}\rfloor\) for the even branch.

Next, it precomputes for every integer up to that range all squarefree divisors together with the corresponding Möbius sign. This is done by extracting the distinct prime factors of each integer and enumerating their subsets, because every subset produces one squarefree divisor and its sign \((-1)^k\).

The main summation then iterates through the odd and even branches exactly as in the formulas above. Each inner tail sum is reduced to \(\operatorname{FS}(X,L)\), and \(\operatorname{FS}(X,L)\) is not evaluated term-by-term. Instead, the implementation groups consecutive denominators that give the same quotient \(\left\lfloor X/m\right\rfloor\), so one arithmetic step handles an entire block.

For large inputs, the C++ implementation can split the odd and even ranges into independent blocks and process them in parallel. The Python and Java implementations reuse that same optimized native computation and only return the final numeric output. Before the full run, the program also checks small checkpoints and compares against a direct brute-force count on a small limit.

Complexity Analysis

Let

$M=\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\sqrt{N/2}\right\rfloor\right).$

Building the smallest-prime-factor sieve up to \(M\) costs \(O(M\log\log M)\) time and \(O(M)\) memory. The stored squarefree-divisor cache contains \(\sum_{k\le M}2^{\omega(k)}\) entries, whose average order is \(O(M\log M)\), so that cache dominates memory usage in practice.

The two outer summations only run to order \(\sqrt N\), not to \(N\). For each cached divisor entry, the remaining work is a quotient-block floor sum rather than a linear scan over all denominators. The exact worst-case expression is messy because it depends on both divisor structure and quotient-block lengths, but the practical behavior is close to \(N^{1/2+o(1)}\), which is dramatically better than the quadratic brute-force definition.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=735
2. Möbius function: Wikipedia — Möbius function
3. Squarefree integer: Wikipedia — Squarefree integer
4. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle
5. Dirichlet hyperbola method: Wikipedia — Dirichlet hyperbola method