12345678910111213141516171819202122232425262728293031323334353637383940414243 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 08 August 2018
- # https://github.com/trizen
- # Efficient algorithm for computing the Pisano period: period of Fibonacci
- # numbers mod `n`, assuming that the factorization of `n` can be computed.
- # This algorithm assumes that Wall-Sun-Sun primes do not exist.
- # See also:
- # https://oeis.org/A001175
- # https://oeis.org/A053031
- # https://en.wikipedia.org/wiki/Pisano_period
- # https://en.wikipedia.org/wiki/Wall%E2%80%93Sun%E2%80%93Sun_prime
- func pisano_period_pp(p, k=1) {
- (p - kronecker(5, p)).divisors.first_by {|d| fibmod(d, p) == 0 } * p**(k-1)
- }
- func pisano_period(n) {
- return 0 if (n <= 0)
- return 1 if (n == 1)
- var d = n.factor_map {|p,k| pisano_period_pp(p, k) }.lcm
- 3.times {|k|
- var t = d<<k
- if ((fibmod(t, n) == 0) && (fibmod(t+1, n) == 1)) {
- return t
- }
- }
- }
- say pisano_period(10!) #=> 86400
- say pisano_period(30!) #=> 204996473853050880000000
- say pisano_period(2**128 + 1) #=> 28356863910078205764000346543980814080
- say {|n| pisano_period(n) }.map(1..20) #=> [1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60]
- say {|n| pisano_period(n!) }.map(1..20) #=> [1, 3, 24, 24, 120, 120, 240, 960, 8640, 86400, 86400, 1036800, 7257600, 14515200, 217728000, 3483648000, 3483648000, 62705664000, 62705664000, 1254113280000]
|