Right Perfect Prime Numbers
 

If P is an even perfect number greater than 6, P-1 is always composite divisible by nine. Is it known which perfect numbers are prime for P+1?

[QUOTE=Housemouse;134548]If P is an even perfect number greater than 6, P-1 is always composite divisible by nine. Is it known which perfect numbers are prime for P+1?[/QUOTE]

Clearly not. We don't even know whether the Mersenne primes are
infinite in number.

[QUOTE=Housemouse;134548]If P is an even perfect number greater than 6, P-1 is always composite divisible by nine. Is it known which perfect numbers are prime for P+1?[/QUOTE]

[URL="http://www.research.att.com/~njas/sequences/A061644"]http://www.research.att.com/~njas/sequences/A061644[/URL]

yes
 

6 (7)
29 (29)
33550336 (33550337)
are Prime

496 (497)
8128 (8129)
8589869056 (8589869057)
are Composite

That is as far as I checked

I trialfactored P+1 for the 44 known perfect numbers P and did ECM on 1 of them:

[U]p: factor(s) of 2[sup]p-1[/sup]*(2[sup]p[/sup]-1) + 1[/U]
2: prime
3: prime
5: 7,71
7: 11,739
13: prime
17: 7,11,111556741
19: prime
31: 29,71,137,1621,5042777503
61: 2432582681,1092853292237112554142488617
89: 7
107: 7,11,67
127: 11,107,261697
521: 7,71
607: 11
1279: 72353441721527140856665601867
2203: 60449,1498429,711309659
2281: 197,557,1999,92033
3217: 11
4253: 7,53,8731,2353129,50820071
4423: 2163571
9689: 7,211,49922567
9941: 7,67,1605697,194147011
11213: 7
19937: 7,11,1129,168457
21701: 7
23209: 35603,620377
44497: 11,13259,16177141,896297147
86243: 7,29,301123,26072029
110503: 491,1493,1529761
132049: ?
216091: 4673,6920341
756839: 7
859433: 7
1257787: 11
1398269: 7,53,12713,17425081,199979189
2976221: 7,71
3021377: 7,11,49603
6972593: 7,6007,8392897,52193821
13466917: 11,45007
20996011: 1552147,114242767
24036583: 149
25964951: 7
30402457: 11
32582657: 7,11,67,34549,127541

So perfectnumber+1 are prime for p=2,3,13 and 19 and unknown for p=132049 (79502 digits) which I trialfactored to 18*10[sup]9[/sup].

[QUOTE=ATH;134626]
So perfectnumber+1 are prime for p=2,3,13 and 19 and unknown for p=132049 (79502 digits) which I trialfactored to 18*10[sup]9[/sup].[/QUOTE]

Please note that if N=2^(p-1)*(2^p-1)+1 (where Mp=2^p-1 is a Mersenne prime), then the primefactorization of N-1 is known so a quick exact primetest is possible.

[quote=ATH;134626]I trialfactored P+1 for the 44 known perfect numbers P and did ECM on 1 of them:

[U]p: factor(s) of 2[sup]p-1[/sup]*(2[sup]p[/sup]-1) + 1[/U]
2: prime
3: prime
5: 7,71
7: 11,739
13: prime
17: 7,11,111556741
19: prime
31: 29,71,137,1621,5042777503
61: 2432582681,1092853292237112554142488617
89: 7
107: 7,11,67
127: 11,107,261697
521: 7,71
607: 11
1279: 72353441721527140856665601867
2203: 60449,1498429,711309659
2281: 197,557,1999,92033
3217: 11
4253: 7,53,8731,2353129,50820071
4423: 2163571
9689: 7,211,49922567
9941: 7,67,1605697,194147011
11213: 7
19937: 7,11,1129,168457
21701: 7
23209: 35603,620377
44497: 11,13259,16177141,896297147
86243: 7,29,301123,26072029
110503: 491,1493,1529761
132049: ?
216091: 4673,6920341
756839: 7
859433: 7
1257787: 11
1398269: 7,53,12713,17425081,199979189
2976221: 7,71
3021377: 7,11,49603
6972593: 7,6007,8392897,52193821
13466917: 11,45007
20996011: 1552147,114242767
24036583: 149
25964951: 7
30402457: 11
32582657: 7,11,67,34549,127541

So perfectnumber+1 are prime for p=2,3,13 and 19 and unknown for p=132049 (79502 digits) which I trialfactored to 18*10[sup]9[/sup].[/quote]
gmp-ecm doesnt think p=132049 is prp

[QUOTE=henryzz;134683]gmp-ecm doesnt think p=132049 is prp[/QUOTE]

