Math::NumSeq::LucasNumbers -- Lucas numbers


 use Math::NumSeq::LucasNumbers;
 my $seq = Math::NumSeq::LucasNumbers->new;
 my ($i, $value) = $seq->next;


The Lucas numbers, L(i) = L(i-1) + L(i-2) starting from values 1,3.

    1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364,...
    starting i=1

This is the same recurrence as the Fibonacci numbers (Math::NumSeq::Fibonacci), but a different starting point.

    L[i+1] = L[i] + L[i-1]

Each Lucas number falls in between successive Fibonaccis, and in fact the distance is a further Fibonacci,

    F[i+1] < L[i] < F[i+2]

    L[i] = F[i+1] + F[i-1]      # above F[i+1]
    L[i] = F[i+2] - F[i-2]      # below F[i+2]


Optional i_start => $i can start the sequence from somewhere other than the default i=1. For example starting at i=0 gives value 2 at i=0,

    i_start => 0
    2, 1, 3, 4, 7, 11, 18, ...


See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.

$seq = Math::NumSeq::LucasNumbers->new ()
$seq = Math::NumSeq::LucasNumbers->new (i_start => $i)

Create and return a new sequence object.


($i, $value) = $seq->next()

Return the next index and value in the sequence.

When $value exceeds the range of a Perl unsigned integer the return is a Math::BigInt to preserve precision.


Move the current sequence position to $i. The next call to next() will return $i and corresponding value.

Random Access

$value = $seq->ith($i)

Return the $i'th Lucas number.

$bool = $seq->pred($value)

Return true if $value is a Lucas number.

$i = $seq->value_to_i_estimate($value)

Return an estimate of the i corresponding to $value. See "Value to i Estimate" below.



Fibonacci F[k] and Lucas L[k] can be calculated together by a powering algorithm with two squares per doubling,

    F[2k] = (F[k]+L[k])^2/2 - 3*F[k]^2 - 2*(-1)^k
    L[2k] =                   5*F[k]^2 + 2*(-1)^k
    F[2k+1] =    ((F[k]+L[k])/2)^2 + F[k]^2
    L[2k+1] = 5*(((F[k]+L[k])/2)^2 - F[k]^2) - 4*(-1)^k

The 2*(-1)^k terms mean adding or subtracting 2 according to k odd or even. This means add or subtract according to the previous bit handled.

At the last step, which is the lowest bit of i, only L[2k] or L[2k+1] is needed for the return, not the F[] too.

For any trailing zero bits of i the final doublings L[2k] can be done without the F[] and with just one square as

    L[2k] = L[k]^2 - 2*(-1)^k


    main double/step L[],F[] until the lowest 1-bit of i is reached
    then L[2k+1] formula for that bit
    then L[2k] single squarings for any low 0-bits

Value to i Estimate

L[i] increases as a power of phi, the golden ratio,

    L[i] = phi^i + beta^i    # exactly

    phi = (1+sqrt(5))/2 = 1.618
    beta = -1/phi = -0.618

So taking a log (natural logarithm) to get i, and ignoring beta^i which quickly becomes small since abs(beta)<1,

    log(L[i]) ~= i*log(phi)
    i ~= log(L[i]) * 1/log(phi)

Or the same using log base 2 which can be estimated from the highest bit position of a bignum,

    log2(L[i]) ~= i*log2(phi)
    i ~= log2(L[i]) * 1/log2(phi)

This is very close to the Fibonacci formula (see "Value to i Estimate" in Math::NumSeq::Fibonacci), being bigger by

    Lestimate(value) - Festimate(value)
      = log(value) / log(phi) - (log(value) + log(phi-beta)) / log(phi)
      = -log(phi-beta) / log(phi)
      = -1.67

On that basis it could even be close enough to take Lestimate = Festimate-1 (or vice-versa).


Math::NumSeq, Math::NumSeq::Fibonacci, Math::NumSeq::Pell



Copyright 2010, 2011, 2012, 2013 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <>.