Problem 303: Multiples with Small Digits

Project Euler Problem 303 Solution

EulerSolve provides an optimized solution for Project Euler Problem 303, Multiples with Small Digits, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For each positive integer $n$, define $f(n)$ as the smallest positive multiple of $n$ whose decimal digits all belong to $\{0,1,2\}$. The task is to compute $$\sum_{n=1}^{N}\frac{f(n)}{n}.$$ Mathematical Approach 1) Why a solution always exists It is not obvious at first that every $n$ has such a multiple. Write $$n=2^a5^b m,\qquad \gcd(m,10)=1.$$ For the coprime part $m$, consider the repunits $$R_k=\underbrace{11\dots1}_{k\text{ digits}}=\frac{10^k-1}{9}\qquad (1\le k\le m).$$ If one of these is already $0\bmod m$, we are done. Otherwise, two of them have the same remainder modulo $m$. Their difference is divisible by $m$ and has decimal form $$11\dots1100\dots0,$$ so it uses only digits $0$ and $1$. Now multiply by $$10^{\max(a,b)}.$$ This adds enough factors of $2$ and $5$ to make the number divisible by $n$, and it still uses only digits $0$ and $1$. Therefore a multiple using digits from $\{0,1,2\}$ always exists. 2) Replace huge integers by residues Instead of building gigantic candidates directly, the code works modulo $n$. If a current decimal string has remainder $r$, then appending a digit $d\in\{0,1,2\}$ produces the new remainder $$r'=(10r+d)\bmod n.$$ So we get a directed graph with $n$ states, one for each residue $0,1,\dots,n-1$, and three outgoing edges from each state....

Detailed mathematical approach

Problem Summary

For each positive integer $n$, define $f(n)$ as the smallest positive multiple of $n$ whose decimal digits all belong to $\{0,1,2\}$. The task is to compute

$$\sum_{n=1}^{N}\frac{f(n)}{n}.$$

Mathematical Approach

1) Why a solution always exists

It is not obvious at first that every $n$ has such a multiple. Write

$$n=2^a5^b m,\qquad \gcd(m,10)=1.$$

For the coprime part $m$, consider the repunits

$$R_k=\underbrace{11\dots1}_{k\text{ digits}}=\frac{10^k-1}{9}\qquad (1\le k\le m).$$

If one of these is already $0\bmod m$, we are done. Otherwise, two of them have the same remainder modulo $m$. Their difference is divisible by $m$ and has decimal form

$$11\dots1100\dots0,$$

so it uses only digits $0$ and $1$.

Now multiply by

$$10^{\max(a,b)}.$$

This adds enough factors of $2$ and $5$ to make the number divisible by $n$, and it still uses only digits $0$ and $1$. Therefore a multiple using digits from $\{0,1,2\}$ always exists.

2) Replace huge integers by residues

Instead of building gigantic candidates directly, the code works modulo $n$. If a current decimal string has remainder $r$, then appending a digit $d\in\{0,1,2\}$ produces the new remainder

$$r'=(10r+d)\bmod n.$$

So we get a directed graph with $n$ states, one for each residue $0,1,\dots,n-1$, and three outgoing edges from each state.

3) Start states and the leading-zero issue

The first digit cannot be $0$, so the only legal one-digit starts are $1$ and $2$. Therefore the BFS starts from residues

$$1\bmod n\qquad\text{and}\qquad 2\bmod n.$$

Every longer legal number is obtained from one of these starts by repeatedly appending $0$, $1$, or $2$.

4) Why BFS gives the shortest valid number

Each edge corresponds to appending exactly one digit, so every edge has unit cost. Breadth-first search explores states in nondecreasing path length. Hence the first time BFS reaches residue $0$, it has found a decimal string with the minimum possible number of digits among all valid multiples of $n$.

This is the key reduction: “smallest multiple” is first turned into “shortest path to remainder $0$” in an unweighted graph.

5) Why the first found answer is also lexicographically smallest

Among strings with the same length, the code explores appended digits in the fixed order

$$0,\ 1,\ 2,$$

and the roots in the order $1,2$. Because BFS processes the queue level by level, the first path reaching a given state at a given depth is the lexicographically smallest one among all shortest paths to that state. In particular, the first time we reach residue $0$, we obtain not only the shortest valid decimal string, but also the lexicographically smallest among all strings of that minimum length.

