123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 |
- #!/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)
- # where:
- # n = floor(k/9)
- # https://projecteuler.net/problem=684
- # Runtime: 0.188s
- const MOD = 1000000007
- func S(k) {
- var n = floor(k/9)
- var sum = (2*(2**n * 5**(n+2) - 7) - 9*n)
- for r in (k%9 + 2 .. 9) {
- sum -= (r * 10**n - 1)
- }
- sum
- }
- func modular_S(k) {
- var n = floor(k/9)
- var sum = (2*(powmod(2, n, MOD) * powmod(5, n+2, MOD) - 7) - 9*n)%MOD
- for r in (k%9 + 2 .. 9) {
- sum -= (r * powmod(10, n, MOD) - 1)%MOD
- }
- sum % MOD
- }
- assert_eq(S(20), 1074)
- assert_eq(S(49), 1999945)
- assert_eq(modular_S(20), 1074)
- assert_eq(modular_S(49), 1999945)
- say sum(2..90, {|k|
- modular_S(fib(k))
- })%MOD
|