Finding the Optimal Product of Primes for Sum of 100

In summary, There are 35 combinations of 7 prime numbers that add up to 100. The smallest 5 numbers in the list add up to 39, therefore all numbers bigger than 59 can be excluded. By using modular arithmetic, it is possible to find 4 solutions for the remaining combinations. A naive program in C++ was also provided to find all possible combinations.
  • #1
Gib Z
Homework Helper
3,351
7
Hey guys I really need some help as fast as you can give it to me. Basically I want to find a selection of 7 of the following numbers, which are primes. These selections have to add up to 100 exactly, and I know that there are 35 combinations.

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

I know that for 7 of these to add up to 100 2 needs to be one of the selections. What I need to be able to do is find the combination of 7 selections which add up to 100, that has the largest product! So if you know some programming, can you test all combinations? If not, do it another way? Please help asap!
 
Mathematics news on Phys.org
  • #2
Well if you want to do it fast, then here's a way of reducing the amount of combinations involved, as you say you need to include 2, so you may as well drop that out of your list and try to sum to 98.

Furthermore, if you need 6 numbers (on this new list without 2), then on the new list the smallest 5 numbers adds up to 39, 98 - 39 = 59, so you may as well get rid of all numbers bigger than 59, leaving your new list as:

3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59

Testing all combinations might not be as difficult now, also consider if a rectangle has a fixed perimetre then its greatest area is a square, so I imagine looking for numbers which are close to each other will get you the greatest product, like:

31, 7, 11, 13, 17, 19

or:

23, 29, 11, 13, 17, 5
 
  • #3
*sigh* Ok I will try to list all the combinations of 6 numbers from your list that add up to 100. If anyone else could be so kind, could you guys post up any combinations you get listing the numbers in ascending order? I will post back when I get at least another 5.
 
  • #4
To be honest I think this might be the answer:

7, 11, 13, 17, 19, 31

Seems to have the lowest variance out of any combination, difficult to verify though, I might try typing up a naive program in C++ shortly and see how long it takes to compute.
 
  • #5
Thank you so so so much! I am make virtually no progress going through the manual combinations..
 
  • #6
You can cut down the search a lot by using modular arithmetic.

All primes > 3 are equal to either 1 or 5 mod 6.
98 = 2 mod 6.
The only possibilities that sum to 2 mod 6 are
1+1+1+1+5+5, 1+5+5+5+5+5, 3+1+1+1+1+1, 3+1+1+5+5+5

Consider the first option 1+1+1+1+5+5.
The only sums of 4 primes equal to 1 mod 6 that are less than 98 are
7+13+19+31 = 70
7+13+19+37 = 76
7+13+19+43 = 82

So the 2 primes equal to 2 mod 6 must sum to 16, 22, or 28.
The only options are
5+11=16
5+17=22
5+23=28
11+17=28

So we have 4 solutions, so far.

The rest is left as an exercise for the reader.
 
  • #7
I'm afraid I don't understand...we are only allowed to use each prime once by the way. What do we have 4 solutions to??..sorry if i seem slow long day today..
 
  • #8
You were right about there being 35, this is what i got:
Code:
2, 5, 11, 13, 17, 23, 29
2, 3, 11, 13, 19, 23, 29
2, 3, 7, 17, 19, 23, 29
2, 7, 11, 13, 17, 19, 31
2, 3, 11, 13, 17, 23, 31
2, 5, 7, 13, 19, 23, 31
2, 3, 5, 17, 19, 23, 31
2, 3, 7, 11, 17, 29, 31
2, 3, 5, 13, 17, 29, 31
2, 3, 5, 11, 19, 29, 31
2, 3, 5, 7, 23, 29, 31
2, 5, 7, 13, 17, 19, 37
2, 3, 7, 11, 17, 23, 37
2, 3, 5, 13, 17, 23, 37
2, 3, 5, 11, 19, 23, 37
2, 3, 5, 11, 13, 29, 37
2, 3, 5, 7, 17, 29, 37
2, 3, 7, 11, 17, 19, 41
2, 3, 5, 13, 17, 19, 41
2, 3, 7, 11, 13, 23, 41
2, 3, 5, 7, 19, 23, 41
2, 3, 5, 7, 13, 29, 41
2, 3, 5, 7, 11, 31, 41
2, 5, 7, 11, 13, 19, 43
2, 3, 5, 11, 17, 19, 43
2, 3, 5, 11, 13, 23, 43
2, 3, 5, 7, 17, 23, 43
2, 3, 5, 7, 11, 29, 43
2, 3, 7, 11, 13, 17, 47
2, 3, 5, 11, 13, 19, 47
2, 3, 5, 7, 17, 19, 47
2, 3, 5, 7, 13, 23, 47
2, 3, 5, 7, 13, 17, 53
2, 3, 5, 7, 11, 19, 53
2, 3, 5, 7, 11, 13, 59
 
  • #9
