information:classification, structural:expansion, linguistic:voice_change
Related problems

Although Goldbach's conjecture implies that every positive integer greater than one can be written as a sum of at most three primes, it is not always possible to find such a sum using a greedy algorithm that uses the largest possible prime at each step. The Pillai sequence tracks the numbers requiring the largest number of primes in their greedy representations.

Similar problems to Goldbach's conjecture exist in which primes are replaced by other particular sets of numbers, such as the squares:

Goldbach's conjecture is used when studying computation complexity. The connection is made through the Busy Beaver function, where BB(n) is the maximum number of steps taken by any n state Turing machine that halts. There is a 27 state Turing machine that halts if and only if Goldbach's conjecture is false. Hence if BB(27) was known, and the Goldbach machine did not stop in that number of steps, it would be known to run forever and hence no counterexamples exist (which proves the conjecture true). This is a completely impractical way to settle the conjecture; instead it is used to suggest that BB(27) will be very hard to compute, at least as difficult as settling the Goldbach conjecture.