 mersenneforum.org > Math Any other primes in this sequence?
 Register FAQ Search Today's Posts Mark Forums Read  2006-02-20, 01:50 #1 brunoparga   Feb 2006 Brasília, Brazil 3·71 Posts 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.   2006-02-20, 10:06 #2 akruppa   "Nancy" Aug 2002 Alexandria 46438 Posts This is, in fact, a good question and well posed. Promoted to "Math". Unfortunately, I don't know the answer. Alex   2006-02-20, 11:18 #3 Greenbank   Jul 2005 1100000102 Posts [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   2006-02-20, 11:28 #4 Greenbank   Jul 2005 18216 Posts 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...   2006-02-20, 12:44 #5 Greenbank   Jul 2005 1100000102 Posts 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   2006-02-20, 14:21 #6 Greenbank   Jul 2005 2×193 Posts 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).   2006-02-20, 14:49   #7
John Renze

Nov 2005

24·3 Posts 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   2006-02-20, 16:29 #8 Greenbank   Jul 2005 6028 Posts Twice in one thread I manage to misread it. More coffee required. Apologies...   2006-02-21, 16:52   #9
maxal

Feb 2005

25210 Posts 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.   2006-02-21, 19:47 #10 akruppa   "Nancy" Aug 2002 Alexandria 1001101000112 Posts 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   2006-02-21, 20:00   #11
maxal

Feb 2005

FC16 Posts Quote:
 Originally Posted by akruppa I think 1552147 | P_20996011. Can you confirm?
I confirm that 1552147 divides P_20996011 + 1.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post emily Math 34 2017-07-16 18:44 sweety439 And now for something completely different 17 2017-06-13 03:49 carpetpool Miscellaneous Math 9 2017-03-17 22:57 PawnProver44 Homework Help 37 2016-03-19 15:43 jinydu Lounge 11 2009-06-06 16:40

All times are UTC. The time now is 14:35.

Fri Oct 22 14:35:35 UTC 2021 up 91 days, 9:04, 1 user, load averages: 1.85, 1.50, 1.38