A015135 - OEIS

%I #19 Mar 24 2024 14:54:15

%S 1,2,2,3,3,4,2,4,3,6,3,5,2,4,5,5,2,4,3,7,3,6,2,6,4,4,4,5,3,10,3,6,5,3,

%T 5,5,2,4,4,7,2,6,2,7,7,3,2,6,3,8,4,5,2,5,5,6,5,6,3,11,2,4,5,7,5,10,2,

%U 4,3,10,3,6,2,4,7,5,5,8,3,9,5,4,2,7,5,4,5,9,2,10,4,4,5,4,7,7,2,6,7,9,3,6,2

%N Consider Fibonacci-type sequences f(0)=X, f(1)=Y, f(k)=f(k-1)+f(k-2) mod n; all are periodic; sequence gives number of distinct periods.

%C Consider the 2-step recursion f(k)=f(k-1)+f(k-2) mod n. For any of the n^2 initial conditions f(1) and f(2) in Zn, the recursion has a finite period. Each of these n^2 vectors belongs to exactly one orbit. In general, there are only a few different orbit lengths for each n. For n=8, there are 4 different lengths: 1, 3, 6 and 12. The maximum possible length of an orbit is A001175(n), the period of the Fibonacci 2-step sequence mod n. - _T. D. Noe_, May 02 2005

%H B. Avila and T. Khovanova, <a href="http://arxiv.org/abs/1403.4614">Free Fibonacci Sequences</a>, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Avila/avila4.html">J. Int. Seq. 17 (2014) # 14.8.5</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>.

%Y Cf. A015134 (orbits of 2-step sequences), A106306 (primes that yield a simple orbit structure in 2-step recursions).

%K nonn

%O 1,2

%A _Phil Carmody_

%E More terms from Larry Reeves (larryr(AT)acm.org), Jan 06 2005