mersenneforum.org > Math Primorials squared primes?
 Register FAQ Search Today's Posts Mark Forums Read

 2010-12-27, 17:52 #1 siegert81   Dec 2010 2×37 Posts 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.
2010-12-27, 18:27   #2
CRGreathouse

Aug 2006

2·2,963 Posts

Quote:
 Originally Posted by siegert81 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 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 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

2010-12-27, 18:49   #3
axn

Jun 2003

22·11·107 Posts

Quote:
 Originally Posted by CRGreathouse 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

2010-12-27, 18:59   #4
CRGreathouse

Aug 2006

2×2,963 Posts

Quote:
 Originally Posted by axn 2,5,13,17,101,181,277,593,641,1733

2010-12-27, 19:42   #5
only_human

"Gang aft agley"
Sep 2002

3,581 Posts

Quote:
 Originally Posted by siegert81 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.

2010-12-28, 07:23   #6
only_human

"Gang aft agley"
Sep 2002

DFD16 Posts

Quote:
 Originally Posted by siegert81 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?

2010-12-28, 15:17   #7
axn

Jun 2003

126416 Posts

Quote:
 Originally Posted by only_human 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

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 Joppe_Bos Factoring 67 2008-01-29 13:51 troels munkner Miscellaneous Math 4 2006-06-02 08:35 grandpascorpion Math 9 2005-02-10 07:13

All times are UTC. The time now is 05:33.

Wed Oct 21 05:33:10 UTC 2020 up 41 days, 2:44, 0 users, load averages: 1.37, 1.46, 1.45