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

[Claudio L.]

(07-03-2019 08:00 PM)Gerson W. Barbosa Wrote:  Thank you all for your interest, comments and great contributions!

Wait, wait!

I have 2 more... neither will be winners of anything, just different approaches to those presented before.

The first one is literal translation of the algorithm you just revealed, except 'q' counts with step 1 and NEXTPRIME is done in pairs:

Code:


«
  0 SWAP 2 0 ROT START
    SWAP OVER 0 PICK3
    START
      NEXTPRIME NEXTPRIME
    NEXT
    SWAP 1 + SWAP 
  NEXT
  DROP →LIST 
»

The second one is inspired by the OEIS website, where it shows the highest number is ithPrime(k^2+k+1), so we can just do NEXTPRIME k^2+k+1 times, but keeping (with DUP) just the ones we are interested in, that have an index 'i' of the form 'i^2+i+1':

Code:


«
  0 → 
    i « 1 + DUPDUP *
    + 2 1 ROT
    FOR 'K'
      IF i DUPDUP * +
      1 + K == THEN
        DUP 1 'i' STO+
      END
      NEXTPRIME 
    NEXT
    DROP i →LIST 
  »
»

[Gerson W. Barbosa]

(07-03-2019 10:33 PM)Claudio L. Wrote:  

(07-03-2019 08:00 PM)Gerson W. Barbosa Wrote:  Thank you all for your interest, comments and great contributions!

Wait, wait!

I have 2 more... neither will be winners of anything, just different approaches to those presented before.

The first one is literal translation of the algorithm you just revealed, except 'q' counts with step 1 and NEXTPRIME is done in pairs:

Code:


«
  0 SWAP 2 0 ROT START
    SWAP OVER 0 PICK3
    START
      NEXTPRIME NEXTPRIME
    NEXT
    SWAP 1 + SWAP 
  NEXT
  DROP →LIST 
»

Looks like we should update the Hall of Fame:

Claudio L: 405.2275 s, 68.5 bytes

I am glad the 70-byte barrier has been broken. Let’s see how far this goes :-)

[DavidM]

(07-04-2019 03:17 AM)Gerson W. Barbosa Wrote:  ... Let’s see how far this goes :-)

Be careful what you ask for!

Inspired by Gerson's program and Claudio's optimizations, I thought I'd try to transcode that version into SysRPL to see how it might turn out.

This version does accommodate both exact and approximate numbers for input. Due to the looping being based on BINTs, it has a maximum input value of 1048575. You are far more patient than me if you want to try values higher than a few hundred, even on emulated systems!

Several command sequences in this algorithm align nicely with SysRPL "combo" commands (combinations of several commands into one opcode), so the program size decreased accordingly to 52 bytes. The SysRPL loop code executes slightly faster than the UserRPL equivalent, and the final runtime shows that as well: about 360 seconds on my 50g for an input of 99.

To try this out on a 50g, make sure you have a suitable extable installed (this one should do), then execute:
256 ATTACH

This will make the built-in development tools available.

Next, place the following code on the stack as a string:

Code:

!NO CODE
!ASM
   DC Z2_ 273C2
!RPL
::
   CKREAL COERCE
   BINT0
   Z2_
   ROT#1+ ZERO_DO
      SWAP2DUP
      #1+ ZERO_DO
         FPTR2 ^Prime+
         FPTR2 ^Prime+
      LOOP
      SWAP#1+SWAP
   LOOP
   DROP
   {}N
;
@

To compile the above code into executable form, simply execute ASM. This will create the program object on the stack, which can then be saved to a global variable or executed directly from the stack with EVAL (don't forget the needed argument, which should be added to the stack prior to execution).

Compiling the code does require the extable to be installed first, of course, but the program itself uses only built-in commands.

Thanks for the mini-challenge, Gerson!

[Claudio L.]

(07-04-2019 08:21 PM)DavidM Wrote:  Thanks for the mini-challenge, Gerson!

Yes, thanks for these minichallenges, they seem simple and shallow at first, but there's always one more thing to tweak, one more algorithm to explore. Things like this keep this forum interesting and fun, and our brains lose some of the rust accumulated over the years.
Thanks again.

[Paul Dale]

The 34S solution is under half the size
I knew we included all those obscure and seemingly duplicated commands for a reason...


Pauli