# Math question: help online somewhere

**URL:** <https://boards.straightdope.com/t/math-question-help-online-somewhere/408641>\
**Category:** Factual Questions\
**Created:** [June 19, 2007, 10:05pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641 "2007-06-19T22:05:09Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![Enderw24](https://avatars.discourse-cdn.com/v4/letter/e/ba9def/32.png) [@Enderw24](https://boards.straightdope.com/u/Enderw24)\
**Post date:** [June 19, 2007, 10:05pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/1 "2007-06-19T22:05:09Z")

</div>

Suppose I am given a problem where I know the sum total of three numbers from 1-1100. I also know nothing about the individual numbers except that all three are different and all three are prime numbers.

So, for instance, x+y+z = 1427 where X,Y, and Z are all prime.

What’s the best way to attempt to solve something like this by hand? Or is there a way to calculate this out using some program online? Even if there are multiple answers to the problem (and I assume in some cases there might be) it could list off what those possibilities would be.

Thanks

---

<div class="post-metadata">

**Author:** ![Arnold\_Winkelried](https://avatars.discourse-cdn.com/v4/letter/a/3d9bf3/32.png) [@Arnold\_Winkelried](https://boards.straightdope.com/u/Arnold_Winkelried)\
**Post date:** [June 19, 2007, 10:57pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/2 "2007-06-19T22:57:25Z")

</div>

Brute force? Store in an array all primes \<= 1427 / 3

then write a program that goes through a loop to find  
prime\_array\* + prime\_array[j] + prime\_array[k] == 1427

---

<div class="post-metadata">

**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\
**Post date:** [June 19, 2007, 11:48pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/3 "2007-06-19T23:48:33Z")

</div>

If the total is an even number, then one of the three primes must be 2. (Three odd numbers can’t add up to an even number, but all primes except 2 are odd.) If [Goldbach’s conjecture](http://en.wikipedia.org/wiki/Goldbach%27s_conjecture) is true (and it certainly is known to be true for integers up to 1100), there must be at least one solution. And if the total T is an odd number, you can start by picking any prime X, and there must be at least one way of finding two other primes Y and Z so that Y + Z = T – X (and thus X + Y + Z = T). But, the primes are not guaranteed to be all different. And I don’t know how you’d find them except by trial and error, preferably with a list of primes handy.

---

<div class="post-metadata">

**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\
**Post date:** [June 20, 2007, 1:10am UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/4 "2007-06-20T01:10:05Z")

</div>

…and, having given myself that clue, I was able to find a program online (the [Goldbach calculator](http://plus.maths.org/issue2/xfile/index.html)) that will find the two primes for you!

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 20, 2007, 1:42am UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/5 "2007-06-20T01:42:05Z")

</div>

[QUOTE=Thudlow Boink]  
…and, having given myself that clue, I was able to find a program online (the [Goldbach calculator](http://plus.maths.org/issue2/xfile/index.html)) that will find the two primes for you!  
[/QUOTE]

Although that program advertises itself as working for all even numbers greater than 4, it fails on 6, since it only reports pairs of distinct primes and the only solution for 6 is 3+3 = 6. (If it was willing to report pairs of nondistinct primes, it could work on 4 as well, with 2+2 = 4; indeed, despite their wording, it appears the program is designed to accept 4 as an input, even though it fails on it like it fails on 6).

---

<div class="post-metadata">

**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\
**Post date:** [June 20, 2007, 3:55am UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/6 "2007-06-20T03:55:16Z")

</div>

Are there any known even numbers besides 4 and 6 for which the only Goldbach pair is degenerate?

---

<div class="post-metadata">

**Author:** ![Enderw24](https://avatars.discourse-cdn.com/v4/letter/e/ba9def/32.png) [@Enderw24](https://boards.straightdope.com/u/Enderw24)\
**Post date:** [June 20, 2007, 1:46pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/7 "2007-06-20T13:46:37Z")

</div>

[QUOTE=Thudlow Boink]  
If the total is an even number, then one of the three primes must be 2. (Three odd numbers can’t add up to an even number, but all primes except 2 are odd.) If [Goldbach’s conjecture](http://en.wikipedia.org/wiki/Goldbach%27s_conjecture) is true (and it certainly is known to be true for integers up to 1100), there must be at least one solution. And if the total T is an odd number, you can start by picking any prime X, and there must be at least one way of finding two other primes Y and Z so that Y + Z = T – X (and thus X + Y + Z = T). But, the primes are not guaranteed to be all different. And I don’t know how you’d find them except by trial and error, preferably with a list of primes handy.  
[/QUOTE]

I figured I would have to just plug and chug on it. I know that whatever N is, the answer most definitely is solveable as three distinct prime numbers. I also know it’s possible (outside the confines of this particular problem) to solve what one of the numbers is. So having the ability to determine what the other two could be is of great assistance. It doesn’t solve it, and I’m still looking for help with that. But this is a good leap in the right direction. Thanks.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 20, 2007, 3:19pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/8 "2007-06-20T15:19:07Z")

</div>

[QUOTE=Arnold Winkelried]  
Brute force? Store in an array all primes \<= 1427 / 3

then write a program that goes through a loop to find  
prime\_array\* + prime\_array[j] + prime\_array[k] == 1427  
[/QUOTE]

This is basically the way I’d approach it, although you’d want to store all of the primes less than your target number. For some large n, it’s possible that the unique decomposition into three primes is 2, 3 and n - 5.

So yeah, use the sieve of Eratosthenes to find all the candidate primes, and then just use a triple loop to try all the possible combinations. You can put in some logic to be clever about not testing combinations that are guaranteed to be too big, but if you’re not in a hurry, 1427 is small enough that you don’t really need it.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [June 20, 2007, 6:59pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/9 "2007-06-20T18:59:23Z")

</div>

[QUOTE=Chronos]  
Are there any known even numbers besides 4 and 6 for which the only Goldbach pair is degenerate?  
[/QUOTE]

According to [this site](http://primes.utm.edu/notes/conjectures/), Schnizel proved that the Goldbach Conjecture is equivalent to “Every integer n \> 17 is the sum of three distinct primes”. Therefore, if the Goldbach Conjecture holds in full, 4 and 6 are the only degenerate cases.

But, should the Goldbach Conjecture happen to fail somewhere, I have no idea whether or not there are cases \> 6 where it succeeds only degenerately.

---

<div class="post-metadata">

**Author:** ![Arnold\_Winkelried](https://avatars.discourse-cdn.com/v4/letter/a/3d9bf3/32.png) [@Arnold\_Winkelried](https://boards.straightdope.com/u/Arnold_Winkelried)\
**Post date:** [June 20, 2007, 9:44pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/10 "2007-06-20T21:44:38Z")

</div>

[QUOTE=ultrafilter]  
This is basically the way I’d approach it, although you’d want to store all of the primes less than your target number. For some large n, it’s possible that the unique decomposition into three primes is 2, 3 and n - 5.  
[/QUOTE]

Of course! :smack:

I wrote this small C program as a proof of concept (got the list of prime numbers from a website)

```auto

#include <stdio.h>
#include <stdlib.h>

extern int main (void)
{
  int p[] = {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, 101, 103, 107, 109, 113,
             127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
             179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
             233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
             283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
             353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
             419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
             467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
             547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
              607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
              661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
              739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
              811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
              877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
              947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
              1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
              1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
              1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
              1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
              1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
              1381, 1399, 1409, 1423, 1427
             } ;
  const int result = 597 ;
  int num_primes ;
  int num_ways ;
  int i ;
  int j ;
  int k ;

  num_primes = sizeof (p) / sizeof (int) ;
  num_ways = 0 ;

  printf ("Ways that 3 different prime numbers can add up to %d
", result) ;

  for (i = 0 ; i < num_primes - 2 && p* + p[i + 1] + p[i + 2] <= result ; i++)
  {
     j = i + 1 ;
     while (j < num_primes - 1 && p* + p[j] + p[j + 1] <= result)
     {
        k = j + 1 ;
        while (k < num_primes && p* + p[j] + p[k] <= result)
        {
           if (p* + p[j] + p[k] == result)
           {
               printf ("%d + %d + %d
", p*, p[j], p[k]) ;
               num_ways++ ;
           }
           k++ ;
        }
        j++ ;
     }
   }

   printf ("%d different ways
", num_ways) ;
  exit (EXIT_SUCCESS) ;
}

```

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [June 20, 2007, 10:04pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/11 "2007-06-20T22:04:04Z")

</div>

[QUOTE=ultrafilter]  
For some large n, it’s possible that the unique decomposition into three primes is 2, 3 and n - 5.  
[/QUOTE]

n = 10.

---

<div class="post-metadata">

**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\
**Post date:** [June 20, 2007, 10:49pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/12 "2007-06-20T22:49:04Z")

</div>

One way to optimize your search is to recognize that for a number to be decomposable into three prime numbers, at least one will be in the range (N/4, N/2)

---

<div class="post-metadata">

**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\
**Post date:** [June 20, 2007, 11:31pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/13 "2007-06-20T23:31:26Z")

</div>

[QUOTE=Punoqllads]  
One way to optimize your search is to recognize that for a number to be decomposable into three prime numbers, at least one will be in the range (N/4, N/2)  
[/QUOTE]  
Why?

If I understand what you’re saying, it’s not true.  
Consider N = 2 + 3 + bigassprime, none of which are between N/4 and N/2.

---

<div class="post-metadata">

**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\
**Post date:** [June 21, 2007, 12:10am UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/14 "2007-06-21T00:10:58Z")

</div>

Forget I said anything, never mind…

---

<div class="post-metadata">

**Author:** ![Santo\_Rugger](https://avatars.discourse-cdn.com/v4/letter/s/e95f7d/32.png) [@Santo\_Rugger](https://boards.straightdope.com/u/Santo_Rugger)\
**Post date:** [June 21, 2007, 1:00am UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/15 "2007-06-21T01:00:31Z")

</div>

[QUOTE=Arnold Winkelried]  
Brute force? Store in an array all primes \<= 1427 / 3

then write a program that goes through a loop to find  
prime\_array\* + prime\_array[j] + prime\_array[k] == 1427  
[/QUOTE]

Why would you use \<=1427/3, and not simply \<=(1427-5) (5, because the smallest two distinct primes are 2 and 3)

---

<div class="post-metadata">

**Author:** ![Arnold\_Winkelried](https://avatars.discourse-cdn.com/v4/letter/a/3d9bf3/32.png) [@Arnold\_Winkelried](https://boards.straightdope.com/u/Arnold_Winkelried)\
**Post date:** [June 21, 2007, 1:23am UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/16 "2007-06-21T01:23:28Z")

</div>

I already smacked myself in the head once, what more do you want from me? My head on a stick? My first-born child? My SDMB password?

---

<div class="post-metadata">

**Author:** ![Santo\_Rugger](https://avatars.discourse-cdn.com/v4/letter/s/e95f7d/32.png) [@Santo\_Rugger](https://boards.straightdope.com/u/Santo_Rugger)\
**Post date:** [June 21, 2007, 4:59pm UTC](https://boards.straightdope.com/t/math-question-help-online-somewhere/408641/17 "2007-06-21T16:59:29Z")

</div>

[QUOTE=Arnold Winkelried]  
I already smacked myself in the head once, what more do you want from me? My head on a stick? My first-born child? My SDMB password?  
[/QUOTE]

Sure, I’ll take your SDMB password.

Sorry, once **ultrafilter** started talking about Eratosthenes, my brain promptly glossed over his entire post. Similarly with your post containing code. I’ll refrain from talking about advance math on this board in the future. :smack: