|
|
A351657
|
|
Period of the Fibonacci n-step sequence mod n.
|
|
2
|
|
|
1, 3, 13, 10, 781, 728, 137257, 36, 273, 212784, 28531167061, 42640
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
a(14) = 92269645680
a(15) = 4976066589192413
a(16) = 136
a(18) = 306281976
(End)
|
|
LINKS
|
|
|
FORMULA
|
Conjecture 1: a(p) = (p^p-1)/(p-1) for p prime, i.e., a(A000040(n)) = A001039(n).
Conjecture 2: a(2^k) = 2^(k-1)*(1+2^k) = A007582(k).
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.
(End)
|
|
EXAMPLE
|
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.
|
|
PROG
|
(Python)
from math import lcm
from itertools import count
from sympy import factorint
def f(n, pe): # period of the Fibonacci n-step sequence mod pe
a = b = (0, )*(n-1)+(1%pe, )
s = 1 % pe
for m in count(1):
b, s = b[1:] + (s, ), (s+s-b[0]) % pe
if a == b:
return m
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|