/
ch-1.pl
executable file
·58 lines (41 loc) · 1011 Bytes
/
ch-1.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
#! /usr/bin/env perl
use strict;
use warnings;
use feature 'say';
use feature 'signatures';
use feature 'state';
use Getopt::Long;
use List::Util 'sum';
no warnings qw(experimental::signatures);
my $verbose = 0;
GetOptions("verbose" => \$verbose);
my $N = shift(@ARGV) // 20;
my $current = 0;
my @values;
while (1)
{
push(@values, $current) if is_fibonacci_sum($current);
last if @values == $N;
$current++;
}
say "f($N)=[" . join(", ", @values) . "]";
sub is_fibonacci_sum ($number)
{
state %is_fibonacci = ( 0 => 1, 1 => 1 );
state $limit = 1;
state $fib_1 = 0;
state $fib_2 = 1;
my $sum = sum split(//, $number);
say ": Considering number $number with sum $sum" if $verbose;
return 1 if $is_fibonacci{$sum};
while ($sum > $limit)
{
my $new = $fib_1 + $fib_2;
$fib_1 = $fib_2;
$fib_2 = $new;
$limit = $new;
say ": Caching Fibonacci number $limit" if $verbose;
$is_fibonacci{$limit} = 1;
}
return $is_fibonacci{$sum};
}