A094401 Composite n such that n divides both Fibonacci(n-1) and Fibonacci(n) - 1.

2737, 4181, 6721, 13201, 15251, 34561, 51841, 64079, 64681, 67861, 68251, 90061, 96049, 97921, 118441, 146611, 163081, 179697, 186961, 194833, 197209, 219781, 252601, 254321, 257761, 268801, 272611, 283361, 302101, 303101, 327313, 330929

Offset

1,1

Comments

Composite n such that Q^(n-1) = I (mod n), where Q is the Fibonacci matrix {{1,1},{1,0}} and I is the identity matrix. The identity is also true for the primes congruent to 1 or 4 (mod 5), which is sequence A045468. The period of Q^k (mod n) is the same as the period of the Fibonacci numbers F(k) (mod n), A001175. Hence the terms in this sequence are the composite n such that A001175(n) divides n-1. [T. D. Noe, Jan 09 2009]

Links

Giovanni Resta, Table of n, a(n) for n = 1..1000 (first 200 terms from T. D. Noe)

Eric Weisstein, MathWorld: Fibonacci Q-Matrix.

Mathematica

Select[Range[2, 50000], ! PrimeQ[ # ] && Mod[Fibonacci[ # - 1], # ] == 0 && Mod[Lucas[ # ] - 1, # ] == 0 &]

Prog

(Python)
from itertools import islice
from sympy import nextprime
def A094401_gen(): # generator of terms
    def f(n, m): # return fibonacci(n-1) mod m and fibonacci(n) mod m
        a, b, c, d, a2, b2, c2, d2 = 1, 1, 1, 0, 1, 0, 0, 1
        for x in bin(n)[2:]:
            e, f = b2*c2%m, k if (k:=a2+d2)<m else k-m
            a2, b2, c2, d2 = (a2*a2+e)%m, b2*f%m, c2*f%m, (d2*d2+e)%m
            if x=='1':
                a2, b2, c2, d2 = (a2*a+b2*c)%m, (a2*b+b2*d)%m, (c2*a+d2*c)%m, (c2*b+d2*d)%m
        return d2, c2
    p, q = 4, 5
    while True:
        for m in range(p, q):
            a, b = f(m, m)
            if not a and b == 1:
                yield m
        p, q = q+1, nextprime(q)
A094401_list = list(islice(A094401_gen(), 30)) # Chai Wah Wu, Jul 09 2026

Crossrefs

Cf. A005845, A069106, A094394, A094400.

Sequence in context: A258904 A221976 A337625 * A035774 A107570 A237680

Adjacent sequences: A094398 A094399 A094400 * A094402 A094403 A094404

Keyword

nonn,changed

Author

Eric Rowland, May 01 2004

Extensions

More terms from Ryan Propper, Sep 24 2005

Status

approved