view release on metacpan or  search on metacpan

lib/Math/NumSeq/LucasNumbers.pm  view on Meta::CPAN

Return the C<$i>'th Lucas number.

=item C<$bool = $seq-E<gt>pred($value)>

Return true if C<$value> is a Lucas number.

=item C<$i = $seq-E<gt>value_to_i_estimate($value)>

Return an estimate of the i corresponding to C<$value>.  See L</Value to i
Estimate> below.

=back

=head1 FORMULAS

=head2 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.

=head2 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

=head2 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)E<lt>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
L<Math::NumSeq::Fibonacci/Value to i Estimate>), 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.

=head2 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

=cut

# MY-PARI-CHECK: [-1,2;2,1] * [-1,2;2,1] == [5,0;0,5]

=pod

=head1 SEE ALSO

L<Math::NumSeq>,
L<Math::NumSeq::Fibonacci>,
L<Math::NumSeq::Pell>

=head1 HOME PAGE

L<http://user42.tuxfamily.org/math-numseq/index.html>

=head1 LICENSE

Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019, 2020 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.