Mersenne prime exponent not randomly distributed? - Page 3

Pascal Ochem · 2006-09-13, 12:28

Quote:

Originally Posted by akruppa

The average exponent of 2 in a prime minus 1 is 2. For the Mersenne primes in Dario's list we have an average exponent of 67/29 = 2.31... without M44, and 77/30 = 2.566... with M44. It's a bit above the expected value, but not an awful lot...

Alex

Maybe this behavior has to do with the following result.

Let p = 3 (mod 4) be prime. 2p+1 is also prime if and only if 2p+1 divides Mp.

http://primes.utm.edu/notes/proofs/MerDiv2.html

R.D. Silverman · 2006-09-13, 13:38

Quote:

Originally Posted by alpertron

If f(2,p) is the second largest factor of p-1 (when p is prime), I'm looking for the average of log(f(2,p))/log p in the range (n, 10n) when n -> inf. I think that it should be a constant near 0.2. Please see post #4 again.

Is p any prime, or restricted to Mersenne prime exponents?

If any prime, then your constant should just be the mean value of
Dickman's Rho_2 function, restricted to just ODD integers minus 1.
Asymptotically, I can't think that the fact that p-1 always has the
small factor 2 should affect the distribution of the 2nd largest factor,
except perhaps by a very very small amount.

See Knuth Vol 2. Section 4.5.4, equation (7) which gives
the function you want for all integers. I do not know how to
modify it for just p-1. One can compute the mean just by integrating
(numerically, of course) the RHS of (7) from Beta = 0 to 1.

If you are restricting to just those p for which M_p is prime, then there
isn't any theory (just heuristics) that would lead to a suitable modification of
Knuth's equation 7.

ewmayer · 2006-09-13, 16:25

Quote:

Originally Posted by R.D. Silverman

All this talk about 'random' is meaningless without some rigorous definitions.

If I had to put precise words to any faint possible "signal" I might be surmising exists, I would state things this way:

