login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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^(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, 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), 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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 23 18:12 EDT 2019. Contains 322387 sequences. (Running on oeis4.)