The Perrin numbers are a sequence of numbers similar to the Fibonacci numbers in that successive numbers are derived from two previous adjacent numbers, only in this case we skip a place so that each number can be obtained from the sum of the numbers two and three places previous.
Expressed more clearly as a recurrence relation the Perrin numbers are defined as:
P(n): P(0) = 3, P(1) = 0, P(2) = 3, and P(n) = P(n-2) + P(n-3)
So that the first handful of Perrin numbers would be:
3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, etc...
At first glance the sequence does not seem to be all that remarkable, but by applying a simple construction we can extract a remarkable property. We proceed to simply label each number in the sequence with it's corresponding n value and note n values that evenly divide their Perrin number. For example: P(2)=2 and 2/2=1 so 2 divides 2 evenly and P(11)=22 and 22/11=2 so 11 divides 22 evenly . Such numbers are bolded below:
n: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
P(n): 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158
Using this method, we obtain the sequence: 2, 3, 5, 7, 11, 13, 17... which amazingly happens to be the exact sequence of the first seven prime numbers. Furthermore, the pattern continues (19, 23, 29, 27...) and going forward, it would appear that we can generate exactly the complete sequence of prime numbers in the fashion! Given that there is no known way of easily generating the complete prime number sequence other than through brute force, this would seem to be a truly amazing discovery!
In 1878 the French mathematician Édouard Lucas was able to prove as a conseqeunce of Fermat's Little Theorem that if n is a prime number then n divides P(n). In other words the prime numbers are at least a subset of the numbers derived from the construction above.
The obvious question that follows is:
Let S be the set of all numbers n such that P(n) is divisible by n. Is S the set of all prime numbers?
Lucas provided a necessary precondition, but his theorem still allows for the possibility that there could exist an n that divides P(n) that is not prime. Such a number would be called a Perrin pseudoprime and the existence of such a number would disprove our ability to generate the prime numbers in this fashion. Likewise if it were proven that no such Perrin pseudoprime exists then we would have successfully found a method to generate the set of prime numbers via the construction detailed above!
Indeed, as recently as 1996 nobody was able to find such a number, but eventually computing power and algorithm research caught up with the problem and since that time it has been found by Christian Holzbaur of the University of Vienna that:
271441 evenly divides P(271441)*
and
271441 = 521*521 - So 271441 is not prime.
Thus 271441 is a Perrin pseudoprime and we have a counterexample proving that we cannot in fact derive the set of prime numbers from the set of Perrin numbers using the construction above. Many more Perrin pseudoprimes follow from there and now it is fairly easy with a little knowledge to verify pseudoprimes. Still, Perrin numbers are damn interesting and hold many other properties of note that are not discussed here.
* P(271441), by the way, is such a large number that it is difficult to calculate this without using modular arithmetic.
Sources:
I gathered many details regarding dates and past research from the following sites, and I am most grateful to them:
http://www.fortunecity.com/emachines/e11/86/padovan.html
http://www.ai.univie.ac.at/perrin.html (Christian Holzbaur's page)
http://www.mathpages.com/home/kmath345.htm
However, most of the information contained in this write-up was simply taken from my own head having studied Perrin numbers and algorithms to test for pseudoprimes fairly extensively on my own as part of a Discrete Mathematics curriculum.