NAME
Math::NumSeq::LucasNumbers  Lucas numbers
SYNOPSIS
use Math::NumSeq::LucasNumbers;
my $seq = Math::NumSeq::LucasNumbers>new;
my ($i, $value) = $seq>next;
DESCRIPTION
The Lucas numbers, L(i) = L(i1) + L(i2) 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[i1]
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[i1] # above F[i+1]
L[i] = F[i+2]  F[i2] # below F[i+2]
Start
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, ...
FUNCTIONS
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.
Iterating
($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 aMath::BigInt
to preserve precision. $seq>seek_to_i($i)

Move the current sequence position to
$i
. The next call tonext()
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.
FORMULAS
Ith
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
So
main double/step L[],F[] until the lowest 1bit of i is reached
then L[2k+1] formula for that bit
then L[2k] single squarings for any low 0bits
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(phibeta)) / log(phi)
= log(phibeta) / log(phi)
= 1.67
On that basis it could even be close enough to take Lestimate = Festimate1 (or viceversa).
SEE ALSO
Math::NumSeq, Math::NumSeq::Fibonacci, Math::NumSeq::Pell
HOME PAGE
http://user42.tuxfamily.org/mathnumseq/index.html
LICENSE
Copyright 2010, 2011, 2012, 2013 Kevin Ryde
MathNumSeq 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.
MathNumSeq 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 MathNumSeq. If not, see <http://www.gnu.org/licenses/>.