-
Notifications
You must be signed in to change notification settings - Fork 6
/
684 Inverse Digit Sum.pl
65 lines (44 loc) · 1.35 KB
/
684 Inverse Digit Sum.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#!/usr/bin/perl
# 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.031s
use 5.020;
use warnings;
use ntheory qw(:all);
use experimental qw(signatures);
my $MOD = 1000000007;
sub fib ($n) {
lucasu(1, -1, $n);
}
sub S($k) {
my $n = divint($k, 9);
my $r = divrem($k, 9) + 2;
my $x = mulmod(mulmod($r-1, $r, $MOD) + 10, powmod(10, $n, $MOD), $MOD);
my $y = mulmod(2, 4 + $r + mulmod(9, $n, $MOD), $MOD);
my $z = invmod(2, $MOD);
mulmod($x-$y, $z, $MOD);
}
S(20) == 1074 or die "error";
S(49) == 1999945 or die "error";
my $sum = 0;
foreach my $k (2 .. 90) {
$sum = addmod($sum, S(fib($k)), $MOD);
}
say $sum;