Perrin number

Short description: Number sequence 3,0,2,3,2,5,5,7,10,...

In mathematics, the Perrin numbers are a doubly infinite constant-recursive integer sequence with characteristic equation $x 3 = x + 1$ . The Perrin numbers bear the same relationship to the Padovan sequence as the Lucas numbers do to the Fibonacci sequence.

Definition

The Perrin numbers are defined by the recurrence relation

\begin{aligned} P (0) & = 3, \\ P (1) & = 0, \\ P (2) & = 2, \\ P (n) & = P (n - 2) + P (n - 3) for n > 2, \end{aligned}

and the reverse

P (n) = P (n + 3) - P (n + 1) for n < 0 .

The first few terms in both directions are

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
P(n)	3	0	2	3	2	5	5	7	10	12	17	22	29	39	51	68	90	119	...^[1]
P(-n)	...	-1	1	2	-3	4	-2	-1	5	-7	6	-1	-6	12	-13	7	5	-18	...^[2]

Perrin numbers can be expressed as sums of the three initial terms

\begin{array}{ccc} n & P (n) & P (- n) \\ 0 & P (0) & . . . \\ 1 & P (1) & P (2) - P (0) \\ 2 & P (2) & - P (2) + P (1) + P (0) \\ 3 & P (1) + P (0) & P (2) - P (1) \\ 4 & P (2) + P (1) & P (1) - P (0) \\ 5 & P (2) + P (1) + P (0) & - P (2) + 2 P (0) \\ 6 & P (2) + 2 P (1) + P (0) & 2 P (2) - P (1) - 2 P (0) \\ 7 & 2 P (2) + 2 P (1) + P (0) & - 2 P (2) + 2 P (1) + P (0) \\ 8 & 2 P (2) + 3 P (1) + 2 P (0) & P (2) - 2 P (1) + P (0) \end{array}

The first fourteen prime Perrin numbers are

n	2	3	4	5	6	7	10	12	20	21	24	34	38	75	...^[3]
P(n)	2	3	2	5	5	7	17	29	277	367	853	14197	43721	1442968193	...^[4]

History

The sequence was mentioned implicitly by Édouard Lucas in 1876,^[5] and his ideas were further developed by Raoul Perrin in 1899.^[6] The most extensive treatment was given by William Adams and Daniel Shanks in 1982,^[7] with a sequel appearing four years later.^[8]

Properties

The Perrin sequence also satisfies the recurrence relation $P (n) = P (n - 1) + P (n - 5) .$ Starting from this and the defining recurrence, one can create an infinite number of further relations, for example $P (n) = P (n - 3) + P (n - 4) + P (n - 5) .$

The generating function of the Perrin sequence is

\frac{3 - x^{2}}{1 - x^{2} - x^{3}} = \sum_{n = 0}^{\infty} P (n) x^{n}

The sequence is related to sums of binomial coefficients by

P (n) = n \times \sum_{k = ⌊ (n + 2) / 3 ⌋}^{⌊ n / 2 ⌋} (\binom{k}{n - 2 k}) / k

.^[9]

Perrin numbers can be expressed in terms of partial sums

\begin{aligned} P (n + 5) - 2 & = \sum_{k = 0}^{n} P (k) \\ P (2 n + 3) & = \sum_{k = 0}^{n} P (2 k) \\ 5 - P (4 - n) & = \sum_{k = 0}^{n} P (- k) \\ 3 - P (1 - 2 n) & = \sum_{k = 0}^{n} P (- 2 k) . \end{aligned}

The Perrin numbers are obtained as integral powers $n \geq 0$ of the matrix

{(\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix})}^{n} (\begin{matrix} 3 \\ 0 \\ 2 \end{matrix}) = (\begin{matrix} P (n) \\ P (n + 1) \\ P (n + 2) \end{matrix}),

and its inverse

{(\begin{matrix} - 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})}^{n} (\begin{matrix} 3 \\ 0 \\ 2 \end{matrix}) = (\begin{matrix} P (- n) \\ P (1 - n) \\ P (2 - n) \end{matrix}) .

The Perrin analogue of the Simson identity for Fibonacci numbers is given by the determinant

| \begin{matrix} P (n + 2) & P (n + 1) & P (n) \\ P (n + 1) & P (n) & P (n - 1) \\ P (n) & P (n - 1) & P (n - 2) \end{matrix} | = - 23 .

The number of different maximal independent sets in an n-vertex cycle graph is counted by the nth Perrin number for $n > 2$ .^[10]

Binet formula

The solution of the recurrence $P (n) = P (n - 2) + P (n - 3)$ can be written in terms of the roots of characteristic equation $x^{3} - x - 1 = 0$ . If the three solutions are real root p (with approximate value 1.324718 and known as the plastic ratio) and complex conjugate roots q and r, the Perrin numbers can be computed with the Binet formula $P (n) = p^{n} + q^{n} + r^{n},$ which also holds for negative n.

