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]
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.
$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.
$value = $seq->ith($i)
$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.
A pair of Lucas numbers L[k], L[k+1] can be calculated together by a powering algorithm with two squares per doubling,
L[2k] = L[k]^2 - 2*(-1)^k L[2k+2] = L[k+1]^2 + 2*(-1)^k L[2k+1] = L[2k+2] - L[2k] if bit==0 then take L[2k], L[2k+1] if bit==1 then take L[2k+1], L[2k+2]
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.
For any trailing zero bits of i the final doublings can be done by L[2k] alone which is one square per 0-bit.
ith_pair(odd part of i) to get L[2k+1] (ignore L[2k+2]) loop L[2k] = L[k]^2 - 2*(-1)^k for each trailing 0-bit of i
L[i] increases as a power of phi, the golden ratio. The exact value is
L[i] = phi^i + beta^i # exactly phi = (1+sqrt(5))/2 = 1.618 beta = -1/phi = -0.618
Since abs(beta)<1 the beta^i term quickly becomes small. So taking a log (natural logarithm) to get i,
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.
It's also possible to calculate a Fibonacci F[k] and Lucas L[k] together by a similar powering algorithm with two squares per doubling, but a couple of extra factors,
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
Or the conversions between a pair of Fibonacci and Lucas are
F[k] = ( - L[k] + 2*L[k+1])/5 F[k+1] = ( 2*L[k] + L[k+1])/5 = (F[k] + L[k])/2 L[k] = - F[k] + 2*F[k+1] L[k+1] = 2*F[k] + F[k+1] = (5*F[k] + L[k])/2
Copyright 2010, 2011, 2012, 2013, 2014 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 <http://www.gnu.org/licenses/>.