 mersenneforum.org Sums of Mersenne Exponents
 Register FAQ Search Today's Posts Mark Forums Read 2009-01-04, 14:58 #1 davar55   May 2004 New York City 102138 Posts Sums of Mersenne Exponents Using the sets Sn of the first n (known) Mersenne Prime exponents, what's the smallest integer (An) that can be written as a sum of distinct elements of Sn in the largest number (Bn) of different ways?   2009-01-04, 15:07 #2 10metreh   Nov 2008 2×33×43 Posts For help, here are the known exponents of Mersenne primes: 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 19937 21701 23209 44497 86243 110503 132049 216091 756839 859433 1257787 1398269 2976221 3021377 6972593 13466917 20996011 24036583 25964951 30402457 32582657 37156667 43112609   2009-07-02, 19:59 #3 davar55   May 2004 New York City 5·7·112 Posts On come on, you can do better than that !   2009-07-02, 21:52 #4 Mini-Geek Account Deleted   "Tim Sorbera" Aug 2006 San Antonio, TX USA 2·3·23·31 Posts Here's my manual brute forcing through n=6: Code:  Primes Sums An Bn B for this A so far 000001 2 2 1 1 000010 3 1 000011 5 2 1 1 000100 5 2 000101 7 1 000110 8 1 000111 10 5 2 1 001000 7 2 001001 9 1 001010 10 2 001011 12 1 001100 12 2 001101 14 1 001110 15 1 001111 17 5 2 1 010000 13 1 010001 15 2 010010 16 1 010011 18 1 010100 18 2 010101 20 1 010110 21 1 010111 23 1 011000 20 2 011001 22 1 011010 23 2 011011 25 1 011100 25 2 011101 27 1 011110 28 1 011111 30 5 2 1 100000 17 2 100001 19 1 100010 20 3 100011 22 2 100100 22 3 100101 24 1 100110 25 3 100111 27 2 101000 24 2 101001 26 1 101010 27 3 101011 29 1 101100 29 2 101101 31 1 101110 32 1 101111 34 1 110000 30 2 110001 32 2 110010 33 1 110011 35 1 110100 35 2 110101 37 1 110110 38 1 110111 40 1 111000 37 2 111001 39 1 111010 40 2 111011 42 1 111100 42 2 111101 44 1 111110 45 1 111111 47 20 3 1 The newest An and Bn calculations are included each time n fully increments. Here's the explanation of those binary numbers you see on the left labeled "Primes": Each bit is one of the set S reversed (17, 13, 7, 5, 3, 2). 1 means to include it in this sum, 0 means to not include it in this sum. e.g. 010000 means include 13, don't include the rest, so sum is 13, and e.g. 001011 means don't include 17, 13, or 5, include 7, 3, and 2, so sum is 12. I can't prove it, but unless the law of small numbers is playing with my logic, I'd suppose An=5 and Bn=2 will continue infinitely. Edit: Just started working to extend it to n=6 and found a third instance of a sum of 20 at 100010 by my binary method, so I'm definitely wrong about 5, 2 continuing indefinitely. Edit again: 2 after that one, I got a second example of a third instance (and a 3rd example another two later)...Seems so far that Bn is limited to ceiling(n/2) Edit 3: Completed to n=6, S6={2, 3, 5, 7, 13, 17}, A6=20, B6=3. (2+5+13=7+13=17+3=20) Last fiddled with by Mini-Geek on 2009-07-02 at 22:14   2009-07-02, 23:18 #5 axn   Jun 2003 123768 Posts Here are the results for up to the first 42. I am running out of memory with excel when trying for higher indexes. Need to move away from excel (duh!). Mersenne Index (Exponent) MaxFrequencySum Frequency Code: M 2 ( 3 ) 2 1 M 3 ( 5 ) 5 2 M 4 ( 7 ) 5 2 M 5 ( 13 ) 5 2 M 6 ( 17 ) 20 3 M 7 ( 19 ) 22 4 M 8 ( 31 ) 39 5 M 9 ( 61 ) 66 6 M 10 ( 89 ) 114 8 M 11 ( 107 ) 129 12 M 12 ( 127 ) 221 17 M 13 ( 521 ) 221 17 M 14 ( 607 ) 760 31 M 15 ( 1279 ) 760 31 M 16 ( 2203 ) 760 31 M 17 ( 2281 ) 3039 58 M 18 ( 3217 ) 5261 59 M 19 ( 4253 ) 6271 84 M 20 ( 4423 ) 8036 135 M 21 ( 9689 ) 11789 155 M 22 ( 9941 ) 18494 243 M 23 ( 11213 ) 20377 357 M 24 ( 19937 ) 32303 469 M 25 ( 21701 ) 42010 795 M 26 ( 23209 ) 52924 1306 M 27 ( 44497 ) 72971 1718 M 28 ( 86243 ) 117483 1775 M 29 ( 110503 ) 172592 3194 M 30 ( 132049 ) 183512 4521 M 31 ( 216091 ) 292894 6134 M 32 ( 756839 ) 292894 6134 M 33 ( 859433 ) 1160267 11795 M 34 ( 1257787 ) 1160267 11795 M 35 ( 1398269 ) 2437565 20756 M 36 ( 2976221 ) 2437565 20756 M 37 ( 3021377 ) 5437333 38044 M 38 ( 6972593 ) 5437333 38044 M 39 ( 13466917 ) 5437333 38044 M 40 ( 20996011 ) 25871742 59769 M 41 ( 24036583 ) 26571417 77479 M 42 ( 25964951 ) 51204169 109648 Last fiddled with by axn on 2009-07-02 at 23:26   2009-07-02, 23:24   #6
