Problem 290: Digital Signature

Project Euler Problem 290 Solution

EulerSolve provides an optimized solution for Project Euler Problem 290, Digital Signature, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We must count all decimal strings of length $d=18$, equivalently all integers $0 \le n \lt 10^{18}$, such that $$s(n)=s(137n),$$ where $s(x)$ denotes the base-10 digit sum. Direct enumeration over $10^{18}$ candidates is impossible, so we need to process the multiplication structurally, one digit at a time. Mathematical Approach 1. Multiply from right to left Write $$n=\sum_{i=0}^{d-1} a_i 10^i,\qquad a_i\in\{0,\dots,9\}.$$ When we multiply by $m=137$, the $i$-th output digit depends only on the current input digit $a_i$ and the incoming carry $c_i$: $$t_i=137a_i+c_i,\qquad b_i=t_i\bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$ Thus the low $d$ digits of $137n$ are produced digit by digit, and whatever remains above position $d-1$ is exactly the final carry $c_d$. 2. The whole past collapses to carry plus digit-sum difference After processing the first $i$ digits, define $$\Delta_i=\sum_{j=0}^{i-1} a_j-\sum_{j=0}^{i-1} b_j.$$ This is the difference between the digit sum already contributed by $n$ and the digit sum already contributed by the low part of $137n$. Once $(c_i,\Delta_i)$ is known, the future no longer depends on earlier digits individually....

Detailed mathematical approach

Problem Summary

Write $s(x)$ for the sum of the decimal digits of a non-negative integer $x$. We must count the integers $n$ with $0\le n\lt10^{18}$ for which $s(n)=s(137n)$, that is, the sum of the digits of $n$ equals the sum of the digits of $137n$. ^[1] The number $n=0$ counts, and so does $n=9$, because $137\cdot9=1233$ and $1+2+3+3=9$. The statement gives no smaller checkpoint, so the small counts below were computed by brute force.

The whole solution in one sentence: we multiply $n$ by $137$ the way it is done on paper, from the last digit to the first, and notice that the rest of the multiplication only needs two numbers, the current carry and the difference of the two digit sums so far, so instead of testing $10^{18}$ numbers we count how many digit strings lead to each of a few tens of thousands of such pairs.

Mathematical Approach

We first look at small cases and at a quick necessary condition, then follow the multiplication digit by digit to find out what it has to remember, and finally count all digit strings in groups.

1. Small cases

For $n=18$ we get $137\cdot18=2466$, whose digit sum is $18$, while $s(18)=9$; so $18$ is not a solution, whereas $9$ is. Below $1000$ there are $33$ solutions, and the first of them are $0, 9, 90, 99, 198, 279, 369, 387, 396$. Let $f(d)$ be the number of solutions $n\lt10^d$; the problem asks for $f(18)$. Testing every number gives

$$\begin{aligned}f(1),f(2),f(3)&=2,\ 4,\ 33,\\ f(4),f(5),f(6)&=306,\ 2902,\ 27955.\end{aligned}$$

From $f(3)$ to $f(6)$ every further digit multiplies the count by more than $9$. Testing all $10^{18}$ candidates one by one is out of the question, so we need a method that counts many candidates together instead of looking at each one.

2. A necessary condition: every solution is a multiple of 9

The number $10$ leaves the remainder $1$ after division by $9$, so every power $10^i$ does as well, and therefore every number leaves the same remainder as its digit sum: $x\equiv s(x)\pmod 9$. This is the old rule of casting out nines. ^[2] If $s(n)=s(137n)$, then

$$\begin{aligned}n&\equiv s(n)=s(137n)\\&\equiv137n\pmod 9,\end{aligned}$$

so $9$ divides $136n$. Since $136=15\cdot9+1$ has no common factor with $9$, it follows that $9$ divides $n$. Indeed all $33$ solutions below $1000$ are multiples of $9$, but only $33$ of the $112$ multiples of $9$ there are solutions, so the condition is far from sufficient, and we must look at the digits of the product itself.

