Perrin episode

The Perrin sequence is a sequence of natural numbers in which, similar to the Fibonacci sequence , each term is the sum of previous terms (i.e. a recursively defined sequence). The individual elements of the sequence are called the Perrin number .

history

In 1876, Édouard Lucas worked on a sequence with the formation rule, which, however, had different starting values ​​than the Perrin sequence. In 1899, Raoul Perrin further developed Lucas's ideas and based his education rule with the starting values and a sequence that has become known as the Perrin sequence . ${\displaystyle P(n)=P(n-2)+P(n-3)}$ ${\displaystyle P(0)=3,P(1)=0}$ ${\displaystyle P(2)=2}$

definition

The terms of the Perrin sequence are defined as follows:

${\displaystyle P_{n}=P_{n-2}+P_{n-3}}$

${\displaystyle P_{0}=3}$

${\displaystyle P_{1}=0}$

${\displaystyle P_{2}=2}$

The result is:

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367, 486, 644, 853, 1130, 1497, 1983, 2627, 3480, 4610, 6107, 8090, 10717, 14197, 18807, 24914, 33004, 43721, 57918, 76725, 101639, 134643, 178364, 236282, 313007, ... (sequence A001608 in OEIS )

It plays a role in graph theory because is the number of maximum stable sets in a cyclic graph with nodes. ${\displaystyle P(n)}$ ${\displaystyle n}$

Divisibility properties

The following table lists the first 10 terms that have a divisor of : ${\displaystyle n}$ ${\displaystyle P(n)}$

n	2	3	5	7th	11	13	17th	19th	23	29
P (n)	2	3	5	7th	22nd	39	119	209	644	3480

Interestingly, in this table all that divide are prime numbers . In fact, it has been proven that when is a prime, it divides the sequence value . Does this mean that if divides the sequence value , then it must be prime? No, there are also compounds that divide. These compound numbers are called Perrin pseudoprimes . The smallest Perrin pseudoprime number is 271441 = 521 ² , the second smallest is 904631 = 7 * 13 * 9941. The first Perrin pseudoprimes are the following: ${\displaystyle n}$ ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle P(n)}$ ${\displaystyle n}$

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, 1091327579, 1133818561, 1235188597, 1389675541, ... (sequence A013998 in OEIS )

There are infinitely many Perrin pseudoprimes.

Perrin primes

A Perrin prime is a Perrin number that is prime. The smallest Perrin prime numbers are:

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792,606,555,396,977, 187278659180417234321, 66241160488780141071579864797, 22584751787583336797527561822649328254745329, ... (sequence A074788 in OEIS )

For these Perrin primes the index is of the following: ${\displaystyle n}$ ${\displaystyle P(n)}$

2, 3, 4, 5, 6, 7, 10, 12, 20, 21, 24, 34, 38, 75, 122, 166, 236, 355, 356, 930, 1042, 1214, 1461, 1622, 4430, 5802, 9092, 16260, 18926, 23698, 40059, 45003, 73807, 91405, 263226, 316872, 321874, 324098, 581132, ... ( continuation A112881 in OEIS )

Example 1:

It is and . So is a prime number (the sixth smallest of the first of the two lists above). The index actually appears in the 8th position in the list above. ${\displaystyle P(9)=12}$ ${\displaystyle P(10)=17}$ ${\displaystyle P(12)=P(10)+P(9)=17+12=29\in \mathbb {P} }$ ${\displaystyle n=12}$

Example 2:

Different Perrin prime numbers are not always obtained with the above list. For example, and is the same. Also and give the same Perrin prime number. However, these two prime numbers are the only ones that can be obtained multiple times with the above index list. ${\displaystyle P(5)=P(3)+P(2)=3+2=5}$ ${\displaystyle P(6)=P(4)+P(3)=2+3=5}$ ${\displaystyle P(2)=2}$ ${\displaystyle P(4)=P(2)+P(1)=2+0=2}$

See also

• Padovan sequence with the same recursion

Individual evidence

1. ^ Jon Grantham: There are infinitely many Perrin pseudoprimes . In: Journal of Number Theory . 130, No. 5, 2010, pp. 1117-1128. doi : 10.1016 / j.jnt.2009.11.008 . (PDF file; 215 kB)