The polar form is $P (n) = p^{n} + 2 \cos (n θ) \sqrt{p^{- n}},$ with $θ = \arccos (- \sqrt{p^{3}} / 2) .$ Since $\lim_{n \to \infty} p^{- n} = 0,$ the formula reduces to either the first or the second term successively for large positive or negative n, and numbers with negative subscripts oscillate. Provided p is computed to sufficient precision, these formulas can be used to calculate Perrin numbers for large n.

Expanding the identity $P^{2} (n) = (p^{n} + q^{n} + r^{n})^{2}$ gives the important index-doubling rule $P (2 n) = P^{2} (n) - 2 P (- n),$ by which the forward and reverse parts of the sequence are linked.

Perrin primality test

The Perrin sequence has the Fermat property: if $p$ is prime, $P(p) \equiv P(1) \equiv 0 (mod p)$ . However, the converse is not true: some composite $n$ may still divide $P(n)$ . A number with this property is called a Perrin pseudoprime.

The seventeen Perrin pseudoprimes below $109$ are

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431.^[11]

The question of the existence of Perrin pseudoprimes was considered by Perrin himself, but none were known until Adams and Shanks (1982) discovered the smallest one, 271441 = 521² (the number $P(271441)$ has 33150 decimal digits).^[12] Jon Grantham later proved that there are infinitely many Perrin pseudoprimes.^[13]

Adams and Shanks noted that primes also satisfy the congruence $P(-p) \equiv P(-1) \equiv -1 (mod p)$ . Composites for which both properties hold are called restricted Perrin pseudoprimes. There are only nine such numbers below $109$ .^[14]

While Perrin pseudoprimes are rare, they overlap with Fermat pseudoprimes. Of the above seventeen numbers, four are also base 2 Fermatians. In contrast, the Lucas pseudoprimes are anti-correlated. Presumably, combining the Perrin and Lucas tests would make a primality test as strong as the reliable BPSW test which has no known pseudoprimes – though at higher computational cost.

Pseudocode

The 1982 Adams and Shanks $O(log n)$ Strong Perrin primality test.^[15]

Two integer arrays u(3) and v(3) are initialized to the lowest terms of the Perrin sequence, with positive indices $t = 0, 1, 2$ in u( ) and negative indices $t = 0,-1,-2$ in v( ).

The main double-and-add loop, originally devised to run on an HP-41C pocket calculator, efficiently computes $P(n) mod n$ and the reverse $P(-n) mod n$ .^[16]

The subscripts of the Perrin numbers are doubled using the identity $P(2t) = P 2 (t) - 2P(-t)$ . The resulting gaps between $P(\pm2t)$ and $P(\pm2t \pm 2)$ are closed by applying the defining relation $P(t) = P(t - 2) + P(t - 3)$ .

Initial values
LET u(0):= 3, u(1):= 0, u(2):= 2
LET v(0):= 3, v(1):=−1, v(2):= 1
     
INPUT integer n, the odd positive number to test
     
SET integer h:= most significant bit of n
     
FOR k:= h − 1 DOWNTO 0
     
  Double the indices of
  the six Perrin numbers.
  FOR i = 0, 1, 2
    temp:= u(i)^2 − 2v(i) (mod n)
    v(i):= v(i)^2 − 2u(i) (mod n)
    u(i):= temp
  ENDFOR
     
  Copy P(2t + 2) and P(−2t − 2)
  to the array ends and use
  in the IF statement below.
  u(3):= u(2)
  v(3):= v(2)
     
  Overwrite P(2t ± 2) with P(2t ± 1)
  temp:= u(2) − u(1)
  u(2):= u(0) + temp
  u(0):= temp
     
  Overwrite P(−2t ± 2) with P(−2t ± 1)
  temp:= v(0) − v(1)
  v(0):= v(2) + temp
  v(2):= temp
     
  IF n has bit k set THEN
    Increase the indices of
    both Perrin triples by 1.
    FOR i = 0, 1, 2
      u(i):= u(i + 1)
      v(i):= v(i + 1)
    ENDFOR
  ENDIF
     
ENDFOR
     
Show the results
PRINT u(0), u(1), u(2)
PRINT v(2), v(1), v(0)

Successively $P(n - 1), P(n), P(n + 1)$ and $P(-n - 1), P(-n), P(-n + 1) (mod n)$ .

If $P(n) = 0$ and $P(-n) = -1$ then n is a probable prime, that is: actually prime or a strong Perrin pseudoprime.

Adams and Shanks enhanced the test by defining "acceptable signatures" comprising all six residues.^[17] An even stronger test also uses the Narayana-Lucas sister sequence,^[18] with recurrence relation $A(n) = A(n - 1) + A(n - 3)$ and initial values

u(0):= 3, u(1):= 1, u(2):= 1
v(0):= 3, v(1):= 0, v(2):=−2

The same doubling rule applies and the formulas for filling the gaps are

temp:= u(0) + u(1)
u(0):= u(2) − temp
u(2):= temp
     
temp:= v(2) + v(1)
v(2):= v(0) − temp
v(0):= temp

