Possible values for k (in Mersenne factors)

[LaurV]

That's what I mainly said in the third paragraph. We are in violent agreement here...

[ewmayer]

Originally Posted by GP2

For each value of p mod 60, there are exactly 16 out of 60 valid values for k mod 60. Earlier, we saw that for each value of p mod 12, there were exactly 4 out of 12 possible value for k mod 12. Also, for each value of p mod 4, there were exactly 2 out of 4 possible values for k mod 4. So by increasing the modulus from 4 to 12 to 60, we reduced the number of cases to test from 50% to 33.33% to 26.67%.

Note that 'reduced the number of cases to test' is misleadingly optimistic, because in practice such a highly-composite-modulo sieve is always combined with a small-prime-factor sieve, which will catch nearly all the 'extra' candidates left over by a smaller-modulus. In other words, the number of expensive operations, that is, modular powerings to test whether a given q = 2kp+1 divides M(p), changes very little from e.g. using (mod 60) to (mod 420).

There are other reasons one might prefer larger moduli, though - last year I spend a few months upgrading my own TF sieve from (mod 60) to (mod 4620) because that will support many more threads (each processing k-ranges in one of the admissible remainder classes) than the maximum of 16 permitted by (mod 60). When next I make an official release of my TF code, the intention is that it support manycore architectures.

[GP2]

At the request of bloodIce, I am posting this here:

(As is well-known, all factors of M_p are of the form 2kp+1 for some k)

Here is the distribution of p mod 4, k mod 4 for all known factors (as of 2016-06-03 00:00) of M_p where p is in the range between 900M and 910M:

Count p, k
 ----- ----
 84572 1, 0   47.9%
 91948 1, 3   52.1%

 85123 3, 0   45.9%
100367 3, 1   54.1%

bloodIce mentions that he has trial-factored this range to 64 bits and plans to complete it to 72 bits.

[alpertron]

Since TJAOI found all missing prime factors less than 4*10¹⁸ of Mersenne numbers (including the case when a Mersenne number has several factors less than that bound), I think a better statistic would be found if we ignore the prime factors greater than 4*10¹⁸.

[Dubslow]

Originally Posted by alpertron

Since TJAOI found all missing prime factors less than 4*10¹⁸ of Mersenne numbers (including the case when a Mersenne number has several factors less than that bound), I think a better statistic would be found if we ignore the prime factors greater than 4*10¹⁸.

He did at least for p < 1B.

[Batalov]

I've played with the 900-910M data (fetched from m.org ab initio).
The general count of factors matches, so far so good: there are exactly 362010 reported factors. If you slice the factors in bin sizes by log₂(f) (e.g. in 5-bit bins, or 2-bit bins), the whole observed difference happens for very small k's, and then all counts are equal within the margin of error in every bin up to the current search size.

[ec2-user@ip-172-30-0-237 Mfa]$ awk -F, '(k=int($2/2/$1))<2**25{print $1%4 "\t" k%4 "\t" int(log(k)/log(2)/5)*5 "-..."}' ALLFA | sort -k3n | uniq -c
  10841 1       0       0-...
  18209 1       3       0-...
  10907 3       0       0-...
  26072 3       1       0-...
  15662 1       0       5-...
  15755 1       3       5-...
  15835 3       0       5-...
  16067 3       1       5-...
  14042 1       0       10-...
  14000 1       3       10-...
  14035 3       0       10-...
  14095 3       1       10-...
  12571 1       0       15-...
  12518 1       3       15-...
  12714 3       0       15-...
  12716 3       1       15-...
  11474 1       0       20-...
  11543 1       3       20-...
  11521 3       0       20-...
  11504 3       1       20-...

[ec2-user@ip-172-30-0-237 Mfa]$ wc -l ALLFA
362010 ALLFA

[ec2-user@ip-172-30-0-237 Mfa]$ head ALLFA
900000011,16200000199,2008-05-16
900000041,7200000329,2008-05-16
900000053,5292000311641,2008-05-16
900000067,228834580435461943,2008-06-01
900000067,2268053060043937457,2014-11-04
900000083,17522227932738649217,2009-05-11
900000131,405000058951,2008-05-16
900000131,148307421586967,2011-05-09
900000131,511393347889932024943,2011-08-15
900000131,2497567103149914321769,2011-08-15
...

There can be multiple possible reasons for that. I'll try to fast-factor some Mp where only one very small factor is known; if I'll find at least one factor, then the hypothesis that TJAOI searches for "all" p would fail.

There may be other biases in this dataset as well.
Don't make assumptions about any dataset "just because it is out there" and is easy to fetch. Run sanity checks.

[Batalov]

Originally Posted by R. Gerbicz

I think most of these differences comes from the very small k values, say seeing only k<=100.
q1=6*p+1 is prime with roughly two times higher probability than q2=8*p+1 (you can generalize this),
and use also that for k=1 or 3 mod 4 if q=2*k*p+1 is prime then this divides 2^p-1 with 1/(2*k) probability, for k=0 mod 4 with 1/k probability.
(obviously these are only heuristics). I've gotten even that k=1 mod 4 gives more "small" factors than k=3 mod 4.

Originally Posted by LaurV

That's what I mainly said in the third paragraph. We are in violent agreement here...

We are in violent agreement here...

#Count p  k   GP2%-age    #smallk  #rest   rest %-age
 84572 1, 0   47.9%       10841    73731   50.00%
 91948 1, 3   52.1%       18209    73739   50.00%
 85123 3, 0   45.9%       10907    74216   49.97%
100367 3, 1   54.1%       26072    74295   50.03%

If GP2 posts some new stats in another half a year (please, don't, there is really [B]no need[/B]), we could see perhaps the fourth or the fifth digit behind the dot in the percentages slightly change.

[alpertron]

Originally Posted by Batalov

I'll try to fast-factor some Mp where only one very small factor is known; if I'll find at least one factor, then the hypothesis that TJAOI searches for "all" p would fail.

I ran the P-1 algorithm for several tens of thousands of composite Mersenne numbers less than 2.3M, and I've never found a prime factor less than the ones found by TJAOI, even though I found more than 10000 prime factors.

[bloodIce]

In the process of double-checking the 900-910M range by simply factoring every exponent to 64 bits, I did not see any new factor coming bellow TF60 or any newly factored exponent. So I believe that all exponents are factored to TF60 at least and quite systematically it seems.
I believe that the argument here is that the arrival of new factors in a climb-up trial factoring is biased in k mod 4, not that the final distribution of k mod 4 will be biased.

[Batalov]

Originally Posted by bloodIce

I believe that the argument here is that the arrival of new factors in a climb-up trial factoring is biased in k mod 4, not that the final distribution of k mod 4 will be biased.

On the contrary, all new (read: large k, i.e. k >> 100) factors are unbiased.

The only source of bias is grossly that one class can* have relatively small factors (with k=1, f=2p+1), the other class can only have 3x larger factors (k=3, f=6p+1, - whose density is log(6*905E6)/log(2*905E6) = 1.09 less), and two more classes can only have 4x larger factors (k=4, f=8p+1, - whose density is log(8*905E6)/log(2*905E6) = 1.11 less), that's all. On this gross bias foundation, there is a lesser bias of a few larger k values (see R.G.'s summation), and then there is no residual bias left.

_____________
*The semantics of can here is simple: if f is composite, then its prime factors are obviously ineligible to divide Mp (their effective "k" would be fractional and less than 1). So f must be prime to divide Mp and the probability of prime f is 1/ln f, nothing more, nothing less. If f is prime then its probability of dividing Mp is indistinguishable from any other small factor (all TF/P-1-reachable f << Mp).

[science_man_88]

if it was wanted to restrict k values to those that could lead to prime factors any k values greater than the original k value of the form (2*k*p+1)*n+k would be eliminated as those are all multiples of 2kp+1.