Post Reply 
OEIS A229580 mini challenge (RPL)
05-01-2018, 06:47 AM
Post: #1
OEIS A229580 mini challenge (RPL)
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.
Find all posts by this user
Quote this message in a reply
05-01-2018, 07:48 AM (This post was last modified: 05-01-2018 09:34 AM by Joe Horn.)
Post: #2
RE: OEIS A229580 mini challenge (RPL)
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. Smile

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! Angry

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
05-01-2018, 11:40 AM (This post was last modified: 05-01-2018 11:41 AM by Gerson W. Barbosa.)
Post: #3
RE: OEIS A229580 mini challenge (RPL)
(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! Angry

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.
Find all posts by this user
Quote this message in a reply
05-01-2018, 11:51 AM
Post: #4
RE: OEIS A229580 mini challenge (RPL)
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.
Find all posts by this user
Quote this message in a reply
05-01-2018, 11:56 AM
Post: #5
RE: OEIS A229580 mini challenge (RPL)
(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.

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
05-01-2018, 12:11 PM
Post: #6
RE: OEIS A229580 mini challenge (RPL)
Thank you, Joe.

Programme now has

size 37.5 Bytes

CkSum F06B h
Find all posts by this user
Quote this message in a reply
05-01-2018, 12:19 PM
Post: #7
RE: OEIS A229580 mini challenge (RPL)
But same size programme with

CkSum 3095 h

is faster.
Find all posts by this user
Quote this message in a reply
05-01-2018, 12:30 PM (This post was last modified: 05-01-2018 12:31 PM by Gerson W. Barbosa.)
Post: #8
RE: OEIS A229580 mini challenge (RPL)
(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.
Find all posts by this user
Quote this message in a reply
05-01-2018, 12:33 PM
Post: #9
RE: OEIS A229580 mini challenge (RPL)
(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.
Find all posts by this user
Quote this message in a reply
05-01-2018, 02:10 PM
Post: #10
RE: OEIS A229580 mini challenge (RPL)
(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?

Stephen Lewkowicz (G1CMZ)
https://my.numworks.com/python/steveg1cmz
Visit this user's website Find all posts by this user
Quote this message in a reply
05-01-2018, 05:22 PM (This post was last modified: 05-01-2018 05:25 PM by Gerson W. Barbosa.)
Post: #11
RE: OEIS A229580 mini challenge (RPL & RPN)
Changing target. Eight steps on the wp34s (not counting LBL and END).
Find all posts by this user
Quote this message in a reply
05-01-2018, 06:07 PM
Post: #12
RE: OEIS A229580 mini challenge (RPL and RPN *and* HP-71B)
.
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.
.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
Visit this user's website Find all posts by this user
Quote this message in a reply
05-01-2018, 07:05 PM
Post: #13
RE: OEIS A229580 mini challenge (RPL)
(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à! :-)
Find all posts by this user
Quote this message in a reply
05-01-2018, 07:40 PM (This post was last modified: 05-01-2018 07:43 PM by Gerson W. Barbosa.)
Post: #14
RE: OEIS A229580 mini challenge (RPL)
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.
Find all posts by this user
Quote this message in a reply
05-01-2018, 08:18 PM
Post: #15
RE: OEIS A229580 mini challenge (RPL)
Mine is 40 bytes, checksum FEB4h. Time for A(30) is .0527 seconds.
Find all posts by this user
Quote this message in a reply
05-01-2018, 08:56 PM
Post: #16
RE: OEIS A229580 mini challenge (RPL)
(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
Find all posts by this user
Quote this message in a reply
05-01-2018, 09:12 PM (This post was last modified: 05-01-2018 09:14 PM by Gerson W. Barbosa.)
Post: #17
RE: OEIS A229580 mini challenge (RPL)
(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.
Find all posts by this user
Quote this message in a reply
05-01-2018, 11:05 PM
Post: #18
RE: OEIS A229580 mini challenge (RPL)
(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).

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
05-01-2018, 11:08 PM
Post: #19
RE: OEIS A229580 mini challenge (RPL)
(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 :-)
Find all posts by this user
Quote this message in a reply
05-01-2018, 11:21 PM
Post: #20
RE: OEIS A229580 mini challenge (RPL)
(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!
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 4 Guest(s)