A015134 -id:A015134 - cp's OEIS frontend

A015135 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.

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, 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, 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

Offset: 1

Phil Carmody

nonn

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

B. Avila and T. Khovanova, Free Fibonacci Sequences, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.8.5
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

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

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

A233246 Sum of squares of cycle lengths for different cycles in Fibonacci-like sequences modulo n.

Original entry on oeis.org

1, 10, 65, 82, 417, 650, 769, 658, 1793, 4170, 1151, 3026, 4705, 7690, 7137, 5266, 10369, 7562, 6319, 19218, 6977, 11510, 25345, 12818, 52417, 47050, 48449, 35410, 11565, 71370, 28351, 42130, 39615, 41482, 81057, 30674, 103969, 25282, 80033

Offset: 1

Brandon Avila and Tanya Khovanova, Dec 06 2013

nonn

Here Fibonacci-like means a sequence following the Fibonacci recursion: b(n)=b(n-1)+b(n-2). These sequences modulo n cycle. The number of different cycles is A015134(n).
This sequence divided by n^2 is the average cycle length per different starting pairs modulo n, see A233248.
If n is in A064414, then a(n)/n^2 is the average distance between two neighboring multiples of n.
If n is in A064414, then a(n)/2n^2 is the average distance to the next zero over all starting pairs of remainders.

			For n=4 there are four possible cycles: A trivial cycle of length 1: 0; two cycles of length 6: 0,1,1,2,3,1; and a cycle of length 3: 0,2,2. Hence, a(4)=1+9+36+36=82.

B. Avila and T. Khovanova, Free Fibonacci Sequences, arXiv preprint arXiv:1403.4614, 2014 and J. Int. Seq. 17 (2014) # 14.8.5

Cf. A233248, A064414.

cl[i_, j_, n_] := (step = 1; first = i; second = j;
  next = Mod[first + second, n];
  While[second != i || next != j, step++; first = second;
   second = next; next = Mod[first + second, n]]; step)
Table[Total[
  Flatten[Table[cl[i, j, n], {i, 0, n - 1}, {j, 0, n - 1}]]], {n, 50}]

A384490 Numbers m such that both roots of x^2 - x - 1 modulo m are primitive roots modulo m.

Original entry on oeis.org

41, 61, 109, 149, 241, 269, 389, 409, 449, 569, 601, 641, 701, 821, 929, 1129, 1181, 1201, 1301, 1321, 1429, 1481, 1489, 1609, 1801, 1889, 1901, 1949, 2129, 2141, 2309, 2341, 2381, 2549, 2609, 2741, 2909, 3061, 3109, 3181, 3209, 3221, 3229, 3361, 3449, 3541

Offset: 1

Jay Anderson, May 31 2025

nonn

Empirical observation: For each m in this sequence A001175(m) = m-1 and A015134(m) = m+2.

			For m = 41 the roots of x^2 - x - 1 (mod 41) are 7 and 35. 7 and 35 are both primitive roots modulo 41.

Wikipedia, Primitive root modulo n.

Cf. A001175, A015134.

test[p_]:=Module[{inv2,sqr},If[JacobiSymbol[5,p]==1,inv2=ModularInverse[2,p]; sqr=PowerMod[5,1/2,p]; {MultiplicativeOrder[Mod[inv2*(sqr-1),p],p],MultiplicativeOrder[Mod[inv2*(-sqr-1),p],p]} == {p-1,p-1},False]]; Cases[Prime[Range[4, 5000]], ?(test[#] &)] (* _Shenghui Yang, Jun 01 2025 *)

{ forprime(p=2, 3600, s=polrootsmod(x^2 - x - 1,p);
 if( #s==2 && p-1==znorder(Mod(s[1],p)) && p-1==znorder(Mod(s[2],p)),
 print1(p,", "); ); ); } \\ Joerg Arndt, May 31 2025

cp's OEIS Frontend

A015135 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.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A233246 Sum of squares of cycle lengths for different cycles in Fibonacci-like sequences modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A384490 Numbers m such that both roots of x^2 - x - 1 modulo m are primitive roots modulo m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI