Programming Praxis

Lucas sequences are important both to the study of prime numbers and in cryptography, and we’ve used Lucas sequences in several previous exercises, most recently just a few months ago; unfortunately, some of the code given in some of those exercises was incorrect, and looking back, I’m not entirely sure about some of the code that I think is correct. In today’s exercise we will describe Lucas sequences, write correct code, and demonstrate its correctness by thorough testing.

Given integers P and Q satisfying the equation D = P² − 4 Q > 0, the roots of x² − P x + Q = 0, by the quadratic equation from high school, are a = (P + √D) ÷ 2 and b = (P − √D) ÷ 2, so a + b = P, a × b = (P² − D) ÷ 4 = Q and a − b = √D. Now define U_n(P,Q) = (aⁿ − bⁿ) ÷ (a − b) and V_n(P,Q) = aⁿ + bⁿ for integer n ≥ 0. The sequences U(P,Q) and V(P,Q) for n from 1 to infinity are called Lucas sequences. Many of these sequences are well known; for instance, the sequence U(1,-1) forms the Fibonacci numbers, the sequence V(1,-1) forms the Lucas numbers (not to be confused with Lucas sequences), and the sequence U(3,2) forms the Mersenne numbers 2ⁿ − 1. Lucas sequences are named for the French mathematician Édouard Lucas, who was instrumental in their development in the second half of the nineteenth century.

A Lucas sequence can be calculated in a manner similar to the Fibonacci sequence; X_n = P X_n-1 − Q X_n-2. Here X takes the place of either U or V. For the U sequence, U₀ = 0 and U₁ = 1, and for the V sequence, V₀ = 2 and V₁ = P.

Any element of a Lucas sequence can be computed in logarithmic time by the application of the following identities: U_2n = U_n V_n, U_2n+1 = U_n+1 V_n − Qⁿ, V_2n = V_n² − 2 Qⁿ, and V_2n+1 = V_n+1 V_n − P Qⁿ. The identities are combined in a Lucas chain that contains pairs of adjacent elements of the sequences. For instance, starting from the pair (0,1), it is possible to reach the pair (100,101) in seven steps, thereby computing the 100^th elements of the sequences: (0,1) → (1,2) → (3,4) → (6,7) → (12,13) → (25,25) → (50,51) → (100,101). Each step in the chain is determined by the binary representation of the desired index n: 1-bits cause a step from (n,n+1) to (2n+1,2n+2) and 0-bits cause a step from (n,n+1) to (2n,2n+1). Note that computing a U sequence requires computation of the corresponding V sequence, but a V sequence can be computed by itself without the corresponding U sequence.

That method works left-to-right across the bits of n, from most-significant bit to least-significant bit, but it is more natural to work right-to-left, because at each step the last bit determines if n is even or odd and moving to the next bit is simply division by 2. Compute members of the U and V sequences at powers of 2, and add them to an accumulating total only when the corresponding bit is 1; the doubling identities were given above, and the addition identities are U_(m+n) = (U_m · V_n + U_n · V_m) / 2 and V_(m+n) = (V_m · V_n + D · U_m · U_n) / 2, where D = P² − 4 Q. Division by 2 is problematic when doing modular arithmetic, so if the current value is odd, first add the modulus before dividing by 2; there is no need to multiply by the inverse. The U and V accumulators are initialized to U = 0 and V = 2 if n is even and U = 1 and V = P if n is odd, then iteration starts at the second least significant bit, since the least significant bit was consumed in the initialization.

Your task is to write functions that compute Lucas sequences and individual members of Lucas sequences, and write a program that tests the functions thoroughly. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2