Skip to main content

Problem 46 Project Euler Solution with python

Goldbach's other conjecture

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
It turns out that the conjecture was false.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?


Algorithm for this program is simple. We will start with number 3. As we don't know the upper limit, we will use a while loop. Question states that the number on the left hand side is a composite odd number. Now let us consider the equation given in the question as follows:

number = prime + 2 × some_number2
⇒ some_number = ((number-prime)/2)1/2

In the above equation for some_number to be a positive integer there are two conditions, value of number should be greater than prime number or we can say - We can iterate with the prime numbers below number. Value of some_number((number-prime)/2) should be a perfect number.

Coming back to our program and its iterations, as 3 is a prime number we will add it to a list of prime numbers. The next odd number is 5, which is again a prime number so add it to primes list. 7 is again a prime number. 9, this is a composite number. We will take a number from [2,3,5,7](prime numbers below 9) and check for the condition - the value of (number-prime)/2 to be a perfect number. If this condition is satisfied with any of the prime numbers below 9 then the number satisfies Goldbach other conjecture. In case of 9, it satisfies the condition.

 But at some point the given number does not satisfy the condition, which is the required answer.

Program


 As already explained, in this program we have written a function is_prime to check if the number is prime or not. 

number = 3
This will be the iter for our while loop.

primes = [2]
As we are not looping through any even numbers, we will add the only even prime in the list to check for the condition. All the other primes will be added to the list further down at the while loop during iterations.


# while loop
while True:
 if is_prime(number):
  primes.append(number)
 else:
  for i in primes:
   if math.sqrt(((number-i)/2)) == int(math.sqrt(((number-i)/2))):
    break
  else:
   print number
   break

 number += 2
As per the question we only need composite odd numbers, also for our calculations we need prime numbers, so in this part of while loop we will check if the number at which we are iterating is prime or not, if it is prime then we will add it to prime number list. If the number is not a prime number i.e if it is a odd composite number, then take each and every number in the primes list(largest number in the list at any given iteration is less than the iterator) and check for the condition((number-prime)/2)
which we have discussed above. We have used for else. You should learn more about for else from google if you are not good at it. It is a good and useful concept for control flow.

 Everything else is easy. I suggest you to take an example i.e start from 3 try all the iterations upto 15(atleast), I am sure you will for sure understand the while loop(and everything else) easily.

 You can download the above source code from Github Gist 46.py

Output


Summary

This is a different problem, it demanded thinking upto infinity. We also had to break out of the loop once the solution is found. I personally liked this problem. When I first wrote a solution for this problem, execution time was around 6 seconds, then I modified the program and then the execution time dropped to 4 seconds. At the end I further modified the program a little bit and then, execution time fell down to less than 0.1 seconds. A very drastic change. I am satisfied with the program. But still there is scope for improvement. 

 As always you can comment in the comment box below if you have any doubt or have not understood anything. I will be glad to help you.

 Please do comment in the comment box below, if you have found any typo, or have a different program or have a better program or have any suggestion. I will be very happy to view each of them.

You can also contact me.

Thank you. Have a nice day😃! 
My References: Toying with a lesser known Goldbach Conjecture
  A lesser knon Goldbach Conjecture
Goldbach Conjecture Wikipedia
Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more