RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
|
06-30-2019, 08:41 PM
(This post was last modified: 06-30-2019 08:43 PM by Gerson W. Barbosa.)
Post: #1
|
|||
|
|||
RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
.
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 ... ... ... Write an RPL program that lists the elements in the central column of the triangle of primes above, starting from a(0) = 2 up to a(k). For example, 2 -> {2 5 17} 5 -> {2 5 17 41 73 127} 99 -> {2 5 17 41 73 ... ... 101323 103613} My checksum is # 7A67h. Have fun! |
|||
06-30-2019, 08:53 PM
Post: #2
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) | |||
06-30-2019, 09:10 PM
Post: #3
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
.
Hi, Gerson: (06-30-2019 08:41 PM)Gerson W. Barbosa Wrote: Write an RPL program that lists the elements in the central column of the triangle of primes above, starting from a(0) = 2 up to a(k). You need to define what k is supposed to be. Also, as this is (as usual) an RPL mini-challenge I won't enter my HP-71B solution, which is a short one-liner. Have a nice weekend. . All My Articles & other Materials here: Valentin Albillo's HP Collection |
|||
06-30-2019, 11:05 PM
Post: #4
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(06-30-2019 09:10 PM)Valentin Albillo Wrote: . Hello, Valentin, I hope the examples I have provided compensate for some lack of rigor from my part. “k” is the number of elements in the list minus 1. Yes, it can fit in one HP-71BASIC line if either NEXTPRIME() or PRIME() function is available. Of course, being this an RPL mini-chalenge, the size of your BASIC code won’t compare to equivalent RPL codes. However, considering optimized algorithms can possibly make for shorter RPL codes than we currently have, I think the submission of non-RPL programs might be helpful, so they’re always welcome. Best regards, Gerson. |
|||
06-30-2019, 11:57 PM
Post: #5
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
HP-42S implementation:
Code: 00 { 86-Byte Prgm } Thank you, Gerson! I always enjoy these challenges. |
|||
07-01-2019, 12:28 AM
Post: #6
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(06-30-2019 11:57 PM)Thomas Okken Wrote: HP-42S implementation: Wow! Only 86 bytes, 77 without LBL. Slightly less here, but NEXTPRIME is built into the HP-49/50g. Well done! |
|||
07-01-2019, 04:49 AM
Post: #7
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
wp34s version:
001 LBL A 002 INC X 003 # 001 004 # 000 005 STO T 006 X<>Y 007 NEXTP 008 X<>Y 009 DSE X 010 BACK 004 011 x<> T 012 INC X 013 INC X 014 X<>Y 015 PSE 10 016 X<>Y 017 DSE Z 018 BACK 013 019 X<>Y 020 END |
|||
07-01-2019, 12:25 PM
Post: #8
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
The 34S version is going to be difficult to beat. Eighteen steps without the initial LBL and the END. Everything is on the stack and no labels or extra registers needed.
For a moment there, I thought that steps 5 and 6 could be combined using the [<->] shuffle command. Alas, no. They need to be separate steps. I think steps 3 and 4 might possibly be contender for combining. Pauli |
|||
07-01-2019, 12:49 PM
(This post was last modified: 07-01-2019 01:05 PM by John Keith.)
Post: #9
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
My simplistic RPL solution. 83 bytes, checksum # EBAAh. Optimized for speed rather than size. An input of 9 takes 1.19 seconds on my HP 50. An input of 99 takes 397 seconds, or 6.98 seconds on EMU48. The HP Prime could solve this almost instantly as the Prime has the 'ithprime' function.
Code:
|
|||
07-01-2019, 01:44 PM
Post: #10
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(07-01-2019 12:25 PM)Paul Dale Wrote: The 34S version is going to be difficult to beat. Eighteen steps without the initial LBL and the END. Everything is on the stack and no labels or extra registers needed. Steps 3 and 4 can be replaced by CPX . |
|||
07-01-2019, 01:52 PM
Post: #11
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
Mine turned out to be very close to John's solution:
Code:
We are at 96 bytes for newRPL, can't beat the 50g with classic RPL in size (never will), but in speed is a different story... Runs the 99 case in 172 msec (second run), or 489 msec for the first run (which runs at 6 MHz for some time before the "turbo" kicks in). Runs the 150 case in 5.61 seconds (second run) and 5.98 sec for the first run, in this case the difference between the first/second run becomes a lot less relevant. |
|||
07-01-2019, 05:05 PM
Post: #12
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) | |||
07-01-2019, 05:20 PM
Post: #13
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(07-01-2019 05:05 PM)John Keith Wrote:(07-01-2019 01:52 PM)Claudio L. Wrote: ...speed is a different story... I do need a third one. My newer 50g (CNA2240GYB) is slightly slower than yours: 402.76 seconds for k=99. My program is a bit slower as well: 409.17 seconds. Code:
|
|||
07-01-2019, 09:45 PM
Post: #14
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(07-01-2019 05:20 PM)Gerson W. Barbosa Wrote: My newer 50g (CNA2240GYB) is slightly slower than yours: 402.76 seconds for k=99. My program is a bit slower as well: 409.17 seconds. Your program might be slower but sure it's more clever! I ran it in newRPL just for kicks: 108 bytes (had to make slight modifications for newRPL, won't comment here to avoid spoiling the answer to others). Your code runs 99 in 176 msec under newRPL. By the way, at 108 bytes you also take the title of newRPL Champion too. That's because I realized my solution does not work properly for an input of 0, so I'm disqualifying myself :-). I re-coded the challenge so it works properly but it grew up to 136 bytes (from 96 bytes), on the other hand it now does 99 in 134 msec. Code:
|
|||
07-01-2019, 11:13 PM
(This post was last modified: 07-01-2019 11:55 PM by Didier Lachieze.)
Post: #15
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(07-01-2019 04:49 AM)Gerson W. Barbosa Wrote: wp34s version: Your algorithm is great! Here is a slightly optimized version of the program (24 bytes), removing the unnecessary X<>Y instructions : 001 LBL A 002 c#001 003 <>XYZY 004 NEXTP 005 DSE T 006 BACK 002 007 INC Y 008 INC Y 009 PSE 10 010 DSL Z 011 BACK 008 012 END EDIT: further optimized by removing the initial INC X with the usage of DSL in step 11. |
|||
07-02-2019, 12:07 AM
(This post was last modified: 07-02-2019 12:14 AM by Gerson W. Barbosa.)
Post: #16
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(07-01-2019 11:13 PM)Didier Lachieze Wrote:(07-01-2019 04:49 AM)Gerson W. Barbosa Wrote: wp34s version: A slightly optimized version? I wonder what your heavily optimized one would look like! :-) Very nice! Indeed a masterpiece. Yes, I noticed there were too many X<>Y instructions. “Let me remove a few and it’ll be perfect”, I thought. Thank you very much for removing THEM ALL! :-) |
|||
07-02-2019, 12:40 AM
Post: #17
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
A work of art.
Pauli |
|||
07-02-2019, 02:21 PM
(This post was last modified: 07-02-2019 02:22 PM by DavidM.)
Post: #18
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
Interesting puzzle, interesting approaches!
Code:
|
|||
07-03-2019, 05:05 AM
Post: #19
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
A version using list processing with ListExt commands:
Code:
|
|||
07-03-2019, 08:00 PM
(This post was last modified: 07-03-2019 10:38 PM by Gerson W. Barbosa.)
Post: #20
|
|||
|
|||
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
Thank you all for your interest, comments and great contributions!
Here is my solution, as hidden elsewhere in this thread: « { } 1 0 DUP 5 ROLL START 1 OVER START UNROT NEXTPRIME ROT NEXT UNROT + LASTARG NIP ROT 2 + NEXT DROP2 » 73 bytes, 409.2391 seconds for k = 99 Algorithm: input k p := 1 q := 0 for i := 0 to k for j := 1 to q ; notice the loop is executed once, when q = 0 p := nextprime(p) next j print p q := q + 2 next i My initial goal was making it shorter than 100 bytes, as my previous program was 112 bytes longer, not to mention it was significantly slower, so I didn't try to optimize it any further. All of the pure RPN solutions submitted thus far are slightly faster and yet small enough in size, which is great. Author time (s, k=99) CK Size John Keith 402.9453 # 2F5h 83 Claudio L. 403.7325 # 4E5Eh 78 David M. 407.3202 # F924h 75 That's OEIS sequence A122566. |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: