RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) (/thread-13213.html) Pages: 1 2 RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Gerson W. Barbosa - 06-30-2019 08:41 PM .                 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! RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Gerson W. Barbosa - 06-30-2019 08:53 PM (06-30-2019 08:41 PM)Gerson W. Barbosa Wrote:  My checksum is # 7A67h. Incidentally, the number of bytes belongs in the central column :-) RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Valentin Albillo - 06-30-2019 09:10 PM . 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. . RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Gerson W. Barbosa - 06-30-2019 11:05 PM (06-30-2019 09:10 PM)Valentin Albillo Wrote:  . 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. 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. RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Thomas Okken - 06-30-2019 11:57 PM HP-42S implementation: Code: ```00 { 86-Byte Prgm } 01▸LBL "PRCOL" 02 STO 00 03 1 04 STO+ 00 05 STO 01 06 ENTER 07 NEWMAT 08 STO "R" 09 INDEX "R" 10 2 11 STOEL 12 GROW 13 STO 03 14 STO 04 15 GTO 03 16▸LBL 00 17 2 18 STO+ 01 19 1 20 STO 02 21▸LBL 01 22 2 23 STO+ 02 24 RCL 02 25 X↑2 26 RCL 01 27 XY 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 RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Paul Dale - 07-01-2019 12:25 PM 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 RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - John Keith - 07-01-2019 12:49 PM 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: ``` *Spoiler alert* \<< I\->R \-> n   \<< 2 2. n 2. *     FOR k DUP 1. k       START NEXTPRIME       NEXT 2.     STEP n 1. + \->LIST   \>> \>>``` RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Didier Lachieze - 07-01-2019 01:44 PM (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. [...] I think steps 3 and 4 might possibly be contender for combining. Steps 3 and 4 can be replaced by CPX . RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Claudio L. - 07-01-2019 01:52 PM Mine turned out to be very close to John's solution: Code: ``` *** Anti-spoil (scroll down to see) *** (classic RPL version - 108 bytes in newRPL) «   →      M « 2 1 M FOR 'K' DUP 1 K 2 * START         NEXTPRIME        NEXT     NEXT     M 1 + →LIST    » » (newRPL dialect - 96 bytes ) «   'M' LSTO 2 1 M FOR 'K' DUP 1 K 2 * START       NEXTPRIME      NEXT   NEXT   M 1 + →LIST  »``` 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. RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - John Keith - 07-01-2019 05:05 PM (07-01-2019 01:52 PM)Claudio L. Wrote:  ...speed is a different story... Runs the 99 case in 172 msec ... Gee, only aboutr 2300* faster! I really need another HP 50... RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Gerson W. Barbosa - 07-01-2019 05:20 PM (07-01-2019 05:05 PM)John Keith Wrote:   (07-01-2019 01:52 PM)Claudio L. Wrote:  ...speed is a different story... Runs the 99 case in 172 msec ... Gee, only aboutr 2300* faster! I really need another HP 50... 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: ``` # 7A67h 73 bytes « { } 1 0 DUP 5 ROLL   START 1 OVER     START UNROT NEXTPRIME ROT     NEXT UNROT + LASTARG NIP ROT 2 +   NEXT DROP2 »``` RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Claudio L. - 07-01-2019 09:45 PM (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: ``` **** Anti - Spoiler **** Here's my rework that meets the original requirements: «   2 * 'M' LSTO 2 DUP 'K'   LSTO WHILE K M ≤ REPEAT     DUP 1 K START       NEXTPRIME      NEXT     K 2 + 'K' STO    END   M 2 / 1 + →LIST  » And this is Gerson's code ported to newRPL: «   { } 1 0 DUP 5 ROLL START     1 OVER START       UNROT NEXTPRIME       ROT      NEXT     UNROT DUP UNROT ADD     SWAP ROT 2 +    NEXT   DROP2  » Here " + LASTARG NIP" was replaced with "DUP UNROT ADD SWAP", because newRPL does not support LASTARG, also + and ADD have swapped their functionality. It adds 4 bytes (1 command) in size to his original solution.``` RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Didier Lachieze - 07-01-2019 11:13 PM (07-01-2019 04:49 AM)Gerson W. Barbosa Wrote:  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 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. RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Gerson W. Barbosa - 07-02-2019 12:07 AM (07-01-2019 11:13 PM)Didier Lachieze Wrote:   (07-01-2019 04:49 AM)Gerson W. Barbosa Wrote:  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 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. 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! :-) RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Paul Dale - 07-02-2019 12:40 AM A work of art. Pauli RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - DavidM - 07-02-2019 02:21 PM Interesting puzzle, interesting approaches! Code: ``` Spoiler spoiler... \<<    0.    { DUP 1. n DUP + START NEXTPRIME NEXT }    'n'    PICK3    5. ROLL    1.    SEQ    NIP \>> The SEQ command actually builds a UserRPL FOR loop behind the  scenes. So I'm guessing its performance should be about the same  as a FOR loop approach (perhaps slightly slower for the overhead  to build the loop).  I'll also experiment with some list-based code for this. The  memory requirements would go up (both for the code and run-time  needs), but it may perform a little better.``` RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - DavidM - 07-03-2019 05:05 AM A version using list processing with ListExt commands: Code: ``` Unspoiled... \<<    2. DUP ROT LASEQ    0. NEXTPRIME SWAP    IF       DUP SIZE    THEN       1.       \<<          OVER          { NEXTPRIME }          ROT LMRPT          EVAL       \>>       DOSUBS    END    + \>> This one weighs in at 97.5 bytes, and finishes an input of  99 in about 383 seconds on my 50g. Two commands from the  ListExt library are used: LASEQ and LMRPT. LASEQ is used  to generate a list of even numbers from { 2..n }, where  the total count of numbers is the input parameter k. In  the case of an input of 99, LASEQ generates the list { 2.  4. 6. 8. ... 198. } in about 43 milliseconds.  LMRPT is used to replicate NEXTPRIME in a list a given  number of times (in this case each of the above even  numbers). So given { NEXTPRIME } and 4 as arguments, LMRPT  creates this list: { NEXTPRIME NEXTPRIME NEXTPRIME  NEXTPRIME }. That result is then executed on a copy of the  last found prime to generate the next one.  Ultimately, all of these RPL programs are at the mercy of  the NEXTPRIME command, which I believe consumes the  majority of processing time. This version achieves a minor  speed advantage by reducing the overall looping overhead  as compared to other versions. It does this at the cost of  a large memory footprint at runtime, though. Using a  k-value of 99 means that a list of 198 NEXTPRIME commands  is created (and executed) for the final pass of the DOSUBS  loop. That list alone is over 2K (bytes) in size!``` RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g) - Gerson W. Barbosa - 07-03-2019 08:00 PM 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.