[seqfan] Re: A1595 mentioned in Medium article
Marc LeBrun
mlb at well.com
Mon Nov 9 21:47:28 CET 2020
It's sometimes useful to know that -- if you just want to get the N-th Fibonacci number without computing so many prior ones -- you can do much better: there's an approach where you can compute it with fixed storage in O(log2 N) operations, by computing the N-th power of a 2x2 matrix the same way numeric N-th powers are efficiently calculated:
To do this, let the identity matrix be
1 0
I :=
0 1
and also define a "multiplier" matrix
0 1
M :=
1 1
and then evaluate the following recursive procedure
matfibpow(N):=
if N==0
then return I
else
let F = matfibpow(floor(N/2))
set F = F * F
if N is odd
then return M * F
else return F
Finally, the N-th Fibonacci number will be the [2,1] element of the returned matrix.
Basically M encodes the the linear recurrence relationship. This approach can be applied for different initial values by modifying the final step, and for different recurrences by using a different multiplier matrix M.
> On Nov 9, 2020, at 10:22 AM, Alonso Del Arte <alonso.delarte at gmail.com> wrote:
>
> Thank you for finding A1610, David. I think I made a mistake when I tried
> to calculate that sequence, so it didn't matter if I omitted the initial
> terms. I decided I did not actually need the sequence for the article, so I
> set it aside. Now that I've had time to sleep on it, I've verified that
> A1610 with a 1 joined at the beginning is the sequence I was looking for.
>
> I should mention that I omitted one line from the article:
>
> public static BigInteger fibonacci(int n) {
> *counter++;*
> switch (n) {
> case 0: return BigInteger.ZERO;
> case 1: return BigInteger.ONE;
> default:
> return fibonacci(n - 2).add(fibonacci(n - 1));
> }
> }
>
> counter is a static variable that keeps track of how many times fibonacci()
> is called.
>
> Fred wrote that
>
>> There is nothing wrong with using the recursion directly for small
> values: simply compute each F(m) in turn for 2 <= m <= n ,
> requiring order n additions.
>
> I think that would be the case if the program remembers previously computed
> values.
>
> I remember a JavaScript whiteboarding meet-up where the moderator used a
> JavaScript implementation like the Java one quoted above. She used it to
> solve a Project Euler problem regarding even Fibonacci numbers. It was only
> necessary to go up to Fibonacci(50), if I recall correctly. It took
> something like a full minute to give a result. No one said anything.
>
> The simple act of saving previously computed values cuts down computation
> times: Fibonacci(50) in a millisecond or two instead of a full minute, and
> Fibonacci(100) in a few milliseconds instead of the theoretical 36 million
> years.
>
> Al
>
> On Mon, Nov 9, 2020 at 8:47 AM David Seal <david.j.seal at gwynmop.com> wrote:
>
>>> On 09/11/2020 05:34 Alonso Del Arte <alonso.delarte at gmail.com> wrote:
>>> ...
>>> I've been wondering about Fibonacci(*n*) − A001595(*n*). That's probably
>>> already in the OEIS, though maybe without signs. It does change sign,
>> right?
>>
>> From the definition of the Fibonacci numbers (A000045), which is "F(n) =
>> F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1", and from the definition of
>> A001595, which is "a(n) = a(n-1) + a(n-2) + 1, with a(0) = a(1) = 1", it is
>> very easy to prove by induction that a(n) >= F(n) for all n >= 0 (with
>> equality if and only if n = 1), and so the difference of the two sequences
>> does not change sign.
>>
>> Is there some subtlety about this question whose significance I'm missing?
>> - for instance, a meaning of "*n*"?
>>
>> A search for the first ten values of A001595(n) - A000045(n), which are
>> 1,0,2,3,6,10,17,28,46,75, says that it doesn't match any sequence in the
>> OEIS. However, leaving off its initial 1 finds A001610, described as "a(n)
>> = a(n-1) + a(n-2) + 1" - an incomplete definition, so I have submitted a
>> change to add "with a(0) = 0 and a(1) = 2". With that completed definition,
>> it's also very easy to prove by induction that A001610(n) = A001595(n+1) -
>> A000045(n+1) for all n >= 0.
>>
>> David
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
>
> --
> Alonso del Arte
> Author at SmashWords.com
> <https://www.smashwords.com/profile/view/AlonsoDelarte>
> Musician at ReverbNation.com <http://www.reverbnation.com/alonsodelarte>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list