Problem 684: Inverse Digit Sum

Mathematical Analysis

Finding s(n): The Smallest Number with Digit Sum n

For a given digit sum $n$, the smallest number is constructed by maximizing the use of 9s (which pack the most digit sum per digit) and placing the remainder in the leading digit.

Write $n = 9q + r$ where $0 \le r \le 8$:

• If $r = 0$: $s(n) = \underbrace{99\ldots9}_{q}$ (a repdigit of $q$ nines)
• If $r > 0$: $s(n) = r \underbrace{99\ldots9}_{q}$ (the digit $r$ followed by $q$ nines)

In both cases: $s(n) = (r+1) \cdot 10^q - 1$ where $r = ((n-1) \bmod 9) + 1$ when $n > 0$, but more cleanly:

Let $q = \lfloor n/9 \rfloor$ and $r = n \bmod 9$. Then:

• If $r = 0$: $s(n) = 10^q - 1$
• If $r > 0$: $s(n) = r \cdot 10^q + (10^q - 1) = (r+1) \cdot 10^q - 1$

Uniformly: $s(n) = (r' + 1) \cdot 10^q - 1$ where we define $r' = n \bmod 9$ if $n \bmod 9 \ne 0$, else handle the $r = 0$ case by writing $n = 9(q-1) + 9$.

Computing S(k)

Group terms by blocks of 9. Let $k = 9Q + R$ with $0 \le R \le 8$.

For a complete block from $n = 9m+1$ to $n = 9m+9$ (i.e., $q = m$ for $n = 9m+1, \ldots, 9m+8$, and $q = m+1$ for $n = 9(m+1)$):

Therefore:

For the remaining $R$ terms ($n = 9Q+1$ to $n = 9Q+R$):

Wait, $\sum_{r=1}^{R}(r+1) = \sum_{j=2}^{R+1} j = \frac{(R+1)(R+2)}{2} - 1$.

So the remainder sum is:

Combining:

where $Q = \lfloor k/9 \rfloor$ and $R = k \bmod 9$.

Simplifying:

Editorial

We iterate over each Fibonacci number, compute $S(f_i)$ using the closed-form formula with modular exponentiation. Finally, sum all results modulo $10^9 + 7$.

Pseudocode

Precompute Fibonacci numbers $f_2, f_3, \ldots, f_{90}$
For each Fibonacci number, compute $S(f_i)$ using the closed-form formula with modular exponentiation
Sum all results modulo $10^9 + 7$

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

• Computing each $S(f_i)$: $O(\log f_i)$ for modular exponentiation, where $f_{90} \approx 2.88 \times 10^{18}$.
• Total: $O(89 \cdot \log(f_{90})) = O(89 \cdot 60) = O(5340)$.

Answer

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

const long long MOD = 1000000007;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long mod_inv(long long a, long long mod) {
    return power(a, mod - 2, mod);
}

// S(k) = 10^Q * (5 + (R+1)(R+2)/2) - 9Q - R - 6
// where Q = k/9, R = k%9
long long S(long long k) {
    if (k <= 0) return 0;
    long long Q = k / 9;
    long long R = k % 9;

    long long p10 = power(10, Q, MOD);

    // coefficient: 5 + (R+1)(R+2)/2
    long long coeff = (5 + (R + 1) * (R + 2) / 2) % MOD;

    long long result = p10 % MOD * coeff % MOD;
    result = (result - 9 % MOD * (Q % MOD) % MOD + MOD) % MOD;
    result = (result - R % MOD + MOD) % MOD;
    result = (result - 6 + MOD) % MOD;

    return result;
}

int main() {
    // Compute Fibonacci numbers
    // f_90 fits in unsigned 64-bit? f_90 ~ 2.88e18, yes
    vector<long long> fib(91);
    fib[0] = 0; fib[1] = 1;
    for (int i = 2; i <= 90; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }

    long long ans = 0;
    for (int i = 2; i <= 90; i++) {
        ans = (ans + S(fib[i])) % MOD;
    }

    cout << ans << endl;
    return 0;
}

MOD = 1_000_000_007

def power(base, exp, mod):
    return pow(base, exp, mod)

def S(k):
    if k <= 0:
        return 0
    Q = k // 9
    R = k % 9

    p10 = power(10, Q, MOD)
    coeff = (5 + (R + 1) * (R + 2) // 2) % MOD

    result = p10 * coeff % MOD
    result = (result - 9 * (Q % MOD) % MOD + MOD) % MOD
    result = (result - R % MOD + MOD) % MOD
    result = (result - 6 + MOD) % MOD

    return result

# Compute Fibonacci numbers
fib = [0] * 91
fib[1] = 1
for i in range(2, 91):
    fib[i] = fib[i-1] + fib[i-2]

ans = 0
for i in range(2, 91):
    ans = (ans + S(fib[i])) % MOD

print(ans)