Advertisement
helton

Goldbach Conjecture in Python (complete, including tests)

Jul 13th, 2013
451
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """
  2.   Numerical solution to Goldbach’s conjecture.
  3.  
  4.   Author: Helton Carlos de Souza <heltoncarlossouza@hotmail.com>
  5.  
  6.   The Goldbach’s Conjecture:
  7.   1) Every even number greater than 2 is the sum of two primes
  8.   2) Every odd number greater than 5 is the sum of three primes.
  9. """
  10.  
  11.  
  12. def divisors(n):
  13.     """
  14.        Return a divisors list of a number
  15.        Ex.: Divisors of 12 == [1, 2, 3, 4, 6, 12]
  16.    """
  17.     return [x for x in range(1, n + 1) if n % x == 0]
  18.  
  19.  
  20. def is_prime(n):
  21.     """
  22.        Check if a number is prime (a prime number has as divisors only 1 and itself)
  23.    """
  24.     return divisors(n) == [1, n]
  25.  
  26.  
  27. def prime_range(n):
  28.     """
  29.        Return a list of prime numbers from 2 for n
  30.    """
  31.     return [x for x in range(2, n + 1) if is_prime(x)]
  32.  
  33.  
  34. def goldbach_conjecture(n):
  35.     """
  36.        Goldbach’s conjecture numerical solution
  37.  
  38.        Input  => n:  A integer value
  39.        Return => List of tuples (the sum of these numbers is equal to the input n):
  40.                  The size of tuples in returned list is equal 2 (to even numbers > 2) or 3 (to odd numbers > 5)
  41.                  Obs.: The repeated pairs are removed. For instance, 8 = 3 + 5 or 5 + 3. To more readable answer, the last pair is removed, so 8 = 3 + 5
  42.    """
  43.     if n % 2 == 0:
  44.         if n > 2:
  45.             return [(x, y) for x in prime_range(n) for y in prime_range(n) if x + y == n and x <= y]
  46.         else:
  47.             raise ValueError('Even numbers must be greater than 2')
  48.     else:
  49.         if n > 5:
  50.             return [(x, y, z) for x in prime_range(n) for y in prime_range(n) for z in prime_range(n) if x + y + z == n and x <= y <= z]
  51.         else:
  52.             raise ValueError('Odd numbers must be greater than 5')
  53.  
  54.  
  55. def show_goldbach_conjecture(n):
  56.     """
  57.        Show the goldbach_conjecture result in a "more friendly way"
  58.    """
  59.     tuples_list = goldbach_conjecture(n)
  60.     print(str(n), end='')
  61.     for t in tuples_list:
  62.         print(" = ", end='')
  63.         for index, number in enumerate(t):
  64.             if index == len(t) - 1:
  65.                 print(str(number), end='')
  66.             else:
  67.                 print(str(number) + " + ", end='')
  68.     print()
  69.  
  70.  
  71. def test(number, expected):
  72.     """
  73.        Test if expected value is equal to the returned value in goldbach_conjecture() function
  74.    """
  75.     returned = goldbach_conjecture(number)
  76.     if returned == expected:
  77.         prefix = ' OK '
  78.     else:
  79.         prefix = 'FAIL'
  80.     print('%4s [Number = %4d] returned: %s expected: %s' % (prefix, number, repr(returned), repr(expected)))
  81.     print('-' * 100)
  82.  
  83.  
  84. def run_tests():
  85.     """
  86.        Automated tests for goldbach_conjecture() function
  87.    """
  88.     print ("Testing goldbach_conjecture() function...")
  89.     test(6,    [(3, 3)])
  90.     test(7,    [(2, 2, 3)])
  91.     test(8,    [(3, 5)])
  92.     test(9,    [(2, 2, 5), (3, 3, 3)])
  93.     test(10,   [(3, 7), (5, 5)])
  94.     test(11,   [(2, 2, 7), (3, 3, 5)])
  95.     test(12,   [(5, 7)])
  96.     test(13,   [(3, 3, 7), (3, 5, 5)])
  97.     test(14,   [(3, 11), (7, 7)])
  98.     test(15,   [(2, 2, 11), (3, 5, 7), (5, 5, 5)])
  99.     test(42,   [(5, 37), (11, 31), (13, 29), (19, 23)])
  100.     test(100,  [(3, 97), (11, 89), (17, 83), (29, 71), (41, 59), (47, 53)])
  101.     test(150,  [(11, 139), (13, 137), (19, 131), (23, 127), (37, 113), (41, 109), (43, 107), (47, 103), (53, 97), (61, 89), (67, 83), (71, 79)])
  102.     test(200,  [(3, 197), (7, 193), (19, 181), (37, 163), (43, 157), (61, 139), (73, 127), (97, 103)])
  103.     test(1000, [(3, 997), (17, 983), (23, 977), (29, 971), (47, 953), (53, 947), (59, 941), (71, 929), (89, 911), (113, 887), (137, 863), (173, 827), (179, 821), (191, 809), (227, 773), (239, 761), (257, 743), (281, 719), (317, 683), (347, 653), (353, 647), (359, 641), (383, 617), (401, 599), (431, 569), (443, 557), (479, 521), (491, 509)])
  104.  
  105. if __name__ == '__main__':
  106.     run_tests()
  107.  
  108. """
  109.   Using Python interpreter...
  110.  
  111.   >> from goldbach_conjecture import goldbach_conjecture, show_goldbach_conjecture
  112.   >> goldbach_conjecture(42)
  113.   [(5, 37), (11, 31), (13, 29), (19, 23)]
  114.   >> show_goldbach_conjecture(42)
  115.   42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23
  116. """
Advertisement
RAW Paste Data Copied
Advertisement