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 a positive integer $n$, let $f(n)$ be the least positive multiple of $n$ whose decimal digits are all at most $2$, that is, all taken from $\{0,1,2\}$. The statement gives $f(2)=2$, $f(3)=12$, $f(7)=21$, $f(42)=210$ and $f(89)=1121222$, with the checkpoint

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

and asks for the same sum with $n$ up to $10\,000$. Every term is a whole number, since $n$ divides $f(n)$ by definition. ^[1]

The whole solution in one sentence: for each $n$ we grow a candidate one digit at a time but remember only its remainder modulo $n$, so that a breadth-first search over those $n$ remainders finds a string with fewest digits leaving remainder $0$ and, among equally long ones, the smallest, and we add up the quotients $f(n)/n$.

Mathematical Approach

1. Smallest means shortest, then smallest digit by digit

A candidate for $f(n)$ is a non-empty string of digits from $\{0,1,2\}$ whose first digit is $1$ or $2$, since a decimal number has no leading zero. Decimal notation splits "least" into two easy comparisons: fewer digits means smaller, and numbers with equally many digits compare exactly as their digit strings compare from the left. So $f(n)$ is the dictionary-first among the shortest candidates that are multiples of $n$.

For $n=8$, none of the one- and two-digit candidates $1,2,10,11,12,20,21,22$ is a multiple of $8$. The first six three-digit candidates $100,101,102,110,111,112$ leave remainders $4,5,6,6,7,0$ modulo $8$, so $f(8)=112=8\cdot14$.

2. Why $f(n)$ exists at all

Nothing so far guarantees that any multiple of $n$ has only small digits. Write $n=2^a5^bm$ with $\gcd(m,10)=1$ and take the repunits

$$R_k=\frac{10^k-1}{9},\qquad k=1,2,\ldots,m,$$

the numbers written with $k$ ones. ^[4] If one of them is a multiple of $m$, take it. Otherwise their remainders modulo $m$ all lie in $\{1,\ldots,m-1\}$, so $m$ numbers share $m-1$ values and two agree by the pigeonhole principle: ^[3] $R_i\equiv R_j$ with $i\lt j$, and then

$$R_j-R_i=R_{j-i}\cdot 10^{\,i}$$

is a multiple of $m$ written with $j-i$ ones and $i$ zeros. Either branch gives a multiple of $m$ built from the digits $0$ and $1$; multiplying it by $10^{\max(a,b)}$ supplies the missing $2^a$ and $5^b$ while appending only zeros. So some multiple of $n$ uses just those two digits, and $f(n)$ is well defined.

For $m=7$ the remainders of $R_1,\ldots,R_6$ are $1,4,6,5,2,0$, so $R_6=111111=7\cdot15873$ works — but this only proves existence: $f(7)=21$ has two digits, not six. The factor $10^{\max(a,b)}$ is no formula either; for $n=4$ it gives $100=4\cdot25$, while $f(4)=12$.

3. From huge numbers to $n$ remainders

Appending a digit $d$ to a number $v$ produces $10v+d$, so modulo $n$ the new remainder depends only on the old one:

$$r\ \longmapsto\ (10r+d)\bmod n.$$

Build a directed graph on the $n$ remainders $0,1,\ldots,n-1$ with one edge $r\to(10r+d)\bmod n$ for each digit $d\in\{0,1,2\}$. A candidate $d_1d_2\ldots d_L$ is the walk that starts at vertex $d_1\bmod n$ and follows the edges labelled $d_2,\ldots,d_L$, and it is a multiple of $n$ exactly when that walk ends at vertex $0$. The first digit must be $1$ or $2$, so the walks start at $1\bmod n$ or $2\bmod n$.

This is the decisive step: the multiple can be enormous — $f(9999)$ has twenty digits — yet the graph has only $n$ vertices and $3n$ edges.

4. Breadth-first search finds the fewest digits

Every edge adds one digit, so minimising the digit count means finding a shortest walk to vertex $0$. When all edges count the same, breadth-first search does exactly that: it holds the discovered vertices in a first-in-first-out queue, finishing every vertex at distance $k$ before any vertex at distance $k+1$, so the distance recorded at first discovery is minimal. ^[2] Two starting vertices are no obstacle: queueing both is like adding one artificial source joined to each.

