Project Euler

Sums of Digit Factorials

Define the following functions: f(n) = sum_(d in digits(n)) d! (sum of factorials of the digits of n). sf(n) = s(f(n)), where s(x) denotes the digit sum of x. g(i) = min{n in Z^+: sf(n) = i}. sg(i)...

Source sync Apr 19, 2026

Problem #0254

Level Level 14

Solved By 1,139

Languages C++, Python

Answer 8184523820510

Length 579 words

modular_arithmeticlinear_algebraoptimization

Define $f(n)$ as the sum of the factorials of the digits of $n$. For example, $f(342) = 3! + 4! + 2! = 32$.

Define $sf(n)$ as the sum of the digits of $f(n)$. So $sf(342) = 3 + 2 = 5$.

Define $g(i)$ to be the smallest positive integer $n$ such that $sf(n) = i$. Though $sf(342)$ is $5$, $sf(25)$ is also $5$, and it can be verified that $g(5)$ is $25$.

Define $sg(i)$ as the sum of the digits of $g(i)$. So $sg(5) = 2 + 5 = 7$.

Further, it can be verified that $g(20)$ is $267$ and $\displaystyle \sum sg(i)$ for $1 \le i \le 20$ is $156$.

What is $\displaystyle \sum sg(i)$ for $1 \le i \le 150$?

Problem 254: Sums of Digit Factorials

Mathematical Foundation

Lemma 1 (Digit-Multiset Invariance). The function $f(n)$ depends only on the multiset of digits of $n$ . Consequently, the smallest $n$ achieving a given multiset has its digits arranged in non-decreasing order.

Proof. $f(n) = \sum_{d \in \text{digits}(n)} d!$ is a symmetric function of the digit multiset. Among all integers with the same digit multiset, the smallest is obtained by sorting digits in ascending order (with the smallest nonzero digit first, but since leading zeros would reduce the digit count, the non-decreasing arrangement is minimal). $\square$

Lemma 2 (Dominance of 9s). For large target values $i$ , the minimizer $g(i)$ consists of a large number of 9s plus a small “adjustment” set of digits from $\{1, \ldots, 8\}$ .

Proof. To minimize $n$ , we minimize the number of digits first, then the digit values. Since $9! = 362880$ is the largest single-digit factorial, using 9s maximizes $f(n)$ per digit, thus requiring the fewest digits to reach a given $f$ -value. Hence the optimal strategy is to use as many 9s as needed, adjusting with a few smaller digits to hit the exact digit-sum target for $f(n)$ . $\square$

Theorem 1 (Modular Constraint). Since $s(x) \equiv x \pmod{9}$ for all $x \ge 1$ , we have $sf(n) \equiv f(n) \pmod{9}$ . For a digit multiset with counts $c_0, c_1, \ldots, c_9$ :

sf(n) \equiv \sum_{d=0}^{9} c_d \cdot d! \pmod{9}.

In particular, since $d! \equiv 0 \pmod{9}$ for $d \ge 6$ , only the digits $0, 1, 2, 3, 4, 5$ affect $sf(n) \pmod{9}$ .

Proof. For $d \ge 6$ , $d!$ is divisible by $720$ and hence by $9$ . Thus $c_d \cdot d! \equiv 0 \pmod{9}$ for $d \ge 6$ . The congruence $s(x) \equiv x \pmod{9}$ is a standard property of the digit sum. $\square$

Theorem 2 (Structure of $g(i)$ ). For each $i \in \{1, \ldots, 150\}$ , $g(i)$ has the form: a non-decreasing sequence of “adjustment” digits from $\{1, \ldots, 8\}$ (possibly empty) followed by $c_9$ copies of the digit 9, where $c_9$ is chosen minimally so that $s(f(n)) = i$ . The digit sum of $g(i)$ is:

sg(i) = 9c_9 + \sum_{d \in \text{adjustment}} d.

Proof. By Lemma 2, we seek the smallest $n$ with $sf(n) = i$ . For a fixed adjustment pattern $A$ (a multiset of digits from $\{1,\ldots,8\}$ ), define $R_A = \sum_{d \in A} d!$ . Then $f(n) = R_A + c_9 \cdot 362880$ , and we need $s(R_A + 362880 c_9) = i$ . For each $A$ , this determines $c_9$ (possibly multiple solutions; take the smallest valid $c_9 \ge 0$ ). Among all valid $(A, c_9)$ pairs, the optimal one minimizes total digit count $|A| + c_9$ , then lexicographic order. The digit sum follows. $\square$

Editorial

f(n) = sum of factorials of digits of n. sf(n) = digit_sum(f(n)). g(i) = smallest n with sf(n) = i. sg(i) = digit_sum(g(i)). Find sum of sg(i) for i = 1..150. Key insight: n has non-decreasing digits (to minimize n). Decompose as “base digits (1-8)” followed by k nines. f(n) = R + k * B where B = 9! = 362880, R = sum of base factorials. Need digit_sum(R + kB) = i, i.e., x = R + kB has digit_sum i and x ≡ R mod B. Algorithm: 1. Precompute feasibility bitsets: can[d][s] = set of residues mod B achievable with d digits and digit sum s. 2. BFS to find minimum-length base for each residue mod B. 3. For each target i and each D (number of digits of x): For each achievable residue r, find minimum x with digit_sum=i and x≡r mod B. Pick the (residue, D) giving minimum n. We iterate over each target i from 1 to 150. We then enumerate small adjustment patterns A (multisets of digits 1..8). Finally, with |A| bounded (say |A| <= 20 for safety).

Pseudocode

For each target i from 1 to 150:
Enumerate small adjustment patterns A (multisets of digits 1..8)
with |A| bounded (say |A| <= 20 for safety)
Find smallest c9 >= 0 such that digit_sum(R_A + 362880 * c9) == i

Complexity Analysis

Time: The number of adjustment patterns is bounded by the number of multisets of $\{1,\ldots,8\}$ with sum $\le$ some moderate bound, which grows polynomially. For each pattern, finding $c_9$ requires $O(1)$ trials on average (since the digit sum cycles). Overall: $O(P \cdot T)$ where $P$ is the number of patterns (a few thousand) and $T$ is the cost per pattern (dominated by big-number digit-sum computation), multiplied by 150 targets. Well within feasibility.
Space: $O(1)$ beyond storing the adjustment patterns.

Answer

\boxed{8184523820510}

C++ project_euler/problem_254/solution.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll FACT[] = {1,1,2,6,24,120,720,5040,40320,362880};
const int B = 362880;
const int M = B;

int digit_sum_int(ll x) {
    int s = 0;
    while (x > 0) { s += x % 10; x /= 10; }
    return s;
}

const int NW = (M + 63) / 64;
const int PD = 17;

uint64_t can[PD+1][9*PD+1][NW];
int pow10m[20];

void cyclic_shift_or(uint64_t* dst, const uint64_t* src, int k) {
    if (k == 0) {
        for (int w = 0; w < NW; w++) dst[w] |= src[w];
        return;
    }
    for (int w = 0; w < NW; w++) {
        if (!src[w]) continue;
        for (int b = 0; b < 64; b++) {
            int p = w * 64 + b;
            if (p >= M) break;
            if (!(src[w] & (1ULL << b))) continue;
            int q = (p + k) % M;
            dst[q / 64] |= 1ULL << (q % 64);
        }
    }
}

bool any_set(const uint64_t* bs) {
    for (int w = 0; w < NW; w++) if (bs[w]) return true;
    return false;
}

bool is_feasible(int d, int s, int r) {
    if (s < 0 || d < 0 || s > 9 * d) return false;
    if (d > PD) return true;
    return (can[d][s][r / 64] >> (r % 64)) & 1;
}

ll find_min_x(int D, int target_sum, int target_res) {
    if (target_sum < 1 || target_sum > 9 * D || D <= 0 || D > 18) return -1;
    int rs = target_sum, rr = target_res;
    ll x = 0;
    for (int pos = 0; pos < D; pos++) {
        int rd = D - pos - 1;
        int lo = (pos == 0) ? 1 : 0;
        bool found = false;
        for (int c = lo; c <= 9; c++) {
            if (c > rs) break;
            int ns = rs - c;
            if (ns > 9 * rd || ns < 0) continue;
            int p = pow10m[D - 1 - pos];
            int nr = ((ll)rr - (ll)c * p % M + M) % M;
            if (rd == 0) {
                if (ns == 0 && nr == 0) {
                    x = x * 10 + c;
                    return x;
                }
                continue;
            }
            if (is_feasible(rd, ns, nr)) {
                x = x * 10 + c;
                rs = ns;
                rr = nr;
                found = true;
                break;
            }
        }
        if (!found) return -1;
    }
    return x;
}

