[VA] SRC #013 - Pi Day 2023 Special

[Valentin Albillo]

  
Hi again !

I thought I was done with this thread for good but while converting it to a PDF document for uploading it to my HP site's HP Calculator Challenges section, I realized there was a bit of unfinished business which had eluded me so far.

Namely, I said in Post #15 the following, I quote:

"As for the Möbius function {μ(N) henceforth}, it's a very important number-theoretical function which is easily computed in various ways, like this simple HP-71B user-defined function FNM (which should be placed at the end of any program using it):  {requires the JPC ROM}

   1  DEF FNM(N) @ IF N=1 THEN FNM=1 @ END ELSE F=1
   2  D=PRIM(N) @ IF NOT D THEN FNM=(-1)^F ELSE IF MOD(N,D*D) THEN F=F+1 @ N=N/D @ GOTO 2

      >FOR N=96673 TO 96686 @ FNM(N); @ NEXT N @@  ►  1 1 0 0 0 0 0 0 1 1 1 0 -1 -1 [...]

[ ... Good and Churchhouse said ...] 'Thus the Möbius sequence contains arbitrarily long runs of zeros, but these long runs presumably occur extremely rarely.'

I showed above such a run of zeros from N = 96675 to 96680, six consecutive zeros in all. It would make for an interesting challenge to locate longer runs."

So, here I address this remaining sub-challenge by creating an HP-71B program to find the first values of N which are the start of a run of 1, 2, 3, ..., consecutive zeros of μ(N). Specifically, this 169-byte 4-liner finds them up to a given maximum N very quickly:   {requires the JPC ROM}

1  DESTROY ALL @ INPUT N @ SETTIME 0 @ INTEGER M(N) @ P=2 @ WHILE P<=N @ S=P*P
2  FOR K=S TO N STEP S @ M(K)=1 @ NEXT K @ P=FPRIM(P+1) @ END WHILE @ Z=0 @ U=0
3  FOR K=1 TO N @ IF M(K) THEN Z=Z+1 ELSE IF Z>U THEN U=Z @ DISP U;K-Z @ Z=0 ELSE Z=0
4  NEXT K @ DISP "OK";TIME

●  Lines 1-2 perform the initialization and identify the zeros of μ(N), while line 3 contains all the logic to locate the start of the first run of 1, 2, 3, ..., consecutive zeros.

Let's find the first initial N for L = 1, 2, 3, ..., consecutive zeros for N up to 25,000 (requires ~ 75 Kb of RAM):

>RUN ->  ? 25000

L    Initial N
----------------
1          4
2          8
3         48
4        242
5        844
6      22020

OK timing (go71b: 10.60", Emu71/Win: 1.39", physical HP-71B: 22' 37")

This means that e.g. for the case L = 5 we have that μ(844), μ(845), μ(846), μ(847) and μ(848) are all zero, thus the first run of 5 consecutive zeros of μ(N) starts at N = 844. This also means that all five numbers in the run are divisible by some square, namely:

844 = 2² x 211;  845 = 5 x 13²;  846 = 2 x 3² x 47;  847 = 7 x 11²;  848 = 2⁴ x 53

Adding up more RAM and/or using boolean arrays and operations we'd be able to extend the search up to N = 1,200,000, say, which would allow us to find two additional runs of lengths 7 and 8, respectively:

7     217070
8    1092747

Longer runs would require much more complex programming and longer execution times.

V.