++ed by:
Kevin Ryde
and 1 contributors

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(i-1) + L(i-2) starting from 1,3

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

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

FUNCTIONS

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

`\$seq = Math::NumSeq::LucasNumbers->new ()`

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.

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``````

At the last step, ie. the lowest bit of i, only L[2k] or L[2k+1] needs to be calculated for the return, not the F[] too.

For any trailing zero bits of i, final doublings L[2k] can also be done with just one square as

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

The main double/step formulas can be applied until the lowest 1-bit of i is reached, then the L[2k+1] formula for that bit, followed by the single squaring for any trailing 0-bits.

Value to i Estimate

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

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

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

``````    log(L[i]) ~= i*log(phi)
i ~= log(L[i]) / 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]) / 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 be close enough to take Lestimate = Festimate-1 (or vice-versa) and share code between the two.