If you follow the link given at the site given by R. Gerbicz,
[url]http://www.primepuzzles.net/puzzles/puzz_203.htm[/url] ,
you will see that PrimeForm agrees with gmp-ecm on this.

Question solved.

I found a factor of 2[sup]p-1[/sup]*(2[sup]p[/sup]-1) + 1 for p=132049 with gmp-ecm:
194528547122653

So of the 44 known perfect numbers P=2[sup]p-1[/sup]*(2[sup]p[/sup]-1), P+1 is only prime for p=2,3,13 and 19.

Updated list:

[CODE][B]p: factor(s) of 2[sup]p-1[/sup]*(2[sup]p[/sup]-1) + 1[/B]
------------------------------------------------------------------
2: prime
3: prime
5: 7 , 71
7: 11 , 739
13: prime
17: 7 , 11 , 111556741
19: prime
31: 29 , 71 , 137 , 1621 , 5042777503
61: 2432582681 , 1092853292237112554142488617
89: 7
107: 7 , 11 , 67
127: 11 , 107 , 261697
521: 7 , 71
607: 11
1279: 72353441721527140856665601867
2203: 60449 , 1498429 , 711309659, 1418050069
2281: 197 , 557 , 1999 , 92033
3217: 11
4253: 7 , 53 , 8731 , 2353129 , 50820071
4423: 2163571
9689: 7 , 211 , 49922567
9941: 7 , 67 , 1605697 , 194147011
11213: 7
19937: 7 , 11 , 1129 , 168457
21701: 7
23209: 35603 , 620377
44497: 11 , 13259 , 16177141 , 896297147
86243: 7 , 29 , 301123 , 26072029
110503: 491 , 1493 , 1529761
132049: 194528547122653
216091: 4673 , 6920341
756839: 7
859433: 7
1257787: 11
1398269: 7 , 53 , 12713 , 17425081 , 199979189
2976221: 7 , 71
3021377: 7 , 11 , 49603
6972593: 7 , 6007 , 8392897 , 52193821
13466917: 11 , 45007
20996011: 1552147 , 114242767
24036583: 149
25964951: 7
30402457: 11
32582657: 7 , 11 , 67 , 34549 , 127541
37156667: 7 , 11 , 44753 , 202577 , 1282451377
42643801: 3593 , 7089208037
43112609: 7 , 211 , 70121 , 71647 , 1846524311
57885161: 7 , 22127627
74207281: No factor < 6*10[sup]12[/sup]
77232917: 7 , 11 , 11587
82589933: 7 , 67 , 599 , 7347113 , 14416229
[/CODE]

So of the now 51 known perfect numbers P=2[sup]p-1[/sup]*(2[sup]p[/sup]-1), P+1 is only still prime for p=2,3,13 and 19, and status unknown for p=74207281.

Can we extend this?

[B]p: factor(s) of 2p-1*(2p-1) + 1[/B]
57885161: [B]7[/B]
74207281: ?

/JeppeSN

[QUOTE=JeppeSN;423710]Can we extend this?

[B]p: factor(s) of 2p-1*(2p-1) + 1[/B]
57885161: [B]7[/B]
74207281: ?

/JeppeSN[/QUOTE]

Update:

42643801: 3593, 7089208037
43112609: 7, 211, 70121, 71647, 1846524311 (was in 2008 post by ATH)
57885161: 7, 22127627
74207281: ?

My trial factoring with the latest perfect number, incremented by one, has not yielded any divisors under $75\cdot 10^9$.

/JeppeSN

Yeah for 57885161 there is also a factor: 22127627.

For p=74207281, I trial factored 2[sup]p-1[/sup]*(2[sup]p[/sup]-1) + 1 up to 4.46*10[sup]12[/sup] with no factor.

[QUOTE=ATH;423758]For p=74207281, I trial factored 2[sup]p-1[/sup]*(2[sup]p[/sup]-1) + 1 up to 4.46*10[sup]12[/sup] with no factor.[/QUOTE]

Do you know if anyone is going further with trial factoring this beast, $2^{74207280}(2^{74207281}-1)+1$, or even do a primality test of it? It may turn out to be very hard to find a prime factor for this one? /JeppeSN

Yeah the chance of finding a factor is very low, and doing a primality test is impossible. At 44.7 million digits only an LL test would be fast enough but it will not work on a number of this form. There is no software I can think of that can even do a PRP test.

Anyway these numbers are not really that important I think, it was just a question a user asked almost 8 years ago which turned into this tiny trial factoring effort. I have never seen any interest in "perfect numbers + 1" anywhere else.

