Nombres de Lucas

The sequence belongs to Édouard Lucas, born in Amiens on 4 April 1842. He worked at the Paris Observatory, served as an artillery officer in the Franco-Prussian War, and afterwards taught mathematics at the Lycée Saint-Louis and the Lycée Charlemagne in Paris. His 1878 memoir on simply periodic numerical functions, published in the American Journal of Mathematics, laid out a general theory of sequences generated by a two-term recurrence — the family now called Lucas sequences. Fibonacci's numbers are one member of it. The sequence on this page, opening 2, 1, 3, 4, 7, is their companion, and it was Lucas who fixed Leonardo of Pisa's nickname onto the more famous of the pair.

Lucas pursued these sequences because they let him test enormous numbers for primality without factoring anything. In 1876, working entirely by hand, he proved that the 39-digit Mersenne number 2¹²⁷ − 1 = 170,141,183,460,469,231,731,687,303,715,884,105,727 is prime. No larger prime was known to anyone for the next 75 years, until calculating machines took over in 1951. Sharpened by Derrick Lehmer in the 1930s, the method survives as the Lucas–Lehmer test, still what the distributed GIMPS project uses to certify each record Mersenne prime.

He is equally remembered for a toy. The Tower of Hanoi went on sale in 1883 credited to "M. Claus" — an anagram of Lucas — packaged with an invented legend about priests shifting sixty-four golden discs.

Lucas died in Paris on 3 October 1891, aged 49, and his biographers all repeat the same strange account: at a scientific banquet a dropped plate sent a fragment into his cheek, and the wound turned into a fatal erysipelas infection within days.

Propriétés principales

• L(0) = 2, L(1) = 1, and L(n) = L(n−1) + L(n−2) — the Fibonacci rule from different seeds.
• L(n) = F(n−1) + F(n+1): every Lucas number is the sum of the Fibonacci numbers either side of it.
• For every n > 1, L(n) is the integer closest to φⁿ, where φ = (1+√5)/2. L(10) = 123 and φ¹⁰ ≈ 122.99.
• L(n)² − 5·F(n)² = 4·(−1)ⁿ, which pins the two sequences together exactly rather than approximately.
• F(2n) = F(n)·L(n), so Lucas numbers are the doubling step used by fast Fibonacci algorithms.
• If L(n) is prime then n is 0, a prime, or a power of 2. Among the powers of 2 only L(2) = 3, L(4) = 7, L(8) = 47 and L(16) = 2207 are known to be prime.
• L(p) ≡ 1 (mod p) for every prime p — a Fermat-style congruence that fails for some composites, which is what makes Lucas pseudoprimes interesting.
• The only perfect squares in the sequence are L(1) = 1 and L(3) = 4.

Où on les rencontre

• L(n) counts the ways to tile a ring of n cells with single squares and dominoes — the "bracelet" count, as against Fibonacci’s count for a straight strip. A ring of 4 cells has L(4) = 7 tilings.
• The Lucas–Lehmer primality test, which grew directly out of this work, is how every record-breaking Mersenne prime since the 1950s has been verified, including those found by the GIMPS volunteer project.
• The Baillie–PSW probable-prime test, built into many computer-algebra systems and cryptography libraries, pairs a base-2 Fermat test with a strong Lucas test on a sequence of this type.
• In phyllotaxis, a minority of plants show spiral counts of 4, 7 or 11 instead of the usual Fibonacci 5, 8, 13 — botanists call this Lucas phyllotaxis. It is a documented but uncommon pattern, not the norm.
• Lucas numbers appear in the fast-doubling identities used to compute huge Fibonacci numbers in logarithmic time, which is how libraries reach F(1,000,000) without a million additions.