Detailed mathematical approach

Problem Summary

For each positive integer \(n\), let \(g(n)\) be the largest perfect square dividing \(n\). The problem asks for

$S(N)=\sum_{n=1}^{N} g(n)$

with \(N=10^{14}\), and the final result is required modulo \(10^9+7\). The implementations use the checkpoints \(S(10)=24\) and \(S(100)=767\). A direct scan over all \(n\le N\) is hopeless, so the sum has to be reorganized around square divisors rather than around the integers themselves.

Mathematical Approach

The key transformation is to rewrite the problem as a weighted sum over \(m\le \lfloor \sqrt N \rfloor\), where the weights turn out to be the Jordan totient values \(J_2(m)\).

Step 1: Split Each Integer into a Squarefree Part and a Square Part

Every positive integer \(n\) can be written uniquely as

$n=s\,d^2,$

where \(s\) is squarefree. In that decomposition, the largest square dividing \(n\) is exactly

$g(n)=d^2.$

If we group all integers by the value of \(d\), then for a fixed \(d\) the admissible values of \(s\) are precisely the squarefree integers satisfying

$1\le s\le \left\lfloor\frac{N}{d^2}\right\rfloor.$

Let \(Q(x)\) denote the number of squarefree integers up to \(x\). Then

$S(N)=\sum_{d=1}^{\lfloor \sqrt N \rfloor} d^2\,Q\!\left(\left\lfloor\frac{N}{d^2}\right\rfloor\right).$

This already removes the need to inspect each \(n\) individually.

Step 2: Express the Squarefree Counting Function with Möbius Inversion

The indicator of squarefreeness satisfies the classical identity

$\mathbf{1}_{\mathrm{sqfree}}(t)=\sum_{k^2\mid t}\mu(k),$

because the Möbius function cancels exactly those integers containing repeated prime factors. Summing this identity for \(1\le t\le x\) gives

$Q(x)=\sum_{k=1}^{\lfloor \sqrt x \rfloor}\mu(k)\left\lfloor\frac{x}{k^2}\right\rfloor.$

Substituting \(x=\left\lfloor N/d^2\right\rfloor\) into the previous formula yields

$S(N)=\sum_{d\le \sqrt N} d^2\sum_{k\le \sqrt{N/d^2}}\mu(k)\left\lfloor\frac{N}{d^2k^2}\right\rfloor.$

Step 3: Merge the Two Square Indices into One

Now let

$m=d\,k.$

Every pair \((d,k)\) with \(d^2k^2\le N\) contributes to the term with \(m^2=d^2k^2\). Reordering the sum by \(m\) instead of by the pair \((d,k)\) gives

$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor}\left(\sum_{d\mid m}\mu\!\left(\frac{m}{d}\right)d^2\right)\left\lfloor\frac{N}{m^2}\right\rfloor.$

The inner divisor sum is the coefficient that matters. Once it is identified, the whole problem collapses to a single floor-sum.

Step 4: Recognize the Inner Coefficient as Jordan's Totient \(J_2\)

Define the Jordan totient of order \(2\) by

$J_2(m)=\sum_{d\mid m}\mu(d)\left(\frac{m}{d}\right)^2.$

Replacing \(d\) by \(m/d\) shows that this is exactly the same coefficient as above, so

$S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor.$

The function \(J_2\) is multiplicative and has the product formula

$J_2(m)=m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right).$

For a prime power \(p^e\), this simplifies to

$J_2(p^e)=p^{2e}-p^{2e-2}.$

This multiplicative structure is exactly what the sieve exploits.

Step 5: Convert the Formula into a Sieve-Friendly Computation

Start with the values \(m^2\) for all \(m\le \lfloor \sqrt N \rfloor\). Each prime \(p\) contributes the factor \((1-1/p^2)\) to every multiple of \(p\). After every prime has applied its factor, the stored value at index \(m\) becomes

$m^2\prod_{p\mid m}\left(1-\frac{1}{p^2}\right)=J_2(m).$

Therefore the final closed form used by the implementations is

$\boxed{S(N)=\sum_{m=1}^{\lfloor \sqrt N \rfloor} J_2(m)\left\lfloor\frac{N}{m^2}\right\rfloor \pmod{10^9+7}.}$

Worked Example: \(N=10\)

Here \(\lfloor\sqrt{10}\rfloor=3\). The Jordan weights are

$J_2(1)=1,\qquad J_2(2)=4\left(1-\frac14\right)=3,\qquad J_2(3)=9\left(1-\frac19\right)=8.$

The floor factors are

$\left\lfloor\frac{10}{1^2}\right\rfloor=10,\qquad \left\lfloor\frac{10}{2^2}\right\rfloor=2,\qquad \left\lfloor\frac{10}{3^2}\right\rfloor=1.$

So

$S(10)=1\cdot 10+3\cdot 2+8\cdot 1=24.$

This matches the direct list of largest square divisors: \(1,1,1,4,1,1,1,4,9,1\).

How the Code Works

The C++, Python, and Java implementations first compute the exact integer value \(R=\lfloor\sqrt N\rfloor\). They allocate an array of length \(R+1\) and initialize entry \(m\) with \(m^2\).

Next, they run a prime sieve up to \(R\). Whenever a prime \(p\) is encountered, the implementation visits every multiple of \(p\) and applies the multiplicative factor \((p^2-1)/p^2\). After this pass, the array stores \(J_2(m)\) for every \(1\le m\le R\).

Finally, the implementation loops over \(m=1,2,\dots,R\), computes \(\lfloor N/m^2\rfloor\), multiplies that count by the precomputed Jordan weight, and accumulates the result modulo \(10^9+7\). The arithmetic is entirely integer-based, so the only care points are an exact square root and safe modular multiplication.

Complexity Analysis

Let \(R=\lfloor\sqrt N\rfloor\). Initializing the array costs \(O(R)\). The sieve that applies the prime factors behaves like a totient-style sieve and runs in \(O(R\log\log R)\) time. The final weighted summation is \(O(R)\). The memory usage is \(O(R)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=745
2. Squarefree integers: Wikipedia — Square-free integer
3. Möbius function: Wikipedia — Möbius function
4. Jordan's totient function: Wikipedia — Jordan's totient function
5. Square number: Wikipedia — Square number