3. Multiplying by 137 on paper

Write $n$ with exactly $d$ digits, allowing leading zeros, as $n=\sum_{i=0}^{d-1}a_i10^i$ with digits $a_i\in\{0,\dots,9\}$, so that $a_0$ is the units digit. Multiplying by $137$ in one pass, the way one multiplies by a single digit on paper, starts with the carry $c_0=0$ and handles one digit per step, from right to left:

$$\begin{aligned}t_i&=137a_i+c_i,\\ b_i&=t_i\bmod10,\\ c_{i+1}&=\lfloor t_i/10\rfloor.\end{aligned}$$

The digit $b_i$ is written down and the carry $c_{i+1}$ moves one place to the left; after the last step the remaining carry $c_d$ is written in front. Long multiplication handles its carries in the same way, ^[3] but since we multiply by the whole number $137$ at once, our carry can exceed $9$. For $n=387$:

$a_0=7$: $t_0=959$, so $b_0=9$ and $c_1=95$;
$a_1=8$: $t_1=1096+95=1191$, so $b_1=1$ and $c_2=119$;
$a_2=3$: $t_2=411+119=530$, so $b_2=0$ and $c_3=53$.

The carry $53$ followed by $b_2,b_1,b_0$ gives $137\cdot387=53019$. We go from right to left because carries move to the left: every digit $b_i$ is final as soon as it is written, while a computation from the left would need the carry coming from digits not seen yet.

4. The carry and the digits of the product

Let $x_i=n\bmod10^i$ be the number formed by the last $i$ digits of $n$. The steps above keep the following identity true:

$$137\,x_i=\sum_{j=0}^{i-1}b_j10^j+c_i\,10^i.$$

For $i=0$ both sides are $0$. If the identity holds for $i$, then $x_{i+1}=x_i+a_i10^i$ and $137a_i+c_i=t_i=b_i+10c_{i+1}$ give

$$\begin{aligned}137\,x_{i+1}&=\sum_{j=0}^{i-1}b_j10^j+t_i\,10^i\\&=\sum_{j=0}^{i}b_j10^j+c_{i+1}10^{i+1}.\end{aligned}$$

Two facts follow. The carry is small. Each $b_j$ is a digit, so the sum of the $b_j10^j$ lies between $0$ and $10^i-1$, and hence $c_i=\lfloor137x_i/10^i\rfloor$. Since $x_i\le10^i-1$, the carry is at most $136$. Conversely, for $i\ge3$ the quotient $137x_i/10^i$ starts at $0$, grows in steps of $137/10^i\lt1$ and ends at $137-137/10^i$, which lies between $136$ and $137$; so its integer part takes every value from $0$ to $136$, and from the third digit on every carry really occurs.

The digits of the product. For $i=d$ the identity reads $137n=\sum_{j\lt d}b_j10^j+c_d10^d$. Read from the units digit upwards, the digits of $137n$ are therefore $b_0,\dots,b_{d-1}$ followed by the digits of $c_d$, where leading zeros add nothing, and

$$s(137n)=\sum_{j=0}^{d-1}b_j+s(c_d).$$

For $387$ this gives $s(53019)=(9+1+0)+s(53)$${}=18=s(387)$, so $387$ is a solution. Leading zeros need no special care: for $a_i=0$ we have $t_i=c_i$, so the step only writes out the last digit of the carry and moves the rest on.

5. Two numbers are all the multiplication remembers

Let $\Delta_i$ be the digit sum of $n$ seen so far minus the digit sum of the product written so far:

$$\Delta_i=\sum_{j=0}^{i-1}(a_j-b_j),\qquad\Delta_0=0.$$

Since $s(n)=a_0+\dots+a_{d-1}$, Section 4 gives $s(n)-s(137n)=\Delta_d-s(c_d)$, and so

$$s(n)=s(137n)\iff\Delta_d=s(c_d).$$

