Return to Answer

# Goldbach's Conjecture tester. from gmpy2 import is_prime import sys import cProfile # or use home grown IsPrime def IsPrime(n): if (n<=1): return False if (n <= 3): return True  if (n % 2 == 0 or n % 3 == 0):    return False   # use 6k ± 1 for the rest  stop = int(n**.5)+1  for i  in range(5, stop, 6):   if (n % i == 0 or n % (i + 2) == 0):    return False return True def goldbach(number): if number == 4: print("\n2 + 2 = 4\n") return elif IsPrime(number - 3): print(f"\n3 + {number-3:,} = {number}\n") return else: for p in range(5, number, 6): # just odds after 3 if IsPrime(p) and IsPrime(number-p): print(f"\n{p:,} + {number-p:,} = {N:,}\n") return elif IsPrime(p+2) and IsPrime(number-(p+2)): print(f"\n{p+2:,} + {number-(p+2):,} = {N:,}\n") return raise Exception(f"Found a counter-example to the Goldbach conjecture: {number}") if __name__=="__main__": N = 1 args = len(sys.argv) if args > 1: N = int(sys.argv[1]) print("This is a test of Goldbach's Conjecture that for all even integers") print("greater than 2 there are two primes that add up to that even number.\n") while (N < 3 or N%2): N = int(input("Please enter an even number > 3 to check with Goldbach's Conjecture> ")) cProfile.run('goldbach(N)') 

# Goldbach's Conjecture tester. from gmpy2 import is_prime import sys import cProfile   # or use home grown IsPrime def IsPrime(n): if (n <= 3): return n > 1    if not (n%6 == 1 or n%6 == 5): return False    for p,q in ((i,i+2) for i in range(5,int(n**.5)+1,6)): if (n%p == 0 or n%q == 0): return False return True     def goldbach(number): if number == 4: print("\n2 + 2 = 4\n") return elif IsPrime(number - 3): print(f"\n3 + {number-3:,} = {number}\n") return else: for p in range(5, number, 6): # just 6k±1 after 3 if IsPrime(p) and IsPrime(number-p): print(f"\n{p:,} + {number-p:,} = {N:,}\n") return elif IsPrime(p+2) and IsPrime(number-(p+2)): print(f"\n{p+2:,} + {number-(p+2):,} = {N:,}\n") return raise Exception(f"Found a counter-example to the Goldbach conjecture: {number}") if __name__=="__main__": N = 1 args = len(sys.argv) if args > 1: N = int(sys.argv[1]) print("This is a test of Goldbach's Conjecture that for all even integers") print("greater than 2 there are two primes that add up to that even number.\n") while (N < 3 or N%2): N = int(input("Please enter an even number > 3 to check with Goldbach's Conjecture> ")) cProfile.run('goldbach(N)') 

 $ python3 goldbach.py 12345678912345678 This is a test of Goldbach's Conjecture that for all even integers greater than 2 there are two primes that add up to that even number. 61 + 12,345,678,912,345,617 = 12,345,678,912,345,678 42 function calls in 3.869 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 3.869 3.869 <string>:1(<module>) 1 0.000 0.000 3.869 3.869 goldbach.py:16(goldbach) 37 3.869 0.105 3.869 0.105 goldbach.py:6(IsPrime) 1 0.000 0.000 3.869 3.869 {built-in method builtins.exec} 1 0.000 0.000 0.000 0.000 {built-in method builtins.print} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}  $ python3 goldbach.py 1000000000 This is a test of Goldbach's Conjecture that for all even integers greater than 2 there are two primes that add up to that even number. 71 + 999,999,929 = 1,000,000,000 47 function calls in 0.001 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 0.001 0.001 <string>:1(<module>) 1 0.000 0.000 0.001 0.001 goldbach.py:16(goldbach) 42 0.001 0.000 0.001 0.000 goldbach.py:6(IsPrime) 1 0.000 0.000 0.001 0.001 {built-in method builtins.exec} 1 0.000 0.000 0.000 0.000 {built-in method builtins.print} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 

 $ python3 goldbach.py 12345678912345678 This is a test of Goldbach's Conjecture that for all even integers greater than 2 there are two primes that add up to that even number. 61 + 12,345,678,912,345,617 = 12,345,678,912,345,678 42 function calls in 3.869 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 3.869 3.869 <string>:1(<module>) 1 0.000 0.000 3.869 3.869 goldbach.py:16(goldbach) 37 3.869 0.105 3.869 0.105 goldbach.py:6(IsPrime) 1 0.000 0.000 3.869 3.869 {built-in method builtins.exec} 1 0.000 0.000 0.000 0.000 {built-in method builtins.print} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} $ python goldbach.py 1000000000000000 This is a test of Goldbach's Conjecture that for all even integers greater than 2 there are two primes that add up to that even number. 11 + 999,999,999,999,989 = 1,000,000,000,000,000 14 function calls in 1.101 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 1.101 1.101 <string>:1(<module>) 1 0.000 0.000 1.101 1.101 goldbach.py:20(goldbach)  3 0.000 0.000 0.000 0.000 goldbach.py:28(<genexpr>) 6 1.101 0.184 1.101 0.184 goldbach.py:7(IsPrime) 1 0.000 0.000 1.101 1.101 {built-in method builtins.exec} 1 0.000 0.000 0.000 0.000 {built-in method builtins.print} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 

Only checks every 6th and 7th odd number for prime. So 1/3 of the checks.

More efficient IsPrime() tests using every 6th odd number as well.

# Goldbach's Conjecture tester. from gmpy2 import is_prime import sys import cProfile # or use home grown IsPrime def IsPrime(n): if (n == 2 or n == 3):  return True   if (n <= 1 or n % 2 == 0 or n % 3 == 0):   return False for i in range(5, int(n**.5)+1, 6):    if (n % i == 0 or n % (i + 2) == 0):   return False   return True def goldbach(number): if number == 4: print("\n2 + 2 = 4\n") return elif IsPrime(number - 3): print(f"\n3 + {number-3:,} = {number}\n") return else: for p in range(5, number, 6): # just odds after 3 if IsPrime(p) and IsPrime(number-p): print(f"\n{p:,} + {number-p:,} = {N:,}\n") return elif IsPrime(p+2) and IsPrime(number-(p+2)): print(f"\n{p+2:,} + {number-(p+2):,} = {N:,}\n") return raise Exception(f"Found a counter-example to the Goldbach conjecture: {number}") if __name__=="__main__": N = 1 args = len(sys.argv) if args > 1: N = int(sys.argv[1]) print("This is a test of Goldbach's Conjecture that for all even integers") print("greater than 2 there are two primes that add up to that even number.\n") while (N < 3 or N%2): N = int(input("Please enter an even number > 3 to check with Goldbach's Conjecture> ")) cProfile.run('goldbach(N)') 

Checks Goldbach prime 3 then uses 6k ± 1 for the rest. So 1/3 of the Goldbach checks vs every odd number > 3.

More efficient IsPrime() tests using every 6th odd number using 6k ± 1 as well.

# Goldbach's Conjecture tester. from gmpy2 import is_prime import sys import cProfile # or use home grown IsPrime def IsPrime(n): if (n<=1): return False  if (n <= 3): return True if (n % 2 == 0 or n % 3 == 0): return False # use 6k ± 1 for the rest  stop = int(n**.5)+1   for i in range(5, stop, 6):    if (n % i == 0 or n % (i + 2) == 0): return False return True def goldbach(number): if number == 4: print("\n2 + 2 = 4\n") return elif IsPrime(number - 3): print(f"\n3 + {number-3:,} = {number}\n") return else: for p in range(5, number, 6): # just odds after 3 if IsPrime(p) and IsPrime(number-p): print(f"\n{p:,} + {number-p:,} = {N:,}\n") return elif IsPrime(p+2) and IsPrime(number-(p+2)): print(f"\n{p+2:,} + {number-(p+2):,} = {N:,}\n") return raise Exception(f"Found a counter-example to the Goldbach conjecture: {number}") if __name__=="__main__": N = 1 args = len(sys.argv) if args > 1: N = int(sys.argv[1]) print("This is a test of Goldbach's Conjecture that for all even integers") print("greater than 2 there are two primes that add up to that even number.\n") while (N < 3 or N%2): N = int(input("Please enter an even number > 3 to check with Goldbach's Conjecture> ")) cProfile.run('goldbach(N)')