Associated Topics || Dr. Math Home || Search Dr. Math

### Finding Sets of 7 Prime Numbers That Sum to 100

```Date: 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.

```

```

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.

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!
```
Associated Topics:
High School Number Theory
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search