[math-fun] permutable primes redux
Despite computer searches, 991 was the last known value of A003459 for improbably long, prompting NJAS to cajole math-fun for more. Rich then found his startling proof that all the elements past 991 were repunits, so next comes (10^19 - 1)/9. In retrospect, R(19) and R(23) should have been found previously by searching. Why weren't they? Bad algorithms? Unavailability of bignums? Programming was more tedious then. See A258706, the condensed version of A003459. Now the tedious part is deciphering the Mathematica. --rwg
Where should I look for Rich's proof? I don't recall it. --Michael On Sat, Jan 7, 2017 at 2:15 AM, Bill Gosper <billgosper@gmail.com> wrote:
Despite computer searches, 991 was the last known value of A003459 for improbably long, prompting NJAS to cajole math-fun for more. Rich then found his startling proof that all the elements past 991 were repunits, so next comes (10^19 - 1)/9.
In retrospect, R(19) and R(23) should have been found previously by searching. Why weren't they? Bad algorithms? Unavailability of bignums? Programming was more tedious then.
See A258706, the condensed version of A003459. Now the tedious part is deciphering the Mathematica. --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Where should I look for Rich's proof? I don't recall it.
In Bill's 24 Jan 2003 message to math-fun [check the archives], he seems "to have lost the mail with Rich's proof". I will point out however that there is a 1951 reference by Hans-Egon Richert (On permutable primtall) which supposedly proved "that in the range 991 < p < 10^175 the only base 10 permutable primes are repunit primes". If Richard Schroeppel had a proof above that range, it deserves to be better known.
in the range 991 < p < 10^175 the only base 10 permutable primes are repunit primes
I'll copy/paste from Arkadii Slinko's "Absolute Primes" (year?): Theorem 2: Let N be an absolute prime, different from repunits, that contains n > 3 digits in its decimal representation. Then n is a multiple of 11088. Proof: According to the previous lemma we assume that n > 16. Since 10 is a primitive root modulo 17, Lemma 6 yields that n divides 16 and hence n >= 32. We can repeat this argument three times, using the primes 19, 23, 29, to obtain that n is a multiple of 18, 22 and 28, respectively. Therefore n divides LCM(16,18,22,28) = 11088. Richert used in addition the primes 47, 59, 61, 97, 167, 179, 263, 383, 503, 863, 887, 983 to show that the number n of digits of the absolute prime number Bn(a,b) is divisible by 321653308662329838581993760. He also mentioned, that by using the tables of primes and their primitive roots up to 10^5, it is possible to show that n > 6*10^175.
in the range 991 < p < 10^175 the only base 10 permutable primes are repunit primes
I'll copy/paste from Arkadii Slinko's "Absolute Primes" (year?):
Apparently there was a preprint of Arkadii's "lecture to math olympiad students" on the Net in 2002. Also note that my quoted range for primes (which came from planetmath.org) is wrong. The bound 6*10^175 is not for the prime itself but for its number of digits! Slinko stated that Richert mentioned "that by using the tables of primes and their primitive roots up to 10^5, it is possible to show that n > 6*10^175". Did Richert actually show it? I don't read it that way. Rather, only that it was possible to show it. So who, if anyone, since 1951 *has* shown it?
Did Richert actually show it? I don't read it that way. Rather, only that it was possible to show it. So who, if anyone, since 1951 *has* shown it?
I'm still struggling with this. On a purely mechanical level though I think I understand now how Richert showed "that the number n of digits of the absolute prime number Bn(a,b) is divisible by 321653308662329838581993760": In[1]:= LCM[16,18,22,28,46,58,60,96,166,178,262,382,502,862,886,982] Out[1]= 321653308662329838581993760 The numbers on which we are doing the LCM are one less than a number of primes whose PrimitiveRoot[{primes},9] are all 10. Why didn't Richert didn't use all the primes (greater than 16, otherwise < https://oeis.org/A001913 >) less than 1000 that yield the result? I guess that in 1951 it was tedious work: In[2]:= t={};Do[If[PrimitiveRoot[Prime[i],9]==10,AppendTo[t,Prime[i]]],{i,PrimePi[1000]}];t Out[2]= {17,19,23,29,47,59,61,97,109,113,131,149,167,179,181,193,223,229,233,257,263,269,313,337,367,379,383,389,419,433,461,487,491,499,503,509,541,571,577,593,619,647,659,701,709,727,743,811,821,823,857,863,887,937,941,953,971,977,983} In[3]:= LCM[16,18,22,28,46,58,60,96,108,112,130,148,166,178,180,192,222,228,232,256,262,268,312,336,366,378,382,388,418,432,460,486,490,498,502,508,540,570,576,592,618,646,658,700,708,726,742,810,820,822,856,862,886,936,940,952,970,976,982] Out[3]= 1903624829738325512638755460871681762868757605195485779200 It's now just a simple matter to scale to the "primes and their primitive roots up to 10^5": In[4]:= t={};Do[If[PrimitiveRoot[Prime[i],9]==10,AppendTo[t,Prime[i]]],{i,PrimePi[10^5]}];t Out[4]= {17,19,23,29,47,...,99901,99971,99989} In[5]:= LCM[16,18,22,28,46,...,99900,99970,99988] Out[5]= 6284645765...5616000000 ~6*10^4044 which is different from Richert's suggested 6*10^175 (perhaps) for the same reason that my 1903624829738325512638755460871681762868757605195485779200 (above) is different from his 321653308662329838581993760. At any rate, doesn't (then) the suggestion that all the elements of A003459 past 991 being repunits boil down to there being an infinite number of terms in A001913?
participants (3)
-
Bill Gosper -
Hans Havermann -
Michael Kleber