Math::NumSeq::LucasNumbers(3pm)

1Math::NumSeq::LucasNumbUesresr(3C)ontributed Perl DocumeMnattaht:i:oNnumSeq::LucasNumbers(3)
2
3
4

NAME

6       Math::NumSeq::LucasNumbers -- Lucas numbers
7

SYNOPSIS

9        use Math::NumSeq::LucasNumbers;
10        my $seq = Math::NumSeq::LucasNumbers->new;
11        my ($i, $value) = $seq->next;
12

DESCRIPTION

14       The Lucas numbers, L(i) = L(i-1) + L(i-2) starting from values 1,3.
15
16           1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364,...
17           starting i=1
18
19       This is the same recurrence as the Fibonacci numbers
20       (Math::NumSeq::Fibonacci), but a different starting point.
21
22           L[i+1] = L[i] + L[i-1]
23
24       Each Lucas number falls in between successive Fibonaccis, and in fact
25       the distance is a further Fibonacci,
26
27           F[i+1] < L[i] < F[i+2]
28
29           L[i] = F[i+1] + F[i-1]      # above F[i+1]
30           L[i] = F[i+2] - F[i-2]      # below F[i+2]
31
32   Start
33       Optional "i_start => $i" can start the sequence from somewhere other
34       than the default i=1.  For example starting at i=0 gives value 2 at
35       i=0,
36
37           i_start => 0
38           2, 1, 3, 4, 7, 11, 18, ...
39

FUNCTIONS

41       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
42       classes.
43
44       "$seq = Math::NumSeq::LucasNumbers->new ()"
45       "$seq = Math::NumSeq::LucasNumbers->new (i_start => $i)"
46           Create and return a new sequence object.
47
48   Iterating
49       "($i, $value) = $seq->next()"
50           Return the next index and value in the sequence.
51
52           When $value exceeds the range of a Perl unsigned integer the return
53           is a "Math::BigInt" to preserve precision.
54
55       "$seq->seek_to_i($i)"
56           Move the current sequence position to $i.  The next call to
57           "next()" will return $i and corresponding value.
58
59   Random Access
60       "$value = $seq->ith($i)"
61           Return the $i'th Lucas number.
62
63       "$bool = $seq->pred($value)"
64           Return true if $value is a Lucas number.
65
66       "$i = $seq->value_to_i_estimate($value)"
67           Return an estimate of the i corresponding to $value.  See "Value to
68           i Estimate" below.
69

FORMULAS

71   Ith Pair
72       A pair of Lucas numbers L[k], L[k+1] can be calculated together by a
73       powering algorithm with two squares per doubling,
74
75           L[2k]   = L[k]^2   - 2*(-1)^k
76           L[2k+2] = L[k+1]^2 + 2*(-1)^k
77
78           L[2k+1] = L[2k+2] - L[2k]
79
80           if bit==0 then take L[2k], L[2k+1]
81           if bit==1 then take L[2k+1], L[2k+2]
82
83       The 2*(-1)^k terms mean adding or subtracting 2 according to k odd or
84       even.  This means add or subtract according to the previous bit
85       handled.
86
87   Ith
88       For any trailing zero bits of i the final doublings can be done by
89       L[2k] alone which is one square per 0-bit.
90
91           ith_pair(odd part of i) to get L[2k+1]  (ignore L[2k+2])
92           loop L[2k] = L[k]^2 - 2*(-1)^k for each trailing 0-bit of i
93
94   Value to i Estimate
95       L[i] increases as a power of phi, the golden ratio.  The exact value is
96
97           L[i] = phi^i + beta^i    # exactly
98
99           phi = (1+sqrt(5))/2 = 1.618
100           beta = -1/phi = -0.618
101
102       Since abs(beta)<1 the beta^i term quickly becomes small.  So taking a
103       log (natural logarithm) to get i,
104
105           log(L[i]) ~= i*log(phi)
106           i ~= log(L[i]) * 1/log(phi)
107
108       Or the same using log base 2 which can be estimated from the highest
109       bit position of a bignum,
110
111           log2(L[i]) ~= i*log2(phi)
112           i ~= log2(L[i]) * 1/log2(phi)
113
114       This is very close to the Fibonacci formula (see "Value to i Estimate"
115       in Math::NumSeq::Fibonacci), being bigger by
116
117           Lestimate(value) - Festimate(value)
118             = log(value) / log(phi) - (log(value) + log(phi-beta)) / log(phi)
119             = -log(phi-beta) / log(phi)
120             = -1.67
121
122       On that basis it could even be close enough to take Lestimate =
123       Festimate-1, or vice-versa.
124
125   Ith Fibonacci and Lucas
126       It's also possible to calculate a Fibonacci F[k] and Lucas L[k]
127       together by a similar powering algorithm with two squares per doubling,
128       but a couple of extra factors,
129
130           F[2k] = (F[k]+L[k])^2/2 - 3*F[k]^2 - 2*(-1)^k
131           L[2k] =                   5*F[k]^2 + 2*(-1)^k
132
133           F[2k+1] =    ((F[k]+L[k])/2)^2 + F[k]^2
134           L[2k+1] = 5*(((F[k]+L[k])/2)^2 - F[k]^2) - 4*(-1)^k
135
136       Or the conversions between a pair of Fibonacci and Lucas are
137
138           F[k]   = ( - L[k] + 2*L[k+1])/5
139           F[k+1] = ( 2*L[k] +   L[k+1])/5   = (F[k] + L[k])/2
140
141           L[k]   =  - F[k] + 2*F[k+1]
142           L[k+1] =  2*F[k] +   F[k+1]       = (5*F[k] + L[k])/2
143

HOME PAGE

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

LICENSE

151       Copyright 2010, 2011, 2012, 2013, 2014 Kevin Ryde
152
153       Math-NumSeq is free software; you can redistribute it and/or modify it
154       under the terms of the GNU General Public License as published by the
155       Free Software Foundation; either version 3, or (at your option) any
156       later version.
157
158       Math-NumSeq is distributed in the hope that it will be useful, but
159       WITHOUT ANY WARRANTY; without even the implied warranty of
160       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
161       General Public License for more details.
162
163       You should have received a copy of the GNU General Public License along
164       with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.
165
166
167
168perl v5.28.0                      2014-06-29     Math::NumSeq::LucasNumbers(3)