Problem 303: Multiples with Small Digits

Mathematical Foundation

Theorem 1 (Existence). For every positive integer $n$, $f(n)$ exists and is finite.

Proof. Consider all numbers whose decimal digits lie in $\{0, 1, 2\}$. Among $\{0, 1, 2\}^d$ (the set of $d$-digit strings from $\{0,1,2\}$), there are $3^d$ values. Their residues modulo $n$ take at most $n$ distinct values. By the pigeonhole principle, when $3^d > n$ (i.e., $d > \log_3 n$), at least two such numbers share the same residue modulo $n$. Their difference is a multiple of $n$ whose digits lie in $\{-2, -1, 0, 1, 2\}$. While this does not directly prove the result, a more refined argument using BFS over residues (see below) guarantees that the BFS terminates after exploring at most $n$ residues. Since BFS reaches every residue class, it eventually reaches residue 0, proving existence. $\square$

Lemma 1 (BFS correctness). A breadth-first search that builds numbers digit-by-digit using digits $\{0, 1, 2\}$, tracking residues modulo $n$, finds $f(n)$ in at most $n$ steps (residue expansions).

Proof. The state space is $\{0, 1, \ldots, n-1\}$ (residues modulo $n$). The BFS starts with residues $1 \bmod n$ and $2 \bmod n$ (corresponding to leading digits 1 and 2). At each step, from residue $r$, we transition to residues $(10r + d) \bmod n$ for $d \in \{0, 1, 2\}$. Since:

1. Each residue is visited at most once (BFS marks visited states),
2. BFS explores states in order of increasing digit count (and lexicographically within the same length),
3. The first time residue 0 is reached yields the smallest qualifying multiple,

the algorithm is correct and terminates after visiting at most $n$ residues. $\square$

Lemma 2 (Hardest cases). For $n$ with large factors of 9, $f(n)/n$ can be large. In particular, $f(9999)$ has 28 digits. The BFS handles these naturally via arbitrary-precision arithmetic.

Proof. The number 9999 = $3^2 \times 11 \times 101$ requires a multiple using only digits $\{0,1,2\}$. The smallest such multiple is $f(9999) = 1111111111111111111111111112$ (24 ones followed by 1112), which has 28 digits. The BFS explores up to 9999 residue classes, each with 3 transitions, staying well within computational limits. $\square$

Editorial

For each n from 1 to 10000, find f(n) = smallest positive multiple of n using only digits {0, 1, 2}. Compute sum of f(n)/n. BFS on remainders mod n. We returns f(n) / n. Finally, start with digits 1 and 2 as leading digit.

Pseudocode

Returns f(n) / n
Start with digits 1 and 2 as leading digit
while queue not empty

Complexity Analysis

• Time: $O\!\left(\sum_{n=1}^{10000} n\right) = O(5 \times 10^7)$ residue transitions in the worst case. Each transition is $O(1)$ for the modular arithmetic, but $O(D)$ if tracking the full big integer (where $D$ is the number of digits of $f(n)$, at most $\sim 30$).
• Space: $O(n)$ per query for the visited array and BFS queue.

Answer

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

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;

/*
 * Problem 303: Multiples with Small Digits
 *
 * For each n from 1 to 10000, find the smallest multiple of n
 * using only digits {0, 1, 2}. Sum up f(n)/n.
 *
 * BFS on remainders mod n, building numbers digit by digit.
 * We track f(n)/n by also tracking the quotient during reconstruction.
 */

// BFS to find f(n)/n
// Returns f(n)/n as a long long (fits since f(n)/n < 3^30 or so)
ull solve(int n) {
    if (n == 1) return 1;
    if (n == 2) return 1;

    // BFS: state = remainder mod n
    // parent[r] = {previous remainder, digit appended}
    vector<int> parent_rem(n, -1);
    vector<int> parent_dig(n, -1);
    vector<bool> visited(n, false);

    queue<int> q;
    // Leading digits 1 and 2
    for (int d = 1; d <= 2; d++) {
        int r = d % n;
        if (r == 0) return d; // f(n) = d, f(n)/n = d/n... but d < n usually
        if (!visited[r]) {
            visited[r] = true;
            parent_rem[r] = -2; // sentinel for root
            parent_dig[r] = d;
            q.push(r);
        }
    }

    while (!q.empty()) {
        int r = q.front();
        q.pop();
        for (int d = 0; d <= 2; d++) {
            int nr = (10LL * r + d) % n;
            if (nr == 0) {
                // Reconstruct the number and compute f(n)/n
                // Build digits in reverse
                vector<int> digits;
                digits.push_back(d);
                int cur = r;
                while (parent_rem[cur] != -2) {
                    digits.push_back(parent_dig[cur]);
                    cur = parent_rem[cur];
                }
                digits.push_back(parent_dig[cur]); // root digit
                reverse(digits.begin(), digits.end());

                // Compute f(n) as big number, then divide by n
                // f(n)/n: we can compute this by long division
                // Since f(n) might not fit in ull, use __int128
                // Actually for n <= 10000, f(n) can have ~30 digits, which is > 64 bits
                // Use __int128 which handles up to ~38 digits
                lll fn = 0;
                for (int dig : digits) {
                    fn = fn * 10 + dig;
                }
                return (ull)(fn / n);
            }
            if (!visited[nr]) {
                visited[nr] = true;
                parent_rem[nr] = r;
                parent_dig[nr] = d;
                q.push(nr);
            }
        }
    }
    return 0; // should not reach here
}

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

    ull total = 0;
    for (int n = 1; n <= 10000; n++) {
        total += solve(n);
    }
    cout << total << endl;
    return 0;
}

"""
Problem 303: Multiples with Small Digits

For each n from 1 to 10000, find f(n) = smallest positive multiple of n
using only digits {0, 1, 2}. Compute sum of f(n)/n.

BFS on remainders mod n.
"""

from collections import deque

def find_f_over_n(n):
    """Find f(n)/n using BFS on remainders."""
    # BFS: build numbers digit by digit, track remainder mod n
    visited = [False] * n
    # parent[r] = (prev_remainder, digit) or None for root
    parent = [None] * n

    q = deque()
    for d in (1, 2):
        r = d % n
        if r == 0:
            return d  # f(n) = d
        if not visited[r]:
            visited[r] = True
            parent[r] = (-1, d)  # -1 means root
            q.append(r)

    while q:
        r = q.popleft()
        for d in (0, 1, 2):
            nr = (10 * r + d) % n
            if nr == 0:
                # Reconstruct digits
                digits = [d]
                cur = r
                while parent[cur][0] != -1:
                    digits.append(parent[cur][1])
                    cur = parent[cur][0]
                digits.append(parent[cur][1])
                digits.reverse()
                # Build f(n)
                fn = 0
                for dig in digits:
                    fn = fn * 10 + dig
                return fn // n
            if not visited[nr]:
                visited[nr] = True
                parent[nr] = (r, d)
                q.append(nr)

    return 0  # Should never reach here

def solve():
    total = 0
    for n in range(1, 10001):
        total += find_f_over_n(n)
    print(total)

solve()