[seqfan] Re: A1595 mentioned in Medium article

Mon Nov 9 22:35:08 CET 2020

Marc,  That's the classic method, of course, but maybe it is worth creating
a text file containing it that we can add to A45.

Is what you sent OK, or do you want to polish it up for posterity?

Send me the final version, and I'll add it to A45.

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com

On Mon, Nov 9, 2020 at 3:47 PM Marc LeBrun <mlb at well.com> wrote:

> 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/
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>