Goldbach Conjecture

This is a discussion on Goldbach Conjecture within the C++ Programming forums, part of the General Programming Boards category; After many hours I figure out 1 part of what I have to do with this. I have to enter ...

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    59

    Goldbach Conjecture

    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.

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  3. #3
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    >>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.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  4. #4
    Registered User
    Join Date
    Feb 2005
    Posts
    59
    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?

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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?

  6. #6
    Registered User
    Join Date
    Feb 2005
    Posts
    59
    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.

  7. #7
    Registered User
    Join Date
    Feb 2005
    Posts
    59
    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.

  8. #8
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    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.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  9. #9
    Registered User
    Join Date
    Feb 2005
    Posts
    59
    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;
    									
    								}
    							}
    							
    					}
    			}
    			
    	}

  10. #10
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  11. #11
    Registered User
    Join Date
    Feb 2005
    Posts
    59
    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;
    									
    									
    								}
    								
    							}
    							
    					}
    			
    			
    	}

  12. #12
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  13. #13
    Registered User
    Join Date
    Feb 2005
    Posts
    59
    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

  14. #14
    Registered User
    Join Date
    Mar 2005
    Posts
    140
    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
    Last edited by spydoor; 03-17-2005 at 01:48 PM.

  15. #15
    Registered User
    Join Date
    Feb 2005
    Posts
    59
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Goldbach's Conjecture
    By cashmerelc in forum C Programming
    Replies: 7
    Last Post: 07-19-2010, 11:41 PM
  2. Goldbach's conjecture
    By dcwang3 in forum C Programming
    Replies: 10
    Last Post: 10-14-2008, 02:34 AM
  3. Godbach conjecture!!
    By Leojeen in forum C Programming
    Replies: 10
    Last Post: 04-20-2008, 07:42 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21