mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Proth Prime Search

Reply
 
Thread Tools
Old 2022-07-06, 15:00   #12
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

10010010102 Posts
Default

Quote:
Originally Posted by Batalov View Post
Quote:
...low weight...
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>.
bur is online now   Reply With Quote
Old 2022-07-07, 19:27   #13
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5·7·283 Posts
Default

Quote:
Originally Posted by bur View Post
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:
Quote:
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?
Batalov is offline   Reply With Quote
Old 2022-07-12, 09:54   #14
Neptune
 
Jul 2022

3 Posts
Default

Thanks for all those links.


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

Quote:
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 P49* 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*1012.

A small function in Pari/GP to find a factor could look like this:
Code:
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

Code:
tdiv(74207281,6*10^12,10^13)
to test P49* between 6*1012 and 1013.

There is a small chance that a factor is found.
Neptune is offline   Reply With Quote
Old 2022-07-12, 16:05   #15
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5×7×283 Posts
Default

Quote:
Originally Posted by Neptune View Post
A small function in Pari/GP to find a factor could look like this:
Code:
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:
Code:
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 is offline   Reply With Quote
Old 2022-07-12, 16:50   #16
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5×7×283 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2022-07-12, 19:53   #17
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3×1,117 Posts
Default

Quote:
Originally Posted by Neptune View Post
Thanks to ATH who has done a great job searching for factors below 6*1012.

A small function in Pari/GP to find a factor could look like this:
Code:
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

Code:
tdiv(74207281,6*10^12,10^13)
to test P49* between 6*1012 and 1013.

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*1013.
ATH is offline   Reply With Quote
Old 2022-07-16, 13:30   #18
Neptune
 
Jul 2022

316 Posts
Default

Thank you Serge Batalov and ATH for the support. With your help the function could be clearly Improved:
Code:
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.
Code:
./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:
Code:
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.
Neptune is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is it possible for an odd perfect number to have the form 8*k+5? carpetpool carpetpool 0 2022-07-03 02:55
Incorrect guess based on limited data: Number of Primes 6k-1 > Number of Primes 6k+1 Dobri Dobri 53 2022-05-18 14:56
Is this a Perfect Number ? Godzilla Miscellaneous Math 8 2016-09-05 05:56
Down to a perfect number fivemack Aliquot Sequences 0 2014-12-23 09:47
Odd Perfect Number is 36k+9 ? isaac Miscellaneous Math 5 2014-07-22 22:18

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


Tue Aug 16 10:07:34 UTC 2022 up 40 days, 4:54, 1 user, load averages: 1.42, 1.19, 1.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