mersenneforum.org  

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

Reply
 
Thread Tools
Old 2006-02-20, 01:50   #1
brunoparga
 
brunoparga's Avatar
 
Feb 2006
Brasília, Brazil

3×71 Posts
Default Any other primes in this sequence?

Hi everyone! What I have here is just a simple and humble curiosity. I'm not a native English speaker nor a mathematician, not even a college level student at that. So please forgive me for any mistakes in spelling, grammar etc. and also in mathematical terms, concepts and symbols. Please do correct me too if I'm wrong, as I really want to learn.

Once again, I don't know if I'm using the correct language and math symbols here. But while I don't know exactly how to call these numbers, I'll call P_p the perfect number you get by multiplying the Mersenne prime M_p (with exponent p) by 2^(p-1). Thus P_2 = 6, P_3 = 28, P_4=496 and so on. (the idea here is that the appropriate letters and numbers are subscript, sorry if they aren't)

My question is: besides P_2 + 1 = 7, P_3 + 1 = 29, P_13 + 1 = 33550337 and P_19 + 1 = 137438691329, are there any other primes with the form P_p + 1? I mean, any other integers immediately following the (even) perfect numbers in the logical sequence of the integers (1, 2, 3, 4, 5...) which are prime?

I've tried to check these numbers here (http://primes.utm.edu/curios/include...primetest.html) and here (http://www.alpertron.com.ar/ECM.HTM). Sorry I still don't know how to input links, but those are Chris Caldwell's Prime Pages and Dario Alpern's ECM factoring applet. I've tried to factor all the even perfect numbers up to P_11213; does anyone know if are there any primes for Mersennes larger that M23? It is also possible I've missed some prime there, I may have mistyped some formula.

Another question, whose answer will most probably involve number and group theories I'm completely clueless about, but I'll ask it anyway: I think I've read somewhere in these forums that it's relatively simple to check if a number P is prime if we know all of the factors of P-1 (I'm clueless because I have no idea why that is true). But since we know all factors in the numbers I've mentioned, is it simple to check them for primality? Could someone please explain to me if there's some way to prove there can't be any more primes in this form, or something like that?

Sorry for the long and repetitive post, I just wanted to be sure I was minimally clear.
brunoparga is offline   Reply With Quote
Old 2006-02-20, 10:06   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246410 Posts
Default

This is, in fact, a good question and well posed. Promoted to "Math". Unfortunately, I don't know the answer.

Alex
akruppa is offline   Reply With Quote
Old 2006-02-20, 11:18   #3
Greenbank
 
Greenbank's Avatar
 
Jul 2005

6028 Posts
Default

[EDIT] - I may have this wrong. I'm using the definition that P_n = ((2^n)-1)*(2^(n-1))
Hope that is what you meant, I'm slightly hungover today and my brain hasn't started working fully (despite it being 11am and I've been at work for 2 hours).

Ok, here's how it goes after P_19:-

P_45+1 is prime, but 45 is not.
P_46+1 is prime, but 46 is not.
P_58+1 is prime, but 58 is not.
P_141+1 is prime, but 141 is not.
P_271+1 is prime AND 271 is prime! (163 digits)
P_336+1 is prime, but 336 is not.

At this point I've stopped doing primality testing on P_n and do Fermat Pseudoprimes for all prime bases below 100, not much should slip through that but you can't be 100% sure. Following link has more info:-

http://mathworld.wolfram.com/FermatPseudoprime.html

P_562+1 is a strong-pseudoprime, but 562 is not prime.
P_601+1 is a strong-pseudoprime AND 601 is prime! (362 digits)
P_1128+1 is a strong-pseudoprime, but 1128 is not prime.
P_1635+1 is a strong-pseudoprime, but 1635 is not prime.
P_2718+1 is a strong-pseudoprime, but 2718 is not prime.
P_2920+1 is a strong-pseudoprime, but 2920 is not prime.

That's it until n=3000.

Last fiddled with by Greenbank on 2006-02-20 at 11:22
Greenbank is offline   Reply With Quote
Old 2006-02-20, 11:28   #4
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

OK, I've re-read it and I understand it now. You only care about P_n where n is the exponent of a known Mersenne prime.

I'll have another look at this...
Greenbank is offline   Reply With Quote
Old 2006-02-20, 12:44   #5
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default

Mersenne exponents from: http://mathworld.wolfram.com/MersennePrime.html

P_2 + 1 = 7 = prime
P_3 + 1 = 29 = prime
P_5 + 1 = 497 = 7 * 71
P_7 + 1 = 8129 = 11 * 739
P_13 + 1 = 33550337 = prime
P_17 + 1 = 8589869057 = 7 * 11 * 111556741
P_19 + 1 = 137438691329 = prime
P_31 + 1 = 2305843008139952129 = 29 * 71 * 137 * 1621 * 5042777503
P_61 + 1 = 2432582681 * 1092853292237112554142488617
P_89 + 1 = 7 * 132599200423201647070231067 * 206381273143696885332153493
P_107 + 1 = 7 * 11 * 11 * 67 * prp60.
P_127 + 1 = 11 * 107 * 261697 * 70333627629913 * prp54.
P_521 + 1 = 7 * 71 * 1050252439763 * c299
:run 77 ECM curves at 11000:1600000)
:running 206 ECM curves at 50000:14000000 (25 digits)
P_607 + 1 = 11 * prp365
P_1279 + 1 = ????
:run 77 ECM curves at 11000:1600000)
:running 206 ECM curves at 50000:14000000 (25 digits)
P_2203 + 1 = 60449 * 1498429 * ????
P_2281 + 1 = 197 * 557 * 1999 * 92033 * ????
P_3217 + 1 = 11 * ????
P_4253 + 1 = 7 * 53 * 8731 * 2353129 * ????
P_4423 + 1 = 2163571 * ????
P_9689 + 1 = 7 * 211 * ????
P_9941 + 1 = 7 * 67 * 1605697 * ????
P_11213 + 1 = 7 * ????
P_19937 + 1 = 7 * 11 * 1129 * 168457 * ????
P_21701 + 1 = 7 * ????
P_23209 + 1 = 35603 * 620377 * ????
P_44497 + 1 = 11 * 13259 * ????
P_86243 + 1 = 7 * 29 * 301123 * ????
P_110503 + 1 = 491 * 1493 * 1529761 * ????
P_132049 + 1 = ????
P_216091 + 1 = 4673 * 6920341 * ????
P_756839 + 1 = 7 * ????
P_859433 + 1 = 7 * ????
P_1257787 + 1 = 11 * ????
P_1398269 + 1 = 7 * 53 * 12713 * ????
P_2976221 + 1 = 7 * 71 * ????
P_3021377 + 1 = 7 * 11 * 49603 * ????
P_6972593 + 1 = 7 * 6007 * ????
P_13466917 + 1 = 11 * 45007 * ????
P_20996011 + 1 = ????
P_24036583 + 1 = 149 * ????
P_25964951 + 1 = 7 * ????
P_30402457 + 1 = 11 * 11 * ????

So, you can see that I have factors for all numbers except P_1279+1, P_132049+1 and P_20996011+1. Looking for these with ECM (15 digit, 20 digit, 25 digit) although P_20996011 is a big number (12640858 digits!)

As for knowing the factors of p-1 helping find p, no it doesn't.

Two ways of thinking about it:

1) If the factorisation of p-1 helped to factor p then we could simply find the factors of p-1 by looking at the factors of p-2. The factors of p-2 could be found with the help of the factors of p-3...etc...etc...This doesn't even touch on the fact that every time you have an even number you can remove all powers of 2 from it to get a smaller odd number.

2) Consider factoring p+1 where p is prime. How does one big prime factor (p-1) help at all?

You may be thinking of p-1 factoring. The p-1 bit refers to factors, not the number you are trying to factor.

See: http://mathworld.wolfram.com/Pollard...ionMethod.html
and: http://en.wikipedia.org/wiki/Pollard%27s_p-1_algorithm
Greenbank is offline   Reply With Quote
Old 2006-02-20, 14:21   #6
Greenbank
 
Greenbank's Avatar
 
Jul 2005

18216 Posts
Default

I've done ECM on 1279 up to, and including, the 25 digit level. Going for the 30 digit level (401 curves at B1=25e4 B2=1.7e8).
Greenbank is offline   Reply With Quote
Old 2006-02-20, 14:49   #7
John Renze
 
John Renze's Avatar
 
Nov 2005

24·3 Posts
Default

Quote:
Originally Posted by brunoparga
...it's relatively simple to check if a number P is prime if we know all of the factors of P-1.
This is correct. A description of the test can be found at http://primes.utm.edu/prove/prove3_1.html

Quote:
Originally Posted by Greenbank
As for knowing the factors of p-1 helping find p, no it doesn't.
Greenbank, I think you may have misread the post. The question was about primality proving, not factoring.

John
John Renze is offline   Reply With Quote
Old 2006-02-20, 16:29   #8
Greenbank
 
Greenbank's Avatar
 
Jul 2005

38610 Posts
Default

Twice in one thread I manage to misread it. More coffee required. Apologies...
Greenbank is offline   Reply With Quote
Old 2006-02-21, 16:52   #9
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by Greenbank
So, you can see that I have factors for all numbers except P_1279+1, P_132049+1 and P_20996011+1.
With the help of Pari/GP I confirm that P_1279+1 and P_132049+1 are NOT prime.
maxal is offline   Reply With Quote
Old 2006-02-21, 19:47   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000002 Posts
Default

I think 1552147 | P_20996011 + 1. Can you confirm?

Alex

Last fiddled with by akruppa on 2006-02-21 at 20:03 Reason: +1 missing
akruppa is offline   Reply With Quote
Old 2006-02-21, 20:00   #11
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by akruppa
I think 1552147 | P_20996011. Can you confirm?
I confirm that 1552147 divides P_20996011 + 1.
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
Primes in A048788 OEIS Sequence carpetpool Miscellaneous Math 9 2017-03-17 22:57
Sequence of primes formation PawnProver44 Homework Help 37 2016-03-19 15:43
Will GIMPS Ever Discover Two Primes Out of Sequence? jinydu Lounge 11 2009-06-06 16:40

All times are UTC. The time now is 02:07.

Thu Nov 26 02:07:04 UTC 2020 up 76 days, 23:18, 3 users, load averages: 1.02, 1.17, 1.21

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.