The Smallest Nontrivial Lucas Sequence
Background:
Named after Edouard Lucas (1842-1891) a Lucas sequence is an integer sequence verifying a second-order linear recurrence and starting with M(0)=0 and M(1)=1.
This includes a number of "classical" integer sequences like the Fibonacci sequence, the Pell numbers, the Jacobstahl numbers, the decimal repunits and other radix-m repunits, including Mersenne numbers (binary repunits). There are also a few "trivial" Lucas sequences which do not exhibit exponential growth, including the sequence of natural numbers 0,1,2,3,4,5,... and the periodic sequence (of period 6) 0,1,1,0,-1,-1,0,1,1,0,-1,-1,0,1,1,0,...
The integers a and b in the recurrence relation M(n+2)=aM(n+1)+bM(n) are usually taken to be coprime, because a sequence where gcd(a,b)=d is readily obtained by multiplying by dn a sequence with coprime coefficients. With this restriction, it is not difficult to see that gcd(M(n),M(p))=|M(gcd(n,p))|.
This relation shows, in particular, that M(n) can only be prime if n is either prime or divisible only by prime numbers p for which M(p) is a unit (1 or -1). For example, all Fibonacci primes have a prime index, with the sole exception of Fib(4)=3, which is prime although 4 is not (this is possible because 4 is only divisible by 2 and Fib(2)=1 is a unit).
Introduction
We shall introduce a few properties of Lucas sequence by studying in depth such a distinguished sequence. It is the slowest-growing of the nontrivial Lucas sequences (only 6 "trivial" cases of periodicity or linear growth are "smaller"). Surprisingly, this sequence does not appear to have an established name. It is defined via:
M(0)=0 M(1)=1 M(n+2) = M(n+1) - 2 M(n) 0, 1, 1, -1, -3, -1, 5, 7, -3, -17, -11, 23, 45, -1, -91, -89, 271, 85, -457, -627, 287, 1541, 967, -2115, -4049, 181, 8279, 7917 ...
(The alternate recurrence M(n+2)= -M(n+1)-2M(n) would give essentially the same sequence, except that the sign of every other term is changed.) A closed form of M is obtained with a standard technique: Look for two geometric progressions satifisfying the recurrence relation, then express the sequence at hand as a linear combination of these two. This involves solving a quadratic equation whose complex roots bring trigonometric functions into the picture:
 |
|
|||
| M(n) = 2 Ö | 2 n/ 7 | sin( n arctan Ö | 7 | ) |
The closed form for M(n) is slightly simpler for M(n) than it is for (-1) n M(n), and this serves to justify our aesthetic preference between the two possible "smallest" Lucas sequences.
A vexing problem with the divisibility properties of M is to determine for what indices n the value of M(n) is a unit (1 or -1). The beginning of the sequence shows this to be the case for n=1, 2, 3, 5 and 13. Are there any other such values? Well, half of the problem is easy to handle: Just look at the sequence modulo 8 (it has period 2 after n=3) and you'll see that M(n) cannot ever be equal to 1 again after n=2. What about M(n)=-1? Is that possible beyond n=13?
Looking for a modulus m that would allow us to conlude quickly the way m=8 allowed us to conclude for the positive unit appears fruitless at first for the negative unit. However, we remark that the periodic behavior of M(n) modulo m=2 k (where k is 3 or more) is particularly simple: The sequence has period 2 k/4 after n=k and the value -1 (modulo m) appears once and only once in each period!
