A351889 Table T(n,k) read by downward antidiagonals: period of n-step Fibonacci numbers mod k, n >= 1, k >= 1.
1, 1, 1, 1, 3, 1, 1, 8, 4, 1, 1, 6, 13, 5, 1, 1, 20, 8, 26, 6, 1, 1, 24, 31, 10, 104, 7, 1, 1, 16, 52, 312, 12, 728, 8, 1, 1, 12, 48, 130, 781, 14, 364, 9, 1, 1, 24, 16, 342, 312, 208, 16, 80, 10, 1, 1, 60, 39, 20, 2801, 728, 9372, 18, 91, 11, 1, 1, 10, 124, 78, 24, 342, 728, 195312
Offset: 1
Examples
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
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
Programs
-
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()))
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.
Comments