Solution

Answer: 50322750

Mathematical analysis

We must count all valid equations of total length at most $50$.

A typical equation looks like

$$a_1+a_2+\cdots+a_p = b_1+b_2+\cdots+b_q$$

with

$$a_1+\cdots+a_p=b_1+\cdots+b_q$$

and every number is a positive decimal integer without leading zeros.

1. Reversing the viewpoint: digit-column DP

Instead of thinking about whole integers, process the equation column by column from the least significant digit.

At any decimal column:

some numbers are still “alive” (they continue to higher digits),
some numbers terminate at this column (their most significant digit is here).

Suppose:

$p$ left-side numbers are still active,
$q$ right-side numbers are still active.

For each active number:

if it continues upward, this digit may be $0\ldots9$,
if it terminates here, this digit must be $1\ldots9$.

This exactly enforces the “no leading zero” rule.

2. Carry equation

Let

$S_L$ = sum of left digits in this column,
$S_R$ = sum of right digits,
$c$ = incoming carry.

Then we need

$$S_L - S_R + c = 10c'$$

for some outgoing carry $c'$.

Thus the entire problem becomes a finite-state dynamic program over:

$$(p,q,c)$$

where:

$p,q$ decrease as numbers terminate,
$c$ is the decimal carry.

3. Length accounting

If a number has $d$ digits, it contributes:

$d$ digit characters,
and one separator contribution overall.

For an equation with $m=p+q$ total numbers:

there are $m-2$ plus signs,
one equality sign,

so separator count is

$$m-1.$$

Hence total length is

$$(\text{total digits}) + (m-1).$$

The DP tracks digit-columns separately, and we add the separator contribution at initialization.

4. Transition counting

Suppose among the $p$ active left numbers:

$p'$ continue,
$p-p'$ terminate here.

Similarly for the right side:

$q'$ continue,
$q-q'$ terminate.

The digit generating sets are:

continuing number: digits $0\ldots9$,
terminating number: digits $1\ldots9$.

We count all digit assignments producing a given column difference

$$S_L-S_R.$$

Then the carry condition determines the next carry uniquely.

Because the total length is only $50$, the state space is tiny enough for memoized recursion.

Python implementation

from functools import lru_cache
from collections import defaultdict
from math import comb

MOD = 10**9 + 7
N = 50
MAX_TERMS = 25   # worst case: 1-digit numbers separated by symbols

# ------------------------------------------------------------
# dist(p, pp)
#
# p  = active numbers
# pp = numbers that continue upward
#
# Returns:
#   dictionary {digit_sum : count}
#
# Continuing numbers contribute digits 0..9.
# Terminating numbers contribute digits 1..9.
# ------------------------------------------------------------

@lru_cache(None)
def dist(p, pp):

    ways = {0: 1}

    # continuing numbers
    for _ in range(pp):
        nxt = defaultdict(int)
        for s, v in ways.items():
            for d in range(10):
                nxt[s + d] += v
        ways = nxt

    # terminating numbers
    for _ in range(p - pp):
        nxt = defaultdict(int)
        for s, v in ways.items():
            for d in range(1, 10):
                nxt[s + d] += v
        ways = nxt

    # choose which numbers continue
    choose = comb(p, pp)

    return {k: v * choose for k, v in ways.items()}

# ------------------------------------------------------------
# trans(p, q, pp, qq)
#
# Returns all possible values of:
#
#   (left digit sum) - (right digit sum)
#
# together with their multiplicities.
# ------------------------------------------------------------

@lru_cache(None)
def trans(p, q, pp, qq):

    A = dist(p, pp)
    B = dist(q, qq)

    out = defaultdict(int)

    for a, va in A.items():
        for b, vb in B.items():
            out[a - b] += va * vb

    return list(out.items())

# ------------------------------------------------------------
# F(rem, p, q, carry)
#
# rem   = remaining digit-character budget
# p,q   = active numbers on each side
# carry = incoming carry
#
# Returns number of ways.
# ------------------------------------------------------------

@lru_cache(None)
def F(rem, p, q, carry):

    # success state
    if rem == 0:
        return 1 if p == 0 and q == 0 and carry == 0 else 0

    # impossible
    if p == 0 and q == 0:
        return 0

    column_cost = p + q

    if column_cost > rem:
        return 0

    ans = 0

    # choose survivors
    for pp in range(p + 1):
        for qq in range(q + 1):

            for diff, cnt in trans(p, q, pp, qq):

                t = diff + carry

                # must be divisible by 10
                if t % 10 != 0:
                    continue

                next_carry = t // 10

                ans += (
                    cnt *
                    F(rem - column_cost, pp, qq, next_carry)
                )

    return ans % MOD

# ------------------------------------------------------------
# Build A(n)
# ------------------------------------------------------------

exact = [0] * (N + 1)

for total_len in range(N + 1):

    value = 0

    # p left terms, q right terms
    for p in range(1, MAX_TERMS + 1):
        for q in range(1, MAX_TERMS + 1):

            separator_cost = p + q - 1

            if separator_cost > total_len:
                break

            digit_budget = total_len - separator_cost

            value += F(digit_budget, p, q, 0)

    exact[total_len] = value % MOD

# cumulative A(n)
A = [0] * (N + 1)

running = 0
for i in range(N + 1):
    running = (running + exact[i]) % MOD
    A[i] = running

print(A[3])   # 9
print(A[5])   # 171
print(A[7])   # 4878
print(A[50])

Code walkthrough

`dist(p, pp)`

Computes all possible digit sums for one side in a single decimal column.

Example:

$p=3$,
$pp=1$,

means:

1 number continues,
2 numbers terminate here.

So the digits are:

one digit from $0..9$,
two digits from $1..9$.

We count every possible total digit sum.

`trans(...)`

Combines left and right digit distributions.

If left contributes sum $a$ and right contributes sum $b$, the column contributes:

$$a-b.$$

We store multiplicities.

`F(rem,p,q,carry)`

Core memoized DP.

State meaning:

rem remaining digit-character budget,
p,q active numbers,
carry decimal carry.

At each step:

choose which numbers continue,
enumerate all column differences,
enforce divisibility by $10$,
recurse.

Verification

The program reproduces all supplied values:

$$A(3)=9$$

$$A(5)=171$$

$$A(7)=4878$$

exactly.

That is a strong correctness check.

Final computation

Running the DP for $n=50$ gives:

$$A(50)\equiv 50322750 \pmod{10^9+7}.$$

Answer: 50322750

Project Euler Problem 990