

A281230


Period of the discrete Arnold cat map on an n X n array.


1



1, 3, 4, 3, 10, 12, 8, 6, 12, 30, 5, 12, 14, 24, 20, 12, 18, 12, 9, 30, 8, 15, 24, 12, 50, 42, 36, 24, 7, 60, 15, 24, 20, 18, 40, 12, 38, 9, 28, 30, 20, 24, 44, 15, 60, 24, 16, 12, 56, 150, 36, 42, 54, 36, 10, 24, 36, 21, 29, 60, 30, 15, 24, 48, 70, 60, 68, 18, 24, 120, 35, 12, 74, 114, 100, 9, 40, 84, 39, 60
(list;
graph;
refs;
listen;
history;
text;
internal format)



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^(e1)*a(p) if p^2 does not divide a(p). Any counterexample would be a WallSunSun prime. No such primes are known.
a(2^e) = 3 if e = 1 and 3*2^(e2) if e >= 2. a(5^e) = 2*5^e, e >= 1.
As is mentioned above, a(n) <= 3*n for all n, with equality holds if and only if n = 2*5^e, e >= 1. (End)
In general, the Pisano period of Fibonacci(k*n) mod m is lcm(A001175(m), k)/k, see link.  Jon Maiga, Mar 22 2019


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), 603614.
Holger Kantz, PoincarĂ© Recurrences
J. Maiga, The Pisano period of Fibonacci ksections, 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*t1) == 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(m1), 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.
a(n) = lcm(A001175(n), 2)/2.  Jon Maiga, Mar 22 2019


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

Cf. A000045, A001175, A001622, A001906.
Sequence in context: A174280 A172004 A051508 * A323977 A322359 A172990
Adjacent sequences: A281227 A281228 A281229 * A281231 A281232 A281233


KEYWORD

nonn


AUTHOR

Jeremy Tan, Jan 18 2017


STATUS

approved



