Solution

Answer: 1111981904675169

Let

$$f(n)=\text{the smallest positive multiple of }n$$

whose decimal expansion uses only the digits $0,1,2$.

We must compute

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

Mathematical analysis

The key observation is that this is fundamentally a shortest-path / BFS on remainders problem.

1. Reformulating the condition

Suppose a number $x$ uses only digits $0,1,2$.

We want:

$$x \equiv 0 \pmod n.$$

Instead of constructing huge integers directly, we work modulo $n$.

If we currently have a number with remainder $r$, then appending a digit $d\in{0,1,2}$ produces the new remainder

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

Thus each remainder is a node in a graph:

vertices: $0,1,\dots,n-1$,
edges:

$$r \to (10r+d)\bmod n,\qquad d\in{0,1,2}.$$

We seek the smallest decimal number (in lexicographic / length order) reaching remainder $0$.

2. Why BFS gives the minimal number

Breadth-first search explores states by:

shortest length first,
within the same length, digit order.

If we enqueue digits in the order

$$0,1,2,$$

after starting from $1$ and $2$, then the first time we reach remainder $0$ we have exactly the smallest valid number.

This works because decimal comparison is equivalent to:

fewer digits,
lexicographically smaller among equal-length numbers.

3. Reconstructing the number

During BFS we store:

the previous remainder,
the digit appended.

Then when remainder $0$ is reached, we backtrack to reconstruct the decimal string.

Finally:

$$\frac{f(n)}{n}$$

is an integer, so we compute it directly and sum.

Python implementation

from collections import deque

def quotient(n):
    """
    Returns f(n) / n, where f(n) is the smallest positive
    multiple of n using only digits 0,1,2.
    """

    # Special case
    if n == 1:
        return 1

    # parent[r] = previous remainder used to reach r
    # digit[r]  = digit appended to reach r
    parent = [-2] * n
    digit = [''] * n

    q = deque()

    # Starting numbers: 1 and 2
    for d in [1, 2]:
        r = d % n

        if parent[r] == -2:
            parent[r] = -1
            digit[r] = str(d)
            q.append(r)

    # BFS over remainders
    while q:
        r = q.popleft()

        # Found divisible number
        if r == 0:
            break

        # Append digits 0,1,2
        for d in [0, 1, 2]:
            nr = (10 * r + d) % n

            if parent[nr] == -2:
                parent[nr] = r
                digit[nr] = str(d)
                q.append(nr)

    # Reconstruct the minimal number
    chars = []
    cur = 0

    while cur != -1:
        chars.append(digit[cur])
        cur = parent[cur]

    s = ''.join(reversed(chars))

    # Return f(n)/n
    return int(s) // n

# Compute the required sum
total = sum(quotient(n) for n in range(1, 10001))

print(total)

Code walkthrough

Initialization

parent = [-2] * n
digit = [''] * n

These arrays store the BFS tree.

parent[r] tells us the previous remainder,
digit[r] tells us which digit was appended.

A value -2 means “unvisited”.

Starting states

for d in [1, 2]:

Numbers cannot begin with 0, so the first digit must be 1 or 2.

Their remainders are inserted into the queue.

BFS transition

nr = (10 * r + d) % n

Appending a decimal digit updates the remainder exactly this way.

Why this is efficient

For each $n$:

there are only $n$ possible remainders,
each remainder is visited once,
each visit tries 3 digits.

So complexity is approximately:

$$O(n)$$

per value of $n$.

For $n\le 10000$, this runs comfortably fast.

Verification on the sample

The program reproduces:

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

which matches the problem statement exactly.

Examples:

$f(2)=2$
$f(3)=12$
$f(7)=21$
$f(42)=210$

all correctly found by the BFS.

Final verification

The computed value is:

$$1111981904675169$$

It is positive and of plausible magnitude because many $f(n)$ values are extremely large numbers consisting only of digits $0,1,2$.

Therefore the final result is:

Answer: 1111981904675169

Project Euler Problem 303