[math-fun] Data compressing the primes < 104000
with CarmichaelQ (fairly simple), and three special cases, Block[{a = 15485857, b = 29462131}, Reap[Do[If[! PrimeQ[k] && ! CarmichaelQ[k] && Divisible[ PowerMod[a + b, k, k] - PowerMod[a, k, k] - PowerMod[b, k, k], k], Sow[k]], {k, 2, 117568}]]] {Null, {{56033, 73633, 93961, 104653}}} There may well be superior and smaller a and b. And almost certainly superior larger ones. But I don't have a good way to look for them. --rwg
This is probably Quixotic, given that four PowerMods plus some fooling around will give you strong pseudoprime testing, where "the bases 2, 13, 23, and 1662803 have no exceptions up to [image: 10^(12)]" http://mathworld.wolfram.com/StrongPseudoprime.html (That's a trillion, in case GMail trashed it) without even CarmichaelQ. But it seems likely there is a pair of fifty-or-so digit a and b that beat the quad strong pseudoprime test (without requiring fifty digit arithmetic), if we could only find them. --rwg On Sat, May 31, 2014 at 12:51 AM, Bill Gosper <billgosper@gmail.com> wrote:
with CarmichaelQ (fairly simple), and three special cases, Block[{a = 15485857, b = 29462131}, Reap[Do[If[! PrimeQ[k] && ! CarmichaelQ[k] && Divisible[ PowerMod[a + b, k, k] - PowerMod[a, k, k] - PowerMod[b, k, k], k], Sow[k]], {k, 2, 117568}]]]
{Null, {{56033, 73633, 93961, 104653}}}
There may well be superior and smaller a and b. And almost certainly superior larger ones. But I don't have a good way to look for them. --rwg
D@mn, forgot the datum: Minor improvement: primes< 109000 with only one case check: In[62]:= Block[{a = 29386219, b = 426229}, Reap[Do[If[! PrimeQ[k] && ! MemberQ[carms, k] && Divisible[ PowerMod[a + b, k, k] - PowerMod[a, k, k] - PowerMod[b, k, k], k], Sow[k]], {k, 2, 172080}]]] Out[62]= {Null, {{96049, 109061, 119341, 145351}}} With four PowerMods, we can do considerably better: In[69]:= Reap[Do[If[! PrimeQ[k] && ! MemberQ[carms, k] && Divisible[2*PowerMod[710, k, k] - PowerMod[616, k, k] - PowerMod[261, k, k] - PowerMod[543, k, k], k], Sow[k]], {k, 2, 512461}]] Out[69]= {Null, {{188191, 206981, 265774, 365041, 481601}}} --rwg On Sat, May 31, 2014 at 10:54 PM, Bill Gosper <billgosper@gmail.com> wrote:
This is probably Quixotic, given that four PowerMods plus some fooling around will give you strong pseudoprime testing, where "the bases 2, 13, 23, and 1662803 have no exceptions up to [image: 10^(12)]" http://mathworld.wolfram.com/StrongPseudoprime.html (That's a trillion, in case GMail trashed it) without even CarmichaelQ. But it seems likely there is a pair of fifty-or-so digit a and b that beat the quad strong pseudoprime test (without requiring fifty digit arithmetic), if we could only find them. --rwg
On Sat, May 31, 2014 at 12:51 AM, Bill Gosper <billgosper@gmail.com> wrote:
with CarmichaelQ (fairly simple), and three special cases, Block[{a = 15485857, b = 29462131}, Reap[Do[If[! PrimeQ[k] && ! CarmichaelQ[k] && Divisible[ PowerMod[a + b, k, k] - PowerMod[a, k, k] - PowerMod[b, k, k], k], Sow[k]], {k, 2, 117568}]]]
{Null, {{56033, 73633, 93961, 104653}}}
There may well be superior and smaller a and b. And almost certainly superior larger ones. But I don't have a good way to look for them. --rwg
participants (1)
-
Bill Gosper