Perrin number

From HandWiki
Short description: Number sequence 3,0,2,3,2,5,5,7,10,...
Spiral of equilateral triangles with side lengths equal to Perrin numbers.

In mathematics, the Perrin numbers are a doubly infinite constant-recursive integer sequence with characteristic equation x3 = 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

[math]\displaystyle{ \begin{align} P(0)&=3, \\ P(1)&=0, \\ P(2)&=2, \\ P(n)&=P(n-2) +P(n-3) \mbox{ for }n\gt 2, \end{align} }[/math]

and the reverse

[math]\displaystyle{ P(n) =P(n+3) -P(n+1) \mbox{ for }n\lt 0. }[/math]

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

[math]\displaystyle{ \begin{array}{c|c|c} n & P(n) & P(-n) \\ \hline 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) +2P(0) \\ 6 & P(2) +2P(1) +P(0) & 2P(2) -P(1) -2P(0) \\ 7 & 2P(2) +2P(1) +P(0) & -2P(2) +2P(1) +P(0) \\ 8 & 2P(2) +3P(1) +2P(0) & P(2) -2P(1) +P(0) \end{array} }[/math]

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 [math]\displaystyle{ P(n) =P(n-1) +P(n-5). }[/math] Starting from this and the defining recurrence, one can create an infinite number of further relations, for example [math]\displaystyle{ P(n) =P(n-3) +P(n-4) +P(n-5). }[/math]

The generating function of the Perrin sequence is

[math]\displaystyle{ \frac{3 -x^2}{1 -x^2 -x^3} =\sum_{n=0}^{\infty} P(n)\,x^n }[/math]

The sequence is related to sums of binomial coefficients by

[math]\displaystyle{ P(n) =n \times \sum_{k =\lfloor (n +2)/3 \rfloor}^{\lfloor n /2 \rfloor}{k \choose n -2k} /k }[/math].[9]

Perrin numbers can be expressed in terms of partial sums

[math]\displaystyle{ \begin{align} P(n+5) -2&=\sum_{k=0}^{n} P(k) \\ P(2n+3)&=\sum_{k=0}^{n} P(2k) \\ 5 -P(4-n)&=\sum_{k=0}^{n} P(-k) \\ 3 -P(1-2n)&=\sum_{k=0}^{n} P(-2k). \end{align} }[/math]

The Perrin numbers are obtained as integral powers n ≥ 0 of the matrix

[math]\displaystyle{ \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}^{n} \begin{pmatrix} 3 \\ 0 \\ 2 \end{pmatrix} = \begin{pmatrix} P(n) \\ P(n+1) \\ P(n+2) \end{pmatrix}, }[/math]

and its inverse

[math]\displaystyle{ \begin{pmatrix} -1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^{n} \begin{pmatrix} 3 \\ 0 \\ 2 \end{pmatrix} = \begin{pmatrix} P(-n) \\ P(1-n) \\ P(2-n) \end{pmatrix}. }[/math]

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

[math]\displaystyle{ \begin{vmatrix} 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{vmatrix} =-23. }[/math]

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 Perrin function extends the sequence to real numbers.

The solution of the recurrence [math]\displaystyle{ P(n) =P(n-2) +P(n-3) }[/math] can be written in terms of the roots of characteristic equation [math]\displaystyle{ x^3 -x -1=0 }[/math]. 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 [math]\displaystyle{ P(n) = p^n + q^n + r^n, }[/math] which also holds for negative n.

The polar form is [math]\displaystyle{ P(n) =p^n +2\cos(n\,\theta) \sqrt{\vphantom{\mid}p^{-n}}, }[/math] with [math]\displaystyle{ \theta =\arccos(-\sqrt{p^3} /2). }[/math] Since [math]\displaystyle{ \lim_{n \to \infty}p^{-n} =0, }[/math] 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 [math]\displaystyle{ P^{2}(n) =(p^n + q^n + r^n)^2 }[/math] gives the important index-doubling rule [math]\displaystyle{ P(2n) =P^{2}(n) -2P(-n), }[/math] 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) ≡ P(1) ≡ 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 = 5212 (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) ≡ P(−1) ≡ −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) = P2(t) − 2P(−t). The resulting gaps between P(±2t) and P(±2t ± 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∙109 and supposed that 2277740968903 = 1067179 ∙ 2134357 is the smallest composite number to pass both tests.[19]

Notes

  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. ↑ dubbed Secundo in (Kurtz Shanks)
  19. ↑ (Kurtz Shanks)

References

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Perrin_number&oldid=3381872"