Detailed mathematical approach

Problem Summary

Let \(\tau(n)\) denote the number of positive divisors of \(n\). For fixed integers \(u\) and \(k\), define

$M_n=\max_{n \le j \le n+k-1}\tau(j),\qquad S(u,k)=\sum_{n=1}^{u-k+1} M_n.$

So each length-\(k\) interval contributes the largest divisor count appearing inside that interval, and the task is to add those maxima over all consecutive intervals from \(1\) up to \(u\). A naive method would recompute each maximum independently and would be far too slow for the full input size, so the solution splits the problem into two linear passes.

Mathematical Approach

Step 1: Formula for the Divisor Count

If

$n=\prod_{r=1}^{t} p_r^{a_r},$

then every divisor of \(n\) is obtained by choosing an exponent \(b_r\) with \(0 \le b_r \le a_r\) for each prime \(p_r\). Hence

$\tau(n)=\prod_{r=1}^{t}(a_r+1).$

This multiplicative formula is the starting point for the sieve. Instead of factoring each integer from scratch, the implementation builds all values \(\tau(1),\tau(2),\dots,\tau(u)\) incrementally.

Step 2: Linear Sieve Recurrence

Suppose \(n=p^a m\) with \(p \nmid m\). Then

$\tau(n)=(a+1)\tau(m).$

Multiplying by a prime gives two cases.

$\tau(np)= \begin{cases} 2\tau(n), & p \nmid n,\\ \tau(n)\dfrac{a+2}{a+1}, & n=p^a m,\ p \nmid m. \end{cases}$

The first case adds a new prime factor of exponent \(1\); the second increases the exponent of an existing prime factor from \(a\) to \(a+1\). The implementations maintain, for each integer, its smallest prime factor and the exponent of that smallest prime factor. That information is exactly what is needed to apply the recurrence in constant time when the next composite number is generated.

The sieve is linear because every composite number is produced once, in its canonical decomposition as a previous integer multiplied by a prime chosen under the smallest-prime-factor rule. As a result, the full divisor-count table up to \(u\) is built in \(O(u)\) time.

Step 3: Reformulate the Outer Sum as Sliding-Window Maxima

Once the table \(\tau(1),\dots,\tau(u)\) is available, the problem becomes a standard fixed-window maximum problem. While scanning integers from left to right, it is convenient to index windows by their right endpoint:

$W_i=[\,i-k+1,\ i\,],\qquad i=k,k+1,\dots,u.$

The contribution of window \(W_i\) is

$\max_{j \in W_i}\tau(j).$

This is the same set of windows as in the original definition, only written by ending position instead of starting position.

Step 4: Monotone Deque Invariant

The key data structure is a deque of candidate indices. It satisfies two invariants at all times:

1. indices in the deque are increasing from front to back;

2. divisor counts are strictly decreasing from front to back.

When a new index \(i\) arrives, all trailing indices \(q\) with \(\tau(q)\le \tau(i)\) are removed before \(i\) is appended. Then any front index \(q \le i-k\) is removed because it has left the current window.

After these two clean-up steps, the front of the deque is the index of the maximum divisor count in the current window, so its \(\tau\)-value is added to the answer.

Step 5: Why Removing Dominated Indices Is Correct

Assume \(q<i\) and \(\tau(q)\le \tau(i)\). From the moment \(i\) is inserted onward, any future window that still contains \(q\) also contains \(i\), because \(i\) is newer and therefore expires no earlier than \(q\). Since \(i\) has divisor count at least as large, \(q\) can never again be the unique best candidate for a maximum. So deleting \(q\) is always safe.

This domination argument is the whole reason the deque stays short and efficient: each index is inserted once, deleted at most once from the back, and deleted at most once from the front.

Worked Example

For \(u=10\) and \(k=3\), the divisor counts are

$\tau(1),\tau(2),\dots,\tau(10)=1,2,2,3,2,4,2,4,3,4.$

The window maxima are therefore

$2,3,3,4,4,4,4,4,$

so

$S(10,3)=2+3+3+4+4+4+4+4=28.$

The same mechanism scales to the full input because the expensive part is no longer the window search; it is just a single amortized-constant-time deque update per index.

How the Code Works

The C++, Python, and Java implementations all follow the same two-stage pipeline. First they build the divisor-count table up to \(u\) using the linear sieve recurrence above. Second they scan that table once with a monotone deque and accumulate the maximum value of each length-\(k\) window.

The optimized method is validated on a published checkpoint,

$S(1000,10)=17176,$

and one implementation also compares a smaller test case against a brute-force window scan to confirm that the optimized and naive methods agree.

Complexity Analysis

The divisor-count sieve runs in \(O(u)\) time. The deque scan is also \(O(u)\) because each index enters the deque once and leaves it at most once. Therefore the overall running time is

$O(u).$

The memory usage is \(O(u)\) for the divisor-count and sieve tables, plus \(O(k)\) for the deque. The asymptotic memory bound is therefore

$O(u).$

Further Reading

1. Problem page: https://projecteuler.net/problem=485
2. Divisor function: Wikipedia — Divisor function
3. Linear sieve: cp-algorithms — Linear Sieve
4. Monotone queue / sliding-window extrema: cp-algorithms — Minimum Queue / Maximum Queue