-
Notifications
You must be signed in to change notification settings - Fork 7
/
435 Polynomials of Fibonacci numbers.pl
55 lines (38 loc) · 1.13 KB
/
435 Polynomials of Fibonacci numbers.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
#!/usr/bin/perl
# Daniel "Trizen" Șuteu
# Date: 11 October 2017
# https://github.com/trizen
# https://projecteuler.net/problem=435
# Runtime: ~1 minute, 33 seconds.
use 5.026;
use strict;
use warnings;
use experimental qw(signatures);
use ntheory qw(addmod mulmod powmod lcm factor_exp factorial);
sub pisano_period($mod) {
my sub find_period($mod) {
my ($x, $y) = (0, 1);
for (my $n = 1 ; ; ++$n) {
($x, $y) = ($y, addmod($x, $y, $mod));
if ($x == 0 and $y == 1) {
return $n;
}
}
}
my @prime_powers = map { $_->[0]**$_->[1] } factor_exp($mod);
my @power_periods = map { find_period($_) } @prime_powers;
return lcm(@power_periods);
}
my $mod = factorial(15);
my $n = powmod(10, 15, pisano_period(factorial(14))); # 870400
my $sum = 0;
my ($f1, $f2) = (0, 1);
foreach my $k (1 .. $n) {
my $power_sum = 0;
foreach my $x (1 .. 100) {
$power_sum = addmod($power_sum, powmod($x, $k, $mod), $mod);
}
$sum = addmod($sum, mulmod($f2, $power_sum, $mod), $mod);
($f1, $f2) = ($f2, addmod($f1, $f2, $mod));
}
say $sum;