OFFSET
1,5
LINKS
Chai Wah Wu, Table of n, a(n) for n = 1..226
M. E. Waddill, Some properties of a generalized Fibonacci sequence modulo m, The Fibonacci Quarterly, vol. 16, no. 4, pp. 344-353 (1978).
Marcellus E. Waddill, Some Properties of the Tetranacci Sequence Modulo m, The Fibonacci Quarterly, vol. 30, no. 3, 232-238 (1992).
D. D. Wall, Fibonacci Series Modulo m, The American Mathematical Monthly, vol. 67, no. 6, pp. 525-532, (1960).
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
Eric Weisstein's World of Mathematics, Pisano Period
FORMULA
T(1,k) = T(n,1) = 1.
T(2,k) = A001175(k).
T(3,k) = A046738(k).
T(4,k) = A106295(k) for k not a multiple of 563.
T(5,k) = A106303(k).
T(n,2) = n + 1 for n > 1.
T(n,3) = A337212(n).
T(n,n) = A351657(n).
T(n,p_1^e_1*...*p_m^e_m) = lcm(T(n,p_1^e_1),...,T(n,p_m^e_m)) for p_i distinct primes.
Conjecture 1: T(n,2^m) = (n+1)*2^(m-1) for n > 1.
Conjecture 2: For p prime, if T(n,p) != T(n,p^2) then T(n,p^k) = p^(k-1)T(n,p).
Conjecture 2 is true for n = 2, n = 3 and n = 4 (see [Wall, 1960], [Waddill, 1978] and [Waddill, 1992] resp.). It is easy to show that T(n,4) != n+1 for all n, and thus Conjecture 2 implies Conjecture 1.
Conjecture 3: T(p^m,p^k) = (p^(pm)-1)*p^(k-1)/(p^m-1) for p prime and k, m > 0.
EXAMPLE
Table T(n,k) starts:
1 1 1 1 1 1 1 1 1 1
1 3 8 6 20 24 16 12 24 60
1 4 13 8 31 52 48 16 39 124
1 5 26 10 312 130 342 20 78 1560
1 6 104 12 781 312 2801 24 312 4686
1 7 728 14 208 728 342 28 2184 1456
1 8 364 16 9372 728 137257 32 1092 18744
1 9 80 18 195312 720 13680 36 240 585936
1 10 91 20 488281 910 5764800 40 273 4882810
1 11 8744 22 19344 96184 19152 44 26232 212784
1 12 3851 24 406224 46212 109531200 48 11553 406224
PROG
(Python)
from functools import lru_cache
from math import lcm
from itertools import count
from sympy import factorint
@lru_cache(maxsize=None)
def A351889_T(n, k): # computes the period of the n-step Fibonacci sequence mod k
if len(fs := factorint(k)) <= 1:
a = b = (0, )*(n-1)+(1 % k, )
s = 1 % k
for m in count(1):
b, s = b[1:] + (s, ), (s + s - b[0]) % k
if a == b:
return m
else:
return lcm(*(A351889_T(n, p**e) for p, e in fs.items()))
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Chai Wah Wu, Feb 24 2022
STATUS
approved