An iteration produces all the prime numbers

[Valentin Albillo]

      
Hi, EdS2:

(02-17-2021 10:00 AM)EdS2 Wrote:  Thanks for explaining!

You're welcome.

Quote:Excellent - thanks again.

You're welcome again.

Re the HP-71B 2-liner I posted above, which instantly computes the constant as given in your linked article (13 decimal places, 2.920050977316), it's quite possible to convert it to a multiprecision program which would compute the constant to the digits shown in this Wikipedia article:

      Formula for primes

where the constant is given as 2.920050977316134712092562917112019. However, for variety's sake let's use instead SwissMicros awesome DM42 calc, which can run HP-42S RPN programs and supports 34-digit precision instead of just 12-digit as both the HP-42S and the HP-71B do.

Thus, I wrote the following 50-step, 86-byte RPN program for the DM42 to perform the feat:

   LBL "CCN"    1           5           X>Y?
   SIZE 30      -          STO 00       GTO 01
    -1         RCL/ 02     LBL 01       RCL 04
   STO 03      RCL+ 03     RCL IND 00   STO IND 01
    6          ENTER       RCL 04       ISG 01
   STO 01      X<> 03      RCL/ ST Y    LBL 03
    2          X=Y?        FP           GTO 02
   STO 02      GTO 04      X=0?         LBL 04
    3          RCL ST Z    GTO 00        2
   STO 04      STOx 02     Rv            +
   STO 05      LBL 00      LASTX        END
   LBL 02       2          X>Y?
   RCL ST X    STO+ 04     ISG 00

Let's execute it:

   XEQ "CCN" -> 2.92005097732
      [SHOW] -> 2.920050977316134712092562917112019

which is computed instantly and exactly matches the Wikipedia's value.

As the DM42 doesn't have any number-theoretic functions in its instruction set (like PRIM, FPRIM, GCD, etc.), my program above generates and uses the prime numbers on the fly. 101 is the last prime needed.

BTW, the program is a quick job, also written on the fly, so it's not optimized to any extent as it already runs instantly and takes little program memory. It can be optimized by improving stack use but I see little need, be my guest if you want to try.  

Regards.
V.