primesum

In number theory, primesum (prime sum) refers to the study of representing integers as sums of prime numbers. The term covers both representations using a fixed number of primes and the related counting functions that tally how many representations an integer admits.

The most famous instance is the Goldbach conjecture: every even integer greater than 2 can be written as the sum of two primes. Despite extensive numerical verification, the conjecture remains unproven in general. A related result is the weak Goldbach conjecture: every odd integer greater than 5 is the sum of three primes, which was established by Harald Helfgott in 2013.

For representations using more than three primes, several theorems describe when and how such representations exist. Vinogradov's theorem shows that every sufficiently large odd integer is a sum of three primes, and Hardy–Littlewood circle methods give asymptotic formulas for the number of representations of large integers as sums of a fixed number of primes. In particular, the asymptotics are known for k >= 3, but not for k=2 unless Goldbach is resolved.

Computational aspects include algorithms to find or count prime-sum representations, prime sieving to generate candidates, and enumeration of all representations of n as a sum of k primes. In programming contexts, prime sums are a common source of problems about optimal representations, counting representations, and efficient searching.

Variants include restricting primes to be distinct, requiring primes to lie in an arithmetic progression, or counting representations with bounded length. Simple examples include 10 = 3+7 = 5+5 and 11 = 3+3+5.