RPL mini-challenge - Triangle of Primes (HP-49G/G+,50g)

[Gerson W. Barbosa]

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

[Gerson W. Barbosa]

(06-30-2019 08:41 PM)Gerson W. Barbosa Wrote:  My checksum is # 7A67h.

Incidentally, the number of bytes belongs in the central column :-)

[Valentin Albillo]

.
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.
.

[Gerson W. Barbosa]

(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.

[Thomas Okken]

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.

[Gerson W. Barbosa]

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

[Gerson W. Barbosa]

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

[Paul Dale]

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

[John Keith]

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
  \>>
\>>

[Didier Lachieze]

(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 .

[Claudio L.]

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.

[John Keith]

(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...

[Gerson W. Barbosa]

(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
»

[Claudio L.]

(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.

[Didier Lachieze]

(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.

[Gerson W. Barbosa]

(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! :-)

[Paul Dale]

A work of art.


Pauli

[DavidM]

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.

[DavidM]

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!

[Gerson W. Barbosa]

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.