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.

Further Reading

1. Problem page: https://projecteuler.net/problem=303
2. Breadth-first search: https://en.wikipedia.org/wiki/Breadth-first_search
3. Modular arithmetic: https://en.wikipedia.org/wiki/Modular_arithmetic