Lesson 8

Moreover, this could potentially help us find answers to many open questions in mathematics! Let us provide some examples. Imagine that we have such a correctly working method.

is_halting(program_file_name, input_file_name)

• Perfect numbers.  Recall that a number is called perfect if it equals the sum of its divisors (excluding itself): \(6=1+2+3\). We still do not know if there exists an odd perfect number. It exists if and only if the following program halts.

  from itertools import count
  
  
  def is_perfect(x):
      return sum([d for d in range(1, x) if x % d == 0]) == x
  
  
  print(next(filter(is_perfect, count(start=1, step=2))))



• Goldbach's conjecture.  Goldbach's conjecture states that every even \(n \in \mathbb{Z}_{\ge 4}\) can be expressed as the sum of two primes. The following program halts if this conjecture is false.

  from itertools import count
  
  
  def goldbach_conjecture():
      for n in count(start=4, step=2):
          if not is_sum_of_two_primes(n):
              return



• Fermat's Last Theorem.  The following program halts if there exist \(u \in \mathbb{Z}_{>0}\) and integers \(3 \le n < u\), \(1 \le a, b, c < u\), such that \[a^{n}+b^{n}=c^{n}\]

  from itertools import count, product
  
  
  for upper in count(start=1):
      for n in range(3, upper):
          for a, b, c, in product(range(1, upper), repeat=3):
              if a ** n + b ** n == c ** n:
                  exit()



• Twin primes.  We still do not know whether there are infinitely many pairs of prime numbers differing by two. The following code halts if and only if this is not the case.

  from itertools import count
  from sympy.ntheory import isprime
  
  
  def exists_large_twins(lower):
      for p in count(start=lower):
          if isprime(p) and isprime(p + 2):
              return
  
  
  for lower in count(start=1):
      if not is_halting(exists_large_twins, lower):
          exit()