For decimal numbers with the same length, lexicographic order and numeric order agree, so this is exactly the desired $f(n)$.

6) Parent reconstruction

The BFS stores, for each visited remainder:

1. its parent remainder;

2. the appended digit used to reach it.

When remainder $0$ is found, the code backtracks through these parent pointers, reverses the digit list, and reconstructs $f(n)$ exactly as a decimal string.

This is much cheaper than carrying the whole candidate number inside every queue entry.

7) Worked examples

Some small cases from the checkpoints make the method concrete:

$$f(2)=2,\qquad \frac{f(2)}{2}=1,$$

$$f(3)=12,\qquad \frac{f(3)}{3}=4,$$

$$f(7)=21,\qquad \frac{f(7)}{7}=3,$$

$$f(42)=210,\qquad \frac{f(42)}{42}=5.$$

The last example is a good reminder that zeros are useful: once a good core number is found, appending zeros can supply extra factors of $2$ and $5$.

8) Sample accumulation

After reconstructing $f(n)$, the solver converts it to an arbitrary-precision integer, divides by $n$, and adds the quotient to the running total. For example, the checkpoint in the C++ code verifies

$$\sum_{n=1}^{100}\frac{f(n)}{n}=11363107.$$

Another small manual checkpoint is

$$\sum_{n=1}^{10}\frac{f(n)}{n}=1389.$$

How the Code Works

The function smallest_multiple_with_digits_leq_2(n) performs the residue BFS for one fixed $n$. It keeps three arrays: seen, parent, and parent_digit. Once remainder $0$ is dequeued, it reconstructs the digit string and returns it.

The outer solve(limit) loop simply evaluates that function for all $1\le n\le N$, converts the returned string to a big integer, divides by $n$, and accumulates the result.

Complexity Analysis

For a fixed $n$, the BFS visits at most $n$ residues, and each residue has exactly three outgoing transitions. Therefore the time complexity per $n$ is

$$O(n),$$

and the memory usage is also

$$O(n).$$

Summed over all $1\le n\le N$, the total work is approximately quadratic:

$$O(N^2).$$

This is practical here because the branching factor is tiny and the state graph for each $n$ is very small compared with the actual size of $f(n)$, which may have many digits.

Problem 303 source code

C++

#include <algorithm>
#include <boost/multiprecision/cpp_int.hpp>
#include <cstdint>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

