Project Euler

Divisible Ranges

A contiguous range of positive integers is called a divisible range if all the integers in the range can be arranged in a row such that the n-th term is a multiple of n. For example, the range [6.....

Source sync Apr 19, 2026

Problem #0896

Level Level 33

Solved By 239

Languages C++, Python

Answer 274229635640

Length 458 words

searchgraphlinear_algebra

A contiguous range of positive integers is called a divisible range if all the integers in the range can be arranged in a row such that the \(n\)-th term is a multiple of \(n\).

For example, the range \([6..9]\) is a divisible range because we can arrange the numbers as \(7,6,9,8\).

In fact, it is the \(4\)th divisible range of length \(4\), the first three being \([1..4], [2..5], [3..6]\).

Find the \(36\)th divisible range of length \(36\).

Give as answer the smallest number in the range.

Problem 896: Divisible Ranges

Mathematical Analysis

Reformulation as a Bipartite Matching Problem

A range [a, a+1, …, a+n-1] of length n is a divisible range if and only if there exists a perfect matching in a bipartite graph where:

Left vertices represent positions 1, 2, …, n
Right vertices represent values a, a+1, …, a+n-1
An edge exists between position k and value v if k divides v

By Hall’s Marriage Theorem, a perfect matching exists if and only if for every subset S of positions, the set of values divisible by at least one element of S has cardinality at least |S|.

Algorithmic Approach

For a given starting value a and length n=36:

Build the bipartite graph relating positions 1..36 to values a..a+35.
Check if a perfect matching exists using the Hopcroft-Karp algorithm.
Enumerate starting values a = 1, 2, 3, … and count divisible ranges until we find the 36th one.

Key Observations

Position k can be matched to value v only if v mod k = 0.
For large k (close to n), the divisibility constraint is stringent, meaning fewer values qualify.
The number of values in [a, a+n-1] divisible by k is floor((a+n-1)/k) - floor((a-1)/k).

Editorial

A contiguous range [a, a+1, …, a+n-1] of length n is a divisible range if the integers can be arranged so that the k-th term is a multiple of k. Find the 36th divisible range of length 36. Give the smallest number in the range. We iterate over each candidate starting value a (incrementing from 1). We then build a bipartite adjacency list: for each position k in 1..36, find which values in [a, a+35] are divisible by k. Finally, run Hopcroft-Karp maximum bipartite matching.

Pseudocode

For each candidate starting value a (incrementing from 1):
Build a bipartite adjacency list: for each position k in 1..36, find which values in [a, a+35] are divisible by k
Run Hopcroft-Karp maximum bipartite matching
If the matching size equals 36, increment our counter
When the counter reaches 36, output a

Complexity Analysis

For each candidate a, building the bipartite graph takes O(n * (n/1 + n/2 + … + n/n)) = O(n * H_n) where H_n is the n-th harmonic number.
Hopcroft-Karp runs in O(E * sqrt(V)) where E is the number of edges and V = 2n.
The total number of candidates tested depends on the density of divisible ranges.

Answer

\boxed{274229635640}

C++ project_euler/problem_896/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Project Euler 896: Divisible Ranges
 *
 * A range [a, a+n-1] of length n is a "divisible range" if the numbers can
 * be arranged so that position k gets a multiple of k (for k=1..n).
 *
 * Find the 36th divisible range of length 36.
 *
 * Key insight: Use Hopcroft-Karp bipartite matching with early termination.
 * Also, we can quickly reject ranges where some position k has no valid value.
 */

struct HopcroftKarp {
    int n, m;
    vector<vector<int>> adj;
    vector<int> matchL, matchR, dist;

    HopcroftKarp(int n, int m) : n(n), m(m), adj(n), matchL(n, -1), matchR(m, -1), dist(n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    bool bfs() {
        queue<int> q;
        for (int u = 0; u < n; u++) {
            if (matchL[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INT_MAX;
            }
        }
        bool found = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int w = matchR[v];
                if (w == -1) {
                    found = true;
                } else if (dist[w] == INT_MAX) {
                    dist[w] = dist[u] + 1;
                    q.push(w);
                }
            }
        }
        return found;
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            int w = matchR[v];
            if (w == -1 || (dist[w] == dist[u] + 1 && dfs(w))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = INT_MAX;
        return false;
    }

    int maxMatching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 0; u < n; u++) {
                if (matchL[u] == -1) {
                    if (dfs(u)) matching++;
                }
            }
        }
        return matching;
    }
};

