A013998 -id:A013998 - cp's OEIS frontend

A001608 Perrin sequence (or Ondrej Such sequence): a(n) = a(n-2) + a(n-3) with a(0) = 3, a(1) = 0, a(2) = 2.

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, 414646, 549289

Offset: 0

N. J. A. Sloane

Has been called the skiponacci sequence or skiponacci numbers. - N. J. A. Sloane, May 24 2013
For n >= 3, also the numbers of maximal independent vertex sets, maximal matchings, minimal edge covers, and minimal vertex covers in the n-cycle graph C_n. - Eric W. Weisstein, Mar 30 2017 and Aug 03 2017
With the terms indexed as shown, has property that p prime => p divides a(p). The smallest composite n such that n divides a(n) is 521^2. For quotients a(p)/p, where p is prime, see A014981.
Asymptotically, a(n) ~ r^n, with r=1.3247179572447... the inverse of the real root of 1-x^2-x^3=0 (see A060006). If n>9 then a(n)=round(r^n). - Ralf Stephan, Dec 13 2002
The recursion can be used to compute a(-n). The result is -A078712(n). - T. D. Noe, Oct 10 2006
For n>=3, a(n) is the number of maximal independent sets in a cycle of order n. - Vincent Vatter, Oct 24 2006
Pisano period lengths are given in A104217. - R. J. Mathar, Aug 10 2012
From Roman Witula, Feb 01 2013: (Start)
Let r1, r2 and r3 denote the roots of x^3 - x - 1. Then the following identity holds:
a(k*n) + (a(k))^n - (a(k) - r1^k)^n - (a(k) - r2^k)^n - (a(k) - r3^k)^n
 = 0 for n = 0, 1, 2,
 = 6 for n = 3,
 = 12*a(k) for n = 4,
 = 10*[2*(a(k))^2 - a(-k)] for n = 5,
 = 30*a(k)*[(a(k))^2 - a(-k)] for n = 6,
 = 7*[6*(a(k))^4 - 9*a(-k)*(a(k))^2 + 2*(a(-k))^2 - a(k)] for n = 7,
 = 56*a(k)*[((a(k))^2 - a(-k))^2 - a(k)/2] for n = 8,
where a(-k) = -A078712(k) and the formula (5.40) from the paper of Witula and Slota is used. (End)
The parity sequence of a(n) is periodic with period 7 and has the form (1,0,0,1,0,1,1). Hence we get that a(n) and a(2*n) are congruent modulo 2. Similarly we deduce that a(n) and a(3*n) are congruent modulo 3. Is it true that a(n) and a(p*n) are congruent modulo p for every prime p? - Roman Witula, Feb 09 2013
The trinomial x^3 - x - 1 divides the polynomial x^(3*n) - a(n)*x^(2*n) + ((a(n)^2 - a(2*n))/2)*x^n - 1 for every n>=1. For example, for n=3 we obtain the factorization x^9 - 3*x^6 + 2*x^3 - 1 = (x^3 - x - 1)*(x^6 + x^4 - 2*x^3 + x^2 - x + 1). Sketch of the proof: Let p,s,t be roots of the Perrin polynomial x^3 - x - 1. Then we have (a(n))^2 = (p^n + s^n + t^n)^2 = a(2*n) + 2*a(n)*x^n -2*x^n + 2/x^n for every x = p,s,t, i.e., x^(3*n) - a(n)*x^(2*n) + ((a(n)^2 - a(2*n))/2)*x^n - 1 = 0 for every x = p,s,t, which finishes the proof. By discussion of the power(a(n))^3 = (p^n + s^n + t^n)^3 it can be deduced that the trinomial x^3 - x - 1 divides the polynomial 2*x^(4*n) - a(n)*x^(3*n) - a(2*n)*x^(2*n) + ((a(n)^3 - a(3*n) - 3)/3)*x^n - a(n) = 0. Co-author of these divisibility relations is also my young student Szymon Gorczyca (13 years old as of 2013). - Roman Witula, Feb 09 2013
The sum of powers of the real root and complex roots of x^3-x-1=0 as expressed as powers of the plastic number r, (see A060006). Let r0=1, r1=r, r2=1+r^(-1) and c0=2, c1=-r and c3 = r^(-5) then a(n) = r(n-2)+r(n-3) + c(n-2)+c(n-3). Example: a(5) = 1 + r^(-1) + 1 + r + 2 - r + r^(-5) = 4 + r^(-1) + r^(-5) = 5. - Richard Turk, Jul 14 2016
Also the number of minimal total dominating sets in the n-sun graph. - Eric W. Weisstein, Apr 27 2018
Named after the French engineer François Olivier Raoul Perrin (1841-1910). - Amiram Eldar, Jun 05 2021
a(p) = p*A127687(p) for p prime. - Robert FERREOL, Apr 09 2024

			From _Roman Witula_, Feb 01 2013: (Start)
We note that if a + b + c = 0 then:
1) a^3 + b^3 + c^3 = 3*a*b*c,
2) a^4 + b^4 + c^4 = 2*((a^2 + b^2 + c^2)/2)^2,
3) (a^5 + b^5 + c^5)/5 = (a^3 + b^3 + c^3)/3 * (a^2 +
    b^2  + c^2)/2,
4) (a^7 + b^7 + c^7)/7 = (a^5 + b^5 + c^5)/5 * (a^2 + b^2 + c^2)/2 = 2*(a^3 + b^3 + c^3)/3 * (a^4 + b^4 + c^4)/4,
5) (a^7 + b^7 + c^7)/7 * (a^3 + b^3 + c^3)/3 = ((a^5 + b^5 + c^5)/5)^2.
Hence, by the Binet formula for a(n) we obtain the relations: a(3) = 3, a(4) = 2*(a(2)/2)^2 = 2, a(5)/5 = a(3)/3 * a(2)/2, i.e., a(5) = 5, and similarly that a(7) = 7. (End)

Olivier Bordellès, Thèmes d'Arithmétique, Ellipses, 2006, Exercice 4.11, p. 127.0
Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.2.
Dmitry Fomin, On the properties of a certain recursive sequence, Mathematics and Informatics Quarterly, Vol. 3 (1993), pp. 50-53.
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 70.
Manfred Schroeder, Number Theory in Science and Communication, 3rd ed., Springer, 1997.
A. G. Shannon, P. G. Anderson and A. F. Horadam, Properties of Cordonnier, Perrin and Van der Laan numbers, International Journal of Mathematical Education in Science and Technology, Volume 37:7 (2006), 825-831. See Q_n.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Indranil Ghosh, Table of n, a(n) for n = 0..8172 (terms 0..1000 from T. D. Noe)
Sadjia Abbad and Hacène Belbachir, The r-Fibonacci polynomial and its companion sequences linked with some classical sequences, Integers (2025), Vol. 25, Art. No. A38. See p. 17.
William Adams and Daniel Shanks, Strong primality tests that are not sufficient, Math. Comp., Vol. 39, No. 159 (1982), pp. 255-300.
Kouèssi Norbert Adédji, Japhet Odjoumani, and Alain Togbé, Padovan and Perrin numbers as products of two generalized Lucas numbers, Archivum Mathematicum, Vol. 59 (2023), No. 4, 315-337.
Bill Amend, "Foxtrot" cartoon, Oct 11, 2005 (Illustration of initial terms! From www.ucomics.com/foxtrot/.)
Mohamadou Bachabi and Alain S. Togbé, Products of Fermat or Mersenne numbers in some sequences, Math. Comm. (2024) Vol. 29, 265-285.
Herbert Batte, Taboka P. Chalebgwa and Mahadi Ddamulira, Perrin numbers that are concatenations of two distinct repdigits, arXiv:2105.08515 [math.NT], 2021.
Daniel Birmajer, Juan B. Gil and Michael D. Weiner, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv:1505.06339 [math.NT], 2015.
Eric Fernando Bravo, On concatenations of Padovan and Perrin numbers, Math. Commun. (2023) Vol 28, 105-119.
Kevin S. Brown, Perrin's Sequence
J. Chick, Problem 81G, Math. Gazette, Vol. 81, No. 491 (1997), p. 304.
Tomislav Doslic and I. Zubac, Counting maximal matchings in linear polymers, Ars Mathematica Contemporanea, Vol. 11 (2016), pp. 255-276.
Robert Dougherty-Bliss, The Meta-C-finite Ansatz, arXiv preprint arXiv:2206.14852 [math.CO], 2022.
Robert Dougherty-Bliss, Experimental Methods in Number Theory and Combinatorics, Ph. D. Dissertation, Rutgers Univ. (2024). See p. 34.
Robert Dougherty-Bliss and Doron Zeilberger, Lots and Lots of Perrin-Type Primality Tests and Their Pseudo-Primes, arXiv:2307.16069 [math.NT], 2023.
E. B. Escott, Problem 151, Amer. Math. Monthly, Vol. 15, No. 11 (1908), p. 209.
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly, Vol. 6 (1968), pp. 64-70.
Daniel C. Fielder, Errata:Special integer sequences controlled by three parameters, Fibonacci Quarterly, Vol. 6 (1968), pp. 64-70.
Zoltán Füredi, The number of maximal independent sets in connected graphs, J. Graph Theory, Vol. 11, No. 4 (1987), pp. 463-470.
Bill Gasarch, When does n divide a_n in this sequence? (2016).
A. Justin Gopinath and B. Nithya, Mathematical and Simulation Analysis of Contention Resolution Mechanism for IEEE 802.11 ah Networks, Computer Communications (2018) Vol. 124, 87-100.
Christian Holzbaur, Perrin pseudoprimes [Original link broke many years ago. This is a cached copy from the WayBack machine, dated Apr 24 2006]
Dmitry I. Ignatov, On the Maximal Independence Polynomial of the Covering Graph of the Hypercube up to n = 6, Int'l Conf. Formal Concept Analysis, 2023.
Stanislav Jakubec and Karol Nemoga, On a conjecture concerning sequences of the third order, Mathematica Slovaca, Vol. 36, No. 1 (1986), pp. 85-89.
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 90.
Bir Kafle, Salah Eddine Rihane and Alain Togbé, A note on Mersenne Padovan and Perrin numbers, Notes on Num. Theory and Disc. Math., Vol. 27, No. 1 (2021), pp. 161-170.
Vedran Krcadinac, A new generalization of the golden ratio, Fibonacci Quart., Vol. 44, No. 4 (2006), pp. 335-340.
G. C. Kurtz, Daniel Shanks and H. C. Williams, Fast primality tests for numbers less than 50*10^9, Mathematics of Computation, Vol. 46, No. 174 (1986), pp. 691-701. [Studies primes in this sequence. - _N. J. A. Sloane_, Jul 28 2019]
I. E. Leonard and A. C. F. Liu, A familiar recurrence occurs again, Amer. Math. Monthly, Vol. 119, No. 4 (2012), 333-336.
J. M. Luck and A. Mehta, Universality in survivor distributions: Characterising the winners of competitive dynamics, Physical Review E, Vol. 92, No. 5 (2015), 052810; arXiv preprint, arXiv:1511.04340 [q-bio.QM], 2015.
Matthew Macauley, Jon McCammond and Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.
Gregory Minton, Three approaches to a sequence problem, Math. Mag., Vol. 84, No. 1 (2011), pp. 33-37.
Gregory T. Minton, Linear recurrence sequences satisfying congruence conditions, Proc. Amer. Math. Soc., Vol. 142, No. 7 (2014), pp. 2337-2352. MR3195758.
B. H. Neumann and L. G. Wilson, Some Sequences like Fibonacci's, Fibonacci Quart., Vol. 17, No. 1 (1979), p. 83.
Mathilde Noual, Dynamics of Circuits and Intersecting Circuits, in Language and Automata Theory and Applications, Lecture Notes in Computer Science, 2012, Volume 7183/2012, 433-444, DOI; also on arXiv, arXiv 1011.3930 [cs.DM], 2010.
Ahmet Öteleş, Bipartite Graphs Associated with Pell, Mersenne and Perrin Numbers, An. Şt. Univ. Ovidius Constantą, (2019) Vol. 27, Issue 2, 109-120.
R. Perrin, Query 1484, L'Intermédiaire des Mathématiciens, Vol. 6 (1899), p. 76.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Salah Eddine Rihane, Chèfiath Awero Adegbindin and Alain Togbé, Fermat Padovan And Perrin Numbers, J. Int. Seq., Vol. 23 (2020), Article 20.6.2.
Salah Eddine Rihane and Alain Togbé, Repdigits as products of consecutive Padovan or Perrin numbers, Arab. J. Math. (2021).
David E. Rush, Degree n Relatives of the Golden Ratio and Resultants of the Corresponding Polynomials, Fibonacci Quart., Vol. 50, No. 4 (2012), pp. 313-325. See p. 318.
J. O. Shallit and J. P. Yamron, On linear recurrences and divisibility by primes, Fibonacci Quart., Vol. 22, No. 4 (1984), p. 366.
Yuksel Soykan, Vedat Irge, and Erkan Tasdemir, A Comprehensive Study of K-Circulant Matrices Derived from Generalized Padovan Numbers, Asian Journal of Probability and Statistics 26 (12):152-70, (2024). See p. 154.
Ian Stewart, Tales of a Neglected Number, Mathematical Recreations, Scientific American, Vol. 274, No. 6 (1996), pp. 102-103.
Ondrej Such, An Insufficient Condition for Primality, Problem 10268, Amer. Math. Monthly, Vol. 102, No. 6 (1995), pp. 557-558.
Ondrej Such, An Insufficient Condition for Primality, Problem 10268, Amer. Math. Monthly, Vol. 103, No. 10 (1996), p. 911.
Takatora Suzuki and Momoko Hayamizu, Which Phylogenetic Networks are Level-k Networks with Additional Arcs? Structure and Algorithms, arXiv:2505.11947 [math.CO], 2025.
Pagdame Tiebekabe and Kouèssi Norbert Adédji, On Padovan or Perrin numbers as products of three repdigits in base delta, 2023.
Razvan Tudoran, Problem 653, College Math. J., Vol. 31, No. 3 (2000), pp. 223-224.
Vincent Vatter, Social distancing, primes, and Perrin numbers, Math Horiz., Vol. 29, No. 1, pp. 5-7.
Stan Wagon, Letter to the Editor, Math. Mag., Vol. 84, No. 2 (2011), p. 119.
Michel Waldschmidt, Lectures on Multiple Zeta Values, IMSC 2011.
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Edge Cover.
Eric Weisstein's World of Mathematics, Minimal Vertex Cover
Eric Weisstein's World of Mathematics, Perrin Pseudoprime
Eric Weisstein's World of Mathematics, Perrin Sequence
Eric Weisstein's World of Mathematics, Sun Graph
Eric Weisstein's World of Mathematics, Total Dominating Set
Willem's Fibonacci site, Perrin and Fibonacci.
Wikipedia, Perrin Number.
Roman Witula and Damian Slota, Conjugate sequences in Fibonacci-Lucas sense and some identities for sums of powers of their elements, Integers, Vol. 7 (2007), #A08.
Richard J. Yanco, Letter and Email to N. J. A. Sloane, 1994
Richard Yanco and Ansuman Bagchi, K-th order maximal independent sets in path and cycle graphs, Unpublished manuscript, 1994. (Annotated scanned copy)
Fatih Yilmaz and Durmus Bozkurt, Hessenberg matrices and the Pell and Perrin numbers, Journal of Number Theory, Volume 131, Issue 8 (August 2011), pp. 1390-1396. [The terms given in the paper contain a typo]
Index entries for linear recurrences with constant coefficients, signature (0,1,1).