Here, n is a probable prime if $A(n) = 1$ and $A(-n) = 0$ .

Shanks et al. found no overlap between the odd pseudoprimes for the two sequences below $50∙10 9$ and supposed that 2277740968903 = 1067179 ∙ 2134357 is the smallest composite number to pass both tests.^[19]

Notes

↑ Sloane, N. J. A., ed. "Sequence A001608". OEIS Foundation. https://oeis.org/A001608.
↑ (sequence A078712 in the OEIS)
↑ (sequence A112881 in the OEIS)
↑ (sequence A074788 in the OEIS)
↑ (Lucas 1876)
↑ (Perrin 1899)
↑ (Adams Shanks)
↑ (Kurtz Shanks)
↑ (sequence A001608 in the OEIS)
↑ (Füredi 1987)
↑ (sequence A013998 in the OEIS)
↑ (Adams Shanks)
↑ (Grantham 2010)
↑ (sequence A018187 in the OEIS)
↑ (Adams Shanks)
↑ (Adams Shanks)
↑ Weisstein, Eric W.. "Recurrence Relation Signature". http://mathworld.wolfram.com/RecurrenceRelationSignature.html. , (sequence A275612 in the OEIS), (sequence A275613 in the OEIS).
↑ dubbed Secundo in (Kurtz Shanks)
↑ (Kurtz Shanks)

References

"Sur la recherche des grands nombres premiers". Congrès de Clermont-Ferrand (5 ed.). Association française pour l'avancement des sciences. 1876. pp. 61−68. http://visualiseur.bnf.fr/CadresFenetre?O=NUMM-201152&I=131&M=pagination.
"Query 1484". L'Intermédiaire des Mathématiciens (Gauthier-Villars et fils) 6: 76−77. 1899.
Adams, William (1982). "Strong primality tests that are not sufficient". Mathematics of Computation (American Mathematical Society) 39 (159): 255−300. doi:10.1090/S0025-5718-1982-0658231-9.
Kurtz, G.C. (1986). "Fast primality tests for numbers less than 50∙10⁹". Mathematics of Computation (American Mathematical Society) 46 (174): 691−701. doi:10.1090/S0025-5718-1986-0829639-7.
"The number of maximal independent sets in connected graphs". Journal of Graph Theory 11 (4): 463−470. 1987. doi:10.1002/jgt.3190110403.
Grantham, Jon (2010). "There are infinitely many Perrin pseudoprimes". Journal of Number Theory 130 (5): 1117−1128. doi:10.1016/j.jnt.2009.11.008.

External links

"Perrin's Sequence". MathPages.com. http://www.mathpages.com/home/kmath345/kmath345.htm.
"Lucas and Perrin Pseudoprimes". MathPages.com. http://www.mathpages.com/home/kmath127/kmath127.htm.
Jacobsen, Dana (2016). "Perrin Primality Tests".
Holzbaur, Christian (1997). "Perrin Pseudoprimes".

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Perrin number. Read more

[1] Sloane, N. J. A., ed. "Sequence A001608". OEIS Foundation. https://oeis.org/A001608.

[2] (sequence A078712 in the OEIS)

[3] (sequence A112881 in the OEIS)

[4] (sequence A074788 in the OEIS)

[5] (Lucas 1876)

[6] (Perrin 1899)

[7] (Adams Shanks)

[8] (Kurtz Shanks)

[9] (sequence A001608 in the OEIS)

[10] (Füredi 1987)

[11] (sequence A013998 in the OEIS)

[12] (Adams Shanks)

[13] (Grantham 2010)

[14] (sequence A018187 in the OEIS)

[15] (Adams Shanks)

[16] (Adams Shanks)

[17] Weisstein, Eric W.. "Recurrence Relation Signature". http://mathworld.wolfram.com/RecurrenceRelationSignature.html. , (sequence A275612 in the OEIS), (sequence A275613 in the OEIS).

[18] ubbed Secundo in (Kurtz Shanks)

[19] (Kurtz Shanks)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

v t e Prime number classes
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Carol $(2 n - 1) 2 - 2$ Kynea $(2 n + 1) 2 - 2$ Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partitions Bell Motzkin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient
Base-dependent	Happy Dihedral Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n - 1, n + 1, 2 n - 1, 2 n + 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k−Tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Safe ( $p, (p - 1)/2$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Titanic (1,000+ digits) Gigantic (10,000+ digits) Mega (1,000,000+ digits) Largest known
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Somer–Lucas Strong Carmichael number Almost prime Semiprime Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers

Anonymous

Search

Perrin number

Namespaces

More

Page actions

Contents

Definition

History

Properties

Binet formula

Perrin primality test

Pseudocode

Notes

References

External links

Navigation

Navigation

Help

googletranslator

Navigation

Wiki tools

Wiki tools

Anonymous

Search

Perrin number

Definition

History

Properties

Binet formula

Perrin primality test

Pseudocode

Notes

References

External links

Navigation

Wiki tools

Page tools

Other projects

Categories