project-euler/Sidef/684 Inverse Digit Sum -- v2.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 27 November 2019
# https://github.com/trizen

# See OEIS sequence:
#   https://oeis.org/A051885

# The smallest numbers whose sum of digits is n, are numbers of the form r*10^j-1, with r=1..9 and j >= 0.

# This solution uses the following formula:
#   Sum_{j=0..n} (r*10^j-1) = (r * 10^(n+1) - r - 9*n - 9)/9

# By letting r=1..9, we get:
#   R(k) = Sum_{r=1..9} Sum_{j=0..n} (r*10^j-1) = 2*(2^n * 5^(n+2) - 7) - 9*n

# From R(k), we get S(k) as:
#   S(k) = R(k) - Sum_{j=2+(k mod 9) .. 9} (j*10^n-1)
#   S(k) = R(k) - (10-r) * (10^n * (r+9) - 2)/2

# Simplifying the formula, we get:
#   S(k) = (((r-1)*r + 10) * 10^n - 2*(r + 9*n + 4))/2

# where:
#   n = floor(k/9)
#   r = 2+(k mod 9)

# https://projecteuler.net/problem=684

# Runtime: 0.176s

const MOD = 1000000007

func S(k) {

    var n = floor(k/9)
    var r = (k%9 + 2)

    (((r-1)*r + 10) * 10**n - 2*(r + 9*n + 4))/2
}

func modular_S(k) {

    var n = floor(k/9)
    var r = (k%9 + 2)

    (((r-1)*r + 10) * Mod(10,MOD)**n - 2*(r + 9*n + 4)) / Mod(2, MOD)
}

assert_eq(S(20), 1074)
assert_eq(S(49), 1999945)

assert_eq(modular_S(20), 1074)
assert_eq(modular_S(49), 1999945)

say map(2..90, {|k|
    modular_S(fib(k))
}).reduce {|a,b| a + b }