OFFSET
1,2
COMMENTS
The discrete Arnold's cat map on an n X n array is defined as (x, y) -> (x + y, x + 2y) mod n, where x and y are integers with 0 <= x, y < n. For a fixed n, iterating this map classifies all points into distinct cycles; a(n) is then the LCM of the cycle lengths.
Dyson and Falk show that log(n)/phi < a(n) <= 3*n, where phi is the golden ratio A001622.
From Jianing Song, Jan 05 2019: (Start)
Pisano periods for A001906.
a(n) is the multiplicative order of (3 + sqrt(5))/2 modulo n over the ring Z[(1 + sqrt(5))/2].
a(n) is the smallest k > 0 such that [3, -1; 1, 0]^k == I (mod n), where I is the identity matrix.
a(m*n) = a(m)*a(n) if gcd(m, n) = 1.
For primes p == +-1 (mod 10), a(p) divides (p - 1)/2.
For primes p == +-3 (mod 10), a(p) divides p + 1, but a(p) does not divide (p + 1)/2.
For odd primes p, a(p^e) = p^(e-1)*a(p) if p^2 does not divide a(p). Any counterexample would be a Wall-Sun-Sun prime. No such primes are known.
a(2^e) = 3 if e = 1 and 3*2^(e-2) if e >= 2. a(5^e) = 2*5^e, e >= 1.
As is mentioned above, a(n) <= 3*n for all n, where the equality holds if and only if n = 2*5^e, e >= 1. (End)
LINKS
Jeremy Tan, Table of n, a(n) for n = 1..10000
Freeman Dyson and Harold Falk, Period of a Discrete Cat Mapping, The American Mathematical Monthly 99 (7), 603-614.
Holger Kantz, Poincaré Recurrences
J. Maiga, The Pisano period of Fibonacci k-sections, 2019.
Wikipedia, Arnold's cat map
FORMULA
a(n) is the smallest positive integer t such that F(2*t) == 0 (mod n) and F(2*t-1) == 1 (mod n), where F(n) is the Fibonacci sequence A000045.
a(n) = A001175(n)/2 for n >= 3 (half the Pisano period for the Fibonacci sequence). Proof: the map sends (F(m-1), F(m)) to (F(m+1), F(m+2)) mod n. F(0) = 0 and F(-1) = 1, so the smallest value of 2*t that makes the two defining congruences valid is A001175(n). For n >= 3, all Pisano periods for the Fibonacci sequence are even, which completes the proof.
EXAMPLE
The cycles for n = 3 are (0,0), (1,0)->(1,1)->(2,0)->(2,2) and (0,1)->(1,2)->(0,2)->(2,1). Since there is one cycle of length 1 and two of length 4, a(3) = 4.
PROG
(PARI) a(n) = {if(n < 2, 1, t = 1; while(Mod(fibonacci(2 * t), n) != 0 || Mod(fibonacci(2 * t - 1), n) != 1, t += 1); t)}
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeremy Tan, Jan 18 2017
STATUS
approved