Detailed mathematical approach

Problem Summary

For a fixed length \(n\), call the interval \([a,a+n-1]\) divisible if its \(n\) terms can be reordered so that the \(k\)-th chosen term is divisible by \(k\) for every \(1\le k\le n\). Problem 896 asks for the \(36\)th starting value \(a\) when \(n=36\).

Equivalently, we need distinct offsets \(o_1,\dots,o_n\in\{0,\dots,n-1\}\) such that

$a+o_d \equiv 0 \pmod d \qquad (1\le d\le n).$

The implementations avoid scanning intervals one by one. Instead they turn each interval into a bipartite matching problem and exploit the fact that the whole condition is periodic modulo \(\operatorname{lcm}(1,2,\dots,n)\).

Mathematical Approach

The key observation is that the problem depends only on which divisibility residues appear inside one block of length \(n\). Once that is rewritten as a matching problem, periodicity and prime-power decomposition reduce the search to a manageable finite computation.

Step 1: Rewrite the interval as a matching problem

For a start value \(a\), define a bipartite graph with left side \(D=\{1,2,\dots,n\}\) and right side \(O=\{0,1,\dots,n-1\}\). Connect divisor \(d\) to offset \(o\) when

$a+o \equiv 0 \pmod d.$

A perfect matching in this graph chooses a distinct interval position for every divisor \(d\). Therefore \([a,a+n-1]\) is divisible if and only if this graph has a perfect matching. Hall's marriage theorem is the mathematical existence criterion, and the implementations test it algorithmically with augmenting paths.

Step 2: The condition is periodic modulo \(L=\operatorname{lcm}(1,2,\dots,n)\)

For each fixed \(d\), the edge relation only depends on \(a \bmod d\). Hence the whole graph depends only on \(a \bmod L\), where

$L=\operatorname{lcm}(1,2,\dots,n)=\prod_{p\le n} p^{\lfloor \log_p n\rfloor}.$

So if \(a\) works, then \(a+L\) works as well. Let the valid starts in one period be

$1\le r_1\lt r_2\lt \dots\lt r_P\le L.$

Then the full infinite sequence of divisible-range starts is periodic:

$a_k=\left\lfloor\frac{k-1}{P}\right\rfloor L+r_{1+((k-1)\bmod P)}.$

Thus the problem reduces to enumerating the valid residues in a single period.

Step 3: Refine residues one prime power at a time

Instead of checking all residues modulo \(L\) at once, the implementations build them incrementally. Write \(L\) as a product of pairwise coprime maximal prime powers

$L=\prod_{p\le n} q_p,\qquad q_p=p^{\lfloor \log_p n\rfloor}.$

After some of these factors have been processed, let \(M\) be their product and suppose we only know \(a\equiv c \pmod M\). For a divisor \(d\), the processed part of the divisibility condition is exactly

$\delta_M(d)=\gcd(M,d).$

Indeed, \(\delta_M(d)\) keeps precisely the prime-power contributions to \(d\) that are already present in \(M\). So an offset \(o\) is still compatible with residue class \(c \bmod M\) whenever

$c+o \equiv 0 \pmod{\delta_M(d)}.$

This gives a relaxed matching problem: it enforces all processed prime-power constraints and ignores the rest until later stages. Every exact solution survives all relaxed stages, and once \(M=L\) the relaxed problem becomes the original one.

Step 4: Extend each residue class and prune aggressively

Suppose the next prime-power factor is \(q\), so the new modulus is \(Mq\). Because \(\gcd(M,q)=1\), every extension of \(c \pmod M\) to modulo \(Mq\) has the form

$c+kM \qquad (0\le k\lt q).$

Each candidate is tested by building the relaxed graph with divisor conditions modulo \(\gcd(Mq,d)\). If that relaxed graph has no perfect matching, the residue class cannot lead to a valid full residue and is discarded immediately.

This branch-and-prune process is far smaller than brute force over all \(L\) residues. By the final stage, the survivors are exactly the valid starts in one period.

Worked Example: Length \(4\)

Take \(n=4\). Then \(L=\operatorname{lcm}(1,2,3,4)=12\). Consider the interval starting at \(a=6\), namely \(\{6,7,8,9\}\). The allowed offsets are

$\begin{aligned} d=1&:& \{0,1,2,3\},\\ d=2&:& \{0,2\},\\ d=3&:& \{0,3\},\\ d=4&:& \{2\}. \end{aligned}$

A perfect matching exists: divisor \(4\) must use offset \(2\) (the number \(8\)), divisor \(3\) can use offset \(3\) (the number \(9\)), divisor \(2\) then uses offset \(0\) (the number \(6\)), and divisor \(1\) takes the remaining offset \(1\) (the number \(7\)). So \(a=6\) is a valid start.

By contrast, for \(a=5\) the interval is \(\{5,6,7,8\}\) and the critical offsets are

$d=2:\{1,3\},\qquad d=3:\{1\},\qquad d=4:\{3\}.$

The divisors \(2,3,4\) together can only use the two offsets \(\{1,3\}\), so Hall's condition fails. This shows exactly why some residues survive the periodic search and others are pruned away.

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. First they compute \(L\) indirectly as the product of the maximal prime powers up to \(n\). Those same prime powers define the staged moduli used during residue construction.

Next they precompute, for every divisor target \(d\), every divisor \(m\mid d\), and every residue \(r\bmod m\), the bitmask of offsets \(o\in\{0,\dots,n-1\}\) satisfying

$o+r \equiv 0 \pmod m.$

This cache means that when a residue class \(c \pmod M\) is tested, the implementation can assemble all allowed offset masks immediately from \(\gcd(M,d)\) and \(c \bmod \gcd(M,d)\).

For each staged modulus, the implementation extends every surviving residue \(c\) to all \(c+kM\) under the next prime-power factor. Each extension yields one bipartite graph on divisors versus offsets. The graph is represented as bit masks, the divisor side is processed from the most constrained masks to the least constrained ones, and a standard augmenting-path matcher checks whether a perfect matching exists.

After the final modulus reaches \(L\), the surviving residues are the exact valid starts within one period. Sorting them gives \(r_1,\dots,r_P\), and the periodic formula above returns the required \(k\)-th start. For Problem 896 the implementations evaluate this with \(n=36\) and \(k=36\).

Complexity Analysis

Let \(n\) be the range length and let \(R\) be the total number of residue classes examined across all stages of the prime-power refinement. Computing the prime list and the maximal prime powers up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory.

The mask cache requires

$\sum_{d=1}^{n}\sum_{m\mid d} O(mn)$

time to build, because for each pair \((d,m)\) every residue class modulo \(m\) is expanded across all \(n\) offsets. This is \(O(n^3)\) in the worst case for generic \(n\), but here \(n=36\) is small and fixed. Its storage is

$\sum_{d=1}^{n}\sum_{m\mid d} O(m),$

which is quadratic-scale in practice.

Each residue test builds \(n\) masks and runs a DFS-based bipartite matching on an \(n\times n\) graph, giving \(O(n^3)\) worst-case time per candidate residue. The total search is therefore \(O(Rn^3)\), with \(R\) kept manageable by strong pruning at early modular stages. That is why the approach is practical even though a naive scan over all intervals would be hopeless.

Footnotes and References

1. Problem page: Project Euler 896
2. Least common multiple: Wikipedia - Least common multiple
3. Bipartite matching: Wikipedia - Matching (graph theory)
4. Hall's marriage theorem: Wikipedia - Hall's marriage theorem
5. Chinese remainder theorem: Wikipedia - Chinese remainder theorem
6. Modular arithmetic: Wikipedia - Modular arithmetic