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

## 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 a `Math::BigInt` to preserve precision.

`\$seq->seek_to_i(\$i)`

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.

# FORMULAS

## Ith Pair

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.

## Ith

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

## Value to i Estimate

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.

## Ith Fibonacci and Lucas

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