princeofsudan

Project Euler #46 Goldbach's other conjecture

Apr 8th, 2013
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.35 KB | None | 0 0
  1. #It was proposed by Christian Goldbach that every odd composite number can be written as the sum of
  2. # a prime and twice a square.
  3.  
  4. #9 = 7 + 2x1**2
  5. #15 = 7 + 2x2**2
  6. #21 = 3 + 2x3**2
  7. #25 = 7 + 2x3**2
  8. #27 = 19 + 2x2**2
  9. #33 = 31 + 2x1**2
  10.  
  11. #It turns out that the conjecture was false.
  12.  
  13. #What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
  14.  
  15. def isPrime(n):
  16.     '''check if integer n is a prime'''
  17.     if n == 2:
  18.         return True
  19.     elif n < 2 or n%2 == 0:
  20.         return False
  21.         # range starts with 2 and only needs to go up the square-root of n
  22.     for x in range(2, int(n**0.5)+1):
  23.         if n % x == 0:
  24.             return False
  25.     return True
  26.  
  27. def isPerfectSquare(n):
  28.     if n < 0:
  29.         return False
  30.     result = int(n**0.5)
  31.     return result*result == n
  32.  
  33. odd = 9
  34. flag = True
  35. while flag:
  36.     if isPrime(odd): #Exluding prime odds from test (check every odd composite number)
  37.         odd += 2
  38.     oddPass = False
  39.     for i in range(2,odd-1):
  40.         if isPrime(odd - i) and i%2 == 0 and isPerfectSquare(i/2):
  41.             #checking if there is a number such that odd-number=prime
  42.             #and if that number is even and number/2 is perfect square
  43.             oddPass = True
  44.             break
  45.     if oddPass:
  46.         odd += 2
  47.     else:
  48.         print odd
  49.         flag = False
Advertisement
Add Comment
Please, Sign In to add comment