Help Needed

[Dean Hickerson]

Mostly to Artur <grafix at csl.pl>:

> Mathematica Procedure can be for case mod 210 following:
> Do[If[(PrimeQ[x^16 + 1]) && (PrimeQ[x^16 + 3]) && (PrimeQ[x^16 + 7]) && \
> (PrimeQ[x^16 + 9]) && (MemberQ[{20, 40, 50, 100, 110, 160, 170, 190},
>        Mod[x, 210]]), Print[x]], {x, 57171409, 70171411}]

That would just slow down the search slightly.  In Mathematica, and many
other computer languages, an expression of the form  A && B && C && ...
is evaluated from left to right:  First A is evaluated; if it's false then
B, C, ... don't get evaluated since we already know that the AND is false.
If A is true, then B gets evaluated, and so on.  So in the program above,
you're still evaluating  PrimeQ[x^16 + 1]  for every x.

To speed things up, you could put the  MemberQ[...]  at the beginning of
the AND.  That way the primality check (which is slow) is only done for
8/210 of the values of x.  But you're still doing the MemberQ test for
all x, which is unnecessary.  It's better to not even look at values of
x that don't satisfy the congruence:

For[n=272244, n<334150, n++,
  For[i=1, i<=8, i++,
    x = 210n + {20,40,50,100,110,160,170,190}[[i]];
    If[PrimeQ[x^16+1] && PrimeQ[x^16+3] && PrimeQ[x^16+7] && PrimeQ[x^16+9],
      Print[x] ] ] ]

Running that almost immediately produces the value x=57171410, which is
just 1 plus your lower bound.  I assume you already knew that.

Mathematica's PrimeQ function isn't perfect; if it returns True, then
the number is probably prime, but to be absolutely sure you should run
some other program which produces a proof of primality.

Dean Hickerson
dean at math.ucdavis.edu