OEIS A229580 mini challenge (RPL)

[Gerson W. Barbosa]

Write an RPL program to compute the elements of OEIS sequence A229580, the shorter and faster the better.

Examples:

1 -> 1

18 -> 300647710720

30 -> 8502796096475496448 (0.0619 on the 50g in exact mode)

Currently 37.5 bytes.

[Joe Horn]

Oh dear... 81 bytes, same answers for 1 and 30, but 0.0989_s for 30. I used a local variable and an algebraic expression. I suspect that you wrote it using only the stack. I gotta see that.

EDIT: Rewrote using just the stack, but it only shrank to 50 bytes, and takes 0.0792_s for an input of 30. Hmmmm.....

EDIT 2: Down to 47.5 bytes, 0.0778_s for an input of 30. You are keeping me up all night!

[Gerson W. Barbosa]

(05-01-2018 07:48 AM)Joe Horn Wrote:  Oh dear... 81 bytes, same answers for 1 and 30, but 0.0989_s for 30.

Great! This means you’ve found a much better formula than the one at OEIS. That’s what really matters here.

(05-01-2018 07:48 AM)Joe Horn Wrote:  EDIT: Rewrote using just the stack, but it only shrank to 50 bytes, and takes 0.0792_s for an input of 30. Hmmmm.....

EDIT 2: Down to 47.5 bytes, 0.0778_s for an input of 30.

52.5 bytes, 0.0980 s; 50 bytes, 0,1000 s. My first and second attempts, respectively. Times change slightly at each run.

(05-01-2018 07:48 AM)Joe Horn Wrote:  You are keeping me up all night!

That was not my intention, sorry! It was almost 4:00 AM here when I posted. Perhaps I should’ve waited a few hours more, but then again someone else would lose sleep over this little problem.
I wish you all have a nice Sunday!

Gerson.

[Gerald H]

For n > 2 on

a(n) = 4*(a(n-1)) + 4^(n-1)

but I find neither a small programme nor one as fast as yours.

[Joe Horn]

(05-01-2018 11:51 AM)Gerald H Wrote:  For n > 2 on
a(n) = 4*(a(n-1)) + 4^(n-1)

SPOILER ALERT. A non-recursive, direct function of n exists. Examining the sequence's prime factors reveals it.

[Gerald H]

Thank you, Joe.

Programme now has

size 37.5 Bytes

CkSum F06B h

[Gerald H]

But same size programme with

CkSum 3095 h

is faster.

[Gerson W. Barbosa]

(05-01-2018 12:19 PM)Gerald H Wrote:  But same size programme with

CkSum 3095 h

is faster.

How faster? My checksum is # 296Fh. I’m using LASTARG, but I am not sure whether it slows things down or not.

[Gerson W. Barbosa]

(05-01-2018 11:56 AM)Joe Horn Wrote:  

(05-01-2018 11:51 AM)Gerald H Wrote:  For n > 2 on
a(n) = 4*(a(n-1)) + 4^(n-1)

SPOILER ALERT. A non-recursive, direct function of n exists. Examining the sequence's prime factors reveals it.

Thanks, Joe! I should have given this hint earlier.

[StephenG1CMZ]

(05-01-2018 12:19 PM)Gerald H Wrote:  But same size programme with

CkSum 3095 h

is faster.

I guess you mean because the code producing that checksum is different...
But it had me wondering whether a program can access its own checksum and use it to save a few bytes/cycles?

I wonder if that has ever been useful?

[Gerson W. Barbosa]

Changing target. Eight steps on the wp34s (not counting LBL and END).

[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.
.

[Gerson W. Barbosa]

(05-01-2018 05:22 PM)Gerson W. Barbosa Wrote:  Eight steps on the wp34s (not counting LBL and END).

Down to 7 steps now. I just ran my RPL program with argument 'n', then EXPAND, an obvious simplification and... voilà! :-)

[Gerson W. Barbosa]

Hello, Valentin,

Thank you very much for you valuable contribution!

(05-01-2018 06:07 PM)Valentin Albillo Wrote:  .
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.

