<jupyter_start><jupyter_text>Problem 684 Inverse Digit SumDefine $s(n)$ to be the smallest number that has digit sum of $n$. For example $s(10) = 19$Let $S(k) = \displaystyle\sum_{n=1}^k s(n)$. You are given $S(20) = 1074$.Further, let $f_i$ be the Fibonacci sequence defined by $f_0 = 0$, $f_1 = 1$ and $f_i = f_{i - 2} + f_{i - 1}$ for all $i \ge 2$.Find $\displaystyle\sum_{i = 2}^{90} S(f_i)$. Give your answer modulo $1000000007$.OEIS Sequence: [A051885](https://oeis.org/A051885) SolutionThe smallest numbers whose sum of digits is $n$, are numbers of the form $10 ^ j a - 1$ with $a \in (1, 9)$ and $j \ge 0$.This solution uses the following formula:$$\sum_{j=0}^b 10 ^ j a - 1 = \frac{10 ^ {b + 1}a - a - 9b - 9}{9}$$By letting $a = (1, 9)$, we get:$$R(k) = \sum _ {a = 1} ^ 9 \sum _ {j = 0} ^ b 10 ^ j a - 1 = 2 (2 ^ b 5 ^ {b + 2} - 7) - 9b$$From $R(k)$, we get $S(k)$ as:$$S(k) = R(k) - \sum _ {j = 2 + (k \mod 9)} ^ 9 10 ^ b j - 1 = R(k) - \frac{(10 - a) (10 ^ b (a + 9) - 2)}{2}$$Simplifying the formula, we get:$$S(k) = \frac{10 ^ b(a (a - 1) + 10) - 2 (a + 9b + 4)}{2}$$where:$$a = k \mod 9 + 2$$$$b = \lfloor \frac{k}{9} \rfloor$$<jupyter_code>from euler.big_int import BigInt
from euler.calculus import fibonacci_numbers
def compute(n: int, m: int = 1_000_000_007) -> BigInt:
    inverted_modulo = pow(2, -1, m)
    result = BigInt(0)
    for f in fibonacci_numbers(n, BigInt):
        a, b = f % 9 + 2, f // 9
        result += (((a * (a - 1) + 10) * pow(BigInt(10), b, m) - 2 * (a + 9 * b + 4)) * inverted_modulo) % m
    return result % m - 1
compute(90)
%timeit -n 100 -r 1 -p 6 compute(90)<jupyter_output>3.89598 s ± 0 ns per loop (mean ± std. dev. of 1 run, 100 loops each)
{'fraction_non_alphanumeric': 0.20235988200589972, 'fraction_numerical': 0.08613569321533923, 'mean_word_length': 2.971896955503513, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '467339', 'license': 'MIT', 'n_tokens_mistral': 832, 'n_tokens_neox': 707, 'n_words': 251, 'path': 'problems/0684/solution.ipynb', 'repo_name': 'Dynortice/didactic-rotary-phone', 'size': '1695'}