cp's OEIS Frontend

A351657 Period of the Fibonacci n-step sequence mod n.

%I A351657 #56 Feb 16 2025 08:34:02
%S A351657 1,3,13,10,781,728,137257,36,273,212784,28531167061,42640
%N A351657 Period of the Fibonacci n-step sequence mod n.
%C A351657 From _Chai Wah Wu_, Feb 23 2022: (Start)
%C A351657 a(14) = 92269645680
%C A351657 a(15) = 4976066589192413
%C A351657 a(16) = 136
%C A351657 a(18) = 306281976
%C A351657 (End)
%H A351657 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>
%H A351657 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PisanoPeriod.html">Pisano Period</a>
%F A351657 From _Chai Wah Wu_, Feb 22 2022: (Start)
%F A351657 Conjecture 1: a(p) = (p^p-1)/(p-1) for p prime, i.e., a(A000040(n)) = A001039(n).
%F A351657 Conjecture 2: a(2^k) = 2^(k-1)*(1+2^k) = A007582(k).
%F A351657 Conjecture 3 (which implies Conjectures 1 and 2): a(p^k) = (p^(p*k)-1)*p^(k-1)/(p^k-1) for k > 0 and prime p.
%F A351657 (End)
%e A351657 For n = 4, take the tetranacci sequence (A000078), 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ... (mod 4), which gives 0, 0, 0, 1, 1, 2, 0, 0, 3, 1, 0, 0, 0, 1, 1, 2, ... This repeats a pattern of length 10, so a(4) = 10.
%o A351657 (Python)
%o A351657 from math import lcm
%o A351657 from itertools import count
%o A351657 from sympy import factorint
%o A351657 def f(n,pe): # period of the Fibonacci n-step sequence mod pe
%o A351657     a = b = (0,)*(n-1)+(1%pe,)
%o A351657     s = 1 % pe
%o A351657     for m in count(1):
%o A351657         b, s = b[1:] + (s,), (s+s-b[0]) % pe
%o A351657         if a == b:
%o A351657             return m
%o A351657 def A351657(n): return 1 if n == 1 else lcm(*(f(n,p**e) for p, e in factorint(n).items())) # _Chai Wah Wu_, Feb 23-27 2022
%Y A351657 Cf. A000040, A001039, A001175, A007582, A046738, A106295, A106303.
%K A351657 nonn,more
%O A351657 1,2
%A A351657 _Ilya Gutkovskiy_, Feb 16 2022
%E A351657 a(11)-a(12) from _Chai Wah Wu_, Feb 22 2022