Prime numbers and primality testing is a Restricted Group with 1117 members.
 Prime numbers and primality testing

 Restricted Group,
 1117 members
Pritchard 1981, A sublinear additive sieve .... Comm ACM 24:1823
Expand Messages
 I have 'issues' with something in Crandall & Pomerance, their
algorithm and their claimed bigOh don't match (they are
'optimistic', heheh). However, they refer to the above paper, which
might provide an explanation. I believe I've 'fixed' their algorithm
(it requires splitting stages into different parts, and changing the
order of things, so it's almost a different algorithm), but if
Pritchard already documents the alterations I propose, then there's
less point in me investigating further.
Does anyone have access to that paper so that I could briefly take a
peek?
I've picked up later papers by Pritchard, Sorensen and Dunten (3
different papers that is) off Citeseer, which all refer to it;
there's a chance that my fix may be in those but from the abstracts I
don't think that's the case, and if it were to be then C&P need to
fix their references.
Cheers,
Phil
__________________________________________________
Do You Yahoo!?
Yahoo! Games  play chess, backgammon, pool and more
http://games.yahoo.com/  Hi,
I was just wondering what the state of play was with looking for a
(pseudo)prime of the form 2^p+3  what search limits have been reached, and
have any PRP's been found? I recall that there was some searching being done a
couple of years ago (I think), but I do not know what (if any) results were
found?
Regards,
Paul.
__________________________________________________
Virus checked by MessageLabs Virus Control Centre.  Paul,
Just a couple of observations regarding primes of the form 2^p+3.
First, there should be infinitely many primes of this form. When p
is even, the result is a number congruent 1 Mod 6; when p is odd, the
result is a number congruent 5 Mod 6. Since all primes other than 2
or 3 are congruent 1 Mod 6 or 5 Mod 6 and since there are infinitely
many primes contained in either of the two congruences, it follows
that there should be infinitely many primes of the form 2^p+3. I
haven't a clue as to the largest prime to date of this form, but
certainly it should be (or could be, with a little focused attention)
very large.
The prime number form you propose are very similar to Mersenne primes
and I would expect prime number results for 2^p+3 to rival those of
Mersenne primes in size and distribution too.
Robert
 In primenumbers@y..., "Paul Jobling" <Paul.Jobling@W...> wrote:
> Hi,
>
> I was just wondering what the state of play was with looking for a
> (pseudo)prime of the form 2^p+3  what search limits have been
reached, and
> have any PRP's been found? I recall that there was some searching
being done a
> couple of years ago (I think), but I do not know what (if any)
results were
> found?
>
> Regards,
>
> Paul.
>
>
> __________________________________________________
> Virus checked by MessageLabs Virus Control Centre.  Hi Robert,
> Just a couple of observations regarding primes of the form 2^p+3.
I believe that we are only interested in p prime here.
> First, there should be infinitely many primes of this form. When p
> is even, the result is a number congruent 1 Mod 6; when p is odd, the
> result is a number congruent 5 Mod 6.
> Since all primes other than 2
Careful... that sort of reasoning is wrong  you are saying that given an
> or 3 are congruent 1 Mod 6 or 5 Mod 6 and since there are infinitely
> many primes contained in either of the two congruences, it follows
> that there should be infinitely many primes of the form 2^p+3.
infinite set N, where an infinite number of its member have some property A,
then any infinite subset M of N must contain an infinite number of members
with the proper A as well (consider N=the integers; A=prime; M=the composite
numbers).
> I
But they do not seem to. The earliest Mersenne primes are quite small, whereas
> haven't a clue as to the largest prime to date of this form, but
> certainly it should be (or could be, with a little focused attention)
> very large.
>
> The prime number form you propose are very similar to Mersenne primes
> and I would expect prime number results for 2^p+3 to rival those of
> Mersenne primes in size and distribution too.
I am not sure that even one example of a pseudoprime of this form has been
found.
Regards,
Paul.
__________________________________________________
Virus checked by MessageLabs Virus Control Centre. > But they do not seem to. The earliest Mersenne primes are
Let me correct that to say "for reasonably large p".
> quite small, whereas
> I am not sure that even one example of a pseudoprime of this
> form has been found.
__________________________________________________
Virus checked by MessageLabs Virus Control Centre.  In primenumbers@y..., "Paul Jobling" <Paul.Jobling@W...> wrote:
> Hi,
reached, and
>
> I was just wondering what the state of play was with looking for a
> (pseudo)prime of the form 2^p+3  what search limits have been
> have any PRP's been found? I recall that there was some searching
being done a
> couple of years ago (I think), but I do not know what (if any)
results were
> found?
http://groups.yahoo.com/group/primenumbers/message/1023
might contain some results for 2^p+3
Paul U.  Well, the OLEIS (A057736) only has 2, 3, 7, 67. But looking at
http://groups.yahoo.com/group/primeform/message/1218
it appears that some searching was going on. So now the question is what
search limits were reached  Christ; Chris?
Paul.
__________________________________________________
Virus checked by MessageLabs Virus Control Centre.  Paul,
I obviously misunderstood your equation; I read it as (2^p) + 3 where
p=2,result 7; p=3, result 11, and so on.
I stand by my earlier statements (let's term it as Robert's
Conjecture) though: A one variable equation which, (a) does not
reduce and (b) contains infinitely many 1 Mod 6 and/or 5 Mod 6
numbers, will contain infinitely many prime numbers.
I enjoy your comments and perspective...
Robert
 In primenumbers@y..., "Paul Jobling" <Paul.Jobling@W...> wrote:
> Hi Robert,
>
> > Just a couple of observations regarding primes of the form 2^p+3.
> > First, there should be infinitely many primes of this form. When
p
> > is even, the result is a number congruent 1 Mod 6; when p is odd,
the
> > result is a number congruent 5 Mod 6.
>
> I believe that we are only interested in p prime here.
>
> > Since all primes other than 2
> > or 3 are congruent 1 Mod 6 or 5 Mod 6 and since there are
infinitely
> > many primes contained in either of the two congruences, it follows
> > that there should be infinitely many primes of the form 2^p+3.
>
> Careful... that sort of reasoning is wrong  you are saying that
given an
> infinite set N, where an infinite number of its member have some
property A,
> then any infinite subset M of N must contain an infinite number of
members
> with the proper A as well (consider N=the integers; A=prime; M=the
composite
> numbers).
>
> > I
> > haven't a clue as to the largest prime to date of this form, but
> > certainly it should be (or could be, with a little focused
attention)
> > very large.
> >
> > The prime number form you propose are very similar to Mersenne
primes
> > and I would expect prime number results for 2^p+3 to rival those
of
> > Mersenne primes in size and distribution too.
>
> But they do not seem to. The earliest Mersenne primes are quite
small, whereas
> I am not sure that even one example of a pseudoprime of this form
has been
> found.
>
> Regards,
>
> Paul.
>
>
> __________________________________________________
> Virus checked by MessageLabs Virus Control Centre.  Paul,
btw this
ABC2 2^($a)2^($a/2+1)+1
a: from 2 to 3000
produced:
2^32^(3/2+1)+1
2^72^(7/2+1)+1
2^472^(47/2+1)+1
2^732^(73/2+1)+1
2^792^(79/2+1)+1
2^1132^(113/2+1)+1
2^1512^(151/2+1)+1
2^1672^(167/2+1)+1
2^2392^(239/2+1)+1
2^2412^(241/2+1)+1
2^3532^(353/2+1)+1
2^3672^(367/2+1)+1
2^4572^(457/2+1)+1
2^13672^(1367/2+1)+1
Note the first exponents are all prime. Are there anymore of these?
Paul U.   rlberry2002 <rlberry2002@...> wrote:
> Just a couple of observations regarding primes of the form 2^p+3.
[SNIP  see Paul J's reply]
> The prime number form you propose are very similar to Mersenne
I wouldn't expect them to have the same distribution.
> primes
> and I would expect prime number results for 2^p+3 to rival those of
>
> Mersenne primes in size and distribution too.
2^p+1, being a cyclotomic form, has restrictions on what its factors
can be. 2^p+3 has no such divisibility criterea.
Phil
__________________________________________________
Do You Yahoo!?
Yahoo! Health  your guide to health and wellness
http://health.yahoo.com  At 04:02 PM 5/1/02 +0000, paulunderwooduk wrote:
>2^1672^(167/2+1)+1
Such as:
>2^2392^(239/2+1)+1
>2^2412^(241/2+1)+1
>2^3532^(353/2+1)+1
>2^3672^(367/2+1)+1
>2^4572^(457/2+1)+1
>2^13672^(1367/2+1)+1
>
>Note the first exponents are all prime. Are there anymore of these?
2^3642892^182145+1
Sure. These are norms of the Gaussian Mersenne primes. Look on the
prime list.   In primenumbers@y..., "rlberry2002" <rlberry2002@y...> wrote:
> Paul,
No, you got it right :)
>
> I obviously misunderstood your equation; I read it as (2^p) + 3
> where p=2,result 7; p=3, result 11, and so on.
> I stand by my earlier statements (let's term it as Robert's
See Sierpinski numbers for a wellknown counterexample:
> Conjecture) though: A one variable equation which, (a) does not
> reduce and (b) contains infinitely many 1 Mod 6 and/or 5 Mod 6
> numbers, will contain infinitely many prime numbers.
78557*2^n+1 contains an infinite number of elements which are
(5 mod 6), but has no prime numbers for any integer n.
Back to the original question... There are easily found concrete
examples of the form 2^p+n which do not have an infinite number of
prime values (with p prime) despite having an infinite number of
(1 mod 6) and (5 mod 6) numbers:
N=2^p+12213 (with p prime) has no prime values whatsoever.
This is because:
If p == 2, N is divisible by 19
If p == 3, N is divisible by 11
If p == 1 (mod 12), N is divisible by 5
If p == 5 (mod 12), N is divisible by 5
If p == 7 (mod 12), N is divisible by 7
If p == 11 (mod 12), N is divisible by 13
Every prime p meets one of the six cases above, so N is never
prime when p is prime.   Phil Carmody <thefatphil@...> wrote:
> > The prime number form you propose are very similar to Mersenne
They of course have their own divisibility criterea. But one
> > primes
> > and I would expect prime number results for 2^p+3 to rival those
> of
> >
> > Mersenne primes in size and distribution too.
>
> I wouldn't expect them to have the same distribution.
> 2^p+1, being a cyclotomic form, has restrictions on what its
> factors
> can be. 2^p+3 has no such divisibility criterea.
unrelated to (a^n+b^n) forms. Their criteria are more similar to
those behind the 'fixed k Proth' problems.
Phil
__________________________________________________
Do You Yahoo!?
Yahoo! Health  your guide to health and wellness
http://health.yahoo.com   In primenumbers@y..., "jbrennen" <jack@b...> wrote:
> In primenumbers@y..., "rlberry2002" <rlberry2002@y...> wrote:
For an infinity of easy to show counter examples, look at this form:
>> Paul,
>>
>> I obviously misunderstood your equation; I read it as (2^p) + 3
>> where p=2,result 7; p=3, result 11, and so on.
>
>No, you got it right :)
>
>> I stand by my earlier statements (let's term it as Robert's
>> Conjecture) though: A one variable equation which, (a) does not
>> reduce and (b) contains infinitely many 1 Mod 6 and/or 5 Mod 6
>> numbers, will contain infinitely many prime numbers.
>
> See Sierpinski numbers for a wellknown counterexample:
> 78557*2^n+1 contains an infinite number of elements which are
> (5 mod 6), but has no prime numbers for any integer n.
k#+p
If p is a "fixed" prime > 3, then the expression will be +1 mod(6),
however, the expression (for a variable k and fixed p) will produce
ONLY a finite (if any) amount of primes. Primes can only be generated
by the above form while k < p. Once k reaches the size of p, then
p will always be a factor of the expression.
Take for example k#+13.
This is prime for k=3, 5, 7 and NO others, since 2#+13=3*5,
11#+13= 23*101 and when k>=13 then k#+13 is always has a factor of 13.
However k#+13 == 1mod(6) (except for 2#+13==3mod(6)).
Jim.  AFAIK the largest PRP of form 2^n+3 is still the one found by me in July
2001:
2^122550+3
It is the 19th largest known PRP, according to Henri Lifchitz's database at
http://ourworld.compuserve.com/homepages/hlifchitz/
The sequence for lower values is Sloane's A057732. I had searched up to
n=127677, and proved primality for n <=2370 using Titanix, finishing this
project on 15 Aug 2001.
(See also my post to the primenumbers group dated 8 Jul 2002.)
Mike Oakes
In a message dated 01/05/02 14:41:02 GMT Daylight Time,
Paul.Jobling@... writes:
> Hi,
[Nontext portions of this message have been removed]
>
> I was just wondering what the state of play was with looking for a
> (pseudo)prime of the form 2^p+3  what search limits have been reached,
> and
> have any PRP's been found? I recall that there was some searching being
> done a
> couple of years ago (I think), but I do not know what (if any) results were
> found?
>
> Regards,
>
> Paul.
>
 Please pardon my ignorance; I am here to learn to grow in my
knowledge of number theory. However, I will try to be more careful
in responding to posts before I have fully thought out my response 
you could extend me the same courtesy.
Your example of N=2^p + 12213 violates one of the two qualifications
that I laid down  "the equation cannot be reducible". I typically
would use this tenet for an equation like 4n + 1 (which does have
infinitely many primes in it)where n is odd. The tenet holds for
numbers of the form 2^p + n also, it just is usually harder to find
the pattern that this type of equation reduces to. In your example,
you provide the pattern which violates my first condition: that is
for 2, 3, 1 Mod 12, 5 Mod 12, 7 Mod 12, & 11 Mod 12; there a fixed
set of possible outcomes each of which will have fixed factors
depending upon which of the outcomes it fall under.
For instance, the equation 30Y + 35 = N generates infinitely many 5
Mod 6 numbers none of which are prime. This equation is easy since it
reduces to 5*(6Y + 7) = N; numbers of the form 2^p + N require a
deeper analysis as long as N itself does not have a factor of 2^p.
Just a few thoughts
Robert
 In primenumbers@y..., "jbrennen" <jack@b...> wrote:
>  In primenumbers@y..., "rlberry2002" <rlberry2002@y...> wrote:
> > Paul,
> >
> > I obviously misunderstood your equation; I read it as (2^p) + 3
> > where p=2,result 7; p=3, result 11, and so on.
>
> No, you got it right :)
>
> > I stand by my earlier statements (let's term it as Robert's
> > Conjecture) though: A one variable equation which, (a) does not
> > reduce and (b) contains infinitely many 1 Mod 6 and/or 5 Mod 6
> > numbers, will contain infinitely many prime numbers.
>
> See Sierpinski numbers for a wellknown counterexample:
> 78557*2^n+1 contains an infinite number of elements which are
> (5 mod 6), but has no prime numbers for any integer n.
>
> Back to the original question... There are easily found concrete
> examples of the form 2^p+n which do not have an infinite number of
> prime values (with p prime) despite having an infinite number of
> (1 mod 6) and (5 mod 6) numbers:
>
> N=2^p+12213 (with p prime) has no prime values whatsoever.
>
> This is because:
>
> If p == 2, N is divisible by 19
> If p == 3, N is divisible by 11
> If p == 1 (mod 12), N is divisible by 5
> If p == 5 (mod 12), N is divisible by 5
> If p == 7 (mod 12), N is divisible by 7
> If p == 11 (mod 12), N is divisible by 13
>
> Every prime p meets one of the six cases above, so N is never
> prime when p is prime.   rlberry2002 <rlberry2002@...> wrote:
> Please pardon my ignorance; I am here to learn to grow in my
I would trust that such courtesy is demonstrated on the list.
> knowledge of number theory. However, I will try to be more careful
> in responding to posts before I have fully thought out my response
>  you could extend me the same courtesy.
(Yeah, flame me off list, you won't be the first... (or the second)
:) )
> Your example of N=2^p + 12213 violates one of the two
Strictly, it is irreducible. The letter of the law is obeyed.
> qualifications
> that I laid down  "the equation cannot be reducible".
> I typically
Sure, but that's not redicibility. What Jack has highlighted is an
> would use this tenet for an equation like 4n + 1 (which does have
> infinitely many primes in it)where n is odd. The tenet holds for
> numbers of the form 2^p + n also, it just is usually harder to find
>
> the pattern that this type of equation reduces to. In your
> example,
> you provide the pattern which violates my first condition: that is
>
> for 2, 3, 1 Mod 12, 5 Mod 12, 7 Mod 12, & 11 Mod 12; there a fixed
> set of possible outcomes each of which will have fixed factors
> depending upon which of the outcomes it fall under.
intrinsically interesting property about that sequence of numbers.
This property will ba shared by an infinite number of other
sequences, not just the ...+12213. The property isn't reducibility,
and that term was used, it's a very precisely defined term, so Jack
and others can't be faulted for taking the term at face falue.
Perhaps the term "with no intrinsic predicatble factorisations" or
similar could be used to cover such concepts.
Such forms are certainly vastly interesting, the Sierpinski/Riesel
problems (that Jack mentioned, IIRC) are all about whether there are
primes with forms that have no intricsic predictable factorisations.
(hmmm, reminder to self or others  is there a link waiting to be
added to the yahoogroup regarding the Sierpinski/Riesel problems?)
Phil
__________________________________________________
Do You Yahoo!?
Yahoo! Health  your guide to health and wellness
http://health.yahoo.com  Phil,
As always, your comments and insights are welcome. I had to do a
little refresher myself on Sierpinski numbers: a positive, odd
integer k for which integers of the form k*2^p + 1 are all composite.
I would suggest that there is little here which serves as an adequate
counter example to the conjecture that I previously made.
First, for all k less than 78557, at least 1 prime has been found to
be generated by k*2^p + 1 with only 19 exceptions (and I feel it is
just that the first prime solution for these 19 k's has not yet been
found). It is only conjectured that k=78557 is a Sierpinski number.
It is likely that the smallest Sierpinski number (if indeed one does
exist) is so large that direct factorization, indirect factorization,
etc. will not be feasible. One final point concerning k=78557 will
show the difficulty in analyzing these numbers: For k=78557, p=300
you get a 95digit result. In other words, the 300th example for
k=78557 is already a number of such magnitude that only 1 number in
300 will be prime. Guess what the odds look like for the next 300
values of p.
Indeed, any series of numbers of the form k*N^p +/ c are very
difficult to analysis except with indirect methods.
Regards,
Robert
 In primenumbers@y..., Phil Carmody <thefatphil@y...> wrote:
