Goldbach Conjecture

**StarOrbs** · 03-15-2005

After many hours I figure out 1 part of what I have to do with this.

I have to enter a positive integer: 44
then this has to output
44 = 3 + 41
44 = 2 + 5 + 37

First off I have to find out if a positive integer is true for the goldbach conjecture.

Every even number > 2 is a sum of two primes
Every integer > 5 is a sum of three primes
For example
44 = 3 + 41
44 = 2 + 5 + 37

346 = 29 + 317
346 = 2 + 7 + 337

Okay now I figured out how to do the sum of two primes for every number greater than 2 by..

44 % 44 = 1
44 is not prime, 1 is not prime

44 % 41 = 3
41 is prime, 3 is prime
therefore 44 = 3 + 41

Now I don't know how to get
44 = 2 + 5 + 37 which is under the sum of 3 primes rule

I have to do this kind of begginer(ish) wise. lol. I can never think of the right word for that. I appreciate any ideas or suggestions. I would also appreciate if anyone could give me any ideas on an easy way to determine if a number is prime.

**PJYelton** · 03-15-2005

Do a search of this board for functions that determine primes, its been asked a lot before.

As for finding 3 numbers, an idea you could try is do exactly what you did for 2 primes, then when you get the second number after taking the modulus, just run your modulus function again on the new number. Then you have three numbers and you just need to figure out if each are prime.

For example, 44%42=2, 42%37=5. 37, 5, 2 are all prime.

Might not be the ideal way to solve this problem, but its the most similar to what you have already so would be easy to understand.

**Hunter2** · 03-15-2005

>>on an easy way to determine if a number is prime.
The most obvious solution is simply to loop from 2 to (squareroot of the number), checking to see if the number is divisible by each.

A slightly more complicated (but more efficient, if you're generating a list of primes) approach would be to store a std::list or std::vector of prime numbers as you encounter them, and only check if:
1) Is it one of the already-found primes?
2) Is it divisible by one of the already-found primes?
3) If the largest already-found prime < (square root of number), loop from that value until (square root of number) checking for divisibility.

>>Now I don't know how to get...
Perhaps you could try:

Loop through your list of primes, and for each one:
-Subtract by the current prime number
-Check the result against the "sum of 2 primes" rule

Just a thought.

**StarOrbs** · 03-15-2005

I get how you did 44%42 to get 2 then subtract 2 from 44 to get 42.. but how did you get to 37 there are several prime numbers above and below 37?

**PJYelton** · 03-15-2005

I simplified because I wasn't exactly sure how your algorithm worked. Basically, just do exactly how you did Goldbach with 2 numbers. If I was to ask you to find two primes that add to 42 you could do it right?

**StarOrbs** · 03-15-2005

Alright thanks a lot I got it. Now I just have to determine if a number is prime and I'm set. Thanks a lot guys/gals.

**StarOrbs** · 03-16-2005

What I don't understand is with the way you determine the 3 numbers. It works if the main number is even, but it doesn't always work when it's odd or prime. Also it always says that you should just subtract 2 from 44 which gives you 42 then I do the same thing but I'm still going to get 2 first when I do 42% 40.

**Hunter2** · 03-16-2005

Ok, well.. it's pretty much:

Code:

Loop from 1 to (the number, n):
  If (current number, i) is prime, then:
    Take (n - i), call it 'm'.
    Loop from 1 to m:
    If (current number, j) is prime, then:
      Take (m - j), and see if that's prime. If it is, then you've got your 3 primes.

**StarOrbs** · 03-16-2005

Okay I tried to implement that idea but I must be missing something, I tried adding and removing a bunch of things but it always gives me 0 or some garbage answer. The prime() function determines if its prime by returning 'y' or 'n'. Any errors or mistypes does anyone see? Thanks...

Code:

	for (i = 1; i < newInNum; i++)
	{
		prime(newInNum, primeAns1);
		prime(i, primeAnsI);
		
		if (primeAnsI == 'y' && primeAns1 == 'y')
			{
				nextLevNum = newInNum - i;
			
				for (i = 1; i < nextLevNum; i++)
					{
						prime(nextLevNum, primeAnsNext);
						if (primeAnsNext == 'y')
							{
								lastNum = nextLevNum - newInNum;
								prime (lastNum, primeAnsLast);
								if (primeAnsLast == 'y')
								{
									ansThree = lastNum - nextLevNum;
									break;
									
								}
							}
							
					}
			}
			
	}

**PJYelton** · 03-16-2005

I'm assuming newInNum is your starting number. If so, why are you checking to see if it is prime at the beginning? For example, if you do newInNum=44, then your if function will always be false since 44 isn't prime. I think you mean to check newInNum-i.

**StarOrbs** · 03-17-2005

Okay so now all I get is when I enter a number is for example 13 = 0 + 0 + 12 or 44 = Garbage + 0 + 43 I tried rearranging some variables and changing other variables. Any other ideas? I've been spending almost my entire sprink break on this last part. I only got 4 days left hopefully I'll at least have a weekend to sit and do nothing, lol.. Thanks everyone for your help.

Code:

for (i = 1; i < newInNum; i++)
	{
		nextLevNum = newInNum - i;
			
				for (i = 1; i < nextLevNum; i++)
					{
						prime(nextLevNum, primeAnsNext);
						if (primeAnsNext == 'y')
							{
								lastNum = nextLevNum - newInNum;
								prime (lastNum, primeAnsLast);
								if (primeAnsLast == 'y')
								{
									ansThree = lastNum - nextLevNum;
									
									
								}
								
							}
							
					}
			
			
	}

**Zach L.** · 03-17-2005

Quick suggestion here (didn't get to read all the posts, not much time):
If you are keeping a long list of primes (for use with multiple numbers, so you don't have to regenerate them), then you can estimate what index you'll need to start looking at for primes about the same size as your number by using the prime distribution theorem: http://www.math.okstate.edu/~wrightd...ay/node17.html
Not a great estimate, but certainly a start.

**StarOrbs** · 03-17-2005

Sorry zach that doesn't have anything to do with what I'm doing. I'm still trying to figure out how to get the 3 primes for 13 for example which is 13 = 3 + 5 + 5

**spydoor** · 03-17-2005

you cannot use i as the iterator for both your inner and outer loop

based on Hunter2's logic

Code:

int main(void)
{
    int number = 13;
    int m;
    int i,j;

    for(i=1; i <= number; i++) {
        if(isPrime(i))
        {
            //We have prime1, check for prime2 in   number-prime1
            m = number-i;

            for(j=1; j < m; j++)
            {
                if(isPrime(j))
                {
                    //We have 2 primes, if   number-(prime1+prime2) is prime..... success
                    if(isPrime(number-(i+j)))
                    {
                        printf("%d %d %d\n", i, j, number-(i+j));
                    }
                }
            }
        }
    }

    return 0;
}

oops.. sorry for the C code

**StarOrbs** · 03-17-2005

I've never used:
printf("%d %d %d\n", i, j, number-(i+j));

Could you tell me what that would mean in cout... I haven't used that yet.

Thread: Goldbach Conjecture

Thread Tools

Search Thread

Display

Goldbach Conjecture

Similar Threads

Goldbach's Conjecture

Goldbach's conjecture

Godbach conjecture!!