684. Inverse Digit Sum.md

684. Inverse Digit Sum

Question

Define s(n) to be the smallest number that has a digit sum of n. For example s(10)=19.

Let S(k)=∑s(n), n=1,...,k. You are given S(20)=1074.

Further let fi be the Fibonacci sequence defined by f0=0, f1=1.

Find ∑S(fi), i=2,...,90. Give your answer modulo 1000000007.

Solution

It's easy to see that . Therefore, we have

Let b, r = divmod(k, 9):

So far so good.

But soon you'll realise that the code will take forever to run due to ! When k=fib(90), b=3.2e17, while already takes ~10 seconds to run, it's impossible to calculate in this case. The solution is simple: pow(10, b, M).

M = 1000000007

@lru_cache(maxsize=None)
def fib(n):
    if n == 0 or n == 1:
        return n
    return fib(n - 1) + fib(n - 2)

def p684():
    def S(k):
        b, r = divmod(k, 9)
        res = (5 + (r + 1) * (r + 2) // 2) * pow(10, b, M) - k - 6
        return res % M
    return sum(S(fib(i)) for i in range(2, 91)) % M

Answer

922058210

Note

• isprime

• Modulo operation

  

  

  

• How to find modular multiplicative inverse of a modulo M?

  According to Fermat's little theorem, if M is a prime, . If a is not divisible by M, we have .