Primefree sequence

From Wikipedia, the free encyclopedia

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₁,a₂) = 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 (sequence A083216 in OEIS).

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₁ = xp,a₂ = yp), due to the distributive property of multiplication it is obvious that a₃ = (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. A108156 gives other indexes of prime numbers in the Wilf-Hoffman sequence.

Several other primefree sequences are known:

a₁ = 331635635998274737472200656430763, a₂ = 1510028911088401971189590305498785 (sequence A083104 in OEIS; Graham 1964),

a₁ = 62638280004239857, a₂ = 49463435743205655 (sequence A083105 in OEIS; Knuth 1990), and

a₁ = 407389224418, a₂ = 76343678551 (sequence A082411 in OEIS; Nicol 1999).

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

a₁ = 106276436867, a₂ = 35256392432 (Vsemirnov 2004).

[edit] References

• Graham, Ronald L. (1964). "A Fibonacci-like sequence of composite numbers". Mathematics Magazine 37: 322–324. 

• Knuth, Donald E.. "A Fibonacci-like sequence of composite numbers". Mathematics Magazine 63 (1): 21–25. MR1042933. 

• Nicol, John W. (1999). "A Fibonacci-like sequence of composite numbers". Electronic Journal of Combinatorics 6 (1): 44. MR1728014. 

• Vsemirnov, M. (2004). "A new Fibonacci-like sequence of composite numbers". Journal of Integer Sequences 7 (3): 04.3.7. MR2110778. 

[edit] External links

• Problem 31. Fibonacci- all composites sequence. The prime puzzles and problems connection.

• Primefree sequence on PlanetMath

• Eric W. Weisstein, Primefree Sequence at MathWorld.