We call the pair $(c_i,\Delta_i)$ the state after $i$ digits. A step needs nothing else: the new digit $a$ gives $t=137a+c$, and the new state $(c',\Delta')$ is

$$\begin{aligned}c'&=\lfloor t/10\rfloor,\\ \Delta'&=\Delta+a-(t\bmod10).\end{aligned}$$

Hence two digit strings that reach the same state after $i$ digits reach the same state again after any common continuation, and in the end they are accepted together or rejected together. The individual digits can be forgotten; only the state matters. For $387$ the states are $(0,0)$, $(95,-2)$, $(119,5)$ and $(53,8)$, and $8=s(53)$, so $387$ is accepted. For $18$ they are $(0,0)$, $(109,2)$ and $(24,-3)$, and $s(24)=6\ne-3$, so $18$ is rejected; indeed $\Delta_2-s(c_2)=-9$ equals $s(18)-s(2466)$. In the language of automata, the carries are the $137$ states of a Mealy machine, a finite-state machine whose output is determined by its current state and its current input: it reads the digits of $n$ and writes those of $137n$. ^[4]

6. Counting digit strings by their state

Let $N_i(c,\Delta)$ be the number of digit strings $a_0a_1\dots a_{i-1}$ that lead to the state $(c,\Delta)$. We start with $N_0(0,0)=1$ and all other counts $0$. Every string of $i+1$ digits is a string of $i$ digits followed by one more digit, and its state is obtained from the state of the shorter string by the step of Section 5. Grouping the longer strings by the state of their first $i$ digits and by their last digit therefore gives

$$N_{i+1}(c',\Delta')=\sum_{(c,\Delta,a)\mapsto(c',\Delta')}N_i(c,\Delta),$$

where the sum runs over all states $(c,\Delta)$ and digits $a$ whose step leads to $(c',\Delta')$. By Section 5 the number of solutions below $10^d$ is

$$f(d)=\sum_{c=0}^{136}N_d\bigl(c,s(c)\bigr).$$

Every string has exactly one state, so the counts after $i$ digits add up to $10^i$. This is dynamic programming: the counts for $i$ digits are computed once and reused for all longer strings, which makes it possible to count the solutions without visiting them all. ^[5]

7. Worked example: one and two digits

After one digit, the ten strings reach ten different states $(c_1,\Delta_1)$:

$a_0=0,1,2,3,4$ give $(0,0)$, $(13,-6)$, $(27,-2)$, $(41,2)$ and $(54,-4)$;
$a_0=5,6,7,8,9$ give $(68,0)$, $(82,4)$, $(95,-2)$, $(109,2)$ and $(123,6)$.

A state is accepted when $\Delta_1=s(c_1)$. This holds for $(0,0)$, because $s(0)=0$, and for $(123,6)$, because $s(123)=6$, and for no other state; for instance $s(13)=4\ne-6$. So $f(1)=2$, with the solutions $0$ and $9$.

After two digits, the $100$ strings reach $100$ different states, and exactly four of them are accepted:

$n=0$: the state stays $(0,0)$;
$n=9$, written $09$: $(123,6)$, then the leading $0$ gives $t=123$ and $(12,3)$, and $s(12)=3$, as $137\cdot9=1233$;
$n=90$: $(0,0)$, then the digit $9$ gives $(123,6)$;
$n=99$: $(123,6)$, then $t=1233+123=1356$ gives $(135,9)$, and $s(135)=9$, as $137\cdot99=13563$.

So $f(2)=4$. The first three layers have $10$, $100$ and $1000$ states, so up to three digits no two strings share a state and nothing is saved yet. From the fourth digit on the strings merge: the $10^4$ strings of four digits lead to only $3649$ states. For example, $n=1$ and $n=10$, written $0001$ and $0010$, have the products $0137$ and $1370$ and both end in the state $(0,-10)$; exactly five four-digit strings do, those of $1$, $10$, $28$, $37$ and $55$, so $N_4(0,-10)=5$. A next digit $2$ gives $t=274$ for all five at once and moves them together to the state $(27,-12)$, which is why the program adds stored counts instead of single strings. After that the number of states grows far more slowly than the number of strings.