axn

Jun 2003

2·2,687 Posts Quote:
 Originally Posted by Mini-Geek I can't prove it, but unless the law of small numbers is playing with my logic, I'd suppose An=5 and Bn=2 will continue infinitely.
Including the recently found one, there are 47 mersenne primes. There are 2^47 distinct combinations. But the max possible sum is around 288 million. So, the _average_ frequency of any given sum is 2^47 / 288 million or roughly 488k. Since average frequency is 488k, the max frequency would be much greater (maybe twice as much?)

Last fiddled with by axn on 2009-07-02 at 23:25 Reason: speelng   2009-07-03, 01:14 #7 axn   Jun 2003 537410 Posts Final numbers: Code: M1(2) @ 2 = 1 M2(3) @ 2 = 1 M3(5) @ 5 = 2 M4(7) @ 5 = 2 M5(13) @ 5 = 2 M6(17) @ 20 = 3 M7(19) @ 22 = 4 M8(31) @ 39 = 5 M9(61) @ 66 = 6 M10(89) @ 114 = 8 M11(107) @ 129 = 12 M12(127) @ 221 = 17 M13(521) @ 221 = 17 M14(607) @ 760 = 31 M15(1279) @ 760 = 31 M16(2203) @ 760 = 31 M17(2281) @ 3039 = 58 M18(3217) @ 5261 = 59 M19(4253) @ 6271 = 84 M20(4423) @ 8036 = 135 M21(9689) @ 11789 = 155 M22(9941) @ 18494 = 243 M23(11213) @ 20377 = 357 M24(19937) @ 32303 = 469 M25(21701) @ 42010 = 795 M26(23209) @ 52924 = 1306 M27(44497) @ 72971 = 1718 M28(86243) @ 117483 = 1775 M29(110503) @ 172592 = 3194 M30(132049) @ 183512 = 4521 M31(216091) @ 292894 = 6134 M32(756839) @ 292894 = 6134 M33(859433) @ 1160267 = 11795 M34(1257787) @ 1160267 = 11795 M35(1398269) @ 2437565 = 20756 M36(2976221) @ 2437565 = 20756 M37(3021377) @ 5437333 = 38044 M38(6972593) @ 5437333 = 38044 M39(13466917) @ 5437333 = 38044 M40(20996011) @ 25871742 = 59769 M41(24036583) @ 26571417 = 77479 M42(25964951) @ 51204169 = 109648 M43(30402457) @ 63851359 = 167111 M44(32582657) @ 68974996 = 260665 M45(37156667) @ 96429723 = 453349 M46(42643801) @ 116789057 = 689687 M47(43112609) @ 139575137 = 1273561   2009-08-22, 18:45   #8
storm5510
Random Account

Aug 2009
Not U. + S.A.

214910 Posts Quote:
 Originally Posted by davar55 Using the sets Sn of the first n (known) Mersenne Prime exponents, what's the smallest integer (An) that can be written as a sum of distinct elements of Sn in the largest number (Bn) of different ways?   2009-08-22, 19:14   #9
Kevin

Aug 2002
Ann Arbor, MI

433 Posts Quote:
 Originally Posted by storm5510 In English, please...
You have a set of integers to work with, namely, the known Mersenne Prime exponents.

Every integer can be written as a sum of distinct known Mersenne Prime exponents in some number of ways. For example, there are zero ways to represent 1. There are two ways to represent 10 (2+3+5, and 3+7. 5+5 doesn't count because "distinct" means you can't use the same number more than once).

There's a large, but still finite number of integers that can be expressed in a non-zero number of ways (because obviously you can't get anything higher than 2+3+5+7+13+...+43112609). So there's going to be a maximum number of ways that an integer can be represented. Being maximum would mean that there are numbers that can be written in k different ways, but no numbers that can be written in k+1 different ways.

Then, once you have the maximum number of ways an integer can be represented as a sum of distinct Mersenne primes, the next question is "What is the smallest number which can be represented in this many ways?". If the maximum is 5, what is the smallest number that can be written as a sum of 5 distinct known Mersenne Prime exponents?

That's what the question is for all known Mersenne Prime exponents. Then what one can do is play the same game with just the first 3 known Mersenne Prime exponents, then the first 4, then the first 5, etc. Each one is a whole separate question. So your set of possible summands (S_n), will be the set of the first n known Mersenne Prime exponents. The maximum number of ways an integer can be written using distinct elements from that set will be called B_n. And then the smallest number that can be written in B_n different ways will be called A_n.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 15 2016-01-23 20:53 baha2007 Information & Answers 2 2007-12-08 20:12 davar55 Puzzles 14 2007-06-29 17:17 Xordan Math 4 2007-06-07 16:05 bearnol Science & Technology 7 2006-01-20 04:04

All times are UTC. The time now is 22:33.

Sun Jun 26 22:33:59 UTC 2022 up 73 days, 20:35, 1 user, load averages: 0.97, 1.58, 1.85