>  rlberry2002 <rlberry2002@y...> wrote:
> > Please pardon my ignorance; I am here to learn to grow in my
> > knowledge of number theory. However, I will try to be more
careful
> > in responding to posts before I have fully thought out my response
> >  you could extend me the same courtesy.
>
> I would trust that such courtesy is demonstrated on the list.
> (Yeah, flame me off list, you won't be the first... (or the second)
> :) )
>
> > Your example of N=2^p + 12213 violates one of the two
> > qualifications
> > that I laid down  "the equation cannot be reducible".
>
> Strictly, it is irreducible. The letter of the law is obeyed.
>
> > I typically
> > would use this tenet for an equation like 4n + 1 (which does have
> > infinitely many primes in it)where n is odd. The tenet holds for
> > numbers of the form 2^p + n also, it just is usually harder to
find
> >
> > the pattern that this type of equation reduces to. In your
> > example,
> > you provide the pattern which violates my first condition: that
is
> >
> > for 2, 3, 1 Mod 12, 5 Mod 12, 7 Mod 12, & 11 Mod 12; there a
fixed
> > set of possible outcomes each of which will have fixed factors
> > depending upon which of the outcomes it fall under.
>
> Sure, but that's not redicibility. What Jack has highlighted is an
> intrinsically interesting property about that sequence of numbers.
> This property will ba shared by an infinite number of other
> sequences, not just the ...+12213. The property isn't reducibility,
> and that term was used, it's a very precisely defined term, so Jack
> and others can't be faulted for taking the term at face falue.
> Perhaps the term "with no intrinsic predicatble factorisations" or
> similar could be used to cover such concepts.
>
> Such forms are certainly vastly interesting, the Sierpinski/Riesel
> problems (that Jack mentioned, IIRC) are all about whether there are
> primes with forms that have no intricsic predictable factorisations.
>
> (hmmm, reminder to self or others  is there a link waiting to be
> added to the yahoogroup regarding the Sierpinski/Riesel problems?)
>
> Phil
>
> __________________________________________________
> Do You Yahoo!?
> Yahoo! Health  your guide to health and wellness
> http://health.yahoo.com  rlberry2002 wrote:
> As always, your comments and insights are welcome. I had to do a
We're glad you did a little research on Sierpinski numbers.
> little refresher myself on Sierpinski numbers: a positive, odd
> integer k for which integers of the form k*2^p + 1 are all composite.
> I would suggest that there is little here which serves as an adequate
> counter example to the conjecture that I previously made.
>
> First, for all k less than 78557, at least 1 prime has been found to
> be generated by k*2^p + 1 with only 19 exceptions (and I feel it is
> just that the first prime solution for these 19 k's has not yet been
> found). It is only conjectured that k=78557 is a Sierpinski number.
However, you must have missed something. It is PROVEN, and can be shown
using nothing more than very simple arithmetic, that k=78557 is
a Sierpinski number. The proof, in condensed form:
If n == 0 (mod 2), 78557*2^n+1 is divisible by 3
If n == 1 (mod 4), 78557*2^n+1 is divisible by 5
If n == 3 (mod 36), 78557*2^n+1 is divisible by 73
If n == 15 (mod 36), 78557*2^n+1 is divisible by 19
If n == 27 (mod 36), 78557*2^n+1 is divisible by 37
If n == 7 (mod 12), 78557*2^n+1 is divisible by 7
If n == 11 (mod 12), 78557*2^n+1 is divisible by 13
Every integer n satisfies one of these seven congruences.
The unproven conjecture is that k=78557 is the
*smallest* Sierpinski number.  Does the idea of 2^p+3 extend to 2^p3? I have found
that 2^2333 is PRP now p is of the form 60k7. Is
this just a coincedence or is there some sort of
pattern.
I haven't checked
2^233= a mod 233
2^(2^233)= 2^n mod a
Like Norman did for 2^p+3 with p=7 and 67
Gary
__________________________________________________
Do You Yahoo!?
Yahoo! Health  your guide to health and wellness
http://health.yahoo.com   Gary Chaffey <garychaffey@...> wrote:
> Does the idea of 2^p+3 extend to 2^p3? I have found
This can be checked as follows.
> that 2^2333 is PRP now p is of the form 60k7. Is
> this just a coincedence or is there some sort of
> pattern.
If 5  2^x3 then 2^x==3 (5) then x==3 (4)
If 7  2^x3 then 2^x==3 (7) no solution
If 11  2^x3 then 2^x==3 (11) then x==8 (10)
If 13  2^x3 then 2^x==3 (13) then x==4 (12)
...
These remove
3,7,11,15,19,23,27,31,35,39,43,47,51,55,59 (mod 60)
8 18 28 38 48 58 (mod 60)
4 16 28 40 52 (mod 60)
...
There are other primes that add to this mod 60 period, obviously.
Not every residue is removed, which leads me to suspect that 53 isn't
the only residue primes will be found along.
Phil
=====

"One cannot delete the Web browser from KDE without
losing the ability to manage files on the user's own
hard disk."  Prof. Stuart E Madnick, MIT.
So called "expert" witness for Microsoft. 2002/04/02
__________________________________________________
Do You Yahoo!?
Yahoo! Health  your guide to health and wellness
http://health.yahoo.com  A little reminder: if you find a PRP of the form
2^n3 or 2^n+3 (for any n, not just a prime) you may
have prospects of a BLS (which failing a KP) proof
by looking at work on factorization of Phi(2,k),
since, in *either* case, *both* N1 and N+1 are
algebraically factorizable into these intensively
studied base2 cyclotomic numbers:
http://www.cerias.purdue.edu/homes/ssw/cun/index.html
Apologies to those for whom this is blindingly obvious.
David Broadhurst
Your message has been successfully submitted and would be delivered to recipients shortly.