Detailed mathematical approach

Problem Summary

For a fixed positive integer \(n\), define

$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{m-1}\right\rfloor \qquad (2\le m\le n).$

The overall quantity of interest is

$L(n)=\sum_{m=2}^{n} T(n,m).$

The challenge is to evaluate \(L(10^7)\) exactly. A literal interpretation of the definition would use a nested loop: for every \(m\), we would sum over all \(k\). That quadratic approach is far too slow, so the goal is to convert each inner floor-sum into a closed form that can be evaluated in constant time.

Mathematical Approach

The decisive observation is that, for fixed \(m\), the values of the floor function stay constant on long consecutive blocks. Once those blocks are counted carefully, the inner sum becomes an arithmetic-series calculation.

Step 1: Replace \(m\) by the block length

Set

$d=m-1.$

Then \(d\) runs from \(1\) to \(n-1\), and the inner term becomes

$T(n,m)=\sum_{k=0}^{n-1}\left\lfloor\frac{k}{d}\right\rfloor.$

This change of variable is convenient because \(d\) is exactly the width of each constant block of the floor function.

Step 2: Divide \(n\) by \(d\)

Write the Euclidean division of \(n\) by \(d\) as

$n=ad+b,\qquad 0\le b\lt d,\qquad a=\left\lfloor\frac{n}{d}\right\rfloor.$

Here \(a\) is the number of full blocks of width \(d\), and \(b\) is the length of the final partial block.

Step 3: Count equal floor values block by block

For \(k=0,1,\dots,n-1\), the value \(\left\lfloor k/d\right\rfloor\) behaves in a rigid pattern:

\(0\) appears exactly \(d\) times, then \(1\) appears exactly \(d\) times, and so on, up to \(a-1\), which also appears exactly \(d\) times. After those full blocks, the value \(a\) appears exactly \(b\) times.

Therefore

$T(n,m)=d\sum_{j=0}^{a-1} j + ba.$

The entire floor-sum has been reduced to counting repeated block values.

Step 4: Collapse the arithmetic series

Using

$\sum_{j=0}^{a-1} j=\frac{a(a-1)}{2},$

we obtain the closed form

$T(n,m)=\frac{d\,a(a-1)}{2}+ba,$

where \(d=m-1\), \(a=\left\lfloor n/d\right\rfloor\), and \(b=n-ad\).

This is the key simplification: each term of \(L(n)\) can now be evaluated with a few integer operations, without any inner summation.

Step 5: Sum over all admissible \(m\)

Since \(d=m-1\), summing over \(m=2,3,\dots,n\) is the same as summing over \(d=1,2,\dots,n-1\). Thus

$L(n)=\sum_{d=1}^{n-1}\left(\frac{d\,a_d(a_d-1)}{2}+b_d a_d\right),$

with

$a_d=\left\lfloor\frac{n}{d}\right\rfloor,\qquad b_d=n-d\,a_d.$

This formula is exactly what the implementations evaluate in one linear pass.

Worked Example

Take \(n=8\) and \(m=4\). Then \(d=m-1=3\), so

$a=\left\lfloor\frac{8}{3}\right\rfloor=2,\qquad b=8-3\cdot 2=2.$

The floor values are

$\left\lfloor\frac{0}{3}\right\rfloor,\left\lfloor\frac{1}{3}\right\rfloor,\left\lfloor\frac{2}{3}\right\rfloor,\left\lfloor\frac{3}{3}\right\rfloor,\left\lfloor\frac{4}{3}\right\rfloor,\left\lfloor\frac{5}{3}\right\rfloor,\left\lfloor\frac{6}{3}\right\rfloor,\left\lfloor\frac{7}{3}\right\rfloor=0,0,0,1,1,1,2,2.$

So

$T(8,4)=0+0+0+1+1+1+2+2=7.$

The closed form gives the same answer immediately:

$T(8,4)=\frac{3\cdot 2\cdot 1}{2}+2\cdot 2=3+4=7.$

For a tiny full sum, \(L(5)=10+4+2+1=17\). The same derivation also reproduces the checkpoint \(L(1000)=3281346\).

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They fix \(n=10^7\), iterate once over every \(d\) from \(1\) to \(n-1\), compute the quotient \(\left\lfloor n/d\right\rfloor\) and the corresponding remainder, and then add the closed-form contribution

$\frac{d\,a(a-1)}{2}+ba$

to the running total.

No nested loop remains, and no table needs to be precomputed. The C++ and Java versions store the answer in a 64-bit integer, while the Python version uses native arbitrary-precision integers. Mathematically, however, all three implementations are identical: each performs a direct evaluation of the derived summation formula above.

Complexity Analysis

There are exactly \(n-1\) outer iterations, and each iteration performs only constant-time integer arithmetic. Therefore the total running time is

$O(n),$

and the extra memory usage is

$O(1).$

This is a major improvement over the naive interpretation of the definition, which would require \(O(n^2)\) work because each choice of \(m\) would trigger a full inner summation over \(k\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=713
2. Floor and ceiling functions: Wikipedia - Floor and ceiling functions
3. Euclidean division: Wikipedia - Euclidean division
4. Arithmetic progression: Wikipedia - Arithmetic progression
5. Summation notation: Wikipedia - Summation