 # 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. """