NumSeq/PisanoPeriod.pm untested

filter: Statementstmt 0.0% 0 / 87 Branchbran 0.0% 0 / 12 Conditioncond 0.0% 0 / 12 MC/DCmcdc 0.0% 0 / 8 Subroutinesub 0.0% 0 / 16 Podpod 0.0% 0 / 1 totaltotal 0.0% 0 / 136 CC 7 SCAR 29.5
CC
7
Cov
0%
ith
56.0
BEGIN
2.0
BEGIN
2.0
CRAP 19.2
1 # Copyright 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde
2  
3 # This file is part of Math-NumSeq.
4 #
5 # Math-NumSeq is free software; you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License as published by the
7 # Free Software Foundation; either version 3, or (at your option) any later
8 # version.
9 #
10 # Math-NumSeq is distributed in the hope that it will be useful, but
11 # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 # for more details.
14 #
15 # You should have received a copy of the GNU General Public License along
16 # with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.
17  
18  
19 # Mark Renault
20 # http://www.math.temple.edu/~renault/fibonacci/fib.html
21 # http://www.math.temple.edu/~renault/fibonacci/thesis.ps
22 # http://web.archive.org/web/20100813104051/http://webspace.ship.edu/msrenault/fibonacci/FibThesis.html
23 #
24 # On Arithmetical Functions Related to the Fibonacci Numbers, Fulton and Morris
25 # aa1621.pdf
26 #
27 # period(m)=m iff m=24*5^(l-1) for some l
28 # l = Leonardo logarithm
29 # A001179 leonardo logarithm
30 #
31 # K.S.Brown a(n)/n <= 6 for all n, a(n)=6n iff n=2*5^k.
32 #
33 # Andreas-Stephan Elsenhans and Jorg Jahnel
34 # http://www.uni-math.gwdg.de/tschinkel/gauss/Fibon.pdf
35 # through to 10^14
36  
37  
38 package Math::NumSeq::PisanoPeriod;
39 use 5.004;
40 use strict;
41 use Math::Prime::XS 'is_prime';
42  
43 use vars '$VERSION', '@ISA';
44 $VERSION = 75;
45  
46 use Math::NumSeq;
47 use Math::NumSeq::Base::IterateIth;
48 @ISA = ('Math::NumSeq::Base::IterateIth',
49 'Math::NumSeq');
50 *_is_infinite = \&Math::NumSeq::_is_infinite;
51  
52 use Math::NumSeq::Base::Cache
53 'cache_hash';
54  
55 use Math::NumSeq::PrimeFactorCount;;
56 *_prime_factors = \&Math::NumSeq::PrimeFactorCount::_prime_factors;
57  
58 # uncomment this to run the ### lines
59 #use Smart::Comments;
60  
61  
62 # use constant name => Math::NumSeq::__('...');
63 use constant description => Math::NumSeq::__('The cycle length of the Fibonacci numbers modulo i.');
64 use constant i_start => 1;
65 use constant characteristic_smaller => 1;
66 use constant characteristic_integer => 1;
67 use constant characteristic_count => 1;
68  
69 use constant values_min => 1;
70  
71 #------------------------------------------------------------------------------
72 # cf A071774 n for which period(n)==2n+1
73 # A060305 period mod nthprime
74 # A001176 how many zeros
75 # A001177 least k where n divides F[k]
76  
77 use constant oeis_anum => 'A001175';
78  
79 #------------------------------------------------------------------------------
80  
81 sub ith {
82 my ($self, $i) = @_;
83 ### PisanoPeriod ith(): "$i"
84  
85 if ($i < 1) {
86 return undef;
87 }
88 if (_is_infinite($i)) {
89 return $i;
90 }
91  
92 my ($good, @primes) = _prime_factors($i);
93 return undef unless $good;
94  
95 my $lcm = Math::NumSeq::_to_bigint(1);
96 while (@primes) {
97 my $prime = shift @primes;
98  
99 my $period = 1;
100 my $power = 1;
101 my $modulus;
102  
103 if ($prime < 1e14) {
104 # period(p^e) = period(p) * p^(e-1)
105 while (@primes && $primes[0] == $prime) {
106 shift @primes;
107 $period *= $prime;
108 }
109 $modulus = $prime;
110 } else {
111 # full period(p^e)
112 while (@primes && $primes[0] == $prime) {
113 shift @primes;
114 $power++;
115 }
116 $modulus = $prime ** $power;
117 }
118  
119 $period *= (cache_hash()->{"PisanoPeriod:$prime,$power"} ||= do {
120 my $f0 = 0;
121 my $f1 = 1;
122 my $period = 1;
123 for ( ; ; $period++) {
124 ### at: "f0=$f0 f1=$f1"
125 ($f0,$f1) = ($f1, ($f0+$f1) % $modulus);
126 if ($f0 == 0 && $f1 == 1) {
127 last;
128 }
129 }
130 ### period calcuated: "prime=$prime power=$power period=$period"
131 $period;
132 });
133  
134 $lcm /= Math::BigInt::bgcd($period,$lcm);
135 $lcm *= $period;
136 }
137  
138 if ($lcm <= 0xFFFF_FFFF) {
139 return $lcm->numify;
140 } else {
141 return $lcm;
142 }
143 }
144  
145 1;
146 __END__