Help Needed

[Nick Hobson]

Hi Artur,

You don't need to check *every* value of x.  For a start, obviously x must  
be even for those numbers to be prime.  Further, since all primes greater  
than 3 are congruent to 1 or 5 (mod 6), we need x^16+1 = 5 (mod 6), which  
implies x = 2 or 4 (mod 6).  This means you need only check the numbers x  
= 40000004, 40000006, 40000010, 40000012, 40000016, 40000018, 40000022,  
40000024, 40000028, 40000030, 40000034, 40000036, 40000040, ... .  This is  
2/6 ~= 0.33 of integers.

Better still, all primes greater than 5 are congruent to 1, 7, 11, 13, 17,  
19, 23, or 29 (mod 30).  Hence we need x^16 + 1 = 11 (mod 30), which  
implies x = 10 or 20 (mod 30).  This narrows the search down further to  
the numbers x = 40000010, 40000030, 40000040, 40000060, 40000070,  
40000090, 40000100, ... .  This is 2/30 ~= 0.067 of integers.

Similarly, if we consider mod 210 = 2*3*5*7, we find that x^16 = 10, 100,  
or 190 (mod 210), implying that x = 20, 40, 50, 100, 110, 160, 170, or 190  
(mod 210).  This brings the proportion of integers to be checked down to  
8/210 ~= 0.038.

Going further, to mod 2310 = = 2*3*5*7*11, brings the proportion of  
numbers to be checked down to 72/2310 ~= 0.031.  This is not much of an  
improvement, so it seems mod 210 represents a good compromise.

In PARI/GP, you could code the check as:

forstep(x=40000010, 50000000, [50,10,50,10,20,40,20,10], y=x^16;  
if(isprime(y+1) && isprime(y+3) && isprime(y+7) && isprime(y+9), print1(x,  
", ")))

The array [50,10,50,10,20,40,20,10] tells the script to take successive  
steps of 50, 10, 50, 10, 20, 40, 20, and 10.  Since 40000010 = 50 (mod  
210), this steps you through 50, 100, 110, 160, 170, 190, 20, and 40 (mod  
210).  Maybe Mathematica has a similar facility?

(It also helps to take the computation of x^16 out of the if statement, in  
case the interpreter/compiler does not optimise the four isprime  
statements, and calculates x^16 up to four times.)

The above script prints no numbers.  (Takes about 21 minutes on my Intel  
2.52GHz.)

To work mod 2310, as mentioned above, it would be advisable to create the  
"step-through" array programmatically, rather than manually as above.   
This would be more work, but if the primality checking function is  
expensive enough (as I suspect it is) it would be worth it.

Nick


On Sat, 30 Dec 2006 11:32:51 -0000, Artur <grafix at csl.pl> wrote:

> Dear Seqfans,
> I'm looking person which can help to find the first number x such
> (x^16+1)&(x^16+3)&(x^16+7)&(x^16+9) are all primes
> I was tested that no such x smallest as 30000001 and now I was execute  
> procedure to 40000001
>
> I'm looking for person which can try find these number in range  
> 40000001, 50000000
>
> e.g. by Mathematica procedure
>
> Do[If[(PrimeQ[x^16 + 1]) && (PrimeQ[x^16 + 3]) && (PrimeQ[x^16 + 7]) &&
> (PrimeQ[x^16 + 9]), Print[x]], {x, 40000001, 50000000}]
>
> These number existed because Schinzel in 1959 prooved that set of this  
> numbers is infinite
>
> BEST WISHES
> ARTUR
>