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

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

Offset

1,2

Comments

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

a(14) = 92269645680

a(15) = 4976066589192413

a(16) = 136

a(18) = 306281976

(End)

Links

Table of n, a(n) for n=1..12.

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

Eric Weisstein's World of Mathematics, Pisano Period

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)

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

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

Sequence in context: A273122 A071708 A136592 * A376431 A340441 A085416

Adjacent sequences: A351654 A351655 A351656 * A351658 A351659 A351660

Keyword

nonn,more

Author

Ilya Gutkovskiy, Feb 16 2022

Extensions

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

Status

approved