A106291 Period of the Lucas sequence A000032 mod n.

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, 84, 72, 48, 14, 24, 30, 48, 40, 36, 16, 24, 76, 18, 56, 12, 40, 48, 88, 30, 24, 48, 32, 24, 112, 60, 72, 84, 108, 72, 20, 48, 72, 42, 58, 24, 60, 30, 48, 96, 28, 120, 136, 36, 48, 48

Offset: 1

Author

T. D. Noe, May 02 2005

Keywords

• nonn

Comments

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.

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

Examples

			From _Klaus Purath_, Jul 10 2019: (Start)
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.
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.
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)
		

References

• 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

Links

• G. C. Greubel and D. Turner, Table of n, a(n) for n = 1..10000
• Brennan Benfield and Oliver Lippard, Fixed points of K-Fibonacci sequences, arXiv:2404.08194 [math.NT], 2024. See p. 11.
• Eric Weisstein's World of Mathematics, Fibonacci n-Step Number

Crossrefs

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

Cf. A000032, A001175, A030430.

Programs

Mathematica

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}]

Python

from math import lcm
from functools import lru_cache
from sympy import factorint
@lru_cache(maxsize=None)
def A106291(n):
    if n < 3:
        return (n<<1)-1
    f = factorint(n).items()
    if len(f) > 1:
        return lcm(*(A106291(a**b) for a,b in f))
    else:
        k,x = 1, (1,3)
        while x != (2,1):
            k += 1
            x = (x[1], (x[0]+x[1]) % n)
        return k # Chai Wah Wu, Apr 25 2025

Sage

def a(n): return BinaryRecurrenceSequence(1, 1, 2, 1).period(n)
[a(n) for n in (1..100)] # G. C. Greubel, Apr 27 2019

Formula

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