Primes of the form 'perfect number' + 1 (a.k.a. RPN)

[bur]

Originally Posted by Batalov

This is, as some folks say, "not even wrong".

Maybe there's some sarcasm that eludes me, but isn't it correct that they have a low weight? If it was just a hint that it's trivially true, then one man's trivia is another man's <opposite of trivia>.

[Batalov]

Originally Posted by bur

Maybe there's some sarcasm that eludes me, but isn't it correct that they have a low weight? If it was just a hint that it's trivially true, then one man's trivia is another man's <opposite of trivia>.

No sarcasm - it is a standard synonym for a non-sequitur, attributed to Pauli, the physicist:

Quite recently, a friend showed him the paper of a young physicist which he suspected was not of great value but on which he wanted Pauli’s views. Pauli remarked sadly ‘It is not even wrong.’

Hints? ok, sure -

1. There is no weight or even a concept of weight for this sequence. Weight is an estimate of yield by test-sieving for a range of n's for a given k. It is like saying "John travelled from Newark to Philadelphia with an average speed of 55 mph. Therefore his speed at the specific light intersection in Edison, NJ was 55 mph." No it wasn't. That average speed has no predction value for the specific speed exactly at that light (and that intersection is the only point of interest - because in this thread k is tied to n; there is only one value!). The speed at that intersection could have been 0 mph for a minute if the light was red; it could have been 40 mph if the light was green. It has nothing to do with the quality, brand or model of that John's car. Or with his average speed over that drive.

