Finding Sets of 7 Prime Numbers That Sum to 100Date: 05/22/2007 at 08:26:24 From: Eliza Subject: 7 prime numbers that add to 100 I'm wondering what 35 sets of 7 prime numbers add to 100. I don't need to know all of them, but I'm wondering which set: a) has the largest product b) has the largest number I don't know how to solve it other than trial and error, and there are 35 combinations, so trial and error will take forever! I tried using the 6 smallest primes < 100 and then figuring out which other prime would work, but this didn't work. For example: 2+3+5+7+11+13 = 41, and to make 100 I need 49, which is not a prime, so I try my next attempt. 3+5+7+11+13+15 = 54, and to make 100 I need 46, which definitely isn't a prime. I continued on like so, but have still not found an answer. Thanks so much for your help! Date: 05/22/2007 at 10:08:39 From: Doctor Ian Subject: Re: 7 prime numbers that add to 100 Hi Eliza, You don't want to use random trial and error. You want to systematically explore the space of possible answers. That's what a problem like this is designed to give you practice with. How do you do that? Start with the largest of your primes, 97. Then you have a smaller problem: 100 = 97 + (6 primes adding up to 3) You can see that this is impossible, so now you have a smaller set of primes to work with: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 Try it again with 89: 100 = 89 + (6 primes adding up to 11) That doesn't work. How about 83? 100 = 83 + (6 primes adding up to 17) At least that isn't impossible on its face. So now you can start exploring, by considering primes less than 17: 100 = 83 + 13 + (5 primes adding up to 4) x 100 = 83 + 11 + (5 primes adding up to 6) x 100 = 83 + 7 + (5 primes adding up to 10) This works 100 = 83 + 5 + (5 primes adding up to 12) ? 100 = 83 + 2 + (5 primes adding up to 15) ? Some of these, we can just forget about. They represent dead ends. One of them works: 100 = 83 + 7 + 2 + 2 + 2 + 2 + 2 (Note that the problem doesn't say that they primes have to be distinct!) The ones that you aren't sure about, you can decompose into smaller problems again: 100 = 83 + 5 + (5 primes adding up to 12) ? = 83 + 5 + 11 + (4 primes adding up to 1) x = 83 + 5 + 7 + (4 primes adding up to 5) x = 83 + 5 + 5 + (4 primes adding up to 7) x = 83 + 5 + 3 + (4 primes adding up to 9) ? = 83 + 5 + 2 + (4 primes adding up to 10) ? 100 = 83 + 2 + (5 primes adding up to 15) ? = 83 + 2 + 13 + (4 primes adding up to 2) x = 83 + 2 + 11 + (4 primes adding up to 4) x = 83 + 2 + 7 + (4 primes adding up to 8) This works = 83 + 2 + 5 + (4 primes adding up to 10) ? = 83 + 2 + 3 + (4 primes adding up to 12) ? = 83 + 2 + 2 + (4 primes adding up to 13) ? Now, note that we get 83 + 2 + 7 + 3 + 2 + 2 + 2 which is really just a rearrangement of something we already found. How can we eliminate these? One way is to always require our primes to appear in descending order. If we'll find ..., a, b, ... where a is greater than or equal to b, then we'll also find ..., b, a, ... This means we can ignore any sets where a smaller prime precedes a larger one. Does that make sense? That makes our search space smaller: 100 = 83 + 5 + (5 primes adding up to 12) ? = 83 + 5 + 5 + (4 primes adding up to 7) x = 83 + 5 + 3 + (4 primes adding up to 9) ? = 83 + 5 + 2 + (4 primes adding up to 10) ? 100 = 83 + 2 + (5 primes adding up to 15) ? = 83 + 2 + 2 + (4 primes adding up to 13) ? Anyway, the point is that you can proceed systematically, examining each prime as the starting point, and working out what can follow it. In this way, you're guaranteed to find EVERY set of 7 primes that can be added to get 100, and by ignoring 'out of order' sets, you can do it with as little work as possible. And as I said, the point of the problem is to give you practice at doing this kind of careful, systematic search. So for me to just tell you which sets have the largest product and the largest member would be like having me eat vitamins so you can get healthier. :^D Does this help? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/ Date: 05/23/2007 at 01:45:31 From: Eliza Subject: Thank you (7 prime numbers that add to 100) Thanks so much! I was totally confuddled (my word for confused) about the whole question, but now I understand it! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/