mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2009-01-04, 14:58   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

102138 Posts
Default 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?
davar55 is offline   Reply With Quote
Old 2009-01-04, 15:07   #2
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

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
10metreh is offline   Reply With Quote
Old 2009-07-02, 19:59   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

5·7·112 Posts
Default

On come on, you can do better than that !
davar55 is offline   Reply With Quote
Old 2009-07-02, 21:52   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2·3·23·31 Posts
Default

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
Mini-Geek is offline   Reply With Quote
Old 2009-07-02, 23:18   #5
axn
 
axn's Avatar
 
Jun 2003

123768 Posts
Default

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
axn is offline   Reply With Quote
Old 2009-07-02, 23:24   #6
axn
 
axn's Avatar
 
Jun 2003

2·2,687 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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
axn is offline   Reply With Quote
Old 2009-07-03, 01:14   #7
axn
 
axn's Avatar
 
Jun 2003

537410 Posts
Default

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
axn is offline   Reply With Quote
Old 2009-08-22, 18:45   #8
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
Not U. + S.A.

214910 Posts
Default

Quote:
Originally Posted by davar55 View Post
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?
In English, please...
storm5510 is offline   Reply With Quote
Old 2009-08-22, 19:14   #9
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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.
Kevin is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Observation about Mersenne exponents paulunderwood Miscellaneous Math 15 2016-01-23 20:53
Mersenne exponents verified baha2007 Information & Answers 2 2007-12-08 20:12
Sums of Mersenne Primes davar55 Puzzles 14 2007-06-29 17:17
Mersenne exponents Xordan Math 4 2007-06-07 16:05
Sending Mersenne exponents into space 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