In 1876 the sequence and its equation were initially mentioned byÉdouard Lucas, who noted that the indexn divides termP(n) ifn is prime.[5] In 1899Raoul Perrin [fr] asked if there were any counterexamples to this property.[6] The firstP(n) divisible by composite indexn was found only in 1982 by William Adams andDaniel Shanks.[7] They presented a detailed investigation of the sequence, with a sequel appearing four years later.[8]
The Perrin sequence also satisfies the recurrence relation Starting from this and the defining recurrence, one can create an infinite number of further relations, for example
Thepolar form is with Since the formula reduces to either the first or the second term successively for large positive or negativen, and numbers with negative subscripts oscillate. Providedα is computed to sufficient precision, these formulas can be used to calculate Perrin numbers for largen.
Expanding the identity gives the important index-doubling rule by which the forward and reverse parts of the sequence are linked.
Thefundamental theorem on symmetric polynomials states that every symmetric polynomial in the complex roots of monic can be represented as another polynomial function in the integer coefficients of
Rearrange into symmetricmonomial summands,permuting exponentsi, j, k:
Substitute prime for power and complex roots for integers and compute representations in terms of for all symmetric polynomial functions. For example, is and thepower sum can be expressed in the coefficients withNewton's recursive scheme. It follows that the identity has integer terms and both sides divisible by prime
To show that prime divides in the reverse sequence, the characteristic equation has to bereflected. The roots are then the coefficients and the same reasoning applies.
Query 1484. The curiousproposition of Chinese origin which is the subject of query 1401[10] would provide, if it is true, a more practical criterium thanWilson's theorem for verifying whether a given number m is prime or not; it would suffice to calculate the residues with respect to m of successive terms of the recurrence sequence un = 3un−1 − 2un−2 with initial values u0 = −1, u1 = 0.[11] I have found another recurrence sequence that seems to possess the same property; it is the one whose general term is vn = vn−2 + vn−3 with initial values v0 = 3, v1 = 0, v2 = 2. It is easy to demonstrate that vn is divisible by n, if n is prime; I have verified, up to fairly high values of n, that in the opposite case it is not; but it would be interesting to know if this is really so, especially since the sequence vn gives much less rapidly increasing numbers than the sequence un (for n = 17, for example, one finds un = 131070, vn = 119), which leads to simpler calculations when n is a large number. The same proof, applicable to one of the sequences, will undoubtedly bear upon the other, if the stated property is true for both: it is only a matter of discovering it.[12]
The Perrin sequence has theFermat property: ifp isprime,P(p) ≡ P(1) ≡ 0 (mod p). However, theconverse is not true: somecompositen may still divideP(n). A number with this property is called a Perrinpseudoprime.
The question of the existence of Perrin pseudoprimes was considered by Malo and Jarden,[13] but none were known until Adams and Shanks found the smallest one, 271441 = 5212 (the numberP(271441) has 33150 decimal digits).[14] Jon Grantham later proved that there are infinitely many Perrin pseudoprimes.[15]
Adams and Shanks noted that primes also satisfy the congruenceP(−p) ≡ P(−1) ≡ −1 (mod p). Composites for which both properties hold are called restricted Perrin pseudoprimes. There are only nine such numbers below109.[17][18][19]
While Perrin pseudoprimes are rare, they overlap withFermat pseudoprimes. Of the above seventeen numbers, four are base 2 Fermatians as well. In contrast, theLucas pseudoprimes are anti-correlated.[20] Presumably, combining the Perrin and Lucas tests should make aprimality test as strong as the reliableBPSW test which has no known pseudoprimes – though at higher computational cost.
The 1982 Adams and ShanksO(log n) Perrin primality test.[21]
Two integer arrays u(3) and v(3) are initialized to the lowest terms of the Perrin sequence, with positive indicest = 0, 1, 2 in u( ) and negative indicest = 0,−1,−2 in v( ).
The maindouble-and-add loop, originally devised to run on anHP-41C pocket calculator, computesP(n) mod n and the reverseP(−n) mod n at the cost of six modular squarings for each bit ofn.
The subscripts of the Perrin numbers are doubled using the identityP(2t) = P2(t) − 2P(−t). The resulting gaps betweenP(±2t) andP(±2t ± 2) are closed by applying the defining relationP(t) = P(t − 2) + P(t − 3).
Initial valuesletint u(0):= 3, u(1):= 0,u(2):= 2letint v(0):= 3, v(1):=−1,v(2):= 1Test odd positive number ninputint nsetint h:= most significant bit of nfor k:= h − 1downto 0Double the indices ofthe 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):= tempendforCopy P(2t + 2) andP(−2t − 2)to the array ends and usein the if-statement below. u(3):= u(2) v(3):= v(2)Overwrite P(2t ± 2) withP(2t ± 1) temp:= u(2) − u(1) u(2):= u(0) + temp u(0):= tempOverwrite P(−2t ± 2) withP(−2t ± 1) temp:= v(0) − v(1) v(0):= v(2) + temp v(2):= tempif n has bit k setthenIncrease the indices ofboth Perrin triples by 1.for i = 0, 1, 2 u(i):= u(i + 1) v(i):= v(i + 1)endforendifendforResultprint v(2), v(1), v(0)print u(0), u(1), u(2)
IfP(−n) = −1 andP(n) = 0 thenn is aprobable prime, that is: actually prime or a restricted Perrin pseudoprime.
Shankset al. observed that for all restricted pseudoprimes they found, the final state of the above six registers (the "signature" ofn) equals the initial state 1,−1,3, 3,0,2.[22] The same occurs with≈ 1/6 of all primes, so the two sets cannot be distinguished on the strength of this test alone.[23] For those cases, they recommend to also use theNarayana-Lucas sister sequence with recurrence relationA(n) = A(n − 1) + A(n − 3) and initial values
Here,n is a probable prime ifA(−n) = 0 andA(n) = 1.
Kurtzet al. found no overlap between the odd pseudoprimes for the two sequences below50∙109 and supposed that 2,277,740,968,903 = 1067179 ∙ 2134357 is the smallest composite number to pass both tests.[24]
If thethird-order Pell-Lucas recurrenceA(n) = 2A(n − 1) + A(n − 3) is used as well, this bound will be pushed up to 4,057,052,731,496,380,171 = 1424263447 ∙ 2848526893.[25]
Additionally, roots of the doubling rule-congruence other than−1 or3 expose composite numbers, like non-trivial square roots of1 in theMiller-Rabin test.[26] This reduces the number of restricted pseudoprimes for each sequence by roughly one-third and is especially efficient in detectingCarmichael numbers.[27]
The least strong restricted Perrin pseudoprime is 46672291 and the above two bounds expand to successively 173,536,465,910,671 and 79,720,990,309,209,574,421.[28]
^The signature does give discriminating information on the remaining two types of primes.For example, the smallest Q-type pseudoprime 50,972,694,899,204,437,633 computed by HolgerStephan (2019) is exposed by signature conditions 14a and 14c inAdams & Shanks (1982, p. 257).
