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.
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!
(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.
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.
(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.
Thank you, Joe.
Programme now has
size 37.5 Bytes
CkSum F06B h
But same size programme with
CkSum 3095 h
is faster.
(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.
(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.
(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?
Changing target. Eight steps on the wp34s (not counting LBL and END).
.
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 a
n 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.
.
(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à! :-)
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.
Mine is 40 bytes, checksum FEB4h. Time for A(30) is .0527 seconds.
(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.
(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).
(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 :-)
(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!