// For each residue, store ALL bases (up to min_base_len, among those: all possible dsums and digit tuples)
// This is too complex. Instead, let me store PER RESIDUE:
// - minimum base_len
// - For that minimum base_len: ALL possible (digit_tuple, dsum) pairs
// Then when comparing, use the digit tuple directly.

// Actually, let me simplify: store per residue the minimum base_len and 
// the lex-smallest digit tuple of that length.
// The lex-smallest tuple with a given residue and base_len:
// this requires a more careful BFS.

// APPROACH: BFS layer by layer. At each layer L:
// For newly discovered residues: find the lex-smallest digit tuple.
// For ties (same residue, same layer): lex-smallest tuple wins.
// 
// The digit tuple is non-decreasing. To find lex-smallest:
// maximize 1s, then 2s, etc.
// For a given residue r at level L:
// the lex-smallest tuple is the one with the most 1s, then most 2s, etc.
// This is hard to track in BFS because we build tuples one digit at a time.
// 
// Alternative: for each residue at level L, track the lex-smallest tuple.
// A tuple of length L with non-decreasing digits from 1-8.
// We can represent this as the vector itself.
// But with 362880 residues and tuples up to length 36: memory is huge.
//
// PRACTICAL COMPROMISE: For each residue, store:
// - min_base_len
// - for that length: lex-smallest tuple (as a vector)
// During BFS, when we extend a tuple by adding digit d >= last_digit:
// new_tuple = old_tuple + [d]. Check if it's lex-smaller than current best for the residue.
//
// This requires careful implementation. Let me try a different approach:
// multi-level BFS where we track (residue, last_digit) at each level.

struct State {
    int residue;
    int last_digit; // last digit used (for non-decreasing)
    int dsum;
    vector<int> digits; // the actual digits
};