2. "k is a large prime" has no association with low or high weight. It could have been high, it could have been low. Test them! (only for disproving "k is a large prime means low weight"; it doesn't). Thought this is meaningless anyway because of see #1.

3. The whole concept of "Proth weight" is out of the window here as well, because these are not Proth (because k > 2^n).

Enough reasons?

[Neptune]

Thanks for all those links.


There was so much written on this subject, I appreciate that.

3. The whole concept of "Proth weight" is out of the window here as well, because these are not Proth (because k > 2^n).

"Right perfect numbers" are not even of Proth type, I regret. But a N-1 primality test is still possible.


We don't know much about the factors of those numbers. Ken Wilke showed some dependencies.



For P_49* we have to trial divide all small primes until we find a factor or perform a costly N-1 / PRP test, right?

Thanks to ATH who has done a great job searching for factors below 6*10¹².

A small function in Pari/GP to find a factor could look like this:

tdiv(s,b1,b2)={my(a);s--;forprime(p=b1,b2,a=Mod(2,p)^s;if(!Mod(2*a*a-a+1,p),return(p)))};

Maybe there are better methods, in case please let me know.

I'm running

tdiv(74207281,6*10^12,10^13)

to test P_49* between 6*10¹² and 10¹³.

There is a small chance that a factor is found.

[Batalov]

Originally Posted by Neptune

A small function in Pari/GP to find a factor could look like this:

tdiv(s,b1,b2)={my(a);s--;forprime(p=b1,b2,a=Mod(2,p)^s;if(!Mod(2*a*a-a+1,p),return(p)))};

Maybe there are better methods, in case please let me know.

There is no error in this, but here is a faster version:

tdiv(s,b1,b2)={my(a);s--;forprime(p=b1,b2,a=Mod(2,p)^s;if(a*(a+a-1)+1,,return(p)))};

This is because Mod() in Pari/gp is not just a operator (like %); a is of class Mod which implements all further work with this variable in its class; no need to call Mod() over it again, which gp interpreter likely will take literally, with overhead. The rest of small tricks are unlikely to make any difference in speed (a+a instead of 2*a, not using '!' but using 'else', or any other regrouping of the expression).

And you can refactor it into plain C or better yet in OpenCL or CUDA; there is a mulmod and powmod2 function that can be borrowed from R.Gerbicz' polysieve; or take polysieve and adapt it to this task. That will be faster still.

[Batalov]

Or you can run 64-threaded LLR (or PFGW) on an appropriate computer and remove all doubts. (You can get one at AWS.)
First check the relative speed of the two programs whichever is running faster, then queue it and wait.

You can use the structured input that LLR accepts (PFGW will accept many more ways to write it):
ABC $a^$b-$a^$c+1
2 148414561 74207280
If PRP test passes then you can open a bottle of champagne and run the N-1 for another slot of time.

llr4 shows this ETA:
Starting Fermat PRP test of 2^148414561-2^74207280+1
Using generic reduction AVX-512 FFT length 16128K, Pass1=896, Pass2=18K, clm=2, 32 threads, a = 3
Iteration: 30000 / 148414560 [0.00%], ms/iter: 69.168, ETA: 118d 18:58
...
I think with -oFFT_Increment=1 one might get FFT length 16M instead of this size (which has 9x in one pass and 7x in the other); it could be faster.

Testing PFGW... ... ... slightly slower, same FFT chosen:
PFGW Version 4.0.1.64BIT.20191203.x86_Dev [GWNUM 29.8]
Generic modular reduction using generic reduction AVX-512 FFT length 16128K, Pass1=896, Pass2=18K, clm=2, 32 threads on A 148414563-bit number
Using stopwatch per 2500 iters -- ms/iter: 73.20 ETA: ~125d 18:00hrs

[ATH]

Originally Posted by Neptune

Thanks to ATH who has done a great job searching for factors below 6*10¹².

A small function in Pari/GP to find a factor could look like this:

tdiv(s,b1,b2)={my(a);s--;forprime(p=b1,b2,a=Mod(2,p)^s;if(!Mod(2*a*a-a+1,p),return(p)))};

Maybe there are better methods, in case please let me know.

I'm running

tdiv(74207281,6*10^12,10^13)

to test P_49* between 6*10¹² and 10¹³.

There is a small chance that a factor is found.

You only need to check about half the primes, as you pointed out Ken Wilke found some dependencies, so you only need to check primes that are 1, 9 or 11 (mod 14) which is about half of all primes (rest are 3, 5 and 13 (mod 14)).

I'm sorry but I started trial factoring again when you started this thread, I often do this when I'm reminded of old "projects", I'm already at 2.4*10¹³.

[Neptune]

Thank you Serge Batalov and ATH for the support. With your help the function could be clearly Improved:

tdiv(s,b1,b2)={my(a);s--;forprimestep(p=b1,b2,Mod(1,14)||Mod(9,14)||Mod(11,14),a=Mod(2,p)^s;if(a*(a+a-1)+1,,return(p)))};

It is especially fast, when functions runs in parallel for each modular step.



I tested LLR 4.0.1 to get an ETA also.

./llr64 -d -t4 -q"2^148414561-2^74207280+1"

2^74207281-1 > 2^74207280, so we can only do a PRP test for 2^148414561-2^74207280+1.
Current FFT beeing too near the limit, next FFT length is forced...
Starting Fermat PRP test of 2^148414561-2^74207280+1
Using generic reduction FMA3 FFT length 17920K, Pass1=1792, Pass2=10K, clm=1, 4 threads, a = 3
  Iteration: 140000 / 148414560 [0.00%], ms/iter: 283.943, ETA: 487d 06:52

LLR showed no output during the first 6 hours. After around 18 hours the ETA was still over 480 days.
This is too much. My computer is to slow for this kind of test.


To move on, I would have liked to run ECM, but neither Yafu nor GMP-ECM worked for me due to memory overflows.


The only thing that worked for me was a P-1 test with B1 = B2 = 15k in Yafu:

wine yafu-x64 -v -v -v -B1pm1 15000 -B2pm1 15000 "pm1(7*(2^148414561-2^74207280+1))"

YAFU Version 2.08
Built with Microsoft Visual Studio 1922
Using GMP-ECM 7.0.4, Powered by MPIR 3.0.0
Detected Intel(R) Core(TM) i5-8250U CPU @ 3.40GHz
Detected L1 = 32768 bytes, L2 = 6291456 bytes, CL = 64 bytes
Using 1 random witness for Rabin-Miller PRP checks
Cached 664579 primes; max prime is 9999991

>> pm1: starting B1 = 15K, B2 = 15K on C44677236
Using mpz_mod
Using lmax = 8 with NTT which takes about 474MB of memory
Using B1=1-15000, B2=15036, polynomial x^1
P = 3, l = 8, s_1 = 4294967298, k = s_2 = 1, m_1 = 2500
Probability of finding a factor of n digits:
20    25    30    35    40    45    50    55    60    65
0.001    3.5e-05    8.7e-07    1.6e-08    3.3e-10    7.3e-15    0    0    0    0
Step 1 took 65649070ms
pm1: Process took 71745.5287 seconds.
pm1: found prp1 factor = 7

***factors found***

   P1 = 7

Adding a small co-factor like 7 prevents Yafu from doing a Miller-Rabin PRP test, wich is hopeless on a 44 million digit number.
The test took about 20 hours and Yafu needed almost 6 GB of my total 8 GB memory. The probability finding a factor of 15 digits, if one exists, is around 2 %.
Better than nothing.