| 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__ |