mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a primefree sequence is a sequence of integers that does not contain any

prime number A prime number (or a prime) 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 ...

s. More specifically, it usually means a

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...

defined by the same

recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...

as the

Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , 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 ...

s, but with different

initial condition In mathematics and particularly in dynamic systems, an initial condition, in some contexts called a seed value, is a value of an evolving variable at some point in time designated as the initial time (typically denoted ''t'' = 0). For ...

s causing all members of the sequence to be

composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...

s that do not all have a common

divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...

. To put it algebraically, a sequence of this type is defined by an appropriate choice of two composite numbers ''a''₁ and ''a''₂, such that the

greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...

\mathrm(a_1,a_2)

is equal to 1, and such that for

n>2

there are no primes in the sequence of numbers calculated from the formula :

a_n=a_+a_

. The first primefree sequence of this type was published by

Ronald Graham Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...

in 1964.

Wilf's sequence

A primefree sequence found by

Herbert Wilf Herbert Saul Wilf (June 13, 1931 – January 7, 2012) was 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 Pennsylv ...

has initial terms :

a_1 = 20615674205555510, a_2 = 3794765361567513

The proof that every term of this sequence is composite relies on the periodicity of Fibonacci-like number sequences

modulo In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is t ...

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 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. The term "covering set" is used only in conjunction with seque ...

for the whole sequence.

Nontriviality

The requirement that the initial terms of a primefree sequence be

coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...

is necessary for the question to be non-trivial. If the initial terms share a prime factor

p

(e.g., set

a_1=xp

and

a_2=yp

for some

x

and

y

both greater than 1), due to the

distributive property In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmetic, ...

multiplication Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...

a_3=(x+y)p

and more generally all subsequent values 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 Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...

, ''

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. The book was first published on July 15, 1998, by Hyperion Books as a hardcover edition. A paperback edition appeared in 1999. ...

'', 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: :

a_1 = 331635635998274737472200656430763, a_2 = 1510028911088401971189590305498785

(sequence A083104 in the

OEIS The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...

; Graham 1964), :

a_1 = 62638280004239857, a_2 = 49463435743205655

(sequence A083105 in the OEIS; Knuth 1990), and :

a_1 = 407389224418, a_2 = 76343678551

(sequence A082411 in the OEIS; Nicol 1999). The sequence of this type with the smallest known initial terms has :

a_1 = 106276436867, a_2 = 35256392432

(sequence A221286 in the OEIS; Vsemirnov 2004).

Notes

References

* * * * *

External links

Problem 31. Fibonacci- all composites sequence
The prime puzzles and problems connection. * *{{mathworld , title = Primefree Sequence , urlname = PrimefreeSequence Integer sequences Number theory Recurrence relations