As R. Gerbicz said in his last post to this thread, an [URL="http://primes.utm.edu/prove/prove3_1.html"]n-1 test[/URL] should be possible. /JeppeSN

Yes true, but that was for 79502 digits. I do not think programs like PFGW, which can do the N-1 test, can handle 44 million digits or anywhere near this size.

A 44 million digit LL test would take 10-14 days on the very fastest computers / graphic cards with Prime95 / CudaLucas, and an N-1 test would take longer than that. I do not think PFGW can save the test during it and restart, but I'm not certain about that.

[QUOTE=ATH;424260]Yes true, but that was for 79502 digits. I do not think programs like PFGW, which can do the N-1 test, can handle 44 million digits or anywhere near this size.
[/QUOTE]
PFGW can. The limit is the same (gwnum library is the same) - FFT max size of 32M which is more than enough, but...
[QUOTE=ATH;424260]A 44 million digit PRP [STRIKE]LL[/STRIKE] test would take [STRIKE][COLOR=DarkRed]10-14[/COLOR][/STRIKE] days on the very fastest computers [STRIKE]/ graphic cards[/STRIKE] with Prime95 [STRIKE]/ CudaLucas[/STRIKE], and an N-1 test would take longer than that. I do not think PFGW can save the test during it and restart, but I'm not certain about that.[/QUOTE]
Because of the form of the number, LL test has no relevance and fast special FFT is inapplicable, so you can safely triple the estimate (and much more than triple if you only use single thread with a vanilla binary). PFGW is single-thread, but you can try to rig Prime95's multithreaded code on zero-padded FFT and write a custom mod step (2^N-2^M+1 is much better than a general number).

[QUOTE=Batalov;424267]PFGW can. The limit is the same (gwnum library is the same) - FFT max size of 32M which is more than enough, but...

Because of the form of the number, LL test has no relevance and fast special FFT is inapplicable, so you can safely triple the estimate (and much more than triple if you only use single thread with a vanilla binary). PFGW is single-thread, but you can try to rig Prime95's multithreaded code on zero-padded FFT and write a custom mod step (2^N-2^M+1 is much better than a general number).[/QUOTE]
Based upon my fiddling with PFGW the FFT length would be probably be 4x as large as the mersenne prime. It would also be general reduction as well.
Possible if someone wants to spend several months on it I think.

On my Windows system, it crashes.

I try with:

[CODE]
.\pfgw64.exe -q"2^74207280*(2^74207281-1)+1" -t -f0 -h"jeppe_M74207281.txt"
[/CODE]where -t should enforce a deterministic N-1 test, -f0 should skip factoring, and the jeppe_M74207281.txt is a local help file containing just one line with 2^74207281-1 on it. The help file is for making PFGW quickly realize it has the full factorization of N-1 (our even perfect number). Apparently, PFGW does not read news sites on the web telling about the recent discovery of M74207281, so I will have to help it.

pfgw32.exe with the same parameters crashes as well, on my machine here.

Using the binaries from .7z file here: [URL]http://sourceforge.net/projects/openpfgw/[/URL]

Can anyone else get to a point where the N-1 test actually progresses?

/JeppeSN

It is much quicker to run a default 3-PRP test, rather than a fully blown N-1 test. If that goes fine, I am sure the authors will fix up PFGW for you :wink:

Here, I would run on linux: [c]./pfgw64 -q"2^74207280*(2^74207281-1)+1" -f0[/c]

The chance it will be prime is next to zero, but you will know! :smile:

Maybe it is smarter to sieve even further before attempting a PRP or primality test. After all, what we want to add to ATH's table above is the smallest prime factor, and it is too optimistic to hope the primality test will result in N being its own smallest prime factor. /JeppeSN

Much further. Of course.

Re: PFGW: Yes, one can try smaller members simply to see that the FFT size tends to be ~3.75-4 times larger. For P74207281, after long initialization the process takes off:
[CODE]No factoring at all, not even trivial division
Generic modular reduction using generic reduction FMA3 FFT length 16000K, Pass1=640, Pass2=25K on A 148414563-bit number
PRP: 2^148414561-2^74207280+1 35000/148414560[/CODE]

[QUOTE=Batalov;424320]Much further. Of course.

Re: PFGW: Yes, one can try smaller members simply to see that the FFT size tends to be ~3.75-4 times larger. For P74207281, after long initialization the process takes off:
[CODE]No factoring at all, not even trivial division
Generic modular reduction using generic reduction FMA3 FFT length 16000K, Pass1=640, Pass2=25K on A 148414563-bit number
PRP: 2^148414561-2^74207280+1 35000/148414560[/CODE][/QUOTE]

