Sums of Mersenne Primes
 

Just an exercise:

Every one of the 44 (known) Mersenne prime exponents > 3 can be expressed
as a sum of 9 or fewer smaller Mersenne prime exponents.

Which is the smallest MPE > 3 that can not be expressed as a sum
of 7 or fewer smaller MPEs?

Is it even remotely possible that there is a fixed integer k >= 9 such
that every MPE > 3 can be expressed as a sum of k or fewer smaller MPEs?
(Of course this is trivial if the set of MPEs is finite.)

[QUOTE=davar55;108678]Just an exercise:

Every one of the 44 (known) Mersenne primes > 3 can be expressed
as a sum of 9 or fewer smaller Mersenne primes.

Which is the smallest MP > 3 that can not be expressed as a sum
of 7 or fewer smaller MPs?

Is it even remotely possible that there is a fixed integer k >= 9 such
that every MP > 3 can be expressed as a sum of k or fewer smaller MPs?
(Of course this is trivial if the set of MPs is finite.)[/QUOTE]

:w00t::w00t:

Crapola.

2^127 - 1 > 9 * 2^107-1; M107 is the largest Mp less than M127.

The statement is not clear but maybe the original poster is thinking about the [b]exponents[/b] of the Mersenne primes.

I was using the set {2,3,5,7,13,17,19,31,etc.},
not the set {2^2-1,2^3-1,2^5-1,2^7-1,2^13-1,etc.}.
If it's wrong to refer to the exponents as MPs, I apologize.

[quote=davar55;108682]
If it's wrong to refer to the exponents as MPs, I apologize.[/quote]
Apology accepted: we all do it, relying on the context to make it clear.

Thank you.
Is it too late to rephrase the original post and its title
to refer to Mersenne prime exponents and MPEs instead?
Otherwise this thread may become an orphan.

[QUOTE=davar55;108684]Thank you.
Is it too late to rephrase the original post and its title
to refer to Mersenne prime exponents and MPEs instead?
Otherwise this thread may become an orphan.[/QUOTE]

Assume for the moment that the current conjecture about
Mersenne primes is true: The exponents are Poisson distributed
and the expected number of Mersenne primes between p and 2p
is exp(gamma).

I *very strongly* suspect that whether any exponent is the sum
of at most a fixed finite number of earlier exponents is UNDECIDABLE.
All we would need is that *somewhere* in the sequence a very large
gap exists.

Let us instead ask the following:

Given: An infinite sequence of integers drawn from the same conjectured distribution as Mp.

Consider the set S of ALL such sequences. Do almost all members of this
set (i.e. their density is 1 when counted appropriately) satisfy the
required property? This question may be decidable using ergodic
methods. The answer should strongly depend on the mean of the Poisson
distribution. Exceptions may exist, but they will be quite rare.

Note however that even if a randomly drawn sequence has the requested
property with probability 1, it does not mean that any *particular*
sequence must have it.

Consider the following analagous situation. Consider a sequence of integers
x_i such that sum(1/log(x_i) CONVERGES. Does such a sequence contain
finitely many primes? It can be shown that almost all such sequences do
contain finitely many primes (when "almost all" is considered in a measure-
theoretic sense since the set of all such sequences is uncountable).
But this does not help to prove that any *particular* sequence has this
property. In particular it does not tell us that the Fermat primes are
finite. Indeed, consider the following sequence: Let p_n be the
smallest prime greater than 2^2^n. Then sum(1/log(p_n)) converges,
but every element of this infinite sequence is prime. However, such
sequences are *rare*.

Thus, even if one can prove that almost all Poisson sequences have
the desired property, I think it unlikely that this particular instance
(Mersenne primes) will even be decidable.

(Please delete this post eventually.)
Thanks for fixing that first post, but the first claim should refer
to Mersenne prime exponents twice.
Hope this is worth your time.

[QUOTE=davar55;108678]Is it even remotely possible that there is a fixed integer k >= 9 such that every MPE > 3 can be expressed as a sum of k or fewer smaller MPEs?[/QUOTE]

[QUOTE=R.D. Silverman;108687]Assume for the moment that the current conjecture about Mersenne primes is true: The exponents are Poisson distributed and the expected number of Mersenne primes between p and 2p is exp(gamma).

...

All we would need is that *somewhere* in the sequence a very large gap exists. [/QUOTE]

Which is sufficient to show that it is not remotely possible there is such a k because arbitrarily long gaps almost always exist in Poisson processes.

To see this, consider the argument for the sum of 1024 of fewer MPEs. If we divide the exponents into blocks by doubling (i.e p to 2p, 2p to 4p, 4p to 8p), any stretch of 10 simultaneously empty blocks generates a counter-example. The expected number of Mersenne Primes in any stretch of 10 blocks is N = 10*exp(gamma), and since the distribution is Poisson, the probability of no primes in the stretch is q = exp(-N). Now group the blocks into stretches of 10 blocks. The probability that s stretches are all going to have at least 1 prime is (1-q)^s. By picking s large enough, you can make this probability arbitrarily small. Hence the probability that there will never be a stretch of 10 empty blocks is zero.

Clearly, there isn't anything magic about 1024 - for any finite value of k there is a stretch that works, and enough stretches will always turn up an empty one.

William

[QUOTE=wblipp;108767]Which is sufficient to show that it is not remotely possible there is such a k because arbitrarily long gaps almost always exist in Poisson processes.[/QUOTE]
Has it been rigorously proved that it /is/ a Poisson process?

[QUOTE=axn1;108882]Has it been rigorously proved that it /is/ a Poisson process?[/QUOTE]

Of course not. It isn't even clear what that would mean for a sequence that isn't really random. Heuristics are not proofs.