5. Why the first string found is also the smallest number

Shortest is not yet smallest. For $n=3$ both $12$ and $21$ are two-digit multiples of $3$ with small digits, and $f(3)=12$, so the order in which the search offers its choices decides what it records.

Claim. If the roots are enqueued in the order $1\bmod n$, then $2\bmod n$, and every vertex leaving the queue offers its digits in the order $0,1,2$, then the string stored at a vertex is the dictionary-smallest among the shortest strings reaching it, and one level's vertices leave the queue in increasing order of their stored strings.

Number levels by digit length, so the roots form level $1$ and level $L$ sits at graph distance $L-1$. (For $n=1$ both roots are the remainder $0$; only the first is kept, and it gives $f(1)=1$.) The proof rests on one observation: if $u$ and $w$ have the same length and $u$ precedes $w$, then $uc$ precedes $wc'$ for any digits $c,c'$, since $u$ and $w$ already differ earlier. Now induct on the level. The roots carry $1$ and $2$, stored in that order. Assume the claim for level $L$; its children are offered in increasing dictionary order, across vertices by the observation and inside one vertex because $0\lt1\lt2$, and dropping already-discovered remainders keeps the order of the rest. So a vertex $t$ first discovered at level $L+1$ receives the smallest $uc$ with $u$ stored at level $L$, and that is optimal for $t$: any shortest string for $t$ is $wc$ with $w$ of length $L$ reaching some $s$; no shorter string reaches $s$, or appending $c$ would reach $t$ with fewer than $L+1$ digits, so $s$ lies on level $L$, its stored string satisfies $u\le w$ by induction, and $uc\le wc$ by the observation.

All shortest candidates have the same length and no leading zero, so on them dictionary order and numerical order agree. The string stored at vertex $0$ is therefore exactly $f(n)$.

6. A complete run by hand: $n=7$

The queue starts with $1\bmod 7=1$, carrying the string $1$, and $2\bmod 7=2$, carrying $2$. All remainders below are modulo $7$.

Vertex $1$ leaves. Its digits give $10\equiv3$, $11\equiv4$, $12\equiv5$: three new vertices with the strings $10$, $11$, $12$.
Vertex $2$ leaves. Its digits give $20\equiv6$, $21\equiv0$, $22\equiv1$; the first two are new, with the strings $20$ and $21$, the third is the already-seen root.
Vertices $3,4,5,6$ leave in turn and discover nothing: their twelve successors $(10r+d)\bmod 7$ are all marked already.
Vertex $0$ leaves and the search stops with the string $21$.

Indeed $f(7)=21=7\cdot3$, so $n=7$ contributes $3$. Vertex $0$ entered the queue during the second step, with four vertices still ahead of it.

7. Reading the digits back

Carrying whole strings through the queue would cost up to $L$ digits per vertex. Instead the search stores two numbers per discovered remainder, where it came from and the digit appended; following those pointers back from vertex $0$ and reversing the digits rebuilds the string — for $n=7$, vertex $0$ came from vertex $2$ with digit $1$, and vertex $2$ is a root with digit $2$, giving $21$. The memory is $O(n)$ instead of $O(nL)$.

8. How long can $f(n)$ be?

Follow those pointers from remainder $0$ back to a root. Every vertex was discovered after its parent, so the chain never repeats a remainder, and it holds exactly one remainder per digit. There are only $n$ remainders, so $f(n)$ has at most $n$ digits.

That bound is very generous. For $n\le10\,000$ the longest value is

$$f(9999)=11112222222222222222,$$

twenty digits, while the mean digit count is about $7.58$ and the commonest length is $8$. A heuristic explains the size: there are $3^L-1$ candidates with at most $L$ digits, and if their remainders were spread evenly over the $n$ classes we should meet remainder $0$ once $3^L$ is comparable with $n$, that is $L\approx\log_3 n$; here $\log_3 10^4\approx8.38$. That even spread is plausible, not proved. The length matters in practice: $f(9999)$ exceeds $2^{63}-1$ and so leaves the signed 64-bit range.

9. The quotients and the sum