Thanks -Job- ! If anyone doesn't know a quicker way, ill go multiply these out on my calculator. Thanks!
 
  • #10
Here's my quite badly written very naive code in C++

Code:
#include <iostream>
#include <string>
#include <fstream>

using namespace std;

void mypause() 
{ 
     
  std::cout<<"               Press [Enter] to continue . . .";
  std::cin.get();
} int main(int argc, char* argv[])
{
    int prime [] = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};
    int bigprime [5];
    int i = 15;
    int prime1;
    int prime2;
    int prime3;
    int prime4;
    int prime5;
    int prime6;
    int sum = 0;
    int prod;
    int prod1 = 0; 
    while(i > -1)
    {
              prime1 = prime[i];
              int j = i - 1;
              while (j > -1)
              {
                    prime2 = prime[j];
                    sum = prime1 + prime2;
                    if (sum < 82)
                    {
                    int k = j - 1;
                    while (k > -1)
                    {
                          prime3 = prime[k];
                          sum = prime1 + prime2 + prime3;
                          if (sum < 89)
                          {
                          int l = k -1;
                          while (l > -1)
                          {
                                prime4 = prime[l];
                                sum = prime1 + prime2 + prime3 + prime4;
                                int m = l - 1;
                                if (sum < 94)
                                {
                                while (m > -1)
                                {
                                      prime5 = prime[m];
                                      sum = prime1 + prime2 + prime3 + prime4 + prime5;
                                      if (sum < 97)
                                      {
                                      int n = m -1;
                                      while (n > -1)
                                      {
                                            prime6 = prime[n];
                                            sum = prime1 + prime2 + prime3 + prime4 + prime5 + prime6;
                                            if (sum == 98)
                                            {
                                                    prod = prime1 * prime2 * prime3 * prime4 * prime5 * prime6;
                                                    cout << " || ";
                                                    cout << prime1 ;
                                                    cout << " ";
                                                    cout << prime2 ;
                                                    cout << " ";
                                                    cout << prime3 ;
                                                    cout << " ";
                                                    cout << prime4 ;
                                                    cout << " ";
                                                    cout << prime5 ;
                                                    cout << " ";
                                                    cout << prime6 ;
                                                    cout << " , ";
                                                    cout << prod ; 
                                                    cout << " || \n";
                                                    if (prod > prod1)
                                                    {
                                                            prod1 = prod;
                                                            bigprime[0] = prime1;
                                                            bigprime[1] = prime2;
                                                            bigprime[2] = prime3;
                                                            bigprime[3] = prime4;
                                                            bigprime[4] = prime5;
                                                            bigprime[5] = prime6;
                                                    }                                                    
                                            }
                                            n--;
                                      }
                                      }
                                      m--;
                                }
                                }
                                l--;
                          }
                          }
                          k--;
                    }
                    }
                    j--;
              }
              i--;
               
    }
    
    cout << "\n";
    cout << bigprime[0];
    cout << " ";
    cout << bigprime[1];
    cout << " ";
    cout << bigprime[2];
    cout << " ";
    cout << bigprime[3];
    cout << " ";
    cout << bigprime[4];
    cout << " ";
    cout << bigprime[5];
    cout << "    ";
    cout << prod1;
    cout << "  \n \n";
    
    mypause();
}

It outputs each combination, followed by a comma, followed by their product.

Then at the end gives the biggest product, with the primes used in the product, here's a screenshot of the output:

http://zurtex.googlepages.com/primes1.jpg [Broken]
 
Last edited by a moderator:
  • #11
I Check back to this page too late :( wow Like 25 mins too late...we'll I get the same solution multiplying them out :) Thanks heaps :D!
 
  • #12
Gib Z said:
I'm afraid I don't understand...we are only allowed to use each prime once by the way. What do we have 4 solutions to??..sorry if i seem slow long day today..

Sorry for not being clear. I meant 4 solutions to the subproblem "find 6 primes that add up to 98".

FWIW you don't need to work through every combination. The "1+5+5+5+5+5 mod 6" case gives one more possibility, so all the sets of primes that sum to 98 and do not include 3 are

5 7 11 13 19 43
5 7 13 19 23 31
5 7 13 17 19 37
5 11 13 17 23 29
7 11 13 17 19 31

The largest product is the 7*11*13*17*19*31 = 10023013.

Suppose there was a larger product 3*p1*p2*p3*p4*p5 where 3+p1+p2+p3+p4+p5 = 98.

Then p1*p2*p3*p4*p5 > 10023013/3
So the geometric mean of p1..p5 > (10023013/3)^{1/5} > 20 .

But the arithmetic mean of p1..p5 > the geometric mean > 20
So p1+p2+p3+p4+p5 > 100, which is impossible.

This is just to demonstrate that you don't HAVE to use a computer to solve this type of problem :tongue:
 
Last edited:
  • #13
Hey guys I found the solution that my teacher said I should have used.

Zurtex I should have listened to your idea about the combination with the numbers closest together :) My teacher said to find the numbers with the smallest deviation, so basically i had to find 6 primes that are close t0 98/6 =16 and 2/3

Thanks tonnes guys!
 
  • #14
AlephZero said:
Sorry for not being clear. I meant 4 solutions to the subproblem "find 6 primes that add up to 98".

FWIW you don't need to work through every combination. The "1+5+5+5+5+5 mod 6" case gives one more possibility, so all the sets of primes that sum to 98 and do not include 3 are

5 7 11 13 19 43
5 7 13 19 23 31
5 7 13 17 19 37
5 11 13 17 23 29
7 11 13 17 19 31

The largest product is the 7*11*13*17*19*31 = 10023013.

Suppose there was a larger product 3*p1*p2*p3*p4*p5 where 3+p1+p2+p3+p4+p5 = 98.

Then p1*p2*p3*p4*p5 > 10023013/3
So the geometric mean of p1..p5 > (10023013/3)^{1/5} > 20 .

But the arithmetic mean of p1..p5 > the geometric mean > 20
So p1+p2+p3+p4+p5 > 100, which is impossible.

This is just to demonstrate that you don't HAVE to use a computer to solve this type of problem :tongue:

That sounds like that would have been a good idea too, thanks!
 
  • #15
u could have just used matlab.
 
  • #16
I am not familiar with matlab, and in general I don't know how to use any mathematical software like Maple or Mathematicia. I am assuming MATLAB is another.
 

1. What is a Product of Primes Programmers?

A Product of Primes Programmers refers to a specific group of programmers who specialize in developing algorithms and software related to prime numbers and their products. These programmers often work on projects involving cryptography, data encryption, and number theory.

2. What skills are required to become a Product of Primes Programmer?

To become a Product of Primes Programmer, one must have a strong understanding of mathematics, particularly in the field of number theory. They should also have strong coding skills in languages such as Python, C++, and Java, as well as experience with data structures and algorithms.

3. What types of projects do Product of Primes Programmers work on?

Product of Primes Programmers work on a variety of projects, including creating efficient algorithms for factoring large prime numbers, developing cryptographic systems for secure communication, and optimizing data encryption methods. They may also work on research projects related to prime numbers and their applications.

4. What makes Product of Primes Programmers unique?

Product of Primes Programmers possess a unique skill set that combines advanced mathematical knowledge with programming expertise. They are able to apply their understanding of number theory to real-world problems and develop innovative solutions using code.

5. What are some examples of real-world applications of Product of Primes Programming?

Product of Primes Programming has many practical applications, including secure online transactions, data encryption for sensitive information, and digital signature verification. It is also used in fields such as finance, telecommunications, and cybersecurity to ensure the security and confidentiality of data and communications.

Similar threads

Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
Replies
14
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
Replies
6
Views
2K
Replies
3
Views
1K
  • General Math
Replies
7
Views
3K
Replies
9
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
990
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
Back
Top