Closely related to A182097.
Cf. A000931, bisection A109377.
Cf. A013998 (Unrestricted Perrin pseudoprimes).
Cf. A018187 (Restricted Perrin pseudoprimes).

a:=[3,0,2];; for n in [4..20] do a[n]:=a[n-2]+a[n-3]; od; a; # Muniru A Asiru, Jul 12 2018

a001608 n = a000931_list !! n
a001608_list = 3 : 0 : 2 : zipWith (+) a001608_list (tail a001608_list)
-- Reinhard Zumkeller, Feb 10 2011

I:=[3,0,2]; [n le 3 select I[n] else Self(n-2) +Self(n-3): n in [1..50]]; // G. C. Greubel, Mar 18 2019

A001608 :=proc(n) option remember; if n=0 then 3 elif n=1 then 0 elif n=2 then 2 else procname(n-2)+procname(n-3); fi; end proc;
[seq(A001608(n),n=0..50)]; # N. J. A. Sloane, May 24 2013

LinearRecurrence[{0, 1, 1}, {3, 0, 2}, 50] (* Harvey P. Dale, Jun 26 2011 *)
per = Solve[x^3 - x - 1 == 0, x]; f[n_] := Floor @ Re[N[ per[[1, -1, -1]]^n + per[[2, -1, -1]]^n + per[[3, -1, -1]]^n]]; Array[f, 46, 0] (* Robert G. Wilson v, Jun 29 2010 *)
a[n_] := n*Sum[Binomial[k, n-2*k]/k, {k, 1, n/2}]; a[0]=3; Table[a[n] , {n, 0, 45}] (* Jean-François Alcover, Oct 04 2012, after Vladimir Kruchinin *)
CoefficientList[Series[(3 - x^2)/(1 - x^2 - x^3), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 03 2015 *)
Table[RootSum[-1 - # + #^3 &, #^n &], {n, 0, 20}] (* Eric W. Weisstein, Mar 30 2017 *)
RootSum[-1 - # + #^3 &, #^Range[0, 20] &] (* Eric W. Weisstein, Dec 30 2017 *)

PARI
```
a(n)=if(n<0,0,polsym(x^3-x-1,n)[n+1])
```

A001608_list(n) = polsym(x^3-x-1,n) \\ Joerg Arndt, Mar 10 2019

A001608_list, a, b, c = [3, 0, 2], 3, 0, 2
for _ in range(100):
    a, b, c = b, c, a+b
    A001608_list.append(c) # Chai Wah Wu, Jan 27 2015

((3-x^2)/(1-x^2-x^3)).series(x, 50).coefficients(x, sparse=False) # G. C. Greubel, Mar 18 2019

G.f.: (3 - x^2)/(1 - x^2 - x^3). - Simon Plouffe in his 1992 dissertation
a(n) = r1^n + r2^n + r3^n where r1, r2, r3 are three roots of x^3-x-1=0.
a(n-1) + a(n) + a(n+1) = a(n+4), a(n) - a(n-1) = a(n-5). - Jon Perry, Jun 05 2003
From Gary W. Adamson, Feb 01 2004: (Start)
a(n) = trace(M^n) where M is the 3 X 3 matrix [0 1 0 / 0 0 1 / 1 1 0], the companion matrix of the characteristic polynomial of this sequence, P = X^3 - X - 1.
M^n * [3, 0, 2] = [a(n), a(n+1), a(n+2)]; e.g., M^7 * [3, 0, 2] = [7, 10, 12].
a(n) = 2*A000931(n+3) + A000931(n). (End)
a(n) = 3*p(n) - p(n-2) = 2*p(n) + p(n-3), with p(n) := A000931(n+3), n >= 0. - Wolfdieter Lang, Jun 21 2010
From Francesco Daddi, Aug 03 2011: (Start)
  a(0) + a(1) + a(2) + ... + a(n) = a(n+5) - 2.
  a(0) + a(2) + a(4) + ... + a(2*n) = a(2*n+3).
  a(1) + a(3) + a(5) + ... + a(2*n+1) = a(2*n+4) - 2. (End)
From Francesco Daddi, Aug 04 2011: (Start)
  a(0) + a(3) + a(6) + a(9) + ... + a(3*n) = a(3*n+2) + 1.
  a(0) + a(5) + a(10) + a(15) + ... + a(5*n) = a(5*n+1)+3.
  a(0) + a(7) + a(14) + a(21) + ... + a(7*n) = (a(7*n) + a(7*n+1) + 3)/2. (End)
a(n) = n*Sum_{k=1..floor(n/2)} binomial(k,n-2*k)/k, n > 0, a(0)=3. - Vladimir Kruchinin, Oct 21 2011
(a(n)^3)/2 + a(3n) - 3*a(n)*a(2n)/2 - 3 = 0. - Richard Turk, Apr 26 2017
2*a(4n) - 2*a(n) - 2*a(n)*a(3n) - a(2n)^2 + a(n)^2*a(2n) = 0. - Richard Turk, May 02 2017
a(n)^4 + 6*a(4n) - 4*a(3n)*a(n) - 3*a(2n)^2 - 12a(n) = 0. - Richard Turk, May 02 2017
a(n+5)^2 + a(n+1)^2 - a(n)^2 = a(2*(n+5)) + a(2*(n+1)) - a(2*n). - Aleksander Bosek, Mar 04 2019
From Aleksander Bosek, Mar 18 2019: (Start)
a(n+12) = a(n) + 2*a(n+4)  +   a(n+11);
a(n+16) = a(n) + 4*a(n+9)  +   a(n+13);
a(n+18) = a(n) + 2*a(n+6)  + 5*a(n+12);
a(n+21) = a(n) + 2*a(n+12) + 6*a(n+14);
a(n+27) = a(n) + 3*a(n+9)  + 4*a(n+22). (End)
a(n) = Sum_{j=0..floor((n-g)/(2*g))} 2*n/(n-2*(g-2)*j-(g-2)) * Hypergeometric2F1([-(n-2g*j-g)/2, -(2j+1)], [1], 1), g = 3 and n an odd integer. - Richard Turk, Oct 14 2019
E.g.f.: exp(r1*x) + exp(r2*x) + exp(r3*x), where r1, r2, r3 are three roots of x^3 - x - 1 = 0. - Fabian Pereyra, Nov 02 2024

Additional comments from Mike Baker, Oct 11 2005
Definition edited by Chai Wah Wu, Jan 27 2015
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

A018187 Restricted Perrin pseudoprimes.

Original entry on oeis.org

27664033, 46672291, 102690901, 130944133, 517697641, 545670533, 801123451, 855073301, 970355431, 1235188597, 3273820903, 3841324339, 3924969689, 4982970241, 5130186571, 5242624003, 6335800411, 7045248121

Offset: 1

R. K. Guy

nonn

From Dana Jacobsen, Aug 03 2016: (Start)
These are the "minimal restricted" Perrin pseudoprimes.  They meet conditions (4) and (5) from Adams and Shanks (1982), equivalent to condition (7) from Kurtz et al. (1986).  That is, A(n) = 0 mod p and A(-n) = -1 mod p.  Kurtz et al. call this the "minimal test", Wagon (1999) calls this the "strong Perrin test".
Further restrictions (Adams and Shanks, Arno / Grantham) lead to subsets of this sequence.
Kurtz et al. (1986) state that all acceptables (numbers where A(n) = 0 mod p and A(-n) = -1 mod p) <= 50*10^9 have S-type signatures.  The first example where this does not hold is 16043638781521, which does not have an S-signature (nor an I- or Q-type signature).
The first example of a pseudoprime in this sequence that does not pass the Adams/Shanks signature test is 167385219121, with an S-signature but the wrong Jacobi symbol.
Some sources have conjectured the restricted Perrin pseudoprimes can be derived from the unrestricted Perrin pseudoprimes by checking if { M=[0,1,0; 0,0,1; 1,1,0]; Mod(M,n) == Mod(M,n)^n }. Counterexamples include 52437986833, 60518537641, 364573433665, and 4094040693601. (End)

S. Wagon, Mathematica in action, 2nd ed., 1999, pp. 402 - 403 and Mathematica notebook for Chapter 18 in attached CD-ROM

Dana Jacobsen, Table of n, a(n) for n = 1..712
W. W. Adams and D. Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), 255-300.
Jon Grantham, There are infinitely many Perrin pseudoprimes, J. Number Theory 130 (2010) 1117-1128.
Dana Jacobsen, Perrin Primality Tests.
G. C. Kurtz, Daniel Shanks and H. C. Williams, Fast Primality Tests for Numbers < 50*10^9, Math. Comp., 46 (1986), 691-701.
Eric Weisstein's World of Mathematics, Perrin Pseudoprime.
Index entries for sequences related to pseudoprimes

Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes).

is(n) = { lift(trace(Mod([0,1,0; 0,0,1; 1,1,0],n)^n)) == 0 && lift(trace(Mod([0,1,0; 0,0,1; 1,0,-1],n)^n)) == n-1; }
forcomposite(n=1,1e8,is(n)&&print(n)) \\ Dana Jacobsen, Aug 03 2016

use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($,1); } 1e8; # _Dana Jacobsen, Aug 03 2016

A173656 Primes p such that p^2 divides P(p), where P = Perrin sequence A001608.

Original entry on oeis.org

521, 190699

Offset: 1

Arkadiusz Wesolowski, Aug 15 2012

It is not known if this sequence is infinite.
The squares are in A013998.
No other terms below 10^10. - Max Alekseyev, Aug 27 2023

			521 is in the sequence since its square 271441 is the factor of A001608(521).

G. L. Honaker, Jr. and Chris Caldwell, Prime Curios! 521
Wikipedia, Perrin number

Cf. A001608, A013998.

lst = {}; a = 3; b = 0; c = 2; Do[P = b + a; If[PrimeQ[n] && Divisible[P, n^2], AppendTo[lst, n]]; a = b; b = c; c = P, {n, 3, 2*10^5}]; lst
lst = {}; PowerMod2[mat_, n_, m_] := Mod[Fold[Mod[If[#2 == 1, #1.#1.mat, #1.#1], m] &, mat, Rest@IntegerDigits[n, 2]], m]; LinearRecurrence2[coeffs_, init_, n_, m_] := Mod[First@PowerMod2[Append[RotateRight /@ Most@IdentityMatrix@Length[coeffs], coeffs], n, m].init, m] /; n >= Length[coeffs]; Do[n = Power[p, 2]; If[PrimeQ[p] && LinearRecurrence2[{1, 1, 0}, {3, 0, 2}, n, n] == 0, AppendTo[lst, p]], {p, 1, 2*10^5, 2}]; lst

/* Assuming b13998 containing second column of b013998.txt */
A013998 = readvec(b13998);
for (k=1,#A013998,if (issquare(A013998[k])==1,print(k," ",A013998[k])));
/* Hugo Pfoertner, Sep 01 2017 */

A215339 a(n) = A001608(n) mod n.

Original entry on oeis.org

0, 0, 0, 2, 0, 5, 0, 2, 3, 7, 0, 5, 0, 9, 8, 10, 0, 14, 0, 17, 10, 2, 0, 13, 5, 15, 12, 23, 0, 20, 0, 26, 25, 19, 12, 2, 0, 21, 3, 5, 0, 33, 0, 2, 32, 2, 0, 21, 7, 42, 20, 41, 0, 23, 27, 3, 41, 2, 0, 34, 0, 33, 61, 26, 44, 27, 0, 53, 26, 31, 0, 34, 0, 2, 68, 21, 29, 18, 0, 5, 39, 43, 0, 71, 39, 2, 3, 10, 0, 83, 46, 2, 65, 49

Offset: 1

Joerg Arndt, Aug 16 2012

nonn

a(n) = 0 for n=1, n a prime, or n a Perrin pseudoprime (A013998).

Seiichi Manyama, Table of n, a(n) for n = 1..10000 (terms 1..1001 from Joerg Arndt)

Cf. A001608 (Perrin sequence), A013998 (Perrin pseudoprimes).

M = [0, 1, 0; 0, 0, 1; 1, 1, 0];
a(n)=lift( trace( Mod(M,n)^n ) );
vector(66,n,a(n))

A075764 Schroeder pseudoprimes: Composites k that divide the k-th Schroeder number A001003(k-1).

Original entry on oeis.org

105, 261, 301, 693, 1605, 1755, 2151, 2905, 2907, 3393, 3875, 4641, 4833, 5005, 5655, 6279, 6913, 7161, 8883, 9405, 10899, 11025, 11289, 15687, 17199, 19203, 22275, 27387, 36855, 37791, 50007, 50463, 53493, 54891, 55209, 55755, 63327, 64337

Offset: 1

Benoit Cloitre, Oct 09 2002

nonn

			105 is a term because A001003(105) = 15646506064359350392347086201481965698808674470977505246623827696393838448345 which is divisible by 105.
105 is a term because A001003(104) = 15646506064359350392347086201481965698808674470977505246623827696393838448345 which is divisible by 105.

Amiram Eldar, Table of n, a(n) for n = 1..422

Intersection of A002808 and A075763.

Cf. A001003, A013998, A075762.

s = {}; k1 = k2 = 1; Do[k3 = ((6*n - 9)*k2 - (n - 3)*k1)/n; If[CompositeQ[n] && Divisible[k3, n], AppendTo[s, n]]; k1 = k2; k2 = k3, {n, 3, 10^5}]; s (* Amiram Eldar, Jun 28 2022 *)

x1 = 1; x2 = 1; for (n = 3, 100000, x = (3*(2*n - 3)*x1 - (n - 3)*x2)/n; if (!isprime(n), if (!(x%n), print(n))); x2 = x1; x1 = x); \\ David Wasserman, Feb 23 2005

More terms from David Wasserman, Feb 23 2005

A174625 Table T(n,k) with the coefficients of the polynomial P_n(x) = P_{n-1}(x) + x*P_{n-2}(x) + 1 in row n, by decreasing exponent of x.

Original entry on oeis.org

0, 2, 3, 2, 4, 5, 5, 2, 9, 6, 7, 14, 7, 2, 16, 20, 8, 9, 30, 27, 9, 2, 25, 50, 35, 10, 11, 55, 77, 44, 11, 2, 36, 105, 112, 54, 12, 13, 91, 182, 156, 65, 13, 2, 49, 196, 294, 210, 77, 14, 15, 140, 378, 450, 275, 90, 15, 2, 64, 336, 672, 660, 352, 104, 16, 17, 204, 714, 1122, 935, 442

Offset: 1

Vladimir Shevelev, Mar 24 2010

The polynomials are defined by the recurrence starting with P_1(x)=0, P_2(x)=2.
The degree of the polynomial (row length minus 1) is A004526(n-2).
All coefficients of P_n are multiples of n iff n is prime.
Apparently a mirrored version of A157000. [R. J. Mathar, Nov 01 2010]

			The table starts
0; # 0
2; # 2
3; # 3
2,4; # 4+2*x
5,5; # 5+5*x
2,9,6; # 6+9*x+2*x^2
7,14,7; # 7+14*x+7*x^2
2,16,20,8; # 8+20*x+16*x^2+2*x^3
9,30,27,9; # 9+27*x+30*x^2+9*x^3
2,25,50,35,10; # 10+35*x+50*x^2+25*x^3+2*x^4
11,55,77,44,11; # 11+44*x+77*x^2+55*x^3+11*x^4

Cf. A018187, A013998, A174531.

p[0]:=0 p[1]:=2; p[n_]:=p[n]=Expand[p[n-1] +x p[n-2]+1]; Flatten[{0, Map[Reverse[CoefficientList[#,x]]&, Table[Expand[p[n]], {n,0,20}]]}] (* Peter J. C. Moses, Aug 18 2013 *)

Definition rephrased, sequence extended, keyword:tabf, examples added R. J. Mathar, Nov 01 2010

A225876 Composite n which divide s(n)+1, where s is the linear recurrence sequence s(n) = -s(n-1) + s(n-2) - s(n-3) + s(n-5) with initial terms (5, -1, 3, -7, 11).

Original entry on oeis.org

4, 14791044, 143014853, 253149265, 490434564, 600606332, 993861182, 3279563483

Offset: 1

Matt McIrvin, May 23 2013

The pseudoprimes derived from the fifth-order linear recurrence A225984(n) are analogous to the Perrin pseudoprimes A013998, and the Lucas pseudoprimes A005845.
For prime p, A225984(p) == p - 1 (mod p). The pseudoprimes are composite numbers satisfying the same relation. 4 = 2^2; 14791044 = 2^2 * 3 * 19 * 29 * 2237; 143014853 = 907 * 157679.
Like the Perrin test, the modular sequence is periodic so simple pre-tests can be performed.  Numbers divisible by 2, 3, 4, 5, 9, and 25 have periods 31, 11, 62, 24, 33, and 120 respectively. - Dana Jacobsen, Aug 29 2016
a(9) > 1.4*10^11. - Dana Jacobsen, Aug 29 2016

			A225984(4) = 11, and 11 == 3 (mod 4). Since 4 is composite, it is a pseudoprime with respect to A225984.

K. Brown, Proof of Generalized Little Theorem of Fermat, proves that for prime p, a(p) == a(1) (mod p) for recurrences of the form of A225984.
R. Holmes, comments to M. McIrvin's post on Google+ (found terms 4 through 7)

N=10^10;
default(primelimit, N);
M = [0, 1, 0, 0, 0; 0, 0, 1, 0, 0; 0, 0, 0, 1, 0; 0, 0, 0, 0, 1; 1, 0, -1, 1, -1];
a(n)=lift( trace( Mod(M, n)^n ) );
ta(n)=lift( trace( Mod(M, n) ) );
{ for (n=2, N,
    if ( isprime(n), next() );
    if ( a(n)==ta(n), print1(n, ", "); );
); }
/* Matt McIrvin, after Joerg Arndt's program for A013998, May 23 2013 */

Terms 4 through 7 found by Richard Holmes, added by Matt McIrvin, May 27 2013

a(8) from Dana Jacobsen, Aug 29 2016

A275612 Restricted Perrin pseudoprimes (Adams and Shanks definition).

Original entry on oeis.org

Offset: 1

Dana Jacobsen, Aug 03 2016

nonn

These are composites which have an acceptable signature mod n for the Perrin sequence (A001608).  See Adams and Shanks (1982), page 261.
They add additional conditions to the unrestricted Perrin test (A013998) and the minimal restricted test (A018187).
The quadratic form restriction for the I-signature (equation 29 in Adams and Shanks (1982)) is sometimes removed.  No pseudoprimes are currently known that match the I-signature congruences.  Adams and Shanks note that objections could be raised to its inclusion in the test, and Arno (1991) and Grantham (2000) both drop it.
Kurtz et al. (1986) call these "acceptable composites for the Perrin sequence". - N. J. A. Sloane, Jul 28 2019

Dana Jacobsen, Table of n, a(n) for n = 1..706
W. W. Adams and D. Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), 255-300.
Steven Arno, A note on Perrin pseudoprimes, Math. Comp. 56 (1991), 371-376.
Jon Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), 873-891.
Jon Grantham, There are infinitely many Perrin pseudoprimes, J. Number Theory 130 (2010) 1117-1128.
Dana Jacobsen, Perrin Primality Tests.
G. C. Kurtz, Daniel Shanks and H. C. Williams, Fast Primality Tests for Numbers < 50*10^9, Math. Comp., 46 (1986), 691-701.

Cf. A001608 (Perrin sequence), A013998 (unrestricted Perrin pseudoprimes), A018187 (minimal restricted Perrin pseudoprimes)

perrin2(n) = {
  my(M,L,S,j,A,B,C,D);
  M=Mod( [0,1,0; 0,0,1; 1,1,0], n)^n;
  L=Mod( [0,1,0; 0,0,1; 1,0,-1], n)^n;
  S=[ 3*L[3,2]-L[3,3],   3*L[2,2]-L[2,3],   3*L[1,2]-L[1,3], \
      3*M[3,1]+2*M[3,3], 3*M[1,1]+2*M[1,3], 3*M[2,1]+2*M[2,3] ];
  if (S[5] != 0 || S[2] != n-1,return(0));
  j = kronecker(-23,n);
  if (j == -1, B=S[3];A=1+3*B-B^2;C=3*B^2-2; if(S[1]==A && S[3]==B && S[4]==B && S[6] == C && B != 3 && B^3-B==1, return(1), return(0)));
  if (S[1] == 1 && S[3] == 3 && S[4] == 3 && S[6] == 2, return(1));
  if (j == 1 && S[1] == 0 && S[6] == n-1 && S[3] != S[4] && S[3]+S[4] == n-3 && (S[3]-S[4])^2 == Mod(-23,n), return(1));
  return(0);
} \\ Dana Jacobsen, Aug 03 2016

use ntheory ":all"; foroddcomposites { say if is_perrin_pseudoprime($,2); } 1e8; # _Dana Jacobsen, Aug 03 2016

A078512 Carmichael numbers that are unrestricted Perrin pseudoprimes.

Original entry on oeis.org

7045248121, 7279379941, 24306384961, 43234580143, 52437986833, 60518537641, 80829302401, 118805562613, 144377609419, 165321688501, 167385219121, 254302215553, 364573433665, 575687567521, 588909469501, 652270080001, 2152302898747, 4094040693601, 6287912246305

Offset: 1

Lekraj Beedassy, Jan 06 2003

nonn

Intersection of A002997 and A013998.

Amiram Eldar, Table of n, a(n) for n = 1..765 (terms below 2^64)
Christian Holzbaur, The 150 Carmichael numbers out of 246683 up to 10^16 that are Perrin pseudoprimes (actually contains the correct number of terms: 108).
H. Li, T. MacHenry, Permanents and Determinants, Weighted Isobaric Polynomials, and Integer Sequences, J. Int. Seq. 16 (2013) #13.3.5, example 49.

Cf. A002997, A013998.

More terms from Amiram Eldar, Jun 28 2019

A178375 The greatest common prime divisor of A000032(n)-1 and A001608(n), or 1 if no such divisor exists.

Original entry on oeis.org

2, 3, 2, 5, 1, 7, 2, 3, 1, 11, 1, 13, 1, 1, 2, 17, 1, 19, 1, 1, 2, 23, 1, 5, 1, 3, 1, 29, 1, 31, 2, 7, 1, 3, 1, 37, 1, 7, 1, 41, 1, 43, 2, 1, 2, 47, 1, 7, 2, 1, 3, 53, 1, 7, 1, 1, 2, 59, 1, 61, 1, 1, 2, 7, 1, 67, 3, 1, 1, 71, 1, 73, 2, 1, 1, 5, 1, 79, 1, 7, 1, 83, 1, 2, 2, 7, 2, 89, 1

Offset: 2

Vladimir Shevelev, May 26 2010

nonn

If n is prime, then n divides c(n). If n is composite and divides c(n) it is a pseudoprime to both the Lucas (Bruckman) and Perrin tests, which is the intersection of A005845 and A013998.

Conjecture: Records of the sequence are consecutive primes.

Cf. A000032, A001608, A178380, A005845, A013998.

More terms from R. J. Mathar, Aug 08 2010

cp's OEIS Frontend

A001608 Perrin sequence (or Ondrej Such sequence): a(n) = a(n-2) + a(n-3) with a(0) = 3, a(1) = 0, a(2) = 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A018187 Restricted Perrin pseudoprimes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Perl

A173656 Primes p such that p^2 divides P(p), where P = Perrin sequence A001608.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A215339 a(n) = A001608(n) mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A075764 Schroeder pseudoprimes: Composites k that divide the k-th Schroeder number A001003(k-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A174625 Table T(n,k) with the coefficients of the polynomial P_n(x) = P_{n-1}(x) + x*P_{n-2}(x) + 1 in row n, by decreasing exponent of x.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A225876 Composite n which divide s(n)+1, where s is the linear recurrence sequence s(n) = -s(n-1) + s(n-2) - s(n-3) + s(n-5) with initial terms (5, -1, 3, -7, 11).

Views

Author

Keywords

Comments

Examples