Perrin number
In mathematics, the Perrin numbers are a doubly infinite constant-recursive integer sequence with characteristic equation x3 = x + 1.
The Perrin numbers, named after the French engineer Raoul Perrin [fr], bear the same relationship to the Padovan sequence as the Lucas numbers do to the Fibonacci sequence.
The Perrin numbers are defined by the recurrence relation and the reverse The first few terms in both directions are Perrin numbers can be expressed as sums of the three initial terms The first fourteen prime Perrin numbers are In 1876 the sequence and its equation were initially mentioned by Édouard Lucas, who noted that the index n divides term P(n) if n is prime.
[5] In 1899 Raoul Perrin [fr] asked if there were any counterexamples to this property.
[6] The first P(n) divisible by composite index n was found only in 1982 by William Adams and Daniel Shanks.
[7] They presented a detailed investigation of the sequence, with a sequel appearing four years later.
Starting from this and the defining recurrence, one can create an infinite number of further relations, for example
(with approximate value 1.324718 and known as the plastic ratio) and complex conjugate roots
Provided α is computed to sufficient precision, these formulas can be used to calculate Perrin numbers for large n. Expanding the identity
with Vieta's formulas: These integer valued functions are the elementary symmetric polynomials in
, Rearrange into symmetric monomial summands, permuting exponents i, j, k: Substitute prime
It follows that the identity has integer terms and both sides divisible by prime
The curious proposition of Chinese origin which is the subject of query 1401[10] would provide, if it is true, a more practical criterium than Wilson'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 the Fermat property: if p is prime, P(p) ≡ P(1) ≡ 0 (mod p).
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 number P(271441) has 33150 decimal digits).
[14] Jon Grantham later proved that there are infinitely many Perrin pseudoprimes.
[15] The seventeen Perrin pseudoprimes below 109 are 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.
The 1982 Adams and Shanks O(log n) Perrin primality test.
The main double-and-add loop, originally devised to run on an HP-41C pocket calculator, computes P(n) mod n and the reverse P(−n) mod n at the cost of six modular squarings for each bit of n. 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).
Shanks et al. observed that for all restricted pseudoprimes they found, the final state of the above six registers (the "signature" of n) 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 the Narayana-Lucas sister sequence with recurrence relation A(n) = A(n − 1) + A(n − 3) and initial values The same doubling rule applies and the formulas for filling the gaps are Here, n is a probable prime if A(−n) = 0 and A(n) = 1.
Kurtz et al. found no overlap between the odd pseudoprimes for the two sequences below 50∙109 and supposed that 2,277,740,968,903 = 1067179 ∙ 2134357 is the smallest composite number to pass both tests.
other than −1 or 3 expose composite numbers, like non-trivial square roots of 1 in the Miller-Rabin test.
[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.
