Pillai sequence (original) (raw)
The Pillai sequence is the sequence of integers that have a record number 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. The th number in the Pillai sequence is the smallest number whose greedy representation as a sum of primes (and one) requires terms. These numbers are 0, 1, 4, 27, 1354, 401429925999155061, ... (sequence in the OEIS)
| Property | Value |
|---|---|
| dbo:abstract | The Pillai sequence is the sequence of integers that have a record number 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 as a sum of primes: choose the first prime in the sum to be the largest prime that is at most , and then recursively construct the remaining sum recursively for .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 th number in the Pillai sequence is the smallest number whose greedy representation as a sum of primes (and one) requires terms. These numbers are 0, 1, 4, 27, 1354, 401429925999155061, ... (sequence in the OEIS) Each number in the sequence is the sum of the previous number with a prime number , the smallest prime whose following prime gap is larger than . 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". (en) |
| dbo:wikiPageID | 56121084 (xsd:integer) |
| dbo:wikiPageLength | 2952 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1112020919 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prime_number_theorem dbr:Prime_gap dbr:Integer_sequence dbr:Subbayya_Sivasankaranarayana_Pillai dbc:Integer_sequences dbc:Prime_numbers dbr:Goldbach's_conjecture dbr:Prime_number dbr:Greedy_algorithm dbr:Subset_sum_problem |
| dbp:wikiPageUsesTemplate | dbt:OEIS dbt:Reflist |
| dct:subject | dbc:Integer_sequences dbc:Prime_numbers |
| rdfs:comment | The Pillai sequence is the sequence of integers that have a record number 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. The th number in the Pillai sequence is the smallest number whose greedy representation as a sum of primes (and one) requires terms. These numbers are 0, 1, 4, 27, 1354, 401429925999155061, ... (sequence in the OEIS) (en) |
| rdfs:label | Pillai sequence (en) |
| owl:sameAs | wikidata:Pillai sequence https://global.dbpedia.org/id/4YB1e |
| prov:wasDerivedFrom | wikipedia-en:Pillai_sequence?oldid=1112020919&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Pillai_sequence |
| is dbo:knownFor of | dbr:Subbayya_Sivasankaranarayana_Pillai |
| is dbo:wikiPageWikiLink of | dbr:List_of_people_from_Nagercoil dbr:Subbayya_Sivasankaranarayana_Pillai dbr:Goldbach's_conjecture |
| is dbp:knownFor of | dbr:Subbayya_Sivasankaranarayana_Pillai |
| is foaf:primaryTopic of | wikipedia-en:Pillai_sequence |