Re: [algogeeks] Re: Application of Prime Number . An Interesting For Geeks
Dear Shashank, What you are trying to do is called " Goldbach's conjecture" . Google for it. There is a million dollar prize to prove it. Ashim On Thu, Mar 24, 2011 at 8:03 PM, ligerdave wrote: > I have to say: "to prove the correctness of this hypotheses" is a > wrong question and there isn't an algorithm for proving something > that's infinity. > > even number is 2n, where n=1 to infinity. > > you can only prove the hypotheses through mathematical methods. > > you can verify the correctness. it's like a P=NP kinda thing. > > > On Mar 24, 1:49 am, bittu wrote: > > yesterday one of the my friends asked this Q to me prove with > > correctness that > > "Every even integer greater than 2 can be expressed as the sum of two > > primes" > > e.g > > > > 4 = 2 + 2 > > 6 = 3 + 3 > > 10 = 7 + 3 or 5 + 5 > > 14 = 3 + 11 or 7 + 7 > > > > Explain & Derive The Time ,Space Complexity of Algorithm > > > > it seems to be that we have to find all possible prime factor of > > number & prints it its not big task , so by checking that number we > > have to generate the all prime factor of it seems O(n) ..Hope i m > > clear corrcet me if i am wrong here.?? > > > > But problem come when even number become bigger say 1 billion 10^9 > > so for this choosing the a number as a prime factor has probability of > > 1/ln(n) > > so say if for 1 billion number out of 21 only 1 is prime. .y question > > is we have to prove the time complexity for two > > choosing a number nearby such big number is 1/ln(n)..?? > > > > with Heuristic justification it can be explained ro induction might > > help but guarantee here but i need some > > mathematical proof for this > > > > Thank & Regards > > Shashank Mani > > CSE,BIT Mesra > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Application of Prime Number . An Interesting For Geeks
Nice @Don! That's something I was thinking but couldn't come up with the name. Finding a large prime itself is already an interesting and difficult thing in number theory. To prove something on top of that could be even more difficult On Mar 24, 12:38 pm, Don wrote: > This is called Goldbach's Conjecture, and has not yet been proven or > disproven. > > Goldbach wrote a letter to Euler in 1742 suggesting that every integer > n > 5 is the sum of three primes. Euler replied that this is > equivalent to every even n > 2 is the sum of two primes--this is now > known as Goldbach's conjecture. Schnizel showed that Goldbach's > conjecture is equivalent to every integer n > 17 is the sum of three > distinct primes. > > It has been proven that every even integer is the sum of at most six > primes and in 1966 Chen proved every sufficiently large even integer > is the sum of a prime plus a number with no more than two prime > factors (a P2). In 1993 Sinisalo verified Goldbach's conjecture for > all integers less than 4*10^11. More recently Jean-Marc Deshouillers, > Yannick Saouter and Herman te Riele have verified this up to 10^14 > with the help, of a Cray C90 and various workstations. In July 1998, > Joerg Richstein completed a verification to 4*10^14 and placed a list > of champions online. More recent work by Oliveira e Silva has extended > this to at least 4*10^17. > > There has been substantial progress on proving that every odd integer> 5 is > the sum of 3 primes, the easier case of Goldbach's conjecture. > > In 1937 Vinogradov proved that this is true for sufficiently large odd > integers n. In 1956 Borodzkin showed n > 3^14348907 is sufficient > (the exponent is 3^15). In 1989 Chen and Wang reduced this bound to > 10^43000. The exponent still must be reduced dramatically before we > can use computers to take care of all the small cases. > > Don > > On Mar 24, 12:49 am, bittu wrote: > > > > > > > > > yesterday one of the my friends asked this Q to me prove with > > correctness that > > "Every even integer greater than 2 can be expressed as the sum of two > > primes" > > e.g > > > 4 = 2 + 2 > > 6 = 3 + 3 > > 10 = 7 + 3 or 5 + 5 > > 14 = 3 + 11 or 7 + 7 > > > Explain & Derive The Time ,Space Complexity of Algorithm > > > it seems to be that we have to find all possible prime factor of > > number & prints it its not big task , so by checking that number we > > have to generate the all prime factor of it seems O(n) ..Hope i m > > clear corrcet me if i am wrong here.?? > > > But problem come when even number become bigger say 1 billion 10^9 > > so for this choosing the a number as a prime factor has probability of > > 1/ln(n) > > so say if for 1 billion number out of 21 only 1 is prime. .y question > > is we have to prove the time complexity for two > > choosing a number nearby such big number is 1/ln(n)..?? > > > with Heuristic justification it can be explained ro induction might > > help but guarantee here but i need some > > mathematical proof for this > > > Thank & Regards > > Shashank Mani > > CSE,BIT Mesra -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Application of Prime Number . An Interesting For Geeks
This is called Goldbach's Conjecture, and has not yet been proven or disproven. Goldbach wrote a letter to Euler in 1742 suggesting that every integer n > 5 is the sum of three primes. Euler replied that this is equivalent to every even n > 2 is the sum of two primes--this is now known as Goldbach's conjecture. Schnizel showed that Goldbach's conjecture is equivalent to every integer n > 17 is the sum of three distinct primes. It has been proven that every even integer is the sum of at most six primes and in 1966 Chen proved every sufficiently large even integer is the sum of a prime plus a number with no more than two prime factors (a P2). In 1993 Sinisalo verified Goldbach's conjecture for all integers less than 4*10^11. More recently Jean-Marc Deshouillers, Yannick Saouter and Herman te Riele have verified this up to 10^14 with the help, of a Cray C90 and various workstations. In July 1998, Joerg Richstein completed a verification to 4*10^14 and placed a list of champions online. More recent work by Oliveira e Silva has extended this to at least 4*10^17. There has been substantial progress on proving that every odd integer > 5 is the sum of 3 primes, the easier case of Goldbach's conjecture. In 1937 Vinogradov proved that this is true for sufficiently large odd integers n. In 1956 Borodzkin showed n > 3^14348907 is sufficient (the exponent is 3^15). In 1989 Chen and Wang reduced this bound to 10^43000. The exponent still must be reduced dramatically before we can use computers to take care of all the small cases. Don On Mar 24, 12:49 am, bittu wrote: > yesterday one of the my friends asked this Q to me prove with > correctness that > "Every even integer greater than 2 can be expressed as the sum of two > primes" > e.g > > 4 = 2 + 2 > 6 = 3 + 3 > 10 = 7 + 3 or 5 + 5 > 14 = 3 + 11 or 7 + 7 > > Explain & Derive The Time ,Space Complexity of Algorithm > > it seems to be that we have to find all possible prime factor of > number & prints it its not big task , so by checking that number we > have to generate the all prime factor of it seems O(n) ..Hope i m > clear corrcet me if i am wrong here.?? > > But problem come when even number become bigger say 1 billion 10^9 > so for this choosing the a number as a prime factor has probability of > 1/ln(n) > so say if for 1 billion number out of 21 only 1 is prime. .y question > is we have to prove the time complexity for two > choosing a number nearby such big number is 1/ln(n)..?? > > with Heuristic justification it can be explained ro induction might > help but guarantee here but i need some > mathematical proof for this > > Thank & Regards > Shashank Mani > CSE,BIT Mesra -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Application of Prime Number . An Interesting For Geeks
I have to say: "to prove the correctness of this hypotheses" is a wrong question and there isn't an algorithm for proving something that's infinity. even number is 2n, where n=1 to infinity. you can only prove the hypotheses through mathematical methods. you can verify the correctness. it's like a P=NP kinda thing. On Mar 24, 1:49 am, bittu wrote: > yesterday one of the my friends asked this Q to me prove with > correctness that > "Every even integer greater than 2 can be expressed as the sum of two > primes" > e.g > > 4 = 2 + 2 > 6 = 3 + 3 > 10 = 7 + 3 or 5 + 5 > 14 = 3 + 11 or 7 + 7 > > Explain & Derive The Time ,Space Complexity of Algorithm > > it seems to be that we have to find all possible prime factor of > number & prints it its not big task , so by checking that number we > have to generate the all prime factor of it seems O(n) ..Hope i m > clear corrcet me if i am wrong here.?? > > But problem come when even number become bigger say 1 billion 10^9 > so for this choosing the a number as a prime factor has probability of > 1/ln(n) > so say if for 1 billion number out of 21 only 1 is prime. .y question > is we have to prove the time complexity for two > choosing a number nearby such big number is 1/ln(n)..?? > > with Heuristic justification it can be explained ro induction might > help but guarantee here but i need some > mathematical proof for this > > Thank & Regards > Shashank Mani > CSE,BIT Mesra -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
