mersenneforum.org Primes of the form 'perfect number' + 1 (a.k.a. RPN)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2022-07-06, 15:00   #12
bur

Aug 2020
79*6581e-4;3*2539e-3

11128 Posts

Quote:
Originally Posted by Batalov
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>.

2022-07-07, 19:27   #13
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5×7×283 Posts

Quote:
 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 .
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?

2022-07-12, 09:54   #14
Neptune

Jul 2022

3 Posts

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.

2022-07-12, 16:05   #15
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5·7·283 Posts

Quote:
 Originally Posted by Neptune 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.

 2022-07-12, 16:50 #16 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 5×7×283 Posts 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
2022-07-12, 19:53   #17
ATH
Einyen

Dec 2003
Denmark

64278 Posts

Quote:
 Originally Posted by Neptune 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.

 2022-07-16, 13:30 #18 Neptune   Jul 2022 3 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool carpetpool 0 2022-07-03 02:55 Dobri Dobri 53 2022-05-18 14:56 Godzilla Miscellaneous Math 8 2016-09-05 05:56 fivemack Aliquot Sequences 0 2014-12-23 09:47 isaac Miscellaneous Math 5 2014-07-22 22:18

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

Tue Aug 16 10:55:34 UTC 2022 up 40 days, 5:42, 1 user, load averages: 0.77, 0.95, 1.13

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.

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