bool isDivisibleRange(long long a, int n) {
    // Quick check: for each position k, count how many values in [a, a+n-1] are divisible by k
    // If any position has 0 candidates, return false immediately
    for (int k = 1; k <= n; k++) {
        long long first_mult = ((a + k - 1) / k) * k;
        if (first_mult > a + n - 1) return false;
    }

    HopcroftKarp hk(n, n);
    for (int k = 1; k <= n; k++) {
        long long first_mult = ((a + k - 1) / k) * k;
        for (long long v = first_mult; v <= a + n - 1; v += k) {
            hk.addEdge(k - 1, (int)(v - a));
        }
    }
    return hk.maxMatching() == n;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n = 36;
    int target = 36;
    int count = 0;

    // Optimization: the largest position k=n=36 needs at least one multiple in [a, a+35].
    // A multiple of 36 occurs every 36 numbers, so [a, a+35] always contains at least one multiple of 36.
    // Similarly for other large k. The bottleneck positions are those with few candidates.

    for (long long a = 1; ; a++) {
        if (isDivisibleRange(a, n)) {
            count++;
            // Print progress
            // fprintf(stderr, "Found divisible range #%d starting at %lld\n", count, a);
            if (count == target) {
                cout << a << endl;
                return 0;
            }
        }
    }

    return 0;
}

Python project_euler/problem_896/solution.py

"""
Project Euler Problem 896: Divisible Ranges

A contiguous range [a, a+1, ..., a+n-1] of length n is a divisible range
if the integers can be arranged so that the k-th term is a multiple of k.

Find the 36th divisible range of length 36. Give the smallest number in the range.
"""

from scipy.optimize import linear_sum_assignment

def is_divisible_range(a, n):
    """Check if [a, a+n-1] is a divisible range using maximum bipartite matching."""
    # Use Hopcroft-Karp via networkx or manual implementation
    # We'll use a simple augmenting path approach

    # adj[k] = list of value indices that position k+1 can match (0-indexed)
    adj = [[] for _ in range(n)]
    for k in range(1, n + 1):
        first_mult = ((a + k - 1) // k) * k
        v = first_mult
        while v <= a + n - 1:
            adj[k - 1].append(v - a)
            v += k

    # Hopcroft-Karp
    match_l = [-1] * n
    match_r = [-1] * n

    def bfs():
        dist = [0] * n
        queue = []
        for u in range(n):
            if match_l[u] == -1:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = float('inf')
        found = False
        qi = 0
        while qi < len(queue):
            u = queue[qi]; qi += 1
            for v in adj[u]:
                w = match_r[v]
                if w == -1:
                    found = True
                elif dist[w] == float('inf'):
                    dist[w] = dist[u] + 1
                    queue.append(w)
        return found, dist

    def dfs(u, dist):
        for v in adj[u]:
            w = match_r[v]
            if w == -1 or (dist[w] == dist[u] + 1 and dfs(w, dist)):
                match_l[u] = v
                match_r[v] = u
                return True
        dist[u] = float('inf')
        return False

    matching = 0
    while True:
        found, dist = bfs()
        if not found:
            break
        for u in range(n):
            if match_l[u] == -1:
                if dfs(u, dist):
                    matching += 1

    return matching == n

def solve():
    n = 36
    target = 36
    count = 0
    a = 1

    while True:
        if is_divisible_range(a, n):
            count += 1
            if count == target:
                print(a)
                return
        a += 1

if __name__ == "__main__":
    solve()