| 123456789101112131415161718192021222324252627 |
- #!/usr/bin/ruby
- # Compute the Pisano periods (or Pisano numbers): period of Fibonacci numbers mod n.
- # See also:
- # https://oeis.org/A001175
- # https://en.wikipedia.org/wiki/Pisano_period
- func pisano_period_pp(p,k) is cached {
- assert(k.is_pos, "k = #{k} must be positive")
- assert(p.is_prime, "p = #{p} must be prime")
- var (a, b, n) = (0, 1, p**k)
- 1..Inf -> first_by {
- (a, b) = (b, (a+b) % n)
- (a == 0) && (b == 1)
- }
- }
- func pisano_period(n) {
- n.factor_map {|p,k| pisano_period_pp(p, k) }.lcm
- }
- say pisano_period.map(1..20)
|
