Math question: help online somewhere

Factual Questions
1

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

2

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

3

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 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.

4

…and, having given myself that clue, I was able to find a program online (the Goldbach calculator) that will find the two primes for you!

5

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).

6

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

7

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.

8

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.

9

According to this site, 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.

10

Of course! :smack:

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



#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) ;
}
11

n = 10.

12

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)

13

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.

14

Forget I said anything, never mind…

15

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

16

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?

17

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: