Threaded Mode | Linear Mode

Valentin Albillo · 03-02-2021, 02:55 AM

Hi all,

These are my original solutions for "Concoction the Fifth: Weird Primes" and "Concoction the Sixth: Weird Year", which concludes all my original solutions for the six Concoctions in this S&SMC #25. You can follow these links to see my previously posted original solutions to:

      "Concoction the First: Weird Limit"
      "Concoction the Second: Weird Sum".
      "Concoction the Third: Weird Integral" and "Concoction the Fourth: Weird Graph"

Note: My HP-71B code might use keywords from the JPC ROM, MATH ROM, HP-IL ROM and STRINGLX LEX file, executed on go71b, while RPN code is for the HP-42S, executed on a DM42.

My original solution for "Concoction the Fifth: Weird Primes"

      "Consider a prime number so 'Perfectly Prime' (a PP for short) that changing any single [base 10] digit would turn it into a composite number. Write a program to compute: (a) the 5 smallest PP, (b) the first PP greater than 500 million, (c) the first PP greater than 777,777,777 and the second PP greater than 666,666,666."

What's so weird about these primes?

The Sleuthing

The first thing to do is to write a program which will find these PP starting from any given integer, and this straightforward 4-line HP-71B program will nicely do:

      1  DESTROY ALL @ INPUT K,N @ FOR P=1 TO K
      2  N=FPRIM(N+2) @ N$=STR$(N) @ FOR I=1 TO LEN(N$) @ M$=N$ @ FOR D=0 TO 9
      3  M$[I,I]=STR$(D) @ IF M$=N$ THEN 4 ELSE IF NOT PRIM(VAL(M$)) THEN 2
      4  NEXT D @ NEXT I @ DISP P;N @ NEXT P

It asks how many PP to output and the lower limit to begin the search from. Let's run it to output the 5 smallest PP, as asked. We begin at 11 as obviously no single-digit prime can be a PP:

      [RUN]  ? 5,11 [ENDLINE]

            1   294001   { PP #1 }
            2   505447   { PP #2 }
            3   584141   { PP #3 }
            4   604171   { PP #4 }
            5   971767   { PP #5 }

As for the remaining questions, we proceed likewise:

      [RUN]  ? 1,5E8       [ENDLINE]  ->   1  500004469    { PP #1318 }
      [RUN]  ? 1,777777777 [ENDLINE]  ->   1  777781429    { PP #2259 }
      [RUN]  ? 2,666666666 [ENDLINE]  ->   1  666850699    { PP #1845 }
                                           2  666999929    { PP #1846 }

The Results

Once the sleuthing's over, the results are as follows:

The 5 smallest PP are: 294001, 505447, 584141, 604171 and 971767.
The first PP > 500 million is 500004469.
The first PP > 777,777,777 is 777781429.
The second PP > 666,666,666 is 666999929.

The Comments

Though for a prime being a PP seems a rare occurrence (the very first one is 294001; that any do actually exist is weird), it's been proved that in fact there's an infinity of PP and what's more, a positive proportion (in terms of asymptotic density) of the primes are PP. That's weirder !

We can try to (very roughly) "guesstimate" said proportion: there are 5,761,455 primes and 334 PP less than 100 million, so the rate comes out as 0.00580 %, i.e.: one PP per ~ 17,200 primes. Going for the next order of magnitude, there are 50,847,534 primes and 3,167 PP less than 1 billion, so the rate now comes out as 0.00623 %, i.e.: one PP per ~ 16,000 primes, hence the proportion, though very small, seems to be increasing (and in any case, it's asymptotically > 0 .)

Furthermore, if that wasn't weird enough, there's also a positive proportion of primes which are PPP (Perfect Prime Plus), which have the property that if any single digit is changed (including any zero among the prime's infinitely many leading zeros), then the resulting number is always composite. That's weirdest !!

For instance, notice that the first PP, 294001, is not a PPP since changing, say, the second leading zero of ...000294001 results in ...010294001, which is prime. Matter of fact, even though a (much smaller, but still) positive proportion of the primes are PPP, none are yet known.

Let's end these Comments by listing some peculiar PP you may find useful to check or optimize your code:

The first five PP found above are all the PP less than 1 million. The next five are 1062599, 1282529, 1524181, 2017963 and 2474431.
PP #24 and PP #25 are consecutive and extremely close: 7469789 and 7469797, respectively.
PP #51 and PP #52 are consecutive and both look like nearby date ranges: 1985_1991 and 2021_2327, resp.
PP #1404 to PP #1414 are consecutive and end in 1,1,1,1,7,7,1,1,7,7,1, resp.
PP #1846 and PP #2539 have only 3 different digits each: 666999929 and 844448333, resp.
PP #3048 = 969094909, has the odd digit 9 in all odd positions and even digits in all even positions.

So much for Perfect Primes but there's more: you might want to try your hand at these four lingering questions (for which I won't provide answers, you'll be on your own):

Are there any Twin PP, i.e: two PP whose difference is 2 ?
Are there any PP which remain so (i.e.: the result is always composite) when changing any two digits ?
Find a PPP. There's an infinity of them and you'll get worldwide fame in the math field if you do,
What about Composites ? What's the first composite (not divisible by 2 or 5) so "Perfectly Composite" [PC] that it remains composite when you change any single [base 10] digit ? (hint: it begins with 2 and ends with 9)

The Hall of Fame

This time the one expert which dealt with this Concoction the Fifth: Weird Primes is:

robve, who wrote HPPL code for the HP Prime and found the correct answers to all four questions asked. He also wrote a "Cheat program" (his own words, mine too) in C which ran much faster (D'oh!), but more importantly, he gave some theoretical considerations to estimate the chance that a prime number is a PP and correctly concluded that "it seems reasonable to see perfect primes for large k [digits] and there are infinitely many of them".

Afterwards he posted an alternative submission in HPPL and augmented his sleuthing above and beyond the call of duty, producing a list of the first PP for every base from 2 to 19, then another list with the PP counts for the same bases, commenting on the results and the interesting pattern obtained. That's what sleuthing is all about !

Finally he also said that "It seems odd to me to change the leading digit to 0 to check for PP" but the reason for that is made clearer in the light of the existence of PPP, as stated in the Comments above.

My original solution for "Concoction the Sixth: Weird Year"

      "2020 shares a very striking numeric property with many other catastrophic years [...] try and discover what simple numeric property {which can be unambiguously stated by saying that the year's number "is a (five words)"} is shared by all the aforementioned numbers, and then write a program to output a listing of all years between AD 4 and AD 5000 (both included) which have this very property.

      Additional questions are: (a) How many years will be listed in the output ? (b) What will be the next predicted potentially catastrophic year after 2020 ? and (c) Should we be concerned ?

The Sleuthing

Here, the very first thing to do is to discover the "striking numeric property" in question, which isn't as difficult as it seems because there are only so many such properties which can be unambiguously stated in just five words, e.g.: the number is a "sum of some prime numbers" does fit, but this is far too generic because every integer > 1 has that property. Many variations are possible (say "5" instead of "some" or replacing "primes" by "squares", "cubes", "factorials", etc.)

One very useful heuristic is to analyze possible properties of the smallest numbers given: we first discover some property they have in common and then check if it applies to the bigger numbers as well. The numbers stated as sharing the sought-for property are 458, 662, 666, 1348, 1556, 1849 and 2020, so the smallest number is 458 and the sleuthing process begins with it.

After discarding many sums of squares and cubes (e.g.: "sum of four square numbers", as every integer is a sum of four square numbers, including 0²) and "sum of some prime numbers" and variations, we eventually discover that 458 = 13² + 17², a sum of exactly two non-zero squares, but regrettably 662 is not. We also notice that the numbers 13 and 17 are primes so we refine the property to "sum of some squared primes" but again that's too generic and gets us nowhere.

Cutting to the chase, eventually we also notice that 13 and 17 are consecutive primes so the property becomes "sum of consecutive squared primes" (5 words!) and this time we hit the jackpot: 458 = 13² + 17² and 662 = 3² + 5² + 7² + 11² + 13² + 17², and checking the bigger numbers we readily get:

      666   = 2² + 3² + 5² + 7² + 11² + 13² + 17²
      1348 = 13² + 17² + 19² + 23²
      1556 = 2² + 3² + 5² + 7² + 11² + 13² + 17² + 19² + 23²
      1849 = 43² { a sum with just one summand is also a sum; the empty sum is 0 }
      2020 = 17² + 19² + 23² + 29²

so bingo !. Now it's just a matter of writing a program to find all the years in the given interval having that property, and this 7-line program for the HP-71B will do:

      1  DESTROY ALL @ OPTION BASE 1 @ DIM P(19) @ K=2 @ L=0 @ C=0
      2  REPEAT @ L=L+1 @ P(L)=K*K @ K=FPRIM(K+1) @ UNTIL K>70
      3  FOR N=4 TO 5000 @ J=L @ WHILE P(J)>N @ J=J-1 @ END WHILE
      4  M=N @ I=J
      5  M=M-P(I) @ IF NOT M THEN C=C+1 @ DISP N; @ GOTO 7
      6  IF M<0 THEN J=J-1 @ GOTO 4 ELSE I=I-1 @ IF I THEN 5
      7  NEXT N @ DISP @ DISP "Total:";C

      [RUN]
                 4     9    13    25    34    38    49
                74    83    87   121   169   170   195
               204   208   289   290   339   361   364
               373   377   458   529   579   628   650
               653   662   666   819   841   890   940
               961   989  1014  1023  1027  1179  1348
              1369  1370  1469  1518  1543  1552  1556
              1681  1731  1802  1849  2020  2189  2209
              2310  2330  2331  2359  2384  2393  2397
              2692  2809  2981  3050  3150  3171  3271
              3320  3345  3354  3358  3481  3530  3700
              3721  4011  4058  4061  4350  4489  4519
              4640  4689  4714  4723  4727  4852  4899

              Total: 91

where the years given as examples appear in bold and the next one after 2020 appears in bold red, which is 2189 = 13² + 17² + 19² + 23² + 29².

The Results

Based on the data obtained by the sleuthing process above and the results from running the program, the answers are:

The simple numeric property is: The years' numbers are a "sum of consecutive squared primes" (five words)
The listing of all years between AD 4 and AD 5000 (both included) which have this property is the output above, 91 years in all.
What will be the next predicted potentially catastrophic year after 2020 ?: It will be 2189, as seen in the output.
Should we be concerned ?: Well, with ever-advancing technology one can never say for sure, but I very much doubt any people reading this in 2021 will be kicking and alive by 2189, so no worries !

The Comments

The joke explanation of why 2020 was such a catastrophic year is an original idea of mine, and implementing it was just a matter of finding some nice but simple numeric property of 2020. After some sleuthing I found it to be that 2020 = 17² + 19² + 23² + 29², which are the squares of consecutive primes (pretty nice indeed), and then I wrote the program to compute all other years between AD 4 and AD 5000 sharing this property. So far, so good.

Then I searched Wikipedia for a list of big catastrophes, and cross-checking the years found there with the years listed by my program I finally selected the ones most remarkable while ignoring numbers too low, to avoid reducing the difficulty too much (e.g.: if chosing AD 13 it would be instantly recognizable as 2² + 3², all too easy!) and le voilà, Concoction 6 ready !

I also wrote the following 6-line program for the HP-71B which accepts a given year in range and demonstrates whether it has the required numeric property (thus, if it indeed was/might be catastrophic) or not.).

      1  DESTROY ALL @ OPTION BASE 1 @ DIM P(19),S$[80] @ K=2 @ L=0
      2  REPEAT @ L=L+1 @ P(L)=K*K @ K=FPRIM(K+1) @ UNTIL K>70 @ INPUT N
      3  J=L @ WHILE P(J)>N @ J=J-1 @ END WHILE
      4  S$="" @ M=N @ I=J
      5  M=M-P(I) @ S$=STR$(SQR(P(I)))&"^2+"&S$ @ IF NOT M THEN S$[LEN(S$)]="" @ DISP S$ @ END
      6  IF M<0 THEN J=J-1 @ GOTO 4 ELSE I=I-1 @ IF I THEN 5 ELSE DISP "Not a sum"

      [RUN]
            ?  2020   ->   17^2+19^2+23^2+29^2                 { VAL(S$) = 2020 }
            ?  666    ->   2^2+3^2+5^2+7^2+11^2+13^2+17^2      { VAL(S$) = 666 }
            ?  1849   ->   43^2                                { VAL(S$) = 1849 }
            ?  555    ->   Not a sum

The Hall of Fame

Again, the one and only expert who dared to deal with this Concoction the Sixth: Weird Year is no other but

Gerson W. Barbosa, who posted RPL code for such models as the HP50G and BASIC code for the HP-75C, both of which correctly produced the list of "weird" years, and he also gave their total number (91) and stated explicitly the remarkable property all these numbers share. Alas, he didn't post any details on his sleuthing, particularly how he managed to find the correct "remarkable and striking numerical property", which would be fascinating for sure but never mind, Well Done !

That's all, this concludes my original solutions for all 6 Concoctions 6 of this S&SMC #25 of mine. Thank you very much to those who contributed their solutions or at least posted some comments, much appreciated.

I really hope you enjoyed it as well as all the readers in general. Over and out.

Note: For any comments not directly related to the math or code here but to ancillary matters such as this or that opinion on the rules or "Halls of Fame" or whatever, please PM me instead of posting them here. Let's keep this thread strictly mathematical and algorithmical in nature. Thanks.

Best regards.
V.