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

1, 3, 13, 10, 781, 728, 137257, 36, 273, 212784, 28531167061, 42640

Offset: 1

Author

Ilya Gutkovskiy, Feb 16 2022

Keywords

• nonn
• more

Comments

From Chai Wah Wu, Feb 23 2022: (Start)

a(14) = 92269645680

a(15) = 4976066589192413

a(16) = 136

a(18) = 306281976

(End)

Examples

			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.
		

Links

• Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
• Eric Weisstein's World of Mathematics, Pisano Period

Crossrefs

Cf. A000040, A001039, A001175, A007582, A046738, A106295, A106303.

Programs

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

Formula

From Chai Wah Wu, Feb 22 2022: (Start)

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)

Extensions

a(11)-a(12) from Chai Wah Wu, Feb 22 2022