EDITED - sequences related to x^x+p being prime
cino hilliard
hillcino368 at hotmail.com
Thu Jul 31 02:06:23 CEST 2003
Hi Hugo,
Thanks for your input. Some comments from me below.
>From: <all at abouthugo.de>
>To: cino hilliard <hillcino368 at hotmail.com>
>CC: <dean at math.ucdavis.edu>, <njas at research.att.com>,
><seqfan at ext.jussieu.fr>
>Subject: Re: EDITED - sequences related to x^x+p being prime
>Date: Wed, 30 Jul 2003 22:08:01 +0200
>
>
>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).
Mathematica help on isprime states "No counter example is known and it has
been conjectured that
such a counter example must be hundreds of digits long."
>
>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:
Not all is lost, at least for me, as I learned that Pari GP 2.2.6 isprime
"proves" primality and ispseudoprime
gives probable primes.
? isprime
isprime(x,{flag=0}): if flag is omitted or 0, true(1) if x is a (proven)
prime
number, false(0) if not. If flag is 1, the primality is certified by the
Pocklington-Lehmer Test. If flag is 2, the primality is certified using the
APRCL test.
?ispseudoprime
ispseudoprime(x,{n}): true(1) if x is a strong pseudoprime, false(0) if not.
If n is 0 or omitted, use BPSW test, otherwise use strong Rabin-Miller test
for n randomly chosen bases.
Karim from Pari further explains:
"In the recent versions, isprime now _proves_ primality [ which is very
expensive, all the more since the APRCL implementation is rather naive ].
Use ispseudoprime() for a cheap pseudo-prime test."
This is good to know since a lot of sequences dealing with primes are
labeled pseudo prime in context. I
guess we could go through and re-do with GP 2.2.6 and clarify at least up to
a point that the sequence
is dealing with proven primes or (God forbid) that a contradiction has been
found. I have plugged a
stack of 700000000 in GP (even though I have 2 gigs of ram GP sputters at
800000000 and higher)
and have been running isprime(444^444+5) for 8hrs so far on a 2.53 ghz p4 xp
pro. I am sure it
will run out of stack. However, if you do isprime(nextprime(200^200+213)),
it gives 1 in a few minutes.
The case Dean mentions for x^x+9 x=130,140 are proven primes.
>isprime(130^130+9)
%2 = 1
>isprime(140^140+9)
%3 = 1
>
>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
Is PFGW windows and free?
>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
_________________________________________________________________
STOP MORE SPAM with the new MSN 8 and get 2 months FREE*
http://join.msn.com/?page=features/junkmail
More information about the SeqFan
mailing list