8. How many states there are

By Section 4 the carry takes at most $137$ values, and each step changes $\Delta$ by $a-b$, a number between $-9$ and $9$. So $|\Delta_i|\le9i$, and after $i$ digits there are at most $137(18i+1)$ states, at most $44525$ for $i=18$. The true numbers are smaller. After $4$, $5$ and $6$ digits there are $3649$, $5677$ and $7715$ states; from the fifth through the eighteenth layer, each layer has between $1828$ and $2038$ more states than the one before; and after $18$ digits there are $30745$ states, with $\Delta$ between $-124$ and $124$. All $137$ carries occur at the end, each of them together with the difference $s(c)$, so the final sum of Section 6 has exactly $137$ terms. Instead of $10^{18}$ numbers, the whole count handles $10$ digits for every state of every layer, $2295970$ steps in total.

How the Code Works

The C++ program ^[7] starts in main, which reads the options with parse_arguments: by default $18$ digits and the multiplier $137$, which --digits= and --multiplier= can change, while --skip-checkpoints turns the self-check off. Unless that flag is given, run_checkpoints first compares solve with brute_small, which simply tests every $n$ below $10^4$ and below $10^5$; if a comparison fails, the program says so and exits with code 2. Then it prints the count that solve returns for the chosen digits and multiplier.

solve is the counting of Section 6. A state $(c,\Delta)$ is packed into one integer key $1000c+\Delta+500$, where $500$ is the constant kOffset, and the counts $N_i$ live in a std::unordered_map<int, u64> named dp, which starts with the key of the state $(0,0)$ and the count 1. For each of the $18$ positions a new map next is filled: every entry is unpacked into carry and diff, and for each digit d from 0 to 9 the program computes t = multiplier * d + carry, the written digit t % 10, the new carry t / 10 and the new difference, and adds the count to the entry of the new key, exactly the step of Section 5. Then dp.swap(next) makes the new layer current. At the end, the counts of all keys with diff == digit_sum(carry) are added up, which is the final sum of Section 6. Both maps get a size hint, dp.reserve(100000) at the start and eight times the current number of states for next; a map simply grows when the hint is too small, as in the first three layers, where the number of states grows tenfold. ^[6]

For the problem's $18$ digits and the multiplier $137$ the packing is safe: the carry is at most $136$ and $|\Delta|\le9\cdot18=162\lt500$, so $\Delta+500$ stays between $338$ and $662$, and different states get different keys. The counts are safe too: the counts of one layer add up to $10^i\le10^{18}$, which is below the largest signed 64-bit integer $2^{63}-1\approx9.2\cdot10^{18}$, so neither the unsigned 64-bit u64 of the C++ program nor the long of the Java program can overflow, and the final count is below $10^{18}$ as well. The options are not checked against such limits: much larger arguments can overflow the argument parser, the int keys or the 64-bit counts. For instance, with --digits=20 --multiplier=1 every number qualifies, and the count $10^{20}$ does not fit in u64. The built-in checks always use the multiplier $137$. The Python and Java files mirror solve line by line with the same key packing. Python uses a dict with nxt.get(next_key, 0) + ways and integers of unlimited precision; its solve takes $18$ and $137$ as default arguments. Java uses a HashMap<Integer, Long> with getOrDefault and fixes $18$ and $137$ as local variables; the initial capacity of each new map, $8/0.75$ times the current number of states, is the same size hint for the default load factor $0.75$. Both return the count as a string and contain no self-check.

Complexity and Verification

For $d$ digits and a multiplier $m$ the carry takes at most $m$ values, so layer $i$ has at most $m(18i+1)$ states. Trying ten digits for every state of every layer gives $O(m\,d^2)$ map updates, and the two maps of the current and the next layer hold $O(m\,d)$ entries. For the problem the counts and keys fit in machine integers, so each update has expected constant cost; much larger $d$ or $m$ would need wider integers. The main count makes $2295970$ updates and stores at most $30745$ entries per map, and the C++ checks add two small counts and brute-force scans of $10^4$ and $10^5$ numbers. In our runs all three programs finished in well under a second.

