Pillai sequence

Last updated

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. [1]

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 A066352 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 . [2] 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". [3]

Related Research Articles

<span class="mw-page-title-main">Prime number</span> Evenly divided only by 1 or itself

A prime number 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 of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

<span class="mw-page-title-main">Goldbach's conjecture</span> Even integers as sums of two primes

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even natural number greater than 2 is the sum of two prime numbers.

2 (two) is a number, numeral and digit. It is the natural number following 1 and preceding 3. It is the smallest and only even prime number. Because it forms the basis of a duality, it has religious and spiritual significance in many cultures.

In recreational mathematics, a repdigit or sometimes monodigit is a natural number composed of repeated instances of the same digit in a positional number system. The word is a portmanteau of repeated and digit. Examples are 11, 666, 4444, and 999999. All repdigits are palindromic numbers and are multiples of repunits. Other well-known repdigits include the repunit primes and in particular the Mersenne primes.

79 (seventy-nine) is the natural number following 78 and preceding 80.

73 (seventy-three) is the natural number following 72 and preceding 74. In English, it is the smallest natural number with twelve letters in its spelled out name.

1000 or one thousand is the natural number following 999 and preceding 1001. In most English-speaking countries, it can be written with or without a comma or sometimes a period separating the thousands digit: 1,000.

127 is the natural number following 126 and preceding 128. It is also a prime number.

167 is the natural number following 166 and preceding 168.

In mathematics, the digit sum of a natural number in a given number base is the sum of all its digits. For example, the digit sum of the decimal number would be .

149 is the natural number between 148 and 150.

216 is the natural number following 215 and preceding 217. It is a cube, and is often called Plato's number, although it is not certain that this is the number intended by Plato.

<span class="mw-page-title-main">Polite number</span>

In number theory, a polite number is a positive integer that can be written as the sum of two or more consecutive positive integers. A positive integer which is not polite is called impolite. The impolite numbers are exactly the powers of two, and the polite numbers are the natural numbers that are not powers of two.

<span class="mw-page-title-main">Sylvester's sequence</span> Doubly exponential integer sequence

In number theory, Sylvester's sequence is an integer sequence in which each term is the product of the previous terms, plus one. The first few terms of the sequence are

In mathematics, the greedy algorithm for Egyptian fractions is a greedy algorithm, first described by Fibonacci, for transforming rational numbers into Egyptian fractions. An Egyptian fraction is a representation of an irreducible fraction as a sum of distinct unit fractions, such as 5/6 = 1/2 + 1/3. As the name indicates, these representations have been used as long ago as ancient Egypt, but the first published systematic method for constructing such expansions was described in 1202 in the Liber Abaci of Leonardo of Pisa (Fibonacci). It is called a greedy algorithm because at each step the algorithm chooses greedily the largest possible unit fraction that can be used in any representation of the remaining fraction.

In mathematics, the Ulam numbers comprise an integer sequence devised by and named after Stanislaw Ulam, who introduced it in 1964. The standard Ulam sequence starts with U1 = 1 and U2 = 2. Then for n > 2, Un is defined to be the smallest integer that is the sum of two distinct earlier terms in exactly one way and larger than all earlier terms.

In mathematics, a sequence of natural numbers is called a complete sequence if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.

In number theory, the integer complexity of an integer is the smallest number of ones that can be used to represent it using ones and any number of additions, multiplications, and parentheses. It is always within a constant factor of the logarithm of the given integer.

In mathematics, a Stanley sequence is an integer sequence generated by a greedy algorithm that chooses the sequence members to avoid arithmetic progressions. If is a finite set of non-negative integers on which no three elements form an arithmetic progression, then the Stanley sequence generated from starts from the elements of , in sorted order, and then repeatedly chooses each successive element of the sequence to be a number that is larger than the already-chosen numbers and does not form any three-term arithmetic progression with them. These sequences are named after Richard P. Stanley.

References

  1. ↑ Pillai, S. S. (1930), "An arithmetical function concerning primes", Annamalai University Journal: 159–167. As cited by Luca & Thangadurai (2009).
  2. ↑ Luca, Florian; Thangadurai, Ravindranathan (2009), "On an arithmetic function considered by Pillai", Journal de Théorie des Nombres de Bordeaux, 21 (3): 693–699, doi: 10.5802/jtnb.695 , MR   2605540
  3. ↑ Sloane, N. J. A. (ed.), "SequenceA066352(Pillai sequence)", The On-Line Encyclopedia of Integer Sequences , OEIS Foundation
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.