The program turns the digit string into an integer by Horner's rule, repeatedly replacing $v$ by $10v+d$, divides by $n$ — an exact division — and adds the quotient. For the $81$ values of $n\le10\,000$ whose own digits are already at most $2$, $f(n)=n$ and the term is $1$; long multiples give the large terms, and $f(9)=12222$ contributes $1358$. Partial sums make handy checkpoints: $1389$ for $n\le10$, $11363107$ for $n\le100$ as the statement says, and $111427232491$ for $n\le1000$.

10. The same numbers in the literature

The values $f(n)$ form the published sequence A181060 and the quotients $f(n)/n$ form A181061. ^[5] Forbidding the digit $2$ changes the answers completely: the least multiple of $n$ built from zeros and ones is A004290, ^[6] whose ninth term is $111111111$, whereas $f(9)=12222$.

How the Code Works

All three programs share two layers: a function computing $f(n)$ for one $n$, and a loop accumulating the quotients.

In the C++ file, smallest_multiple_with_digits_leq_2(n) is the search of Sections 3 to 7. ^[9] After returning "1" at once for $n=1$ it allocates three vectors of length $n$ — seen, parent, parent_digit — and a std::queue<int>. The roots $1\bmod n$ and $2\bmod n$ are pushed in that order, with parent set to the marker $-2$ and parent_digit to the first digit, so the loop over first_digit from $1$ to $2$ gives the root order Section 5 needs. The main loop pops rem, stops if it is $0$, and otherwise evaluates (rem * 10 + digit) % n for digit from $0$ to $2$ — Section 5's digit order — pushing each remainder seen has not marked. Reconstruction walks from end_rem along parent, with cur >= 0 stopping at the marker, and std::reverse reverses the digits.

Because rem is below $n\le10\,000$, rem * 10 + digit never exceeds $99\,992$ and stays well inside int. solve(limit) converts each string to a Boost cpp_int, an arbitrary-precision integer, ^[7] then divides by $n$ and accumulates; since the twenty-digit value of Section 8 already leaves the signed 64-bit range, cpp_int spares the program any hand-made width bounds. run_checkpoints verifies $f(2)$, $f(3)$, $f(7)$, $f(42)$ and solve(100) against $11363107$, with exit code $2$ on failure, and parse_arguments recognises --limit= and --skip-checkpoints, reading a limit into an int with no overflow guard, so the bounds here hold for limits up to $10\,000$.

One design detail deserves naming: the search stops when vertex $0$ leaves the queue, although Section 5 shows its stored string is final the moment it enters. Both rules give the same string for every $n\le10\,000$, as we checked, but the published one first removes everything queued ahead of $0$, which need not be the whole level: for $n=6$ the equally long $21$ is still queued when $0$ is removed. Over one sweep of $n\le10\,000$ that is $24\,801\,491$ removals instead of $12\,981\,568$.

The Python file fixes limit = 10000 inside solve and holds the search in the nested smallest_multiple_012, with a bytearray for seen, two lists for the pointers and a collections.deque, whose popleft is constant time where a list's front removal would cost $O(n)$. ^[8] It builds the integer during reconstruction and divides with //; Python integers are unbounded, so no extra library appears. The Java file uses a plain int[] q of length $n$ with head and tail indices, enough since every remainder is enqueued at most once, and hoists r10 = (rem * 10) % n out of the digit loop, forming r10 + digit and subtracting $n$ once if the sum reaches it — one remainder operation per vertex instead of three. new BigInteger(multiple) then parses the string and divide gives the quotient. ^[8] Neither port has checkpoints or options, and all three allocate fresh arrays per $n$.

Complexity and Verification

Counting remainder arithmetic as one step, a search initialises $O(n)$ array entries, removes at most $n$ remainders and inspects three edges per nonzero removal, costing $O(n)$ time and $O(n)$ memory; reconstruction adds $O(L)$ steps for the $L\le n$ digits. Rebuilding $f(n)$ and dividing by $n$ is separate work, up to $O(L^{2})$ digit operations, negligible at $L\le20$. Summing the search work over $n=1,\ldots,N$ gives

$$\sum_{n=1}^{N}O(n)=O(N^{2}),$$

