[VA] SRC #013 - Pi Day 2023 Special

[2old2randr]

Hi Valentin,

Edit: I have corrected the formatting (thanks, Valentin for the explanation) and added a column for run times using the (much faster) Sys RPL version of the Möbius function written by Gerald H. This is more than twice as fast as the HP-71B times you have listed.

I attempted this because it is simpler than your usual problems and you were complaining about the lack of RPL solutions for your last challenge Using a brute force solution on a physical HP 50g, I get decent run times (13' 20'' for 33 million [5' 21" for the Sys RPL version]) as shown below. Although I am not sure if the 50g qualifies as a vintage calculator, of course.

                                           Runtime (seconds)
       Number        Count  Approximation  User RPL  Sys RPL
-------------  -----------  -------------  --------  -------
           10            7  2.92770021885      0.44     0.29
       12,345        7,503  3.14198204634     15.52     6.02
      100,000       60,794  3.14155932716     45.08    16.93
      567,890      345,237  3.14158683822    110.40    40.39
    1,000,000      607,926  3.14159550063    147.82    54.99
   10,000,000    6,079,291  3.14158749068    469.88   139.11
   25,000,000   15,198,180  3.14159239999    692.35   277.43
   33,000,000   20,061,593  3.14159276017    800.43   321.11
  100,000,000   60,792,694  3.14159307180       n/a   448.08
1,000,000,000  607,927,124  3.14159259637       n/a  1453.24

I used the equation S(n) = Sum(i from 1 to sqrt(n); mu(i) * int(n / i * i)) to get the count of square free numbers less than or equal to 'n'. In the equation, mu is the Möbius function.

The code (VA is the problem solution, MOB is the Möbius function):
VA
« → n
  « 0. 1. n √ IP
    FOR i
      i MOB n i SQ / IP * +
    NEXT
    DUP 6. n * SWAP / √
  »
»

MOB (User RPL version)
« R→I
  IF DUP 1 > THEN
    FACTOR
    IF DUP TYPE 9. SAME THEN
      DUP →STR
      IF "^" POS THEN
        DROP 0
      ELSE
        SIZE 1. + 2. / 1 SWAP 2. MOD { NEG } IFT
      END
    ELSE
      DROP -1
    END
  END
»

MOB (System RPL version)
::
  CK1&Dispatch
  # FF
  ::
    {
      ROTDROPSWAP
      %1
      EQUALcase
      FPTR2 ^RNEGext
      FPTR2 ^DROPZ0
    }
    1LAMBIND
    ::
      FPTR2 ^ZAbs
      FPTR2 ^DupQIsZero?
      caseSIZEERR
      FPTR2 ^DupZIsOne?
      ?SEMI
      FPTR2 ^MZSQFF
      #2/
      ZINT 1
      SWAP
      ZERO_DO
      1GETLAM
      COMPEVAL
      LOOP
    ;
    ABND
  ;
;

Sudhir