int main() {
    pow10m[0] = 1;
    for (int i = 1; i < 20; i++) pow10m[i] = (ll)pow10m[i-1] * 10 % M;
    
    memset(can, 0, sizeof(can));
    can[0][0][0] = 1;
    
    fprintf(stderr, "Precomputing feasibility...\n");
    for (int d = 1; d <= PD; d++) {
        int p = pow10m[d-1];
        for (int s = 0; s <= 9*d; s++) {
            for (int c = 0; c <= min(9, s); c++) {
                int sp = s - c;
                if (sp > 9*(d-1)) continue;
                if (!any_set(can[d-1][sp])) continue;
                int sh = (ll)c * p % M;
                cyclic_shift_or(can[d][s], can[d-1][sp], sh);
            }
        }
        fprintf(stderr, "  d=%d\n", d);
    }
    
    // For each residue: find the base with minimum base_len, 
    // then among those: the one whose (digits, k) gives lex-smallest n.
    // Since k = (x - R) / B, and x depends only on residue, k is determined.
    // n = digits followed by k nines.
    // For same residue and same base_len: all have same k.
    // So lex-smallest n = lex-smallest (digits, 9...9) = lex-smallest digits
    // (since the 9s are the same suffix).
    // Lex-smallest non-decreasing digits of given length L and given sum mod B = r:
    // This is: most 1s as possible, then 2s, etc.
    
    // BFS with (residue, last_digit) states.
    // min_len[r] = minimum number of digits to achieve residue r.
    // For that min_len: best_digits[r] = lex-smallest digit tuple.
    
    // State: (residue, last_digit). 
    // Since digits are non-decreasing and we add one at a time:
    // last_digit restricts which digits we can add next.
    // We track: for each (residue, last_digit): minimum length to reach here.
    // Among same length: lex-smallest prefix.
    
    // Memory: B * 8 states = 2.9M. Manageable.
    
    // dist[r][d] = min length to achieve residue r with last digit d.
    // Then min_base_len[r] = min over d of dist[r][d].
    
    vector<vector<int>> dist(B, vector<int>(9, -1)); // d = 1..8, index d-1
    // Also track dsum and digits
    vector<vector<int>> best_dsum(B, vector<int>(9, INT_MAX));
    vector<vector<vector<int>>> best_digits_arr(B, vector<vector<int>>(9));
    
    // Initial: length 0, residue 0, last_digit 0 (can use any digit 1-8)
    // First step: choose digit d (1-8), residue = d! % B, last_digit = d.
    for (int d = 1; d <= 8; d++) {
        int r = (int)(FACT[d] % B);
        if (dist[r][d-1] == -1) {
            dist[r][d-1] = 1;
            best_dsum[r][d-1] = d;
            best_digits_arr[r][d-1] = {d};
        } else if (dist[r][d-1] == 1) {
            if (d < best_dsum[r][d-1]) {
                best_dsum[r][d-1] = d;
                best_digits_arr[r][d-1] = {d};
            }
        }
    }
    
    vector<pair<int,int>> cur_states; // (residue, last_digit_idx)
    for (int d = 1; d <= 8; d++) {
        int r = (int)(FACT[d] % B);
        cur_states.push_back({r, d-1});
    }
    // Deduplicate
    sort(cur_states.begin(), cur_states.end());
    cur_states.erase(unique(cur_states.begin(), cur_states.end()), cur_states.end());
    
    int level = 1;
    int total_reached = 0;
    
    // Count reached residues
    vector<int> min_len_r(B, -1);
    for (int d = 1; d <= 8; d++) {
        int r = (int)(FACT[d] % B);
        if (min_len_r[r] == -1) min_len_r[r] = 1;
    }
    for (int r = 0; r < B; r++) if (min_len_r[r] >= 0) total_reached++;
    fprintf(stderr, "Level 1: %d states, %d residues reached\n", (int)cur_states.size(), total_reached);
    
    while (!cur_states.empty() && total_reached < B) {
        level++;
        vector<pair<int,int>> next_states;
        
        for (auto& [r, di] : cur_states) {
            int last_d = di + 1; // digit value
            for (int d = last_d; d <= 8; d++) {
                int nr = (r + (int)(FACT[d] % B)) % B;
                int new_dsum = best_dsum[r][di] + d;
                
                if (dist[nr][d-1] == -1) {
                    dist[nr][d-1] = level;
                    best_dsum[nr][d-1] = new_dsum;
                    best_digits_arr[nr][d-1] = best_digits_arr[r][di];
                    best_digits_arr[nr][d-1].push_back(d);
                    next_states.push_back({nr, d-1});
                    if (min_len_r[nr] == -1) {
                        min_len_r[nr] = level;
                        total_reached++;
                    }
                } else if (dist[nr][d-1] == level) {
                    // Same level: compare lex (the digit tuples)
                    vector<int> new_digits = best_digits_arr[r][di];
                    new_digits.push_back(d);
                    if (new_digits < best_digits_arr[nr][d-1]) {
                        best_digits_arr[nr][d-1] = new_digits;
                        best_dsum[nr][d-1] = new_dsum;
                    }
                }
            }
        }
        
        sort(next_states.begin(), next_states.end());
        next_states.erase(unique(next_states.begin(), next_states.end()), next_states.end());
        cur_states = next_states;
        
        fprintf(stderr, "Level %d: %d states, %d/%d residues\n", level, (int)cur_states.size(), total_reached, B);
        if (level > 50) break;
    }
    
    // For each residue: find the best (last_digit, dsum, digits)
    // Best = minimum len, then lex-smallest digits tuple
    struct BaseInfo {
        int len;
        int dsum;
        vector<int> digits;
        ll R;
    };
    
    vector<BaseInfo> base_info(B);
    for (int r = 0; r < B; r++) {
        base_info[r].len = -1;
        for (int di = 0; di < 8; di++) {
            if (dist[r][di] < 0) continue;
            if (base_info[r].len < 0 || dist[r][di] < base_info[r].len ||
                (dist[r][di] == base_info[r].len && best_digits_arr[r][di] < base_info[r].digits)) {
                base_info[r].len = dist[r][di];
                base_info[r].dsum = best_dsum[r][di];
                base_info[r].digits = best_digits_arr[r][di];
                ll R = 0;
                for (int d : base_info[r].digits) R += FACT[d];
                base_info[r].R = R;
            }
        }
    }
    // Residue 0: empty base
    if (base_info[0].len < 0 || 0 < base_info[0].len) {
        base_info[0].len = 0;
        base_info[0].dsum = 0;
        base_info[0].digits.clear();
        base_info[0].R = 0;
    }
    
    // Now solve
    ll total_sg = 0;
    
    for (int i = 1; i <= 150; i++) {
        int target_mod9 = i % 9;
        
        ll best_total = LLONG_MAX;
        vector<int> best_n_prefix; // for lex comparison
        ll best_sg = 0;
        
        for (int D = max(1, (i + 8) / 9); D <= 18; D++) {
            for (int r = 0; r < B; r++) {
                if (base_info[r].len < 0) continue;
                if (r % 9 != target_mod9) continue;
                
                ll x = find_min_x(D, i, r);
                if (x < 0) continue;
                
                ll R = base_info[r].R;
                if (x < R) continue;
                if ((x - R) % B != 0) continue;
                
                ll k = (x - R) / B;
                ll total_digits = (ll)base_info[r].len + k;
                ll sg = (ll)base_info[r].dsum + 9LL * k;
                
                if (total_digits < best_total) {
                    best_total = total_digits;
                    best_sg = sg;
                    best_n_prefix = base_info[r].digits;
                } else if (total_digits == best_total) {
                    // Compare n lexicographically
                    // n1 = best_n_prefix + (best_total - best_n_prefix.size()) nines
                    // n2 = base_info[r].digits + k nines
                    // Both have same total_digits.
                    // Compare digit by digit:
                    const auto& d2 = base_info[r].digits;
                    bool n2_better = false;
                    int L = total_digits;
                    for (int p = 0; p < min((ll)40, (ll)L); p++) {
                        int v1 = (p < (int)best_n_prefix.size()) ? best_n_prefix[p] : 9;
                        int v2 = (p < (int)d2.size()) ? d2[p] : 9;
                        if (v1 != v2) {
                            n2_better = (v2 < v1);
                            break;
                        }
                    }
                    if (n2_better) {
                        best_sg = sg;
                        best_n_prefix = d2;
                    }
                }
            }
            
            // Don't break: larger D with different residue might give smaller total_digits
            // because a base with fewer digits might only work at larger D.
            // At D+1, it might find a solution with much smaller base.
            //
            // So we CANNOT break after the first D. We must check all D values.
            // But the maximum D is 18, so it's bounded.
        }
        
        total_sg += best_sg;
        if (i <= 50 || i >= 140)
            fprintf(stderr, "i=%d: total=%lld, sg=%lld\n", i, best_total, best_sg);
    }
    
    printf("%lld\n", total_sg);
    return 0;
}

