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
 Gerson W. Barbosa Senior Member Posts: 1,507 Joined: Dec 2013
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
 Gerson W. Barbosa Senior Member Posts: 1,507 Joined: Dec 2013
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(06-30-2019 08:41 PM)Gerson W. Barbosa Wrote:  My checksum is # 7A67h.

Incidentally, the number of bytes belongs in the central column :-)
06-30-2019, 09:10 PM
Post: #3
 Valentin Albillo Senior Member Posts: 1,000 Joined: Feb 2015
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
 Gerson W. Barbosa Senior Member Posts: 1,507 Joined: Dec 2013
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(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.
06-30-2019, 11:57 PM
Post: #5
 Thomas Okken Senior Member Posts: 1,828 Joined: Feb 2014
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
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 X<Y? 28 GTO 02 29 LASTX 30 MOD 31 X=0? 32 GTO 00 33 GTO 01 34▸LBL 02 35 DSE 03 36 GTO 00 37 J+ 38 STOEL 39 2 40 STO+ 04 41 RCL 04 42 STO 03 43▸LBL 03 44 DSE 00 45 GTO 00 46 RCL "R" 47 CLV "R" 48 END

Thank you, Gerson! I always enjoy these challenges.
07-01-2019, 12:28 AM
Post: #6
 Gerson W. Barbosa Senior Member Posts: 1,507 Joined: Dec 2013
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(06-30-2019 11:57 PM)Thomas Okken Wrote:  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 X<Y? 28 GTO 02 29 LASTX 30 MOD 31 X=0? 32 GTO 00 33 GTO 01 34▸LBL 02 35 DSE 03 36 GTO 00 37 J+ 38 STOEL 39 2 40 STO+ 04 41 RCL 04 42 STO 03 43▸LBL 03 44 DSE 00 45 GTO 00 46 RCL "R" 47 CLV "R" 48 END

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
 Gerson W. Barbosa Senior Member Posts: 1,507 Joined: Dec 2013
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
 Paul Dale Senior Member Posts: 1,792 Joined: Dec 2013
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
 John Keith Senior Member Posts: 934 Joined: Dec 2013
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:
 *Spoiler alert* \<< I\->R \-> n   \<< 2 2. n 2. *     FOR k DUP 1. k       START NEXTPRIME       NEXT 2.     STEP n 1. + \->LIST   \>> \>>
07-01-2019, 01:44 PM
Post: #10
 Didier Lachieze Senior Member Posts: 1,576 Joined: Dec 2013
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.

[...]

I think steps 3 and 4 might possibly be contender for combining.

Steps 3 and 4 can be replaced by CPX .
07-01-2019, 01:52 PM
Post: #11
 Claudio L. Senior Member Posts: 1,871 Joined: Dec 2013
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
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.
07-01-2019, 05:05 PM
Post: #12
 John Keith Senior Member Posts: 934 Joined: Dec 2013
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(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...
07-01-2019, 05:20 PM
Post: #13
 Gerson W. Barbosa Senior Member Posts: 1,507 Joined: Dec 2013
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...
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 »
07-01-2019, 09:45 PM
Post: #14
 Claudio L. Senior Member Posts: 1,871 Joined: Dec 2013
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:
 **** 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.
07-01-2019, 11:13 PM (This post was last modified: 07-01-2019 11:55 PM by Didier Lachieze.)
Post: #15
 Didier Lachieze Senior Member Posts: 1,576 Joined: Dec 2013
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
(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.
07-02-2019, 12:07 AM (This post was last modified: 07-02-2019 12:14 AM by Gerson W. Barbosa.)
Post: #16
 Gerson W. Barbosa Senior Member Posts: 1,507 Joined: Dec 2013
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:

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! :-)
07-02-2019, 12:40 AM
Post: #17
 Paul Dale Senior Member Posts: 1,792 Joined: Dec 2013
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
 DavidM Senior Member Posts: 932 Joined: Dec 2013
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
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.
07-03-2019, 05:05 AM
Post: #19
 DavidM Senior Member Posts: 932 Joined: Dec 2013
RE: RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)
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!
07-03-2019, 08:00 PM (This post was last modified: 07-03-2019 10:38 PM by Gerson W. Barbosa.)
Post: #20
 Gerson W. Barbosa Senior Member Posts: 1,507 Joined: Dec 2013
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: