Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

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

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. That is why the dynamic-programming state can be just

$\text{state}_i=(c_i,\Delta_i).$

If the next digit chosen is $a_i$, then the produced output digit is $b_i$, so the update is simply

$\Delta_{i+1}=\Delta_i+a_i-b_i.$

3. Why the final condition is $\Delta_d=s(c_d)$

After all $d$ input digits have been processed, the product has the form

$137n=\sum_{i=0}^{d-1} b_i10^i+c_d10^d.$

The first term contributes digit sum $\sum_{i=0}^{d-1} b_i$, and the untouched carry tail contributes $s(c_d)$. Therefore

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

Since also $s(n)=\sum_{i=0}^{d-1} a_i$, the target condition $s(n)=s(137n)$ is equivalent to

$\sum_{i=0}^{d-1} a_i-\sum_{i=0}^{d-1} b_i=s(c_d),$

that is, precisely

$\boxed{\Delta_d=s(c_d).}$

This is the key point: we never need the full product, only the final carry and the running digit-sum difference.

4. Why the state space stays small

The carry is tightly bounded. If $c_i\le 136$, then

$c_{i+1}\le \left\lfloor\frac{137\cdot 9+136}{10}\right\rfloor=136.$

Because $c_0=0$, induction gives

$0\le c_i\le 136\qquad \text{for all }i.$

The difference $\Delta_i$ also grows only linearly, since each step changes it by $a_i-b_i\in[-9,9]$. So the reachable state space is tiny compared with $10^{18}$ possibilities. The implementation uses a safe offset when packing $(carry,diff)$ into a hash-map key.

5. Worked example: $n=9$

This is the smallest nonzero solution. We have

$137\cdot 9=1233,\qquad s(9)=9,\qquad s(1233)=1+2+3+3=9.$

The DP sees this as one processed digit:

$t_0=137\cdot 9+0=1233,\qquad b_0=3,\qquad c_1=123.$

Hence

$\Delta_1=9-3=6,\qquad s(c_1)=s(123)=6.$

So the acceptance condition $\Delta_1=s(c_1)$ holds exactly.

6. Small checkpoints

The code verifies the DP against brute force on smaller sizes:

$\text{solve}(4,137)=306,\qquad \text{solve}(5,137)=2902.$

After those checks, the program computes the required case

$\text{solve}(18,137)=20444710234716473.$

How the Code Works

The implementation stores a hash map from packed keys $(carry,diff)$ to counts. For each of the $18$ positions, it tries all $10$ possible next digits, computes the new output digit and carry, updates the difference, and accumulates the new count. At the end it sums exactly those states for which diff == digit_sum(carry). A brute-force routine is included only for the small validation cases.

Complexity Analysis

If $S$ is the number of reachable $(carry,diff)$ states, then each layer tries $10$ digits, so the running time is

$O(d\cdot S\cdot 10),$

with memory $O(S)$. Here $d=18$, and $S$ is small because the carry is bounded by $136$ and the difference range is narrow. This is exponentially smaller than testing all $10^{18}$ candidates one by one.