namespace {

using boost::multiprecision::cpp_int;

struct Options {
    int limit = 10000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 1;
}

std::string smallest_multiple_with_digits_leq_2(const int n) {
    if (n == 1) {
        return "1";
    }

    std::vector<int> parent(static_cast<std::size_t>(n), -1);
    std::vector<int> parent_digit(static_cast<std::size_t>(n), -1);
    std::vector<std::uint8_t> seen(static_cast<std::size_t>(n), 0U);
    std::queue<int> q;

    for (int first_digit = 1; first_digit <= 2; ++first_digit) {
        const int rem = first_digit % n;
        if (seen[static_cast<std::size_t>(rem)] != 0U) {
            continue;
        }
        seen[static_cast<std::size_t>(rem)] = 1U;
        parent[static_cast<std::size_t>(rem)] = -2;  // root marker
        parent_digit[static_cast<std::size_t>(rem)] = first_digit;
        q.push(rem);
    }

    int end_rem = -1;
    while (!q.empty()) {
        const int rem = q.front();
        q.pop();
        if (rem == 0) {
            end_rem = rem;
            break;
        }

        for (int digit = 0; digit <= 2; ++digit) {
            const int next = (rem * 10 + digit) % n;
            if (seen[static_cast<std::size_t>(next)] != 0U) {
                continue;
            }
            seen[static_cast<std::size_t>(next)] = 1U;
            parent[static_cast<std::size_t>(next)] = rem;
            parent_digit[static_cast<std::size_t>(next)] = digit;
            q.push(next);
        }
    }

    std::string digits;
    int cur = end_rem;
    while (cur >= 0) {
        digits.push_back(static_cast<char>('0' + parent_digit[static_cast<std::size_t>(cur)]));
        cur = parent[static_cast<std::size_t>(cur)];
    }
    std::reverse(digits.begin(), digits.end());
    return digits;
}

cpp_int solve(const int limit) {
    cpp_int total = 0;
    for (int n = 1; n <= limit; ++n) {
        const std::string multiple = smallest_multiple_with_digits_leq_2(n);
        cpp_int value = 0;
        for (char c : multiple) {
            value *= 10;
            value += static_cast<int>(c - '0');
        }
        total += value / n;
    }
    return total;
}

bool run_checkpoints() {
    if (smallest_multiple_with_digits_leq_2(2) != "2") {
        std::cerr << "Checkpoint failed for f(2)=2" << '\n';
        return false;
    }
    if (smallest_multiple_with_digits_leq_2(3) != "12") {
        std::cerr << "Checkpoint failed for f(3)=12" << '\n';
        return false;
    }
    if (smallest_multiple_with_digits_leq_2(7) != "21") {
        std::cerr << "Checkpoint failed for f(7)=21" << '\n';
        return false;
    }
    if (smallest_multiple_with_digits_leq_2(42) != "210") {
        std::cerr << "Checkpoint failed for f(42)=210" << '\n';
        return false;
    }
    if (solve(100) != cpp_int("11363107")) {
        std::cerr << "Checkpoint failed for limit=100 sample sum" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

from collections import deque

def solve():
    limit = 10000

    def smallest_multiple_012(n):
        if n == 1:
            return 1
        seen = bytearray(n)
        parent = [-1] * n
        parent_digit = [-1] * n
        q = deque()
        for d in range(1, 3):
            r = d % n
            if not seen[r]:
                seen[r] = 1
                parent[r] = -2
                parent_digit[r] = d
                q.append(r)

        end_rem = -1
        while q:
            rem = q.popleft()
            if rem == 0:
                end_rem = rem
                break
            for d in range(3):
                nxt = (rem * 10 + d) % n
                if not seen[nxt]:
                    seen[nxt] = 1
                    parent[nxt] = rem
                    parent_digit[nxt] = d
                    q.append(nxt)

        digits = []
        cur = end_rem
        while cur >= 0:
            digits.append(parent_digit[cur])
            cur = parent[cur]
        digits.reverse()
        val = 0
        for d in digits:
            val = val * 10 + d
        return val

    total = 0
    for n in range(1, limit + 1):
        m = smallest_multiple_012(n)
        total += m // n

    return str(total)

if __name__ == '__main__':
    print(solve())

Java

import java.math.BigInteger;

public class Euler303 {

    static String smallestMultipleWithDigitsLeq2(int n) {
        if (n == 1)
            return "1";

        int[] parent = new int[n];
        int[] parentDigit = new int[n];
        boolean[] seen = new boolean[n];
        int[] q = new int[n];
        int head = 0, tail = 0;

        for (int firstDigit = 1; firstDigit <= 2; firstDigit++) {
            int rem = firstDigit % n;
            if (seen[rem])
                continue;
            seen[rem] = true;
            parent[rem] = -2;
            parentDigit[rem] = firstDigit;
            q[tail++] = rem;
        }

        int endRem = -1;
        while (head < tail) {
            int rem = q[head++];
            if (rem == 0) {
                endRem = rem;
                break;
            }

            int r10 = (rem * 10) % n;
            for (int digit = 0; digit <= 2; digit++) {
                int next = r10 + digit;
                if (next >= n)
                    next -= n;
                if (!seen[next]) {
                    seen[next] = true;
                    parent[next] = rem;
                    parentDigit[next] = digit;
                    q[tail++] = next;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        int cur = endRem;
        while (cur >= 0) {
            sb.append((char) ('0' + parentDigit[cur]));
            cur = parent[cur];
        }
        return sb.reverse().toString();
    }

    static BigInteger solve(int limit) {
        BigInteger total = BigInteger.ZERO;
        for (int n = 1; n <= limit; n++) {
            String multiple = smallestMultipleWithDigitsLeq2(n);
            BigInteger val = new BigInteger(multiple);
            total = total.add(val.divide(BigInteger.valueOf(n)));
        }
        return total;
    }

    public static void main(String[] args) {
        System.out.println(solve(10000));
    }
}