What command line did you use? :smile:

[QUOTE=Batalov;424320]Much further. Of course.

Re: PFGW: Yes, one can try smaller members simply to see that the FFT size tends to be ~3.75-4 times larger. For P74207281, after long initialization the process takes off:
[CODE]No factoring at all, not even trivial division
Generic modular reduction using generic reduction FMA3 FFT length 16000K, Pass1=640, Pass2=25K on A 148414563-bit number
PRP: 2^148414561-2^74207280+1 35000/148414560[/CODE][/QUOTE]

Interesting. PFGW crashes for me trying to run that same expression. Tried both 3.7.7 and 3.7.10.

You'd need quite a bit of free memory (perhaps for the first, "giants", step; it can also be the reason for a very low start; "giants" object is created first and then converted to a gwnum object and may be used for the mod step; for a faster implementation, this needs to be custom written inside the code), maybe this is why it is crashes for you guys.

I've used three ways, and all worked (all on linux, can't vouch for W!ndows).
One (common with trying LLR*):
File a.abc
[CODE]ABC $a^$b-$a^$c+1
2 148414561 74207280[/CODE]And then ./pfgw -f0 -V -N -l a.abc and/or ./sllr -d a.abc.
Another, ./pfgw -f0 -V -N -q"2^148414561-2^74207280+1" (works, too).
Third one, ./pfgw -f0 -V -N -t -hhelper -q"2^148414561-2^74207280+1" (where helper file has 2^74207281-1 in it)

________________
*LLR turns out to be not immediately helpful for the purpose of the N-1 proof because it implements a >50% proof only (a k*2^n+1 approach with desired k < 2^n).

I'll try those. I tried "pfgw64.exe -f0 -q"2^148414561-2^74207280+1" on Windows 7 boxes with 32GB and 16GB respectively. Watching Task Manager, the process never pulled more than about 1 GB of RAM for use.

It's not a big deal, obviously, but now I'm just curious. :smile:

Edit: Yeah, none of those worked for me (pfgw or llr). I guess I'll stick to slightly lower numbers then. :smile:

It [B]does[/B] segfault on Windows. What a [URL="http://mersenneforum.org/showthread.php?p=424098#post424098"]terribly written program[/URL]!! :tantrum:
[QUOTE]...unfortunate, but I suppose state of the art [STRIKE]factoring [/STRIKE]primality software is unlikely to win any awards for user friendliness.[/QUOTE]:kracker:

It's all good. This is the first issue I've run into with it after a good amount of use, so I'd say it's doing alright. :tu:

Of course! Mark is also very helpful,; the only wrinkle I thought of was that he doesn't read every thread (not that I blame him), so I PM'd him with a link, too. Undoubtedly this will get fixed.

I finally read Batalov's PM. I'll see what I can do.

As for pfgw being "terribly written", I would agree. The code base is very convoluted. I have considered rewriting the program, but that would probably take months.

[QUOTE=rogue;424393]I finally read Batalov's PM. I'll see what I can do.

As for pfgw being "terribly written", I would agree. The code base is very convoluted. I have considered rewriting the program, but that would probably take months.[/QUOTE]

What would it take to add gwnum multithreading for prp testing? Is it a case of using different gwnum functions?

[QUOTE=henryzz;424400]What would it take to add gwnum multithreading for prp testing? Is it a case of using different gwnum functions?[/QUOTE]

I'm not familiar with that feature of gwnum.

I have good news and bad news. The good news is that I have been able to reproduce the problem on Windows. The bad news is that the bug is causing memory to be overwritten so the call stack is lost. It says the memcpy is to blame, but it is not one of the many calls to memcpy in the application. I suspect that an assignment is calling memcpy under the covers. This will take a lot more work to debug. Ugh!

[QUOTE=rogue;424451]I'm not familiar with that feature of gwnum.

I have good news and bad news. The good news is that I have been able to reproduce the problem on Windows. The bad news is that the bug is causing memory to be overwritten so the call stack is lost. It says the memcpy is to blame, but it is not one of the many calls to memcpy in the application. I suspect that an assignment is calling memcpy under the covers. This will take a lot more work to debug. Ugh![/QUOTE]

I think it might be as simple as calling gwset_num_threads before gwsetup. This information is in gwnum.h

Does anyone need this to be fixed on Windows? I finally have some time to look into it, but knowing that this will be painful to debug, I'm not overly excited about looking into it. I suspect this is a problem with heap space needed by GMP.