and for $N=10\,000$ the crude count is $N(N+1)/2=50\,005\,000$ remainders. One measured sweep does about half of that: $24\,801\,491$ vertices leave the queue and $74\,374\,476$ edges are inspected, because most searches reach remainder $0$ long before the graph is exhausted. Only $1112$ searches mark all $n$ of their remainders, the largest being $n=9999$, the slowest case and the one with the longest $f$. With four-byte int the arrays and the queue hold at most $13n$ bytes of elements, so $130$ kB at $n=10\,000$ — an upper bound, not a measured process peak. Timed once on the machine used here, the C++ program takes $0.19$ s, the Java port $0.22$ s and the Python port $5.5$ s.

The C++ file checks itself first: $f(2)=2$, $f(3)=12$, $f(7)=21$, $f(42)=210$ and $11363107$ for $n\le100$. Beyond those, the following was verified for this article.

All three implementations give $1389$ for $n\le10$, $11363107$ for $n\le100$ and $111427232491$ for $n\le1000$, and the search reproduces $f(89)=1121222$. Only C++ takes a limit on the command line; the other two were run from copies with the hard-coded limit changed.
Listing all $531\,440$ integers with at most twelve digits from $\{0,1,2\}$ in increasing numerical order and keeping the first multiple of $n$ agrees with the search for $9987$ of the $10\,000$ values of $n$; the other $13$ have longer $f(n)$.
An independent method with no queue reproduces all $10\,000$ strings, the twenty-digit $f(9999)$ included: a backward table recording whether remainder $r$ can reach $0$ in exactly $j$ further digits, then a greedy left-to-right choice of the smallest digit that still allows a completion.
The first twelve values agree with A181060 and the quotients with A181061. ^[5]
Stopping the moment remainder $0$ enters the queue gives the same string for every $n\le10\,000$, confirming Section 5 numerically too.

These cross-checks are not part of the published programs.

Footnotes and References

The references below supply the background facts used above. The existence argument, the remainder graph, the minimality proof and the operation counts are derived explicitly in this article.

Project Euler 303 — Multiples with Small Digits. The official statement defines f(n) as the least positive multiple of n whose base-10 digits are all at most 2, lists f(2) = 2, f(3) = 12, f(7) = 21, f(42) = 210 and f(89) = 1121222, gives 11363107 for the sum of f(n)/n up to n = 100, and asks for the sum up to n = 10000.
Wikipedia — Breadth-first search states that the algorithm explores all nodes at the present depth before the next level, uses a first-in-first-out queue rather than a stack, and finds the shortest path in edges from a root to every vertex in time O(|V| + |E|) — the facts used in Sections 4, 5 and the complexity section.
Wikipedia — Pigeonhole principle: if n items are put into m containers with n greater than m, at least one container holds more than one item — applied in Section 2 to the m repunits and the m − 1 nonzero remainders modulo m.
Wikipedia — Repunit. The base-10 repunit is the number written with k ones, with closed form (10^k − 1)/9 for k at least 1, as used in Section 2.
OEIS A181060, "a(n) is the smallest positive multiple of n whose decimal digits are all 0, 1 or 2", lists 1, 2, 12, 12, 10, 12, 21, 112, 12222, 10, 11, 12 from n = 1 and says it was inspired by this problem. Its cross-reference A181061 gives the smallest positive k with all digits of n·k in {0, 1, 2}; that entry starts at n = 0, and its terms for n = 1 to 12 are the quotients f(n)/n.
OEIS A004290, "Least positive multiple of n that when written in base 10 uses only 0's and 1's", gives 1, 10, 111, 100, 10, 1110, 1001, 1000, 111111111 for n = 1 to 9; the ninth term is the comparison in Section 10.
Boost.Multiprecision — cpp_int is documented as the arbitrary-precision integer typedef of cpp_int_backend; the C++ program uses it for the multiples and the total.
Python — collections.deque states that appends and pops at either end cost approximately O(1), whereas a list incurs O(n) memory movement for pop(0). Java — BigInteger documents immutable arbitrary-precision integers, a constructor translating a decimal string, and divide.
C++ — Euler303.cpp. The linked immutable revision contains smallest_multiple_with_digits_leq_2, solve and run_checkpoints, and is the implementation record for this article; the comparisons above are extra checks, not tests in that file.

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));
    }
}