Solution

Answer: 20444710234716473

Let $s(n)$ denote the sum of the decimal digits of $n$.

We seek the number of integers

$$0 \le n < 10^{18}$$

such that

$$s(n)=s(137n).$$

Mathematical analysis

Let

$$n=\sum_{i=0}^{17} d_i 10^i, \qquad 0\le d_i\le 9.$$

We process multiplication by $137$ digit-by-digit from least significant to most significant.

1. Digit-sum behavior under carrying

Suppose at some step we compute

$$137d_i + c_i,$$

where $c_i$ is the incoming carry.

Write

$$137d_i+c_i = 10c_{i+1}+e_i,$$

with $e_i$ the output digit of $137n$.

Then:

$$e_i = (137d_i+c_i)\bmod 10, \qquad c_{i+1}=\left\lfloor \frac{137d_i+c_i}{10}\right\rfloor.$$

The contribution to the digit-sum difference is

$$d_i-e_i.$$

After all 18 digits are processed, some carry remains. Its decimal digits also contribute to the digit sum of $137n$.

Hence

$$s(n)-s(137n) = \sum_{i=0}^{17}(d_i-e_i) - s(c_{18}),$$

where $s(c_{18})$ is the digit sum of the final carry.

We therefore need

$$\sum_{i=0}^{17}(d_i-e_i)=s(c_{18}).$$

This is ideal for digit DP.

2. State compression

At each position we only need:

the current carry,
the accumulated difference

$$\Delta=\sum(d_i-e_i).$$

So define:

$$\text{DP}(pos, carry, \Delta)$$

= number of ways to fill digits from position pos onward.

At the end (pos = 18), we accept iff

$$\Delta = s(carry).$$

The carry remains small:

$$137\cdot 9 + \text{carry} < 1400,$$

so the state space is tiny.

Python implementation

from functools import lru_cache

LENGTH = 18
MULTIPLIER = 137

@lru_cache(None)
def dp(pos, carry, diff):
    """
    pos   : current digit position (0 = least significant)
    carry : carry entering this position
    diff  : accumulated value of sum(d_i - e_i)
    """

    # All 18 digits processed
    if pos == LENGTH:

        # Remaining carry contributes digits to 137n
        carry_digit_sum = 0
        c = carry

        while c > 0:
            carry_digit_sum += c % 10
            c //= 10

        # Need total digit sums to match
        return 1 if diff == carry_digit_sum else 0

    total = 0

    # Choose next digit of n
    for d in range(10):

        value = MULTIPLIER * d + carry

        # Output digit of 137n
        out_digit = value % 10

        # Next carry
        next_carry = value // 10

        # Update digit-sum difference
        next_diff = diff + d - out_digit

        total += dp(pos + 1, next_carry, next_diff)

    return total

answer = dp(0, 0, 0)

print(answer)

Code walkthrough

Constants

LENGTH = 18
MULTIPLIER = 137

We consider all integers below $10^{18}$, so exactly 18 decimal positions.

Memoized DP

@lru_cache(None)
def dp(pos, carry, diff):

The DP state stores:

pos: current digit index,
carry: carry from previous multiplication step,
diff: accumulated difference

$$\sum(d_i-e_i).$$

Base case

if pos == LENGTH:

All digits have been processed.

The remaining carry still contributes decimal digits to $137n$, so we compute:

carry_digit_sum

and accept iff

diff == carry_digit_sum

which is exactly equivalent to

$$s(n)=s(137n).$$

Transition

For every possible decimal digit:

for d in range(10):

we compute:

value = 137 * d + carry

The resulting output digit is:

out_digit = value % 10

and the next carry is:

next_carry = value // 10

The digit-sum difference changes by:

d - out_digit

so we recurse.

Small sanity check

Take $n=1$:

$$137n = 137.$$

Digit sums:

$$s(1)=1,\qquad s(137)=1+3+7=11.$$

Not equal.

Our DP rejects this because the accumulated difference is not balanced by the final carry digits.

Final verification

The count should be large:

there are $10^{18}$ candidates total,
the digit-sum constraint is restrictive but not extremely rare,
the final answer around $2\times 10^{16}$ is plausible.

The DP state space is tiny and exhaustive, so the result is exact.

Answer: 20444710234716473

Project Euler Problem 290