Editing Goldbach's conjecture (section)

== 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.<ref>{{Cite OEIS|A066352|name=Pillai sequence}}</ref>

Similar problems to Goldbach's conjecture exist in which primes are replaced by other particular sets of numbers, such as the squares:
* It was proven by [[Joseph-Louis Lagrange|Lagrange]] that [[Lagrange's four-square theorem|every positive integer is the sum of four squares]]. See [[Waring's problem]] and the related [[Waring–Goldbach problem]] on sums of powers of primes.
* Hardy and Littlewood listed as their Conjecture I: "Every large odd number ({{math|''n'' > 5}}) is the sum of a prime and the double of a prime".<ref>''[[Mathematics Magazine]]'', 66:1 (1993): 45–47.</ref> This conjecture is known as [[Lemoine's conjecture]] and is also called ''Levy's conjecture''.
* The Goldbach conjecture for [[practical number]]s, a prime-like sequence of integers, was stated by Margenstern in 1984,<ref>{{cite journal |first=M. |last=Margenstern |title=Results and conjectures about practical numbers |journal= [[Comptes rendus de l'Académie des Sciences]]|volume=299 |year=1984 |pages=895–898 }}</ref> and proved by [[Giuseppe Melfi|Melfi]] in 1996:<ref>{{cite journal |first=G. |last=Melfi |title=On two conjectures about practical numbers |journal= [[Journal of Number Theory]] |volume=56|year=1996 | pages=205–210 |doi=10.1006/jnth.1996.0012|doi-access=free }}</ref> every even number is a sum of two practical numbers.
* [[Harvey Dubner]] proposed a strengthening of the Goldbach conjecture that states that every even integer greater than 4208 is the sum of two [[twin prime]]s (not necessarily belonging to the same pair).<ref>{{Cite web|url=https://oeis.org/A007534/a007534.pdf|title=TWIN PRIME CONJECTURES|website=oeis.org}}</ref>{{better source|reason= This is raw html, although it seems to have been published in Recreational Mathematics|date=September 2023}} Only 34 even integers less than 4208 are not the sum of two twin primes; Dubner has verified computationally that this list is complete up to <math>2\cdot 10^{10}.</math><ref>{{Cite OEIS|A007534|name=Even numbers that are not the sum of a pair of twin primes}}</ref>{{check|reason=This source states 10^9, and the other source is unclear on the limit|date=September 2023}} A proof of this stronger conjecture would not only imply Goldbach's conjecture, but also the [[twin prime conjecture]].
* According to [[Bertrand's postulate]], for every integer <math>n > 1</math>, there is always at least one prime <math>p</math> such that <math>n < p < 2n.</math> If the postulate were false, there would exist some integer <math>n</math> for which no prime numbers lie between <math>n</math> and <math>2n</math>, making it impossible to express <math>2n</math> as a sum of two primes. 

Goldbach's conjecture is used when studying computational complexity.<ref name="quanta">{{cite web |url=https://www.quantamagazine.org/how-the-slowest-computer-programs-illuminate-maths-fundamental-limits-20201210/ |title=How the Slowest Computer Programs Illuminate Math's Fundamental Limits|date=10 December 2020 }}</ref>  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.<ref name="quanta"/> Hence if BB(27) was known, and the Turing 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.
{{clear}}