[seqfan] Re: A1595 mentioned in Medium article

[Alonso Del Arte]

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>