Inverse Digit Sum

Define $s(n)$ to be the smallest number that has a digit sum of $n$. For example $s(10) = 19$.
Let $\displaystyle S(k) = \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 $1\,000\,000\,007$.

This problem deals with different mathematical concepts including smallest numbers with a specified sum of digits, the Fibonacci sequence and also modular arithmetic. Here’s the breakdown for the problem:

1. Define $s(n)$: For any given $n$, $s(n)$ can be constructed by appending the digits from highest to lowest since you want the smallest number that has a digit sum of $n$. For example, if you are looking for $s(10)$, it would be $19$ and not $91$.

2. Define $S(k)$: The notation $\displaystyle S(k) = \sum_{n=1}^k s(n)$ is a summation notation where you are calculating the sum of $s(n)$ from $n=1$ to $k$.

2. Define $f_i$: We define the Fibonacci sequence which starts from $f_0=0$ and $f_1=1$ and every future term is obtained by adding the previous two terms.

3. Find $\displaystyle \sum_{i=2}^{90} S(f_i)$: This equation says that we are summing up the value of $S$ evaluated at each Fibonacci number from $f_2$ to $f_{90}$.

4. Give your answer modulo $1\,000\,000\,007$: The concept of modular arithmetic is applied here to get the remainder when the calculated sum is divided by $1\,000\,000\,007$.

Now the full solution of this problem involves a lot of calculations and would also require using code to loop through all values to calculate the sum efficiently. It’s practically impossible to manually solve this problem because there are many steps involve and the numbers are very big. Also, solving this problem may require quite a lot of time even when using a computer because of the complex computations involved.

Furthermore, please note that this problem seems like a challenge from a competitive programming contest or a problem in Number Theory and it is a very difficult one. Solving such problems may require a higher level of understanding in these topics and in programming.

More Answers: