Primefree sequence

In mathematics, a primefree sequence is a sequence of integers that does not contain any prime numbers. More specifically, it generally means a Fibonacci-like sequence with composite but coprime initial terms that is infinite but contains no primes. To put it algebraically, the sequence defined by $GCD(a\_1,\; a\_2)\; =\; 1$, and for $n\; >\; 2$ the recurrence relation $a\_n\; =\; a\_\{n\; -\; 2\}\; +\; a\_\{n\; -\; 1\}$, is a sequence that contains no primes.

Perhaps the best known primefree sequence is the one found by Herbert Wilf, with initial terms

:"a"₁ = 20615674205555510, "a"₂ = 3794765361567513 OEIS|id=A083216.

The requirement that the initial terms 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., $a\_1\; =\; xp,\; a\_2\; =\; yp$), due to the distributive property of multiplication it is obvious that $a\_3\; =\; (x\; +\; y)p$; indeed all terms of the sequence will be multiples of "p", with the primefreeness being a trivial consequence of that.

The proof that every term of these sequences is composite relies on the periodicity of Fibonacci numbers modulo a given set of primes, resulting in a covering set.

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. OEIS2C|id=A108156 gives other indexes of prime numbers in the Wilf-Hoffman sequence.

Several other primefree sequences are known::"a"₁ = 331635635998274737472200656430763, "a"₂ = 1510028911088401971189590305498785 (sequence [fullurl:OEIS:A083104 A083104] in OEIS; Graham 1964),:"a"₁ = 62638280004239857, "a"₂ = 49463435743205655 (sequence [fullurl:OEIS:A083105 A083105] in OEIS; Knuth 1990), and:"a"₁ = 407389224418, "a"₂ = 76343678551 (sequence [fullurl:OEIS:A082411 A082411] in OEIS; Nicol 1999).The sequence of this type with the smallest known initial terms has:"a"₁ = 106276436867, "a"₂ = 35256392432 (Vsemirnov 2004).

References

*cite journal
author = Graham, Ronald L.
authorlink = Ronald L. Graham
title = A Fibonacci-like sequence of composite numbers
journal = Mathematics Magazine
volume = 37
year = 1964
url = http://www.math.ucsd.edu/~sbutler/ron/64_06_fibonacci.pdf
pages = 322–324

*cite journal
author = Knuth, Donald E.
authorlink = Donald Knuth
title = A Fibonacci-like sequence of composite numbers
journal = Mathematics Magazine
volume = 63
issue = 1
pages = 21–25
id = MathSciNet | id = 1042933

*cite journal
author = Nicol, John W.
title = A Fibonacci-like sequence of composite numbers
journal = Electronic Journal of Combinatorics
volume = 6
issue = 1
year = 1999
pages = 44
url = http://www.combinatorics.org/Volume_6/Abstracts/v6i1r44.html
id = MathSciNet | id = 1728014

*cite journal
author = Vsemirnov, M.
title = A new Fibonacci-like sequence of composite numbers
journal = Journal of Integer Sequences
volume = 7
year = 2004
issue = 3
pages = 04.3.7
id = MathSciNet | id = 2110778
url = http://www.emis.ams.org/journals/JIS/VOL7/Vsemirnov/vsem5.pdf

External links

* [http://www.primepuzzles.net/problems/prob_031.htm Problem 31. Fibonacci- all composites sequence] . The prime puzzles and problems connection.

*planetmath reference|id=7917|title=Primefree sequence

*mathworld | title = Primefree Sequence | urlname = PrimefreeSequence