==========
Conjecture: For the odd primes p for which 2^p-1 is also prime, the average smoothness of the corresponding p-1 factorizations is greater than would be expected for a random collection of primes satisfying the same statistical size distribution (i.e. average ratio of successive p's ~= e^-gamma or about 1.4757...), after removing any bias due to the guaranteed powers 2² or 2¹ appearing in said factorizations depending on whether the individual p == 1 or 3 (mod 4), respectively.
==========

I'm tempted to retitle (or subtitle) this thread using Martin Gardner's appellation of 20-some years ago (cf. Gordon Palameta's post #12 of this thread), about "infuriating hints of order."

(Which likely says more about human nature than about the data in question - but half the fun is playing with the statistical chicken entrails in various ways, while waiting for more data to arrive.)

R.D. Silverman · 2006-09-13, 16:30

Quote:

Originally Posted by ewmayer

If I had to put precise words to any faint possible "signal" I might be surmising exists, I would state things this way:

==========
Conjecture: For the odd primes p for which 2^p-1 is also prime, the average smoothness of the corresponding p-1 factorizations is greater than would be expected for a random collection of primes satisfying the same statistical size distribution (i.e. average ratio of successive p's ~= e^-gamma or about 1.4757...), after removing any bias due to the guaranteed powers 2² or 2¹ appearing in said factorizations depending on whether the individual p == 1 or 3 (mod 4), respectively.
==========

I'm tempted to retitle (or subtitle) this thread using Martin Gardner's appellation of 20-some years ago (cf. Gordon Palameta's post #12 of this thread), about "infuriating hints of order."

(Which likely says more about human nature than about the data in question - but half the fun is playing with the statistical chicken entrails in various ways, while waiting for more data to arrive.)

You also have to be leary of Richard Guy's "Law of small numbers":
Coincidences happen most among small numbers.

(1) The size of the current dataset is small.
(2) The known exponents themselves are small. 8 digits is nothing when
dealing with phenomena that (can) grow as loglog(x) [or worse]
(3) As J. Selfridge said: we know loglog x goes to infinity. But noone
has ever observed it doing so.

ewmayer · 2006-09-13, 16:58

Quote:

Originally Posted by R.D. Silverman

You also have to be leary of Richard Guy's "Law of small numbers"

You won't find me disagreeing with you there - but you (quite correctly) asked for the folks discussing this to provide some mathematically precise verbiage, and this was my attempt to do so.

wblipp · 2006-09-13, 18:32

I did some exploratory data analysis on the number of single digit factors. I got far enough to realize what really needs to be done, but I'm probably not going to have the time to do it soon, so I'll summarize and perhaps someone else will pick up the ball.

Summary
Using mean and standard deviation, the number of 2's looks high and the number of 7's looks very high, while the number of 3's and 5's look typical. All lumped together, the number of single digit factors looks high. However, there is significant skew in the distribution of number of factors, and this is ignored by simple mean and standard deviation analysis, so the real effects are smaller than this approach implies. The exact distribution of the number of single digit factors is easy to derive using numerical convolution, and this is the appropriate way investigate the question.

Distribution of Number of Factors
It's been observed without comment that the expected number of 2's for a random p-1 is 2. This is because the distibution of the number of 2's is a geometric distribution with parameter 1/2. (This is exactly true only in the limit because at any finite p the number of factors is bounded, but the error is smaller than numerical roundoff.) For the number of 3's, the probability of ANY 3's is 1/2 because the residues mod 3 are equally likely to be 0 or 1, but cannot be 2 because then (p-1)+1 would not be prime. The conditional distribution of the number of 3's, given that there are any, will be a geometric distribution with parameter 2/3. This generalizes in the obvious way - the probability of any factors of q is 1/(q-1), and the conditional distribution of the number of factors of q is geometric with parameter (q-1)/q. Straight forward calculations show that the mean number of factors of q is q/(q-1)^2 and the variance is q(q^2-q-1)/(q-1)^4. From this you can calculate the expected number of 2's, 3's, 5's, and 7's in the factors of 30 random (p-1)'s (using the standard and obvious definiton of random - results taken for uniform distribution over bounded range, and the limit taken as the range increases without bound) are

60, 22.5, 9.375, and 5.833, totaling 97.708.

Likewise, the variances are

60, 28.125, 11.133, and 6.644, totaling 105.901.

The observed counts are

77, 26, 9, and 14, totaling 126.

The z-scores are

2.19, 0.66, -0.11, 3.17, and total 2.75

At this point it is tempting to invoke the Central Limit Theorem and declare the distribution of sums should all be approximately normal. But the total appears to be dominated by the result for 7's, and distribution for 7's is roughly the sum of 5 geometric random variables (we expect 5/6 of the 30 factors to have no 7's, and the other 1/6 to have a geometric distribution). This distribution should still show substantial effects of the long geometric tail, causing much higher probabilities of large numbers of 7's than the normal distribution.

What to do next
It would be straight forward although a bit tedious to calculate the skew and kurtosis of the distribution of the number of factors. But the previous section suggests these will probably show that the normal distribution is a poor approximation, and then you have to find a different approximation.

We can avoid all those approximation problems by calculating the exact distribution using numerical convolution. The individual distributions are scaled geometric distributions, and the distribution of the sum of two random variables is the convolution of their distributions. Repeated application of this gives the total distribution. We can truncate the distributions above 126 - say at 150 - and lump the tails into a final category called "large." Then we can exactly answer "what is the probability of 126 or more single digit factors from 30 random (p-1)'s. If nobody else does this first, I'll probably get around to it in a week or two.

T.Rex · 2006-09-14, 10:41

Look also at the factors of 2*q+1 .
Though sometimes there are 4 or 3 factors, most often there are only 2, and also several times it is a prime.
Hope it helps.
T.

ewmayer · 2009-06-12, 20:15

Time to update the table in the original post with the subsequently discovered Mersenne exponents, and now giving both the factorization of p-1 and p+1 for each M-prime exponent p:

Code:

p              p-1       # of p-1 factors     p+1          # of p+1 factors

1279        2.3^2.71             4         2^8.5                9
2203        2.3.367              3         2^2.19.29            4
2281        2^3.3.5.19           6         2.7.163              3
3217        2^4.3.67             6         2.1609               2
4253        2^2.1063             3         2.3.709              3
4423        2.3.11.67            4         2^3.7.79             5
9689        2^3.7.173            5         2.3.5.17.19          5
9941        2^2.5.7.71           5         2.3.1657             3
11213       2^2.2803             3         2.3^2.7.89           5
19937       2^5.7.89             7         2.3.3323             3
21701       2^2.5^2.7.31         6         2.3.3617             3
23209       2^3.3.967            5         2.5.11.211           4
44497       2^4.3^3.103          8         2.19.1171            3
86243       2.13.31.107          4         2^3.3.7187           4
110503      2.3^2.7.877          5         2^3.19.727           5
132049      2^4.3^2.7.131        8         2.5^2.19.139         6
216091      2.3^2.5.7^4          8         2^3.89.607           4
756839      2.23.16453           3         2^3.3.5.7.17.53      8
859433      2^3.7.103.149        6         2.3.143239           3
1257787     2.3^2.69877          4         2^2.7.29.1549        5
1398269     2^2.349567           3         2.3.5.127.367        5
2976221     2^2.5.13.11447       5         2.3.401.1237         4
3021377     2^6.17.2777          8         2.3.503563           3
6972593     2^4.11.173.229       7         2.3.1162099          3
13466917    2^2.3^2.83.4507      6         2.149.45191          3
20996011    2.3^4.5.7^2.23^2    10         2^2.83.63241         4
24036583    2.3.4006097          3         2^3.11.13.21011      6
25964951    2.5^2.11.17.2777     6         2^3.3.13.83221       6
30402457    2^3.3.7.37.67.73     8         2.23.660923          3
32582657    2^10.47.677         12         2.3.5430443          3
37156667    2.19.59.16537        4         2^2.3.3096389        4
42643801    2^3.3^3.5^2.53.149  10         2.197.108233         3
43112609    2^5.7.11.17497       8         2.3^2.5.479029       5

Number of prime factors (including repeated factors):

p-1: 4,3,6,6,3,4,5,5,3,7,6,5,8,4,5,8,8,3,6,4,3,5,8,7,6,10,3,6,8,12,4,10,8 Average = 5.85

p+1: 9,4,3,2,3,5,5,3,5,3,3,4,3,4,5,6,4,8,3,5,5,4,3,3,3,4,6,6,3,3,4,3,5 Average = 4.21

The disparity between the number of factors of the (p-1) and the (p+1) has widened significantly with the last dozen discoveries. Still a small sample set, though.

Mini-Geek · 2009-06-12, 21:18

Quote:

Originally Posted by ewmayer

Still a small sample set, though.

Well, we should try to make that sample set larger!

But really, how large would it have to be to stop saying that?

ewmayer · 2013-02-04, 23:26

In advance of the official announcement of the discovery of the 48th known M-prime, time to revive this dormant thread. Regarding the various measures of smoothness discussed previously here, I think perhaps we've been overlooking a simple standard statistical way of quantifying "expectedness" (or deviation therefrom) of such data.

If you want to see if your 2-year-old is of "normal" height, your pediatrician will invariably express the child's eight in a percentile fashion, relative to the height distribution for some representative cohort of same-aged children. If your child is anywhere near the 50th percentile, that is perfectly average. Less than the 40th or greater than the 60th may be statistically significantly below or above average, depending on how far from 50%, the size and nature of the cohort used as a reference sample, and the measurement error (height varies throughout the day, children will generally span some range of ages, etc). OTOH, percentiles at either extreme nearly always convey a signal.

The same rationale can be applied to (p-1) smoothness of M-prime exponents, with the sample cohort for each p being some sample of generic primes of similar size. For the analysis below, I used M-prime exponents > 10^5 and for each, used a cohort consisting of all primes in the interval [exponent - 10^4, exponent + 10^4]. That yielded sample sizes ranging from around 1700 primes for M(110503), and decreasing gradually to around 1100 primes for the largest known M-primes.

I decided it would be useful to use more than one measure of factorization smoothness, so in addition to the commonly used B-smoothness ("integer n has all prime factors <= B") based solely on the largest factor of the integer in question n, I further define a smoothness measure based on all the prime factors of n, and normalized to lie in the interval (0,1] irrespective of the size of n. The measure I use is a simple one based on an L^p-norm of the logarithmic sizes of the individual prime factors of n: If n has k prime factors f₁ <= f₂ <= ... <= f_k, i.e.
$<br /> n = \prod_{j=1}^{k} f_j ,<br />$
the corresponding L^p-smoothness is defined

$<br /> S_{L^p} := \frac{1}{k}\sqrt[p]{ (\log_n f_1)^p +(\log_n f_2)^p + ... + (\log_n f_k)^p }.<br />$

(Perhaps "L^p roughness" is more apt; we could define the above as the roughness R and then define a corresponding smoothness via S := 1 - R. But for now let's just use "S"). As with the analogous L^p norms from functional analysis, we consider p >= 1.

For any admissible p, the above measure is maximized at 1 for n prime and is < 1 for all composite n. Increasing number of prime factors means more smooth, in the sense that any (k+1)-factor number has norm strictly less than any k-factor number, irrespective of the relative size distributions of the individual prime factors. Obviously for any p >= 1 the associated norm --> 0 as k --> infty. Now let us consider 3 specific values of p which yield smoothness measures differing in interesting ways:

o p = 1: Since the base-n logs of the prime factors of n necessarily sum to 1, S_{L[sup]1[/sup]} = 1/k, the reciprocal of the number of prime factors, irrespective of their relative sizes.

o p = 2: This is the classic Euclidean vector norm applied to the prime factors of n and turned into a smoothness measure via normalization by the prime factor count. Unlike S_{L[sup]1[/sup]}, S_{L[sup]2[/sup]} does take notice of factor size disparities: E.g. for n = f₁ * f₂ a product of 2 primes with, smaller f₁ / f₂ (greater factor size disparity) yields a larger (implying "less smooth") value of S_{L[sup]2[/sup]}.

o p = oo: This yields a smoothness measure based on the supremum ("L infinity") norm. Since taking the limit p --> oo causes all but the largest factor of n to be "powered into oblivion" the resulting smoothness measure superficially appears akin to classical B-smoothness, but notice the log-induced normalization. Further, the smaller factors "are still in there" by way of the 1/k multiplier.

For my little exercise in number crunching that follows, I use S_{L[sup]2[/sup]} in addition to B-smoothness. I wrote a small C program which generates the above prime cohorts and sorts them both by B-smoothness and L²-smoothness. Data dumps and resulting smoothness percentiles for known M-primes (not including the as-yet-unannounced latest one) follow in individual posts-with-gzipped-attachments.

I shall provide data for the newest M-prime as well as a summary tabulation tomorrow. The motivated reader is encouraged to try the other S-measures and let us know whether the resulting numbers differ appreciably from the ones I obtain.

ewmayer · 2013-02-04, 23:30

B -smoothness: 110503 is 901 of 1708, percentile = 47.31
S_{L[sup]2[/sup]}-smoothness: 110503 is 738 of 1708, percentile = 56.85

2013-02-04, 23:26	#32
ewmayer ∂²ω=0 Sep 2002 República de California 103·113 Posts	In advance of the official announcement of the discovery of the 48th known M-prime, time to revive this dormant thread. Regarding the various measures of smoothness discussed previously here, I think perhaps we've been overlooking a simple standard statistical way of quantifying "expectedness" (or deviation therefrom) of such data. If you want to see if your 2-year-old is of "normal" height, your pediatrician will invariably express the child's eight in a percentile fashion, relative to the height distribution for some representative cohort of same-aged children. If your child is anywhere near the 50th percentile, that is perfectly average. Less than the 40th or greater than the 60th may be statistically significantly below or above average, depending on how far from 50%, the size and nature of the cohort used as a reference sample, and the measurement error (height varies throughout the day, children will generally span some range of ages, etc). OTOH, percentiles at either extreme nearly always convey a signal. The same rationale can be applied to (p-1) smoothness of M-prime exponents, with the sample cohort for each p being some sample of generic primes of similar size. For the analysis below, I used M-prime exponents > 10^5 and for each, used a cohort consisting of all primes in the interval [exponent - 10^4, exponent + 10^4]. That yielded sample sizes ranging from around 1700 primes for M(110503), and decreasing gradually to around 1100 primes for the largest known M-primes. I decided it would be useful to use more than one measure of factorization smoothness, so in addition to the commonly used B-smoothness ("integer n has all prime factors <= B") based solely on the largest factor of the integer in question n, I further define a smoothness measure based on all the prime factors of n, and normalized to lie in the interval (0,1] irrespective of the size of n. The measure I use is a simple one based on an L^p-norm of the logarithmic sizes of the individual prime factors of n: If n has k prime factors f₁ <= f₂ <= ... <= f_k, i.e. $<br /> n = \prod_{j=1}^{k} f_j ,<br />$ the corresponding L^p-smoothness is defined $<br /> S_{L^p} := \frac{1}{k}\sqrt[p]{ (\log_n f_1)^p +(\log_n f_2)^p + ... + (\log_n f_k)^p }.<br />$ (Perhaps "L^p roughness" is more apt; we could define the above as the roughness R and then define a corresponding smoothness via S := 1 - R. But for now let's just use "S"). As with the analogous L^p norms from functional analysis, we consider p >= 1. For any admissible p, the above measure is maximized at 1 for n prime and is < 1 for all composite n. Increasing number of prime factors means more smooth, in the sense that any (k+1)-factor number has norm strictly less than any k-factor number, irrespective of the relative size distributions of the individual prime factors. Obviously for any p >= 1 the associated norm --> 0 as k --> infty. Now let us consider 3 specific values of p which yield smoothness measures differing in interesting ways: o p = 1: Since the base-n logs of the prime factors of n necessarily sum to 1, S_{L[sup]1[/sup]} = 1/k, the reciprocal of the number of prime factors, irrespective of their relative sizes. o p = 2: This is the classic Euclidean vector norm applied to the prime factors of n and turned into a smoothness measure via normalization by the prime factor count. Unlike S_{L[sup]1[/sup]}, S_{L[sup]2[/sup]} does take notice of factor size disparities: E.g. for n = f₁ * f₂ a product of 2 primes with, smaller f₁ / f₂ (greater factor size disparity) yields a larger (implying "less smooth") value of S_{L[sup]2[/sup]}. o p = oo: This yields a smoothness measure based on the supremum ("L infinity") norm. Since taking the limit p --> oo causes all but the largest factor of n to be "powered into oblivion" the resulting smoothness measure superficially appears akin to classical B-smoothness, but notice the log-induced normalization. Further, the smaller factors "are still in there" by way of the 1/k multiplier. For my little exercise in number crunching that follows, I use S_{L[sup]2[/sup]} in addition to B-smoothness. I wrote a small C program which generates the above prime cohorts and sorts them both by B-smoothness and L²-smoothness. Data dumps and resulting smoothness percentiles for known M-primes (not including the as-yet-unannounced latest one) follow in individual posts-with-gzipped-attachments. I shall provide data for the newest M-prime as well as a summary tabulation tomorrow. The motivated reader is encouraged to try the other S-measures and let us know whether the resulting numbers differ appreciably from the ones I obtain. Last fiddled with by ewmayer on 2013-02-05 at 00:32 Reason: Fixed some small typoes, added note about disjoint smoothness norm subintervals for different #s of prime factors

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Mersenne Prime Exponent Distribution	PawnProver44	Miscellaneous Math	26	2016-03-18 08:48
PC shuts down randomly. Need Help please	mdq	Hardware	38	2009-05-23 09:35
Fun with the new Mersenne prime exponent	ewmayer	Lounge	4	2006-09-06 20:57
Distributed Factoring and prime testing algorithms	bunbun	Software	6	2006-03-27 17:14
Mersenne composites (with prime exponent)	Dougy	Math	4	2005-03-11 12:14

2006-09-13, 18:32	#28
wblipp "William" May 2003 New Haven 2·7·13² Posts	I did some exploratory data analysis on the number of single digit factors. I got far enough to realize what really needs to be done, but I'm probably not going to have the time to do it soon, so I'll summarize and perhaps someone else will pick up the ball. Summary Using mean and standard deviation, the number of 2's looks high and the number of 7's looks very high, while the number of 3's and 5's look typical. All lumped together, the number of single digit factors looks high. However, there is significant skew in the distribution of number of factors, and this is ignored by simple mean and standard deviation analysis, so the real effects are smaller than this approach implies. The exact distribution of the number of single digit factors is easy to derive using numerical convolution, and this is the appropriate way investigate the question. Distribution of Number of Factors It's been observed without comment that the expected number of 2's for a random p-1 is 2. This is because the distibution of the number of 2's is a geometric distribution with parameter 1/2. (This is exactly true only in the limit because at any finite p the number of factors is bounded, but the error is smaller than numerical roundoff.) For the number of 3's, the probability of ANY 3's is 1/2 because the residues mod 3 are equally likely to be 0 or 1, but cannot be 2 because then (p-1)+1 would not be prime. The conditional distribution of the number of 3's, given that there are any, will be a geometric distribution with parameter 2/3. This generalizes in the obvious way - the probability of any factors of q is 1/(q-1), and the conditional distribution of the number of factors of q is geometric with parameter (q-1)/q. Straight forward calculations show that the mean number of factors of q is q/(q-1)^2 and the variance is q(q^2-q-1)/(q-1)^4. From this you can calculate the expected number of 2's, 3's, 5's, and 7's in the factors of 30 random (p-1)'s (using the standard and obvious definiton of random - results taken for uniform distribution over bounded range, and the limit taken as the range increases without bound) are 60, 22.5, 9.375, and 5.833, totaling 97.708. Likewise, the variances are 60, 28.125, 11.133, and 6.644, totaling 105.901. The observed counts are 77, 26, 9, and 14, totaling 126. The z-scores are 2.19, 0.66, -0.11, 3.17, and total 2.75 At this point it is tempting to invoke the Central Limit Theorem and declare the distribution of sums should all be approximately normal. But the total appears to be dominated by the result for 7's, and distribution for 7's is roughly the sum of 5 geometric random variables (we expect 5/6 of the 30 factors to have no 7's, and the other 1/6 to have a geometric distribution). This distribution should still show substantial effects of the long geometric tail, causing much higher probabilities of large numbers of 7's than the normal distribution. What to do next It would be straight forward although a bit tedious to calculate the skew and kurtosis of the distribution of the number of factors. But the previous section suggests these will probably show that the normal distribution is a poor approximation, and then you have to find a different approximation. We can avoid all those approximation problems by calculating the exact distribution using numerical convolution. The individual distributions are scaled geometric distributions, and the distribution of the sum of two random variables is the convolution of their distributions. Repeated application of this gives the total distribution. We can truncate the distributions above 126 - say at 150 - and lump the tails into a final category called "large." Then we can exactly answer "what is the probability of 126 or more single digit factors from 30 random (p-1)'s. If nobody else does this first, I'll probably get around to it in a week or two.

2006-09-14, 10:41	#29
T.Rex Feb 2004 France 1624₈ Posts	Look also at the factors of 2*q+1 . Though sometimes there are 4 or 3 factors, most often there are only 2, and also several times it is a prime. Hope it helps. T.