The Boolean Pythagorean triples problem

Unsolved Very hard Archive

archive posted 9 Aug 2026

Can the integers $1, 2, \dots, N$ be colored red and blue so that no Pythagorean triple $a^{2} + b^{2} = c^{2}$ has $a$ , $b$ and $c$ all the same color? Find the largest $N$ for which this is possible, or show that it is possible for every $N$ .

Posed by Ronald Graham

Like0

History and references

Solved in 2016 by Marijn Heule, Oliver Kullmann and Victor W. Marek.

Ronald Graham asked the question in the 1980s and offered a prize of 100 dollars for it. In May 2016 Heule, Kullmann and Marek settled it with a SAT solver using the cube-and-conquer method. The numbers 1 to 7824 can be colored with no monochromatic triple, but 1 to 7825 cannot. The search took about two days on a cluster with 800 cores, the Stampede supercomputer, and produced a formal proof of about 200 terabytes that was verified with a proof checker and compressed to a 68 gigabyte certificate. The version with three or more colors was still open as of 2018.

References

Solutions 0

Nobody has posted a solution here yet. Solutions written on Problempedia are credited to the people who write them.

References

Solutions 0

Discussion 0