mersenneforum.org > News Doubts, scientific breakthroughs and conspiracy theories about Wagstaff Conjecture (from Lucky13)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2018-12-19, 03:16   #78
Serpentine Vermin Jar

Jul 2014

2×23×71 Posts

Quote:
 Originally Posted by kriesel I hope it's either statistical fluctuation, or an actual pattern with mathematical justification TBD, not a consequence of similar effect undiscovered bugs lurking in the primality test codes. Some of the codes have ancestry in common. If there was an issue in common, present in a bit of "DNA in common", despite the best efforts of the authors and extreme care in using differing programs on differing hardware in multiple confirmations by multiple individuals, how could we know?
If it helps put you at ease, the current iterations of programs can be run against the known primes that have an exponent == 3 mod 4, and I think those tests have been done lately and confirmed. But if in doubt, run your own test to make sure.

EDIT: By "done lately and confirmed" I mean there are people who do sometimes run new tests of previously discovered primes - the server doesn't accept them, but people do the tests, I guess just to see what happens, or whatever.

Last fiddled with by Madpoo on 2018-12-19 at 03:19

2018-12-19, 05:32   #79
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×5×11×37 Posts

Quote:
 Originally Posted by Madpoo If it helps put you at ease, the current iterations of programs can be run against the known primes that have an exponent == 3 mod 4, and I think those tests have been done lately and confirmed. But if in doubt, run your own test to make sure. EDIT: By "done lately and confirmed" I mean there are people who do sometimes run new tests of previously discovered primes - the server doesn't accept them, but people do the tests, I guess just to see what happens, or whatever.
Perhaps people rerun them to test their setup for reliability, or to see what sort of alert sound it might make. (No sound if it's a known one, in my experience.)

In PRP3, for the series of all known Mersenne exponents, I'm half way through M49 now, having started from M2, running the exponents big enough for gpuOwL V5.0-9c13870, and the lower exponents were run on prime95 v29.4b8.
After the gpuowl run completes (and perhaps with some delay if I've guessed M51 right), run times will go up at https://www.mersenneforum.org/showpo...6&postcount=10

Haven't seen anything out of the ordinary yet. That's encouraging but not definitive.

If they all pass, it does not necessarily mean the existing codes are without flaw.
If one fails, it does not necessarily mean the existing codes are flawed, it could be a transient hardware issue.There's a sliver of a chance of an error occurring outside the loop of iterations that are guarded for accuracy by the Gerbicz check.
No disrespect to any of the authors (or users, or hardware designers for that matter; some tasks are just very hard). I've fixed code that failed nonreproducibly at low rates. Ppb or lower frequency bugs can be hard to determine exist, much less identify and resolve. Current assignments can be of order 1018 core clocks to complete.

2018-12-19, 08:18   #80
GP2

Sep 2003

257910 Posts

Quote:
 Originally Posted by Madpoo I ran a quick count of the distinct exponents with any known factors and whether that exponent is 1 or 3 mod 4: Mod Count 1 14,559,812 (49.301%) 3 14,972,752 (50.699%) I wouldn't say it's a runaway for the 3 mod 4 exponents being factored. In fact it seems like a pretty basic variation around 50/50 based on an incomplete set.
But exponents of p=3 mod 4 do have slightly more factors than exponents of p=1 mod 4, as was noted as early as 1967 by Ehrman (and cited by Wagstaff in 1983).

So I would expect that the counts above will never be exactly 50/50 even theoretically. If you slightly alter the λ of a Poisson distribution then you slightly alter your counts at k=0.

We could look at the factors themselves, rather than distinct exponents with or without factors. Based on the same dataset I used before (frozen on 2018-12-01), I get:

Code:
                         all f    f <= 65 bits
p=1 mod 4, f=1 mod 8    9846883     9304449
p=3 mod 4, f=1 mod 8    9833742     9310151

p=1 mod 4, f=7 mod 8   10655959    10119410
p=3 mod 4, f=7 mod 8   11565454    11045807
So
1. There are more factors with f=7 (mod 8) than f=1 (mod 8)
2. The fact that exponents with p=3 (mod 4) are more likely to have factors than exponents with p=1 (mod 4) is due to the factors that are 7 (mod 8).
3. As your post also reflected, factors of size 65 bits or less are a pretty big subset of the set of all known factors

If p=3 mod 4 and 2p+1 is prime, then it's a factor of the Mersenne number with exponent p, and f=2p+1=7 mod 8. And if p=1 mod 4 then the smallest possible factor is 6p+1, and again in this case there will be f=6p+1=7 mod 8.

Last fiddled with by GP2 on 2018-12-19 at 08:29

2018-12-19, 09:42   #81
preda

"Mihai Preda"
Apr 2015

2×19×29 Posts

Quote:
 Originally Posted by kriesel I hope it's either statistical fluctuation, or an actual pattern with mathematical justification TBD, not a consequence of similar effect undiscovered bugs lurking in the primality test codes. Some of the codes have ancestry in common. If there was an issue in common, present in a bit of "DNA in common", despite the best efforts of the authors and extreme care in using differing programs on differing hardware in multiple confirmations by multiple individuals, how could we know?
I think we are confident with very high probability that the currently known mersenne primes (51 of them) are indeed prime.

So the "systematic error" could be only in the form of undiscovered primes (below the current wavefront).

If that would be the case, then the density of MPs would be even farther away from what's theoretically predicted.

2018-12-19, 16:33   #82
mart_r

Dec 2008
you know...around...

32·61 Posts

Quote:
 Originally Posted by GP2 There are more factors with f=7 (mod 8) than f=1 (mod 8) The fact that exponents with p=3 (mod 4) are more likely to have factors than exponents with p=1 (mod 4) is due to the factors that are 7 (mod 8). As your post also reflected, factors of size 65 bits or less are a pretty big subset of the set of all known factors If p=3 mod 4 and 2p+1 is prime, then it's a factor of the Mersenne number with exponent p, and f=2p+1=7 mod 8. And if p=1 mod 4 then the smallest possible factor is 6p+1, and again in this case there will be f=6p+1=7 mod 8.

Not sure how good of a comparison they are, but generalized repunits may provide enough data for some empirical analysis.
Some time ago I searched for primes p such that 2kp+1 give less primes than average for small k, thus making it more probable that (b^p-1)/(b-1) is prime. The output was not that significant, as far as I remember, but it was just a thought.

2018-12-19, 18:12   #83
GP2

Sep 2003

2,579 Posts

Quote:
 Originally Posted by mart_r Not sure how good of a comparison they are, but generalized repunits may provide enough data for some empirical analysis. Some time ago I searched for primes p such that 2kp+1 give less primes than average for small k, thus making it more probable that (b^p-1)/(b-1) is prime. The output was not that significant, as far as I remember, but it was just a thought.
Paul Bourdelais is looking for generalized repunit primes, but I think he's only reached the 1M or 2M exponent ranges by now.

And apart from Wagstaff (b=−2), I've been doing ECM lately to find more factors for generalized repunits for bases 3, 5, 7, 11, 12 and −3, −5, −7, −10, −11, −12. I've contributed the factors to FactorDB and found some new PRP cofactors, But it's mostly very unexplored territory. For instance, for base b=3 I'm finding lots of small factors unknown by FactorDB at a wavefront of a mere p=63k or so, and at even lower p for the other bases.

So right now there just aren't that many known primes or semiprimes yet for these repunits, and the statistics are too low to be meaningful.

2018-12-21, 20:26   #84
GP2

Sep 2003

2,579 Posts

As mentioned earlier, filtering by non-tiny p is in practice equivalent to filtering by the asymmetricity of the factors that make up the semiprime.

We can only find relatively small factors, so beyond the Cunningham project range where nearly everything is fully factored, every Mersenne semprime or Wagstaff semiprime that we are capable of discovering is necessarily composed of two highly asymmetric factors.

These were the counts when we filtered Mersenne semiprimes by size of the exponent p:

Quote:
 Originally Posted by GP2 Code: Mersenne semiprimes filter by p greater than: 10^3 10^4 10^5 mod 4 p=1 16 10 7 p=3 30 20 14 mod 8 p=1 8 5 3 p=3 12 7 5 p=5 8 5 4 p=7 18 13 9
But if we consider only Mersenne semiprimes (of any size) where the bit length of the (smaller) factor is less than 5% of the bit length of the Mersenne number, then we get nearly the same counts as when we filter for exponent p < 10^3 :

Code:
Mersenne semiprimes

filter by asymmetric bit length:
len(small factor) < 0.05 *
len(Mersenne number)
mod 4
p=1    15
p=3    29
mod 8
p=1     8
p=3    11
p=5     7
p=7    18
Similarly, these were the counts when we filtered Wagstaff semiprimes by size of the exponent p:

Quote:
 Originally Posted by GP2 Code: Wagstaff semiprimes filter by p greater than: 10^3 10^4 10^5 mod 4 p=1 24 13 5 p=3 13 6 2 mod 8 p=1 14 9 3 p=3 6 3 2 p=5 10 4 2 p=7 7 3 0
And again, if we consider only Wagstaff semiprimes (of any size) where the bit length of the (smaller) factor is less than 5% of the bit length of the Wagstaff number, then we get nearly the same counts as when we filter for exponent p < 10^3 :

Code:
Wagstaff semiprimes

filter by asymmetric bit length:
len(small factor) < 0.05 *
len(Mersenne number)
mod 4
p=1    21
p=3    11
mod 8
p=1    12
p=3     5
p=5     9
p=7     6

Last fiddled with by GP2 on 2018-12-21 at 20:35

 2018-12-29, 16:21 #85 GP2     Sep 2003 2,579 Posts All factors of Mersenne numbers are 1 or 7 (mod 8). But all factors in general are 1 or 5 (mod 6), except for 2 and 3. Combining the two gives: All factors of Mersenne numbers are 1 or 7 or 17 or 23 (mod 24). The various congruence classes are not equally likely (factor data frozen as of December 1): Code: [(1, 170925), (7, 190532), (17, 185312), (23, 207834)] 0M < p < 10M [(1, 135127), (7, 150156), (17, 146802), (23, 165115)] 10M < p < 20M [(1, 83674), (7, 95232), (17, 92200), (23, 104402)] 990M < p < 1000M There is a marked difference between p=1 (mod 4) and p=3 (mod 4): Code:  p=1 (mod 4) [(1, 85562), (7, 102644), (17, 92628), (23, 88934)] 0M < p < 10M [(1, 67370), (7, 81196), (17, 73487), (23, 69787)] 10M < p < 20M [(1, 41802), (7, 51688), (17, 46104), (23, 44159)] 990M < p < 1000M p=3 (mod 4) [(1, 85363), (7, 87888), (17, 92684), (23, 118900)] 0M < p < 10M [(1, 67757), (7, 68960), (17, 73315), (23, 95328)] 10M < p < 20M [(1, 41872), (7, 43544), (17, 46096), (23, 60243)] 990M < p < 1000M It's interesting, for example, that for exponents p=3 (mod 4), factors that are f=23 (mod 24) are found about one-third more frequently than the other kinds. Empirically, all Mersenne numbers with odd exponent are 7 mod 24 (that is, the values of the Mersenne numbers themselves, not the values of the exponents). Therefore a Mersenne semiprime must consist of either a (1, 7) mod 24 pair of factors or a (17, 23) mod 24 pair of factors. So the frequency asymmetries of 1,7,17,23 mod 24 factors maybe can start to explain why p=1 (mod 4) and p=3 (mod 4) seem to produce semiprimes with different likelihood? Last fiddled with by GP2 on 2018-12-29 at 16:56
 2018-12-29, 16:25 #86 GP2     Sep 2003 2,579 Posts Likewise, all factors of Wagstaff numbers are 1 or 3 (mod 8) and consequently 1, 11, 17, 19 (mod 24). For all known factors (as of a couple of days ago), we also have asymmetries: Code:  all [(1, 520596), (11, 807965), (17, 638798), (19, 672074)] p=1 (mod 4) [(1, 257566), (11, 514932), (17, 316467), (19, 279297)] p=3 (mod 4) [(1, 263030), (11, 293033), (17, 322331), (19, 392777)] Empirically, all 2^n+1 with odd exponent are 9 mod 24, and Wagstaff numbers (2^n+1)/3 with odd exponent are all 11 or 19 mod 24, except for n=3 which gives (2^n+1)/3 = 3. Last fiddled with by GP2 on 2018-12-29 at 16:46
2018-12-29, 17:03   #87
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by GP2 All factors of Mersenne numbers are 1 or 7 (mod 8). But all factors in general are 1 or 5 (mod 6), except for 2 and 3. Combining the two gives: All factors of Mersenne numbers are 1 or 7 or 17 or 23 (mod 24). The various congruence classes are not equally likely (factor data frozen as of December 1): Code: [(1, 170925), (7, 190532), (17, 185312), (23, 207834)] 0M < p < 10M [(1, 135127), (7, 150156), (17, 146802), (23, 165115)] 10M < p < 20M [(1, 83674), (7, 95232), (17, 92200), (23, 104402)] 990M < p < 1000M There is a marked difference between p=1 (mod 4) and p=3 (mod 4): Code:  p=1 (mod 4) [(1, 85562), (7, 102644), (17, 92628), (23, 88934)] 0M < p < 10M [(1, 67370), (7, 81196), (17, 73487), (23, 69787)] 10M < p < 20M [(1, 41802), (7, 51688), (17, 46104), (23, 44159)] 990M < p < 1000M p=3 (mod 4) [(1, 85363), (7, 87888), (17, 92684), (23, 118900)] 0M < p < 10M [(1, 67757), (7, 68960), (17, 73315), (23, 95328)] 10M < p < 20M [(1, 41872), (7, 43544), (17, 46096), (23, 60243)] 990M < p < 1000M It's interesting, for example, that for exponents p=3 (mod 4), factors that are f=23 (mod 24) are found about one-third more frequently than the other kinds. Empirically, all Mersenne numbers with odd exponent are 7 mod 24 (that is, the values of the Mersenne numbers themselves, not the values of the exponents). Therefore a Mersenne semiprime must consist of either a (1, 7) mod 24 pair of factors or a (17, 23) mod 24 pair of factors. So the frequency asymmetries of 1,7,17,23 mod 24 factors maybe can start to explain why p=1 (mod 4) and p=3 (mod 4) seem to produce semiprimes with different likelihood?
no matter the mersenne with prime exponent, an odd number of prime factors need be 3 mod 4, 1 mod 4 can have any number at last check. so 7 mod 8 is slightly biased potentially from that. not just sophie germain primes.

 2018-12-29, 18:39 #88 JeppeSN     "Jeppe" Jan 2016 Denmark 7816 Posts I do not know what "empirically" means in the preceding posts, but for any odd $$p$$ we have $2^p\equiv(-1)^p = -1 \pmod 3$ and also for any $$p\ge 3$$ we have $2^p=2^3\cdot 2^{p-3}\equiv 0\cdot 2^{p-3}=0 \pmod 8$ so if we combine, whenever $$p$$ is both odd and at least three, then $$2^p\equiv 8 \pmod {24}$$. Therefore $$2^p-1\equiv 7 \pmod {24}$$ and $$2^p+1\equiv 9 \pmod {24}$$. /JeppeSN Last fiddled with by JeppeSN on 2018-12-29 at 18:41

 Similar Threads Thread Thread Starter Forum Replies Last Post Tony Reix Wagstaff PRP Search 7 2013-10-10 01:23 paramveer Information & Answers 32 2012-01-15 06:05 davieddy Miscellaneous Math 209 2011-01-23 23:50 davieddy PrimeNet 17 2010-07-21 00:07 jasong Soap Box 11 2010-07-05 12:23

All times are UTC. The time now is 05:16.

Fri Jul 10 05:16:39 UTC 2020 up 107 days, 2:49, 0 users, load averages: 1.26, 1.27, 1.18