mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-12-27, 17:52   #1
siegert81
 
Dec 2010

7410 Posts
Default Primorials squared primes?

Is there any sort of search for primes of the form (2*3*5*7*...*p)^2 + 1?

I noticed that projects search for both factorial and primorial primes, but I'm curious about squaring the primorial first, then adding one. Numbers of the form n^2 + 1 are only divisible by primes congruent to 1 mod 4. Wouldn't this imply that they are more frequently prime than the average number? Additionally, wouldn't it be easier to trial factor such numbers?

How about a modified "primorial" involving only two and the primes congruent to 1 mod 4? In other words, (2*5)^2 + 1 = 101 (a prime), (2*5*13)^2 + 1 = 16901 (a prime), (2*5*13*17)^2 + 1 = 4884101 (a prime), and so on.
siegert81 is offline   Reply With Quote
Old 2010-12-27, 18:27   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001001012 Posts
Default

Quote:
Originally Posted by siegert81 View Post
Is there any sort of search for primes of the form (2*3*5*7*...*p)^2 + 1?
None that I know of. 2, 3, 7, 11, 19, 53, 1571, ... are the initial p for which the numbers are prime (cf. Sloane's A092061; the next p must be at least 19139, corresponding to a 16422-digit number). There should be about a
\frac{e^\gamma\log p}{p-1}
chance for p#^2 + 1 to be prime, so there should be something like
\log x-1/2\cdot\log\log x
primes up to x#^2 + 1.

Quote:
Originally Posted by siegert81 View Post
Numbers of the form n^2 + 1 are only divisible by primes congruent to 1 mod 4. Wouldn't this imply that they are more frequently prime than the average number?
I'm not sure. The effect of "no small primes divide the number" is surely much larger.

Quote:
Originally Posted by siegert81 View Post
Additionally, wouldn't it be easier to trial factor such numbers?
You could trial factor almost twice as quickly, so factoring to (say) 40 bits would only take a little longer than factoring a 'normal' number to 39 bits.

Last fiddled with by CRGreathouse on 2010-12-27 at 18:59
CRGreathouse is offline   Reply With Quote
Old 2010-12-27, 18:49   #3
axn
 
axn's Avatar
 
Jun 2003

111318 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
The p here are 2, 5, 11, 17, 23, 59, 67, ...; I'd be surprised if this was in the OEIS.
2,5,13,17,101,181,277,593,641,1733
axn is offline   Reply With Quote
Old 2010-12-27, 18:59   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default

Quote:
Originally Posted by axn View Post
2,5,13,17,101,181,277,593,641,1733
Oops, I misread the requirements.
CRGreathouse is offline   Reply With Quote
Old 2010-12-27, 19:42   #5
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

EAA16 Posts
Default

Quote:
Originally Posted by siegert81 View Post
Is there any sort of search for primes of the form (2*3*5*7*...*p)^2 + 1?

I noticed that projects search for both factorial and primorial primes, but I'm curious about squaring the primorial first, then adding one. Numbers of the form n^2 + 1 are only divisible by primes congruent to 1 mod 4. Wouldn't this imply that they are more frequently prime than the average number? Additionally, wouldn't it be easier to trial factor such numbers?

How about a modified "primorial" involving only two and the primes congruent to 1 mod 4? In other words, (2*5)^2 + 1 = 101 (a prime), (2*5*13)^2 + 1 = 16901 (a prime), (2*5*13*17)^2 + 1 = 4884101 (a prime), and so on.
I think you will find the paper Prime Number Races by Andrew Granville and Greg Martin very interesting. Although very clearly presented, I don't feel capable of abstracting the information properly. It also explains a logarithmic measure that seems more suited in studying the situation. Applying this measure, according to a theorem by Rubinstein and Sarnak, quoted therein, there are more primes of the form 4n + 3 than the form 4n +1 summed up to some x, 99.59% of the time. I don't have a proper link for the paper but Google seems to have a few.
only_human is offline   Reply With Quote
Old 2010-12-28, 07:23   #6
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2×1,877 Posts
Default

Quote:
Originally Posted by siegert81 View Post
Numbers of the form n^2 + 1 are only divisible by primes congruent to 1 mod 4. Wouldn't this imply that they are more frequently prime than the average number? Additionally, wouldn't it be easier to trial factor such numbers?
I understand that you intend n to be even here. Although these generated numbers may be divisible by primes congruent to 1 mod 4, might they also be divisible by a even number of primes congruent to -1 mod 4?
only_human is offline   Reply With Quote
Old 2010-12-28, 15:17   #7
axn
 
axn's Avatar
 
Jun 2003

7·11·61 Posts
Default

Quote:
Originally Posted by only_human View Post
I understand that you intend n to be even here. Although these generated numbers may be divisible by primes congruent to 1 mod 4, might they also be divisible by a even number of primes congruent to -1 mod 4?
No. They are GFNs -- b^(2^n)+1 -- and hence divisibility rules for Fermat numbers apply, i.e. factors must be of the form k.2^(n+1)+1
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
The factorization of primorials +/- 1 Joppe_Bos Factoring 67 2008-01-29 13:51
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35
Factors of primorials grandpascorpion Math 9 2005-02-10 07:13

All times are UTC. The time now is 20:44.

Fri Sep 25 20:44:17 UTC 2020 up 15 days, 17:55, 0 users, load averages: 1.37, 2.12, 2.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.