Python project_euler/problem_254/solution.py

"""
Problem 254: Sums of Digit Factorials

f(n) = sum of factorials of digits of n.
sf(n) = digit_sum(f(n)).
g(i) = smallest n with sf(n) = i.
sg(i) = digit_sum(g(i)).
Find sum of sg(i) for i = 1..150.

Key insight: n has non-decreasing digits (to minimize n).
Decompose as "base digits (1-8)" followed by k nines.
f(n) = R + k * B where B = 9! = 362880, R = sum of base factorials.
Need digit_sum(R + k*B) = i, i.e., x = R + k*B has digit_sum i and x ≡ R mod B.

Algorithm:
1. Precompute feasibility bitsets: can[d][s] = set of residues mod B achievable
   with d digits and digit sum s.
2. BFS to find minimum-length base for each residue mod B.
3. For each target i and each D (number of digits of x):
   For each achievable residue r, find minimum x with digit_sum=i and x≡r mod B.
   Pick the (residue, D) giving minimum n.

Answer: 8184523820510
"""

import sys
from collections import deque

def solve():
    FACT = [1,1,2,6,24,120,720,5040,40320,362880]
    B = 362880
    M = B

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

    PD = 17
    pow10m = [1] * 20
    for i in range(1, 20):
        pow10m[i] = pow10m[i-1] * 10 % M

    # Precompute feasibility bitsets using Python big integers
    print("Precomputing feasibility...", file=sys.stderr)
    can = [[0] * (9*PD+1) for _ in range(PD+1)]
    can[0][0] = 1
    MASK = (1 << M) - 1

    for d in range(1, PD+1):
        p = pow10m[d-1]
        for s in range(9*d+1):
            for c in range(min(9, s)+1):
                sp = s - c
                if sp > 9*(d-1):
                    continue
                src = can[d-1][sp]
                if src == 0:
                    continue
                shift = c * p % M
                if shift == 0:
                    can[d][s] |= src
                else:
                    shifted = ((src << shift) | (src >> (M - shift))) & MASK
                    can[d][s] |= shifted
        print(f"  d={d}", file=sys.stderr)

    def is_feasible(d, s, r):
        if s < 0 or d < 0 or s > 9 * d:
            return False
        if d > PD:
            return True
        return bool(can[d][s] & (1 << r))

    def find_min_x(D, target_sum, target_res):
        if target_sum < 1 or target_sum > 9 * D or D <= 0 or D > 18:
            return None
        rs = target_sum
        rr = target_res
        x = 0
        for pos in range(D):
            rd = D - pos - 1
            lo = 1 if pos == 0 else 0
            found = False
            for c in range(lo, 10):
                if c > rs:
                    break
                ns = rs - c
                if ns > 9 * rd or ns < 0:
                    continue
                p = pow10m[D - 1 - pos]
                nr = (rr - c * p) % M
                if nr < 0:
                    nr += M
                if rd == 0:
                    if ns == 0 and nr == 0:
                        x = x * 10 + c
                        return x
                    continue
                if is_feasible(rd, ns, nr):
                    x = x * 10 + c
                    rs = ns
                    rr = nr
                    found = True
                    break
            if not found:
                return None
        return x

    # BFS for minimum bases (non-decreasing digits 1-8)
    print("BFS for minimum bases...", file=sys.stderr)
    # State: (residue, last_digit)
    dist = [[-1]*8 for _ in range(B)]  # dist[r][d-1]
    best_dsum = [[float('inf')]*8 for _ in range(B)]
    best_digits = [[None]*8 for _ in range(B)]

    cur_states = []
    for d in range(1, 9):
        r = FACT[d] % B
        if dist[r][d-1] < 0:
            dist[r][d-1] = 1
            best_dsum[r][d-1] = d
            best_digits[r][d-1] = (d,)
            cur_states.append((r, d-1))
        elif dist[r][d-1] == 1 and (d,) < best_digits[r][d-1]:
            best_digits[r][d-1] = (d,)
            best_dsum[r][d-1] = d

    cur_states = list(set(cur_states))
    reached = set()
    for d in range(1, 9):
        reached.add(FACT[d] % B)
    reached.add(0)

    level = 1
    while cur_states and len(reached) < B:
        level += 1
        next_states = set()
        for r, di in cur_states:
            last_d = di + 1
            for d in range(last_d, 9):
                nr = (r + FACT[d]) % B
                new_dsum = best_dsum[r][di] + d
                new_digits = best_digits[r][di] + (d,)
                if dist[nr][d-1] < 0:
                    dist[nr][d-1] = level
                    best_dsum[nr][d-1] = new_dsum
                    best_digits[nr][d-1] = new_digits
                    next_states.add((nr, d-1))
                    reached.add(nr)
                elif dist[nr][d-1] == level and new_digits < best_digits[nr][d-1]:
                    best_digits[nr][d-1] = new_digits
                    best_dsum[nr][d-1] = new_dsum
        cur_states = list(next_states)
        print(f"  Level {level}: {len(reached)}/{B} residues", file=sys.stderr)
        if level > 50:
            break

    # Collect best base per residue
    base_info = {}
    # Residue 0: empty base
    base_info[0] = (0, 0, (), 0)  # (len, dsum, digits, R)
    for r in range(B):
        for di in range(8):
            if dist[r][di] < 0:
                continue
            L = dist[r][di]
            dg = best_digits[r][di]
            ds = best_dsum[r][di]
            R = sum(FACT[d] for d in dg)
            if r not in base_info or L < base_info[r][0] or (L == base_info[r][0] and dg < base_info[r][2]):
                base_info[r] = (L, ds, dg, R)

    # Solve
    total_sg = 0
    for i in range(1, 151):
        target_mod9 = i % 9
        best_total = float('inf')
        best_sg = 0
        best_prefix = None

        for D in range(max(1, (i+8)//9), 19):
            for r, (blen, bds, bdig, bR) in base_info.items():
                if r % 9 != target_mod9:
                    continue
                x = find_min_x(D, i, r)
                if x is None:
                    continue
                if x < bR:
                    continue
                if (x - bR) % B != 0:
                    continue
                k = (x - bR) // B
                total_digits = blen + k
                sg = bds + 9 * k

                if total_digits < best_total:
                    best_total = total_digits
                    best_sg = sg
                    best_prefix = bdig
                elif total_digits == best_total:
                    # Lex compare n
                    n2_better = False
                    for p in range(min(40, total_digits)):
                        v1 = best_prefix[p] if p < len(best_prefix) else 9
                        v2 = bdig[p] if p < len(bdig) else 9
                        if v1 != v2:
                            n2_better = (v2 < v1)
                            break
                    if n2_better:
                        best_sg = sg
                        best_prefix = bdig

        total_sg += best_sg
        print(f"i={i}: sg={best_sg}", file=sys.stderr)

    print(total_sg)

if __name__ == "__main__":
    solve()