EDITED - sequences related to x^x+p being prime

[all at abouthugo.de]

cino hilliard <hillcino368 at hotmail.com> schrieb am 30.07.2003, 01:56:53:
> Hi Dean,
> 
> Thanks for all your work.
> 
> >From: Dean Hickerson 
> >To: njas at research.att.com
> >CC: hillcino368 at hotmail.com
> >Subject: EDITED - sequences related to x^x+p being prime
> >Date: Tue, 29 Jul 2003 02:10:20 -0700
> >
> >Neil:  Please delete sequences A086654, A086655, and A086656 from Cino
> >Hilliard.
> >
> >For reference, here are the current %S and %N lines of these:
> >
> >%S A086654 
> >5,8,11,17,24,41,50,53,59,65,77,83,89,90,98,118,119,125,129,142,143,144,
> >%N A086654 Numbers p such that x^x + p produces no primes for x = 1,2,..
> >
> >
> >%S A086655 
> >1,2,3,4,6,7,9,10,12,13,14,15,16,18,19,20,21,22,23,25,26,27,28,29,30,31,
> >%N A086655 Numbers p such that x^x + p produces primes for x = 1,2,..
> >
> >
> >%S A086656 
> >1,2,4,1,3,2,1,3,7,43,1,2,4,6,32,2,1,3,7,9,39,1,5,2,4,16,42,3,23,2,4,1,
> >%N A086656 Numbers x such that x^x + p is prime for p = 1,2,..
> >
> >
> >A086654 is defined as "Numbers p such that x^x + p produces no primes for
> >x = 1,2,.." and begins with 5,8,11.  But Mathematica reports that x^x+5 is
> >probably prime for x=444.  I haven't found probable primes of the forms
> >x^x+8 and x^x+11, but I see no reason to doubt their existence:
> >Heuristically, the probability that x^x+8 is prime is about 1/(x log(x)).
> >The sum of this from x=1 to n is about log(log(n)), which goes to infinity
> >as n does.  So it seems likely that there are infinitely many primes of the
> >given form unless there's some "obvious" reason to the contrary.  I don't
> >see any such reason, so I suspect that there are infinitely many primes of
> >the given form.  The same is true for the form x^x+p for any p>1, so I
> >believe that sequence A086654 is empty.  (p=1 is different:  x^x+1 can only
> >be prime if x=1 or x has the form 2^2^r with r>=0 and x^x+1 = 2^2^(r+2^r)+1
> >is a Fermat prime.  There probably aren't any more of these besides x=1,
> >2, and 4.)
> >
> >A086655 appears to be the complement of A086654, so if that sequence is
> >empty, then this one consists of all positive integers.
> >
> >A086656 seems to be defined as the concatenation of the set of x for which
> >x^x+1 is prime, the set of x for which x^x+2 is prime, ...; it begins with
> >1,2,4, 1,3, 2, 1,3,7,43 because
> >
> >    x^x+1 is prime for x = 1, 2, 4;
> >    x^x+2 is prime for x = 1, 3;
> >    x^x+3 is prime for x = 2;
> >    x^x+4 is prime for x = 1, 3, 7, 43.
> >
> >As I said above, it seems likely that the above list for x^x+1 is complete.
> >But I think each of the other lists is infinite, so we can't concatenate
> >them.  (In particular, x^x+2 is probably prime for x=737, and x^x+9 is
> >probably prime for x=130 and x=140; these aren't shown in the current
> >sequence.)
> >
> >Dean Hickerson
> >dean at math.ucdavis.edu
> 
> I tried isprime(444^444+5) on Gp 2.2.6 alpha and it bombed. I cc'd you  My 
> Email  report to Karim
> Belabas, the Pari developer.
> 
> Too bad we will never know if 444^444+5 is _really_  a prime.
> 
> This has roused my curiousity. How probable is a probable prime in 
> Mathematica,Maple,Pari? I assume
> they all use the same algorithm but what is the number? 1 in 10^10, 1 in 
> 10^100? 1 in googolplex
> that it is not really prime?  I've got it!
> 
>                     99 and 444 one thousands percent pure?
> 
> Thanks,
> Cino Hilliard

First, to answer the probability question:
For 444^444+5 which is approximately
2.74181867963021452236233098115e+1175
the probability, that it passes one probable prime
test although being composite is
< 1.2*10^(-123). This number is given in
http://www.utm.edu/research/primes/notes/prp_prob.html
(Prime pages: Probable-primes: How Probable?)
for a 1000 digit random PRP.
Mathematica & others almost certainly use a combination
of several tests. AFAIK there is no known case
that a probably prime found by one of the well-
known programs has later been found composite by
something like PRIMO (which uses ECM to _prove_
primality).

Considering the 3 sequences proposed by Cino,
it's a little bit sad, that nothing shall remain
from this effort. So let me propose to put 2
related sequences in the OEIS:

1) Smallest x>0 such that x^x+n is prime:
The sequence starts for n=1

1 1 2 1 444 1 2 ? 2 1 ? 1 2 3 2 1 ? 1 2 3

? at n=8,11,17

To eliminate the trivial cases n+1=prime, which
always produce a sequence term 1 [(1^1)+n]
we could introduce another sequence:
2) Smallest x>1 such that x^x+n is prime:
2 3 2 3 444 ? 2 ? 2 3 ? 5 2 3 2 3 ? 19 2 3

? at n=6,8,11,17

Filling the ? gaps might be a nice task: What is the difference
between "almost certainly" knowing that there are no further
Fermat primes beyond 65537 and knowing that
"each of the other lists is infinite", e.g. for n=8?

These results come from running PFGW for n=1..20
and x<1070, which produced the following
astonishingly short list of results:

(1^1)+1
(2^2)+1
(4^4)+1

(1^1)+2
(3^3)+2
(737^737)+2

(2^2)+3
(1036^1036)+3 (3124 digits)

(1^1)+4
(3^3)+4
(7^7)+4
(43^43)+4

(444^444)+5

(1^1)+6

(2^2)+7
(4^4)+7
(6^6)+7
(32^32)+7

(2^2)+9
(130^130)+9
(140^140)+9

(1^1)+10
(3^3)+10
(7^7)+10
(9^9)+10
(39^39)+10

(1^1)+12
(5^5)+12
(817^817)+12

(2^2)+13
(4^4)+13
(16^16)+13
(42^42)+13

(3^3)+14
(23^23)+14

(2^2)+15
(4^4)+15

(1^1)+16
(3^3)+16
(13^13)+16
(243^243)+16

(1^1)+18
(19^19)+18
(49^49)+18

(2^2)+19
(10^10)+19
(30^30)+19

(3^3)+20
(53^53)+20
(129^129)+20

Hugo Pfoertner