The Pillai sequence is the sequence of integers that have a record number of terms in their greedy representations as sums of

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

s (and one). It is named after

Subbayya Sivasankaranarayana Pillai Subbayya Sivasankaranarayana Pillai (5 April 1901 – 31 August 1950) was an Indian mathematician specialising in number theory. His contribution to Waring's problem was described in 1950 by K. S. Chandrasekharan as "almost certainly his best ...

, who first defined it in 1930. It would follow from Goldbach's conjecture that every integer greater than one can be represented as a sum of at most three

s. However, finding such a representation could involve solving instances of the

subset sum problem The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T''.'' T ...

, which is computationally difficult. Instead, Pillai considered the following simpler

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

for finding a representation of

n

as a sum of primes: choose the first prime in the sum to be the largest prime

p

that is at most

n

, and then recursively construct the remaining sum recursively for

n-p

. If this process reaches zero, it halts. And if it reaches one instead of zero, it must include one in the sum (even though it is not prime), and then halt. For instance, this algorithm represents 122 as 113 + 7 + 2, even though the shorter representations 61 + 61 or 109 + 13 are also possible. The

n

th number in the Pillai sequence is the smallest number whose greedy representation as a sum of primes (and one) requires

n

terms. These numbers are :0, 1, 4, 27, 1354, 401429925999155061, ... Each number

a(n)

in the sequence is the sum of the previous number

a(n-1)

with a prime number

p

, the smallest prime whose following

prime gap A prime gap is the difference between two successive prime numbers. The ''n''-th prime gap, denoted ''g'n'' or ''g''(''p'n'') is the difference between the (''n'' + 1)-th and the ''n''-th prime numbers, i.e. :g_n = p_ - p_n.\ W ...

is larger than

a(n-1)

. For instance, the number 27 in the sequence is 4 + 23, where the first prime gap larger than 4 is the one between 23 and 29. Because the prime numbers become less dense as they become larger (as quantified by the prime number theorem), there is always a prime gap larger than any term in the Pillai sequence, so the sequence continues to an infinite number of terms. However, the terms in the sequence grow very rapidly. It has been estimated that expressing the next term in the sequence would require "hundreds of millions of digits".

References

{{reflist Integer sequences Prime numbers