OEIS A229580 mini challenge (RPL)

[Valentin Albillo]

.
Hi, Gerson:

(05-01-2018 06:47 AM)Gerson W. Barbosa Wrote:  Write an RPL program to compute the elements of OEIS sequence A229580, the shorter and faster the better.

Since you just changed the Subject to include RPN, I'm changing it again to include the HP-71B, I hope you won't mind. This is how I solved your challenge with my HP-71B:
The sequence is: 1,6,40,224,1152,5632,26624,122880,557056,...

1) I ran my LINREC program to find the recurrence (and see if it agrees with the one given in the OEIS page), ignoring the first term (1) as the OEIS page warns us that the recurrence doesn't apply to it:

>CAT
      LINREC BASIC 540 bytes
>RUN
      ? 6,40,224,1152

            2-term recurrence:

                  a(n) = 8*a(n-1)-16*a(n-2)

                        6,40,224,1152,5632,...

As can be seen, my program found the correct recurrence and for checking purposes it produced an additional term which fully agrees with the sequence.

2) Thus, the characteristic polynomial for this recurrence is

            a\(^2\)-8*a+16 = 0

which has a double root 4, so the explicit formula is of the form:

            a(n)=(k1+k2*n)*4\(^n\)

for some constants k1 and k2 which can be computed from the initial terms (or any two others) as follows:

            n=2      => (k1+2*k2)*16 = 6
            n=3      => (k1+3*k2)*64 = 40

and solving this trivial system we get

            k1=-1/8, k2 = 1/4

so the explicit formula is:

            if n=1 then a(1) = 1
                     else a(n) = (-1/8+1/4*n)*4\(^n\)  = (4*n-2)*4\(^{n-2}\)

which takes essentially zero time for any n, no matter how big.

3) Let's check it:

>FOR N=2 TO 18 @ N;(4*N-2)*4^(N-2) @ NEXT N

       2 6
       3 40
       4 224
       5 1152
       6 5632
       7 26624
       8 122880
       9 557056
      10 2490368
      11 11010048
      12 48234496
      13 209715200
      14 905969664
      15 3892314112
      16 16642998272
      17 70866960384
      18 300647710720

And, of course, the trivial HP-71B user-defined function would be:

      1 DEF FNA(N) = (4*N-2)*4^(N-2)

Regards.
V.
.