Are any Mersenne factors 1 mod p^2? - Page 5

charybdis · 2023-01-16, 01:53

Quote:

Originally Posted by charybdis

Invoking the "Assumption of Ignorance" would give a default answer of each of the p values of 2*k (mod p) being equally likely. Of course, this might also apply to (M_p - 1)/p (mod p). Choosing the value 0 (mod p) would then indicate that there "should" be about log(log(X)) (base-2) Wieferich primes up to X. However, the numerical data does not seem to support this. The largest known (base-2) Wieferich prime is 3511, and the search bound is at least of order 10¹⁵ and may be higher by now.

Why would the log log be to base 2? We're just summing 1/p, right?

The search limit is at least 2^64 now, but log log 2^64 = 3.79 so it's not that surprising we've only found 2.

Dr Sardonicus · 2023-01-16, 13:10

Quote:

Originally Posted by charybdis

Why would the log log be to base 2? We're just summing 1/p, right?

I meant Wieferich primes to the base 2. Sorry I wasn't clear.

Quote:

The search limit is at least 2^64 now, but log log 2^64 = 3.79 so it's not that surprising we've only found 2.

You're right about the numerical evidence. It's sometimes hard to keep in mind how very slow-growing log(log(x)) really is.

I should have checked the value of log(log(10^15)) before posting.

I realized this some hours after I'd posted.

Andrew Usher · 2023-01-19, 00:31

That unknown cofactor, M281903623, has now been taken to 2^80 and P-1 to mersenne.ca bounds, and is therefore ready for PRP should anyone care enough.

alpertron · 2023-01-19, 02:04

I'm running P-1 on the cofactor with B1 = 10M, B2 = 300M. At this moment the computer is running step 1 which is 67.28% complete. At this rate, step 2 will start on Friday.

Andrew Usher · 2023-01-19, 23:33

This is well beyond what anyone could expect - even though I asked the question I didn't expect much computational effort put into it, and I'd consider this factor of interest only if shown PRP. But I'd have to say that B2 should be higher if you are going to do P-1 to extra length.

You are running 30.8, and limiting the B2 manually is rarely a good idea with the new algorithm, in which B2 increases faster than linearly with time. If you must set it manually I'd expect it should be at least 100:1, as I tried to achieve even with the old algorithm in such cases.

alpertron · 2023-01-20, 01:46

The speed-up of the second step depends not only on the amount of RAM but also on the exponent being considered. If you worked with a 7-digit exponent the ratio B2/B1 could be a lot larger.

At this moment step 1 is 86.11% complete.

kriesel · 2023-01-20, 07:41

Quote:

Originally Posted by alpertron

The speed-up of the second step depends on

more precisely I think, the integer number of fft-length size buffers that will fit in the allowed ram. It's not a continuous function of ram/exponent. Fft length is a stepwise function of exponent. So it is a "staircase".

And there could be more to it. I don't recall whether the new prime95 algorithm also has a requirement similar to one that Mlucas P-1 has, that the buffer count be an integer multiple of 24 or 40.

Andrew Usher · 2023-01-21, 00:59

I can't answer that last - it should be in the source - but yes, of course it's discrete. Even the old algorithm has discrete 'relative primes', and FFT sizes are discrete. It's just that continuous functions are much nicer approximations, and generally close enough for this work.

But we all know it depends on allocated RAM and on exponent. My supposition was that it also depended on B2, so the optimal B2/B1 (holding memory and exponent fixed) should be increasing with B1. The stage 2/stage 1 runtime ratio for alpertron's runs on this exponent would immediately show whether I'm right (if roughly constant, as with the old algorithm, then I'm wrong). The actual values used by others on small exponents seem to support this.

alpertron · 2023-01-21, 14:00

I changed B2 to 1G. Now the computer is running step 2 of P-1.

It appears that it will finish on Wednesday.

alpertron · 2023-01-28, 11:57

No prime factor was found using P-1 with the bounds noted above.

Andrew Usher · 2023-01-29, 02:42

So we're done with this now? I'm guessing you are tired of it by now and content to leave it there, as am I as my question has been gone over quite sufficiently, and I gratefully accept your contribution to it.

I am still curious about my conjecture on P-1, though.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
factors of Mersenne numbers	bhelmes	Number Theory Discussion Group	21	2021-09-15 02:07
Mersenne factors 2kp+1	ATH	Miscellaneous Math	7	2020-10-09 11:09
factors of Mersenne numbers	bhelmes	Miscellaneous Math	8	2020-09-14 17:36
Distribution of Mersenne Factors	tapion64	Miscellaneous Math	21	2014-04-18 21:02
Known Mersenne factors	CRGreathouse	Math	5	2013-06-14 11:44

2023-01-19, 00:31	#47
Andrew Usher Dec 2022 2⁶·7 Posts	That unknown cofactor, M281903623, has now been taken to 2^80 and P-1 to mersenne.ca bounds, and is therefore ready for PRP should anyone care enough.

2023-01-19, 02:04	#48
alpertron Aug 2002 Buenos Aires, Argentina 2×761 Posts	I'm running P-1 on the cofactor with B1 = 10M, B2 = 300M. At this moment the computer is running step 1 which is 67.28% complete. At this rate, step 2 will start on Friday.

2023-01-19, 23:33	#49
Andrew Usher Dec 2022 111000000₂ Posts	This is well beyond what anyone could expect - even though I asked the question I didn't expect much computational effort put into it, and I'd consider this factor of interest only if shown PRP. But I'd have to say that B2 should be higher if you are going to do P-1 to extra length. You are running 30.8, and limiting the B2 manually is rarely a good idea with the new algorithm, in which B2 increases faster than linearly with time. If you must set it manually I'd expect it should be at least 100:1, as I tried to achieve even with the old algorithm in such cases.

2023-01-20, 01:46	#50
alpertron Aug 2002 Buenos Aires, Argentina 2·761 Posts	The speed-up of the second step depends not only on the amount of RAM but also on the exponent being considered. If you worked with a 7-digit exponent the ratio B2/B1 could be a lot larger. At this moment step 1 is 86.11% complete.

2023-01-21, 00:59	#52
Andrew Usher Dec 2022 2⁶·7 Posts	I can't answer that last - it should be in the source - but yes, of course it's discrete. Even the old algorithm has discrete 'relative primes', and FFT sizes are discrete. It's just that continuous functions are much nicer approximations, and generally close enough for this work. But we all know it depends on allocated RAM and on exponent. My supposition was that it also depended on B2, so the optimal B2/B1 (holding memory and exponent fixed) should be increasing with B1. The stage 2/stage 1 runtime ratio for alpertron's runs on this exponent would immediately show whether I'm right (if roughly constant, as with the old algorithm, then I'm wrong). The actual values used by others on small exponents seem to support this.

2023-01-21, 14:00	#53
alpertron Aug 2002 Buenos Aires, Argentina 2×761 Posts	I changed B2 to 1G. Now the computer is running step 2 of P-1. It appears that it will finish on Wednesday.

2023-01-28, 11:57	#54
alpertron Aug 2002 Buenos Aires, Argentina 10111110010₂ Posts	No prime factor was found using P-1 with the bounds noted above.

2023-01-29, 02:42	#55
Andrew Usher Dec 2022 111000000₂ Posts	So we're done with this now? I'm guessing you are tired of it by now and content to leave it there, as am I as my question has been gone over quite sufficiently, and I gratefully accept your contribution to it. I am still curious about my conjecture on P-1, though.