sequence (x+1)^x + x^x

[r.shepherd]

Cino Hilliard's message contained (in part):
> >      print1(3" ");
> >      forstep(x=2,n,2,
> >        y=(x+1)^x+x^x;
> >         if(isprime(y),print1(y" "))
> >
> > Maybe someone can further limit the search or find more terms?
>

To which Jim Nastos replied (in part):
>   Since primality testing is costly for large numbers, you might want to
> verify that y is +/- 1 modulo 6 before testing primality as any prime > 3
> must satisfy that. But since your number y is always going to be odd, the
> only way it won't be +/- 1 mod 6 is if it is a multiple of 3 so I suppose
> this is equivalent to just checking divisibility by 3 before testing
> primality. I'm not sure if that's useful.

To which I add/clarify that it's my experience that even Pari's *probable*-
primality testing is costly for sufficiently large numbers (i.e., isprime is
slow with numbers that are thousands of digits long -- at least with the old
version of Pari I've always used so far:  2.0.17 (beta)).  At some point I
usually find it beneficial to loop through "small" prime divisors first
(y%prime(k)<>0) before trying isprime.  I've not yet done any systematic
timings though to look for the optimal strategy to use.

Another thing I've tried is predefining a constant(s) one time (which I
suppose could be saved to a file for efficient input for later runs); e.g.,
c=prod(k=1,40000,prime(k)) to get prime(40000)# (primorial)
and then doing a gcd(y,c)==1 test to determine with one test whether
*any* of these first 40000 primes are factors (greatest common
divisor tests are relatively cheap) -- in order to save many isprime()
tests.  Again, I haven't done any systematic timings.  {It could also be
of benefit to predefine and check gcd with c1, c2, c3, etc., where each
cj is a product of consecutive primes greater than any of the primes in
the preceding ci's.}

I'm curious if anyone already uses a demonstrably good, time-saving
probable-prime-finding strategy similar to this (with Pari).  Perhaps newer
versions of Pari already do more advanced time-saving strategies....

Regards,
Rick

Jim, thanks much to you and the students, by the way, for further extending
A085632 and A085633.  Someday I really will send the pictures of the 6-coin
graphs that I prepared earlier (after finding a little time for some
clean-up work)!