[seqfan] Re: A1595 mentioned in Medium article

[Marc LeBrun]

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/