Before the main count, the C++ program checks the counting against brute force for $4$ and $5$ digits, where both give $306$ and $2902$. For this article the same counting was compared with a brute force over every $n\lt10^9$: both give $f(7)=271523$, $f(8)=2636394$ and $f(9)=25594614$, and the brute force found no solution that is not a multiple of $9$, as Section 2 predicts. The counts of every layer add up to $10^i$, and the C++, Python and Java programs print the same number. As a further check, $n$ was split into two nine-digit halves, $n=10^9H+L$. With $137L=10^9c+R$, where $R\lt10^9$ and $c\le136$, we have $s(137n)=s(137H+c)+s(R)$. Counting the lower halves by $c$ and $s(L)-s(R)$, the upper halves, with the same state counting started from the carry $c$, by $c$ and $s(137H+c)-s(H)$, and combining matching pairs gives the same result for $18$ digits. This check is not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The state $(c,\Delta)$, its acceptance rule $\Delta_d=s(c_d)$, the bounds on the number of states and the operation counts are derived explicitly in this article.

Project Euler 290 — Digital Signature. The official statement asks how many integers 0 ≤ n < 10¹⁸ have the property that the sum of the digits of n equals the sum of the digits of 137n. It gives no smaller example.
Wikipedia — Casting out nines. Replacing a number by the sum of its digits leaves the remainder after division by nine unchanged, because every number of the form 10ⁱ − 1 is divisible by 9; Section 2 uses this to show that every solution is a multiple of 9.
Wikipedia — Multiplication algorithm. Its pseudocode for long multiplication adds the carry to a digit product, takes the quotient by the base as the new carry and the remainder as the digit, and takes the last digit from the final carry, the step of Section 3.
Wikipedia — Mealy machine. A Mealy machine is a finite-state machine whose output values are determined both by its current state and by the current inputs; the multiplication by 137 is such a machine, with the 137 possible carries as its states.
Wikipedia — Dynamic programming. Dynamic programming solves each subproblem only once and stores the solutions in a table; the article notes that it makes it possible to count the number of solutions without visiting them all, which is what the counts of Section 6 do.
cppreference — std::unordered_map::reserve makes room for at least the given number of elements within the maximum load factor. The Java HashMap documentation gives the default load factor 0.75: no rehash occurs if the initial capacity exceeds the maximum number of entries divided by the load factor. Python — numeric types: integers have unlimited precision.
C++ — Euler290.cpp. The linked immutable C++ revision contains parse_arguments, digit_sum, solve, brute_small and run_checkpoints. It is the implementation record for this article.

Problem 290 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>

namespace {

using u64 = std::uint64_t;

struct Options {
    int digits = 18;
    int multiplier = 137;
    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, "--digits=", options.digits) ||
            parse_int_after_prefix(arg, "--multiplier=", options.multiplier)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.digits >= 1 && options.multiplier >= 1;
}

int digit_sum(u64 x) {
    int s = 0;
    while (x > 0ULL) {
        s += static_cast<int>(x % 10ULL);
        x /= 10ULL;
    }
    return s;
}

u64 solve(const int digits, const int multiplier) {
    // key = carry * 1000 + (diff + offset)
    // diff = sum(processed digits of n) - sum(processed low digits of multiplier*n)
    static constexpr int kOffset = 500;

    std::unordered_map<int, u64> dp;
    dp.reserve(100000);
    dp[0 * 1000 + kOffset] = 1ULL;

    for (int pos = 0; pos < digits; ++pos) {
        std::unordered_map<int, u64> next;
        next.reserve(dp.size() * 8U);
        for (const auto& [key, ways] : dp) {
            const int carry = key / 1000;
            const int diff = (key % 1000) - kOffset;
            for (int d = 0; d <= 9; ++d) {
                const int t = multiplier * d + carry;
                const int out_digit = t % 10;
                const int next_carry = t / 10;
                const int next_diff = diff + d - out_digit;
                const int next_key = next_carry * 1000 + (next_diff + kOffset);
                next[next_key] += ways;
            }
        }
        dp.swap(next);
    }

    u64 answer = 0ULL;
    for (const auto& [key, ways] : dp) {
        const int carry = key / 1000;
        const int diff = (key % 1000) - kOffset;
        if (diff == digit_sum(static_cast<u64>(carry))) {
            answer += ways;
        }
    }
    return answer;
}

u64 brute_small(const int digits, const int multiplier) {
    u64 upper = 1ULL;
    for (int i = 0; i < digits; ++i) {
        upper *= 10ULL;
    }
    u64 count = 0ULL;
    for (u64 n = 0; n < upper; ++n) {
        if (digit_sum(n) == digit_sum(static_cast<u64>(multiplier) * n)) {
            ++count;
        }
    }
    return count;
}

bool run_checkpoints() {
    if (solve(4, 137) != brute_small(4, 137)) {
        std::cerr << "Checkpoint failed for digits=4 multiplier=137" << '\n';
        return false;
    }
    if (solve(5, 137) != brute_small(5, 137)) {
        std::cerr << "Checkpoint failed for digits=5 multiplier=137" << '\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.digits, options.multiplier) << '\n';
    return 0;
}

Python

def digit_sum(x):
    s = 0
    while x > 0:
        s += x % 10
        x //= 10
    return s

def solve(digits=18, multiplier=137):
    kOffset = 500
    dp = {0 * 1000 + kOffset: 1}
    
    for _ in range(digits):
        nxt = {}
        for key, ways in dp.items():
            carry = key // 1000
            diff = (key % 1000) - kOffset
            for d in range(10):
                t = multiplier * d + carry
                out_digit = t % 10
                next_carry = t // 10
                next_diff = diff + d - out_digit
                next_key = next_carry * 1000 + (next_diff + kOffset)
                nxt[next_key] = nxt.get(next_key, 0) + ways
        dp = nxt
        
    answer = 0
    for key, ways in dp.items():
        carry = key // 1000
        diff = (key % 1000) - kOffset
        if diff == digit_sum(carry):
            answer += ways
            
    return str(answer)

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

Java

import java.util.HashMap;
import java.util.Map;

public class Euler290 {
    static int digitSum(long x) {
        int s = 0;
        while (x > 0) {
            s += (int) (x % 10);
            x /= 10;
        }
        return s;
    }

    public static String solve() {
        int digits = 18;
        int multiplier = 137;
        int kOffset = 500;

        Map<Integer, Long> dp = new HashMap<>();
        dp.put(0 * 1000 + kOffset, 1L);

        for (int pos = 0; pos < digits; ++pos) {
            Map<Integer, Long> next = new HashMap<>((int) (dp.size() * 8 / 0.75f) + 1);
            for (Map.Entry<Integer, Long> entry : dp.entrySet()) {
                int key = entry.getKey();
                long ways = entry.getValue();

                int carry = key / 1000;
                int diff = (key % 1000) - kOffset;

                for (int d = 0; d <= 9; ++d) {
                    int t = multiplier * d + carry;
                    int outDigit = t % 10;
                    int nextCarry = t / 10;
                    int nextDiff = diff + d - outDigit;
                    int nextKey = nextCarry * 1000 + (nextDiff + kOffset);

                    next.put(nextKey, next.getOrDefault(nextKey, 0L) + ways);
                }
            }
            dp = next;
        }

        long answer = 0L;
        for (Map.Entry<Integer, Long> entry : dp.entrySet()) {
            int key = entry.getKey();
            long ways = entry.getValue();
            int carry = key / 1000;
            int diff = (key % 1000) - kOffset;
            if (diff == digitSum(carry)) {
                answer += ways;
            }
        }

        return String.valueOf(answer);
    }

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