Primefree sequence
Encyclopedia
In mathematics
, a primefree sequence is a sequence
of integer
s that does not contain any prime number
s. More specifically, it generally means a sequence defined by the same recurrence relation
as the Fibonacci number
s, but with different initial conditions causing all members of the sequence to be composite number
s 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
GCD(a1,a2) = 1, and such that for n > 2 there are no primes in the sequence of numbers calculated from the formula
, with initial terms
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 p, the positions in the sequence where the numbers are divisible by p repeat in a periodic pattern, and different primes in the set have overlapping patterns that result in a covering set
for the whole sequence.
of multiplication
it is obvious that a3 = (x + y)p and more generally all subsequent value in the sequence will be multiples of p. 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 439351292910452432574786963588089477522344721.
The sequence of this type with the smallest known initial terms has
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a primefree sequence is a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s that does not contain any prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s. More specifically, it generally means a sequence defined by the same recurrence relation
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....
as the Fibonacci number
Fibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
s, but with different initial conditions causing all members of the sequence to be composite number
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
s that do not all have a common divisor
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
. 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
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
GCD(a1,a2) = 1, and such that for n > 2 there are no primes in the sequence of numbers calculated from the formula
- an = an − 1 + an − 2.
Wilf's sequence
Perhaps the best known primefree sequence is the one found by Herbert WilfHerbert Wilf
Herbert Saul Wilf is a mathematician, specializing in combinatorics and graph theory. He was the Thomas A. Scott Professor of Mathematics in Combinatorial Analysis and Computing at the University of Pennsylvania. He has written numerous books and research papers...
, with initial terms
- a1 = 20615674205555510, a2 = 3794765361567513 .
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 p, the positions in the sequence where the numbers are divisible by p repeat in a periodic pattern, and different primes in the set have overlapping patterns that result in a covering set
Covering set
In mathematics, a covering set for a sequence of integers refers to a set of prime numbers such that every term in the sequence is divisible by at least one member of the 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 we allow the initial terms to share a prime factor p (e.g., set a1 = xp and a2 = yp for some x and y both greater than 1), due to the distributive propertyDistributivity
In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalizes the distributive law from elementary algebra.For example:...
of multiplication
Multiplication
Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
it is obvious that a3 = (x + y)p and more generally all subsequent value in the sequence will be multiples of p. 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
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
, The man who loved only numbers
The Man Who Loved Only Numbers
The Man Who Loved Only Numbers is a biography of the famous mathematician Paul Erdős written by Paul Hoffman. It was first published in 1998 as a hardcover edition. A paperback edition appeared in 1999. The book is, in the words of the author, "a work in oral history based on the recollections of...
, 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 439351292910452432574786963588089477522344721.
Other sequences
Several other primefree sequences are known:- a1 = 331635635998274737472200656430763, a2 = 1510028911088401971189590305498785 (sequence A083104 in OEISOn-Line Encyclopedia of Integer SequencesThe On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...
; Graham 1964), - a1 = 62638280004239857, a2 = 49463435743205655 (sequence A083105 in OEISOn-Line Encyclopedia of Integer SequencesThe On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...
; Knuth 1990), and - a1 = 407389224418, a2 = 76343678551 (sequence A082411 in OEISOn-Line Encyclopedia of Integer SequencesThe On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...
; Nicol 1999).
The sequence of this type with the smallest known initial terms has
- a1 = 106276436867, a2 = 35256392432 (Vsemirnov 2004).
External links
- Problem 31. Fibonacci- all composites sequence. The prime puzzles and problems connection.