login
Period of the Lucas sequence A000032 mod n.
18

%I #42 Apr 18 2024 13:46:58

%S 1,3,8,6,4,24,16,12,24,12,10,24,28,48,8,24,36,24,18,12,16,30,48,24,20,

%T 84,72,48,14,24,30,48,40,36,16,24,76,18,56,12,40,48,88,30,24,48,32,24,

%U 112,60,72,84,108,72,20,48,72,42,58,24,60,30,48,96,28,120,136,36,48,48

%N Period of the Lucas sequence A000032 mod n.

%C This sequence differs from the Fibonacci periods (A001175) only when n is a multiple of 5, which can be traced to 5 being the discriminant of the characteristic polynomial x^2-x-1.

%C This sequence coincides with the Fibonacci periods (A001175) if n is a multiple of 5^j and the following conditions apply: n contains at least one prime factor of the form p = 10*k+1 (A030430) which occurs in Fibonacci(m) or Lucas(m) as prime factor, where m must be the smallest possible index containing p and a factor 5^i and j <= i. If n contains several prime factors from A030430 that satisfy the above conditions, the largest applicable i is decisive. - _Klaus Purath_, Apr 26 2019

%D S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989. See p. 89. - From _N. J. A. Sloane_, Feb 20 2013

%H G. C. Greubel and D. Turner, <a href="/A106291/b106291.txt">Table of n, a(n) for n = 1..10000</a>

%H Brennan Benfield and Oliver Lippard, <a href="https://arxiv.org/abs/2404.08194">Fixed points of K-Fibonacci sequences</a>, arXiv:2404.08194 [math.NT], 2024. See p. 11.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>

%F Let the prime factorization of n be p1^e1...pk^ek. Then a(n) = lcm(a(p1^e1), ..., a(pk^ek)).

%e From _Klaus Purath_, Jul 10 2019: (Start)

%e n = 3*5*31 = 465, j = 1; L(15) is the smallest Lucas number with prime factor 31; 15 = 3*5, i = 1 = j. Hence Lucas period (mod 465) = Fibonacci period (mod 465) = 120, but if n = 3*5^2*31 = 2325, j = 2 > i. Hence Lucas period (mod 2325) = 120 < Fibonacci period (mod 2325) = 600.

%e n = 5*701 = 3505, j = 1; F(175) is the smallest Fibonacci number with prime factor 701; 175 = 7*5^2, i = 2 > j. Therefore Lucas period (mod 3505) = Fibonacci period (mod 3505) = 700, but if n = 5^3*701 = 87625, j = 3 > i. Therefore Lucas period (mod 87625) = 700 < Fibonacci period (mod 87625) = 3500.

%e n = 5^2*11*101 = 27775, j =2; L(5) is the smallest Lucas number with prime factor 11, i = 1; L(25) = is the smallest Lucas number with prime factor 101; 25 = 5^2, i = 2 ( decisive); j = i. Hence Lucas period (mod 27775) = Fibonacci period (mod 27775) = 100, but if n = 5^3*11*101 = 138875, j = 3 > i. Hence Lucas period (mod 138875) = 100 < Fibonacci period (mod 138875) = 500. (End)

%t n=2; Table[p=i; a=Join[Table[ -1, {n-1}], {n}]; a=Mod[a, p]; a0=a; k=0; While[k++; s=Mod[Plus@@a, p]; a=RotateLeft[a]; a[[n]]=s; a!=a0]; k, {i, 70}]

%o (Sage)

%o def a(n): return BinaryRecurrenceSequence(1, 1, 2, 1).period(n)

%o [a(n) for n in (1..100)] # _G. C. Greubel_, Apr 27 2019

%Y Cf. A106273 (discriminant of the polynomial x^n-x^(n-1)-...-x-1).

%Y Cf. A000032, A001175, A030430.

%K nonn

%O 1,2

%A _T. D. Noe_, May 02 2005