Primefree sequence

Last updated

In mathematics, a primefree sequence is a sequence of integers that does not contain any prime numbers. More specifically, it usually means a sequence defined by the same recurrence relation as the Fibonacci numbers, but with different initial conditions causing all members of the sequence to be composite numbers that do not all have a common divisor. To put it algebraically, a sequence of this type is defined by an appropriate choice of two composite numbers a1 and a2, such that the greatest common divisor is equal to 1, and such that for there are no primes in the sequence of numbers calculated from the formula

Contents

.

The first primefree sequence of this type was published by Ronald Graham in 1964.

Wilf's sequence

A primefree sequence found by Herbert Wilf has initial terms

(sequence A083216 in the OEIS )

The proof that every term of this sequence is composite relies on the periodicity of Fibonacci-like number sequences modulo the members of a finite set of primes. For each prime , the positions in the sequence where the numbers are divisible by repeat in a periodic pattern, and different primes in the set have overlapping patterns that result in a covering set for the whole sequence.

Nontriviality

The requirement that the initial terms of a primefree sequence be coprime is necessary for the question to be non-trivial. If the initial terms share a prime factor (e.g., set and for some and both greater than 1), due to the distributive property of multiplication and more generally all subsequent values in the sequence will be multiples of . In this case, all the numbers in the sequence will be composite, but for a trivial reason.

The order of the initial terms is also important. In Paul Hoffman's biography of Paul Erdős, The man who loved only numbers , the Wilf sequence is cited but with the initial terms switched. The resulting sequence appears primefree for the first hundred terms or so, but term 138 is the 45-digit prime . [1]

Other sequences

Several other primefree sequences are known:

(sequence A083104 in the OEIS; Graham 1964),
(sequence A083105 in the OEIS; Knuth 1990), and
(sequence A082411 in the OEIS; Nicol 1999).

The sequence of this type with the smallest known initial terms has

(sequence A221286 in the OEIS; Vsemirnov 2004).

Notes

  1. Sloane, N. J. A. (ed.). "SequenceA108156". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.

Related Research Articles

<span class="mw-page-title-main">Fibonacci number</span> Integer in the infinite Fibonacci sequence

In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the first few values in the sequence are:

In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.

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.

A highly composite number is a positive integer with more divisors than any smaller positive integer has. A related concept is that of a largely composite number, a positive integer which has at least as many divisors as any smaller positive integer. The name can be somewhat misleading, as the first two highly composite numbers are not actually composite numbers; however, all further terms are.

21 (twenty-one) is the natural number following 20 and preceding 22.

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.

In mathematics, and more particularly in number theory, primorial, denoted by "#", is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, the function only multiplies prime numbers.

4000 is the natural number following 3999 and preceding 4001. It is a decagonal number.

<span class="mw-page-title-main">1,000,000</span> Natural number

One million (1,000,000), or one thousand thousand, is the natural number following 999,999 and preceding 1,000,001. The word is derived from the early Italian millione, from mille, "thousand", plus the augmentative suffix -one.

Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.

<span class="mw-page-title-main">Practical number</span> Number such that it and all smaller numbers may be represented as sums of its distinct divisors

In number theory, a practical number or panarithmic number is a positive integer such that all smaller positive integers can be represented as sums of distinct divisors of . For example, 12 is a practical number because all the numbers from 1 to 11 can be expressed as sums of its divisors 1, 2, 3, 4, and 6: as well as these divisors themselves, we have 5 = 3 + 2, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1, and 11 = 6 + 3 + 2.

<span class="mw-page-title-main">Pell number</span> Natural number used to approximate √2

In mathematics, the Pell numbers are an infinite sequence of integers, known since ancient times, that comprise the denominators of the closest rational approximations to the square root of 2. This sequence of approximations begins 1/1, 3/2, 7/5, 17/12, and 41/29, so the sequence of Pell numbers begins with 1, 2, 5, 12, and 29. The numerators of the same sequence of approximations are half the companion Pell numbers or Pell–Lucas numbers; these numbers form a second infinite sequence that begins with 2, 6, 14, 34, and 82.

<span class="mw-page-title-main">Znám's problem</span> On divisibility among sets of integers

In number theory, Znám's problem asks which sets of integers have the property that each integer in the set is a proper divisor of the product of the other integers in the set, plus 1. Znám's problem is named after the Slovak mathematician Štefan Znám, who suggested it in 1972, although other mathematicians had considered similar problems around the same time.

100,000 (one hundred thousand) is the natural number following 99,999 and preceding 100,001. In scientific notation, it is written as 105.

In mathematics, a superabundant number is a certain kind of natural number. A natural number n is called superabundant precisely when, for all m < n

<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.

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

In mathematics, a nonhypotenuse number is a natural number whose square cannot be written as the sum of two nonzero squares. The name stems from the fact that an edge of length equal to a nonhypotenuse number cannot form the hypotenuse of a right angle triangle with integer sides.

In number theory, reversing the digits of a number n sometimes produces another number m that is divisible by n. This happens trivially when n is a palindromic number; the nontrivial reverse divisors are

References