Lesson plan
Pillai sequence
The Pillai sequence is the sequence of integers that have record numbers of terms in their greedy representations as sums of prime numbers (and one). It is named after Subbayya Sivasankaranarayana Pillai, 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 prime numbers. However, finding such a representation could involve solving instances of the subset sum problem, which is computationally difficult. Instead, Pillai considered the following simpler greedy algorithm 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, then it halts; if it reaches one instead of zero, then 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, ... .…
Article summary
The Pillai sequence is the sequence of integers that have record numbers of terms in their greedy representations as sums of prime numbers (and one). It is named after Subbayya Sivasankaranarayana Pillai, 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 prime numbers. However, finding such a representation could involve solving instances of the subset sum problem, which is computationally difficult. Instead, Pillai considered the following simpler greedy algorithm 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, then it halts; if it reaches one instead of zero, then 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, ... .…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.