mersenneforum.org Are any Mersenne factors 1 mod p^2?
 Register FAQ Search Today's Posts Mark Forums Read

 2023-01-29, 11:47 #56 alpertron     Aug 2002 Buenos Aires, Argentina 101110111002 Posts Running PRP on the cofactor requires 71 days in my computer. I think that it is too much for me.
2023-02-03, 06:37   #57
ATH
Einyen

Dec 2003
Denmark

32×383 Posts

Quote:
 Originally Posted by alpertron I searched the complete range 0-1000M and I found no more solutions.
I made my own program and found the same 22 solutions as you.

I also checked all factors from mersenne.ca from 1G to 10G, there were no solutions at all.

 2023-02-03, 10:05 #58 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 5·112·17 Posts Still reading through the topic. Is this what you want to achieve?
2023-02-03, 10:47   #59
ATH
Einyen

Dec 2003
Denmark

32·383 Posts

Quote:
 Originally Posted by LaurV Still reading through the topic. Is this what you want to achieve?
No, this is about Mersenne factors that are:
2*k*p2 + 1 instead of 2*k*p + 1

There are only 1 known example where the factor is prime:
2*674487*930772 + 1

and 20 others found in this thread that are composite and 1 unknown status:
(2281903623-1)/4929034977952529199403122399722497889153231 (see post #36)

Last fiddled with by ATH on 2023-02-03 at 10:50

 2023-02-03, 13:07 #60 Andrew Usher   Dec 2022 23·3·13 Posts So, the reasonable question is: how did you use the mersenne.ca data if its format was such an obstacle as alpertron saw? And, yes, this topic turns out not really to be related to Wieferich primes, except in the trivial way that the whole number (as a divisor of itself) is on the list if and only if the exponent is one, as 2^p - 1 = 1 <-> 2^(p-1) = 1, mod anything.
2023-02-03, 13:59   #61
ATH
Einyen

Dec 2003
Denmark

1101011101112 Posts

Quote:
 Originally Posted by Andrew Usher So, the reasonable question is: how did you use the mersenne.ca data if its format was such an obstacle as alpertron saw? And, yes, this topic turns out not really to be related to Wieferich primes, except in the trivial way that the whole number (as a divisor of itself) is on the list if and only if the exponent is one, as 2^p - 1 = 1 <-> 2^(p-1) = 1, mod anything.
There are lists of comma separated txt files at the bottom here with "exponent,k" so you just calculate the factor 2*k*exponent + 1 after reading the 2 values.
https://www.mersenne.ca/export/

 2023-02-03, 14:14 #62 alpertron     Aug 2002 Buenos Aires, Argentina 150010 Posts Notice that you have to sort the numbers by exponent. After you get n prime factors of 2k - 1 from mersenne.ca, you have to test which of the 2n + 1 - 1 factors (we have to exclude the number 1) of 2k - 1 are congruent to 1 mod k2. Last fiddled with by alpertron on 2023-02-03 at 14:22
2023-02-03, 16:36   #63
ATH
Einyen

Dec 2003
Denmark

32×383 Posts

Quote:
 Originally Posted by alpertron Notice that you have to sort the numbers by exponent. After you get n prime factors of 2k - 1 from mersenne.ca, you have to test which of the 2n + 1 - 1 factors (we have to exclude the number 1) of 2k - 1 are congruent to 1 mod k2.
They are in exponent order in these files, see screenshot. https://www.mersenne.ca/export/

Don't you mean if there are n factors there are 2n - 1 options to check?

I my program I treat it as a binary number if each factor is "on" or "off" in this product: f1*f2*f3...*fn
Skip 0 because that would give the product 1, then make a loop from 1 to 2n-1 and multiply those factors that are "on" in the binary representation of that number.

For example n=5: There are 5 ways to choose 1 factor, (5 choose 2) = 10 ways to choose 2 of 5 factors, (5 choose 3) = 10 ways to choose 3 of 5, (5 choose 4) = 5 and 1 way to choose all:
5+10+10+5+1 = 25-1

Edit: Ah right for each of those above I check the product as well as (2p-1)/product and finally the number (2p-1) itself so a total of 2*(2n-1) + 1 = 2n+1 -1, you are right.
Attached Thumbnails

Last fiddled with by ATH on 2023-02-03 at 16:40

 2023-02-04, 13:05 #64 alpertron     Aug 2002 Buenos Aires, Argentina 22·3·53 Posts Yesterday I started running PRP for (2281903623-1)/4929034977952529199403122399722497889153231 It will require about 70 days.
2023-02-04, 15:43   #65
ATH
Einyen

Dec 2003
Denmark

D7716 Posts

Quote:
 Originally Posted by ATH Edit: Ah right for each of those above I check the product as well as (2p-1)/product and finally the number (2p-1) itself so a total of 2*(2n-1) + 1 = 2n+1 -1, you are right.
You don't have to actually calculate (2p-1)/"product", I started by doing that and it took forever. Several hours to just get to 50M (on 1 core).

If N=2p-1=a*b, and a is the "product" then b=N/a is the one we want to check mod p2.

If we calculate N (mod p2) by modular exponentiation and the "product" a mod p2 then:
N mod p2 = (a mod p2)*(b mod p2)

But we only want to know if (b mod p2) is 1 or not, and the only way it can be 1 is if:
N (mod p2) = a (mod p2) (where a is the current "product" in our loop checking all posibilities.)

So we only need to calculate (2p-1) mod p2 once by modular exponentiation and then compare it to all the different products mod p2.

Last fiddled with by ATH on 2023-02-04 at 15:45

 2023-02-05, 13:44 #66 Andrew Usher   Dec 2022 23×3×13 Posts I see (and alpertron has already gone through how that computation is best accomplished). So is that "exponent,k" format newly added, after the search in which he said he couldn't use mersenne.ca's data? It is indeed not difficult with that.

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Number Theory Discussion Group 21 2021-09-15 02:07 ATH Miscellaneous Math 7 2020-10-09 11:09 bhelmes Miscellaneous Math 8 2020-09-14 17:36 tapion64 Miscellaneous Math 21 2014-04-18 21:02 CRGreathouse Math 5 2013-06-14 11:44

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

Sun Mar 26 18:10:23 UTC 2023 up 220 days, 15:38, 0 users, load averages: 0.97, 1.08, 0.95