| 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 |
- #!/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, Q, p, k=1) {
- (p - kronecker(P*P - 4*Q, p)).divisors.first_by {|d| lucasUmod(P, Q, d, p) == 0 } * p**(k-1)
- }
- func pisano_period(n, P=1, Q=-1) {
- return 0 if (n <= 0)
- return 1 if (n == 1)
- var d = n.factor_map {|p,k| pisano_period_pp(P, Q, p, k) }.lcm
- 3.times {|k|
- var t = d<<k
- if ((lucasUmod(P, Q, t, n) == 0) && (lucasUmod(P, Q, t+1, n) == 1)) {
- return t
- }
- }
- die "Error for n = #{n} with P = #{P} and Q = #{Q}"
- }
- say {|n| pisano_period(n, 1, -1) }.map(1..30) # Periods of Fibonacci numbers
- say {|n| pisano_period(n, 2, -1) }.map(1..30) # Periods of Pell numbers
- say {|n| pisano_period(n, 3, -1) }.map(1..30) # Periods of 3-Fibonacci numbers
- __END__
- [1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60, 16, 30, 48, 24, 100, 84, 72, 48, 14, 120]
- [1, 2, 8, 4, 12, 8, 6, 8, 24, 12, 24, 8, 28, 6, 24, 16, 16, 24, 40, 12, 24, 24, 22, 8, 60, 28, 72, 12, 20, 24]
- [1, 3, 2, 6, 12, 6, 16, 12, 6, 12, 8, 6, 52, 48, 12, 24, 16, 6, 40, 12, 16, 24, 22, 12, 60, 156, 18, 48, 28, 12]
|