Of course not! This should have been opened to other calculators in the first place, my bad. As I said, more important than the resulting optimization was the better formula the participants would eventually come up with. My first attempt using your formula gives me 40 bytes on the hp 50g, but others may improve on that.

By factoring the first few elements, I have obtained an = (2n - 1)*2^(2n - 3), which is probably the same formula Joe has come up with, since he used the same method I did. Both formulas are of course equivalent and hopefully will make for even better optimizations on the original target.

Best regards,

Gerson.

[John Keith]

Mine is 40 bytes, checksum FEB4h. Time for A(30) is .0527 seconds.

[Gerald H]

(05-01-2018 07:40 PM)Gerson W. Barbosa Wrote:  Hello, Valentin,

Thank you very much for you valuable contribution!

(05-01-2018 06:07 PM)Valentin Albillo Wrote:  .
Hi, Gerson:


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.

Of course not! This should have been opened to other calculators in the first place, my bad. As I said, more important than the resulting optimization was the better formula the participants would eventually come up with. My first attempt using your formula gives me 40 bytes on the hp 50g, but others may improve on that.

By factoring the first few elements, I have obtained an = (2n - 1)*2^(2n - 3), which is probably the same formula Joe has come up with, since he used the same method I did. Both formulas are of course equivalent and hopefully will make for even better optimizations on the original target.

Best regards,

Gerson.

Your formula returns

1/2

for input

1

[Gerson W. Barbosa]

(05-01-2018 08:56 PM)Gerald H Wrote:  

(05-01-2018 07:40 PM)Gerson W. Barbosa Wrote:  Hello, Valentin,

Thank you very much for you valuable contribution!


Of course not! This should have been opened to other calculators in the first place, my bad. As I said, more important than the resulting optimization was the better formula the participants would eventually come up with. My first attempt using your formula gives me 40 bytes on the hp 50g, but others may improve on that.

By factoring the first few elements, I have obtained an = (2n - 1)*2^(2n - 3), which is probably the same formula Joe has come up with, since he used the same method I did. Both formulas are of course equivalent and hopefully will make for even better optimizations on the original target.

Best regards,

Gerson.

Your formula returns

1/2

for input

1

The first element in the sequence is anomalous. The formula is valid for n > 1, but you are right, I’ve forgotten to mention that. Fortunately a simple built-in function, available on the wp34s as well, will turn that fraction into the right integer while keeping all the remaining elements unchanged, as we are aware of.

[Joe Horn]

(05-01-2018 07:40 PM)Gerson W. Barbosa Wrote:  By factoring the first few elements, I have obtained an = (2n - 1)*2^(2n - 3), which is probably the same formula Joe has come up with, since he used the same method I did.

Correct. My final attempt (before going to bed) was:

<< DUP + 1 - 2 DUP2 - ^ * CEIL >>

BYTES: 35.0 #D66Dh
0.057_s for an input of 30 (on my 50g).

[Gerson W. Barbosa]

(05-01-2018 11:40 AM)Gerson W. Barbosa Wrote:  I wish you all have a nice Sunday!

Because of the 1st of May holiday, today it’s been feeling like Sunday to me since morning. Well, a nice holiday, a nice working week and a nice weekend then :-)

[Gerson W. Barbosa]

(05-01-2018 11:05 PM)Joe Horn Wrote:  

(05-01-2018 07:40 PM)Gerson W. Barbosa Wrote:  By factoring the first few elements, I have obtained an = (2n - 1)*2^(2n - 3), which is probably the same formula Joe has come up with, since he used the same method I did.

Correct. My final attempt (before going to bed) was:

<< DUP + 1 - 2 DUP2 - ^ * CEIL >>

BYTES: 35.0 #D66Dh
0.057_s for an input of 30 (on my 50g).

Very nice!

Here is my (now) lengthy one:

« DUP + 3 - 2 SWAP ^ LASTARG + * CEIL
»

37.5 bytes, 0.062 s, #296Fh

Glad the 37.5-byte barrier has been broken!