|
%I M0429 N0163 #420 Apr 10 2024 09:19:31
%S 3,0,2,3,2,5,5,7,10,12,17,22,29,39,51,68,90,119,158,209,277,367,486,
%T 644,853,1130,1497,1983,2627,3480,4610,6107,8090,10717,14197,18807,
%U 24914,33004,43721,57918,76725,101639,134643,178364,236282,313007
%N Perrin sequence (or Ondrej Such sequence): a(n) = a(n-2) + a(n-3) with a(0) = 3, a(1) = 0, a(2) = 2.
%C Has been called the skiponacci sequence or skiponacci numbers. - _N. J. A. Sloane_, May 24 2013
%C 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
%C 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.
%C 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
%C The recursion can be used to compute a(-n). The result is -A078712(n). - _T. D. Noe_, Oct 10 2006
%C For n>=3, a(n) is the number of maximal independent sets in a cycle of order n. - _Vincent Vatter_, Oct 24 2006
%C Pisano period lengths are given in A104217. - _R. J. Mathar_, Aug 10 2012
%C From _Roman Witula_, Feb 01 2013: (Start)
%C 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
%C = 0 for n = 0, 1, 2,
%C = 6 for n = 3,
%C = 12*a(k) for n = 4,
%C = 10*[2*(a(k))^2 - a(-k)] for n = 5,
%C = 30*a(k)*[(a(k))^2 - a(-k)] for n = 6,
%C = 7*[6*(a(k))^4 - 9*a(-k)*(a(k))^2 + 2*(a(-k))^2 - a(k)] for n = 7,
%C = 56*a(k)*[((a(k))^2 - a(-k))^2 - a(k)/2] for n = 8,
%C where a(-k) = -A078712(k) and the formula (5.40) from the paper of Witula and Slota is used. (End)
%C 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
%C 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
%C 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
%C Also the number of minimal total dominating sets in the n-sun graph. - _Eric W. Weisstein_, Apr 27 2018
%C Named after the French engineer François Olivier Raoul Perrin (1841-1910). - _Amiram Eldar_, Jun 05 2021
%C a(p) = p*A127687(p) for p prime. - _Robert FERREOL_, Apr 09 2024
%D Olivier Bordellès, Thèmes d'Arithmétique, Ellipses, 2006, Exercice 4.11, p. 127.0
%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.2.
%D Dmitry Fomin, On the properties of a certain recursive sequence, Mathematics and Informatics Quarterly, Vol. 3 (1993), pp. 50-53.
%D Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 70.
%D Manfred Schroeder, Number Theory in Science and Communication, 3rd ed., Springer, 1997.
%D 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.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Indranil Ghosh, <a href="/A001608/b001608.txt">Table of n, a(n) for n = 0..8172</a> (terms 0..1000 from T. D. Noe)
%H William Adams and Daniel Shanks, <a href="http://dx.doi.org/10.1090/S0025-5718-1982-0658231-9">Strong primality tests that are not sufficient</a>, Math. Comp., Vol. 39, No. 159 (1982), pp. 255-300.
%H Kouèssi Norbert Adédji, Japhet Odjoumani, and Alain Togbé, <a href="http://dml.cz/dmlcz/151790">Padovan and Perrin numbers as products of two generalized Lucas numbers</a>, Archivum Mathematicum, Vol. 59 (2023), No. 4, 315-337.
%H Bill Amend, <a href="/A001608/a001608.gif">"Foxtrot" cartoon, Oct 11, 2005</a> (Illustration of initial terms! From www.ucomics.com/foxtrot/.)
%H Herbert Batte, Taboka P. Chalebgwa and Mahadi Ddamulira, <a href="https://arxiv.org/abs/2105.08515">Perrin numbers that are concatenations of two distinct repdigits</a>, arXiv:2105.08515 [math.NT], 2021.
%H Daniel Birmajer, Juan B. Gil and Michael D. Weiner, <a href="http://arxiv.org/abs/1505.06339">Linear recurrence sequences with indices in arithmetic progression and their sums</a>, arXiv:1505.06339 [math.NT], 2015.
%H Eric Fernando Bravo, <a href="https://www.mathos.unios.hr/mc/index.php/mc/article/view/4733">On concatenations of Padovan and Perrin numbers</a>, Math. Commun. (2023) Vol 28, 105-119.
%H Kevin S. Brown, <a href="http://www.mathpages.com/home/kmath345/kmath345.htm">Perrin's Sequence</a>
%H J. Chick, <a href="http://www.jstor.org/stable/3619223">Problem 81G</a>, Math. Gazette, Vol. 81, No. 491 (1997), p. 304.
%H Tomislav Doslic and I. Zubac, <a href="http://amc-journal.eu/index.php/amc/article/view/851">Counting maximal matchings in linear polymers</a>, Ars Mathematica Contemporanea, Vol. 11 (2016), pp. 255-276.
%H Robert Dougherty-Bliss, <a href="https://arxiv.org/abs/2206.14852">The Meta-C-finite Ansatz</a>, arXiv preprint arXiv:2206.14852 [math.CO], 2022.
%H Robert Dougherty-Bliss, <a href="https://sites.math.rutgers.edu/~zeilberg/Theses/RobertDoughertyBlissThesis.pdf">Experimental Methods in Number Theory and Combinatorics</a>, Ph. D. Dissertation, Rutgers Univ. (2024). See p. 34.
%H Robert Dougherty-Bliss and Doron Zeilberger, <a href="https://arxiv.org/abs/2307.16069v1">Lots and Lots of Perrin-Type Primality Tests and Their Pseudo-Primes</a>, arXiv:2307.16069 [math.NT], 2023.
%H E. B. Escott, <a href="http://www.jstor.org/stable/2971527">Problem 151</a>, Amer. Math. Monthly, Vol. 15, No. 11 (1908), p. 209.
%H Daniel C. Fielder, <a href="http://www.fq.math.ca/Scanned/6-3/fielder.pdf">Special integer sequences controlled by three parameters</a>, Fibonacci Quarterly, Vol. 6 (1968), pp. 64-70.
%H Daniel C. Fielder, <a href="http://www.fq.math.ca/Scanned/6-3/errata.pdf">Errata:Special integer sequences controlled by three parameters</a>, Fibonacci Quarterly, Vol. 6 (1968), pp. 64-70.
%H Zoltán Furedi, <a href="https://doi.org/10.1002/jgt.3190110403">The number of maximal independent sets in connected graphs</a>, J. Graph Theory, Vol. 11, No. 4 (1987), pp. 463-470.
%H Bill Gasarch, <a href="http://blog.computationalcomplexity.org/2016/06/when-does-n-divide-in-this-sequence.html">When does n divide a_n in this sequence?</a> (2016).
%H A. Justin Gopinath and B. Nithya, <a href="https://doi.org/10.1016/j.comcom.2018.04.006">Mathematical and Simulation Analysis of Contention Resolution Mechanism for IEEE 802.11 ah Networks</a>, Computer Communications (2018) Vol. 124, 87-100.
%H Christian Holzbaur, <a href="/A013998/a013998.html">Perrin pseudoprimes</a> [Original link broke many years ago. This is a cached copy from the WayBack machine, dated Apr 24 2006]
%H Dmitry I. Ignatov, <a href="https://doi.org/10.1007/978-3-031-35949-1_11">On the Maximal Independence Polynomial of the Covering Graph of the Hypercube up to n = 6</a>, Int'l Conf. Formal Concept Analysis, 2023.
%H Stanislav Jakubec and Karol Nemoga, <a href="http://dml.cz/dmlcz/136415">On a conjecture concerning sequences of the third order</a>, Mathematica Slovaca, Vol. 36, No. 1 (1986), pp. 85-89.
%H Dov Jarden, <a href="/A001602/a001602.pdf">Recurring Sequences</a>, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 90.
%H Bir Kafle, Salah Eddine Rihane and Alain Togbé, <a href="https://doi.org/10.7546/nntdm.2021.27.1.171-187">A note on Mersenne Padovan and Perrin numbers</a>, Notes on Num. Theory and Disc. Math., Vol. 27, No. 1 (2021), pp. 161-170.
%H Vedran Krcadinac, <a href="http://www.fq.math.ca/Papers1/44-4/quartkrcadinac04_2006.pdf">A new generalization of the golden ratio</a>, Fibonacci Quart., Vol. 44, No. 4 (2006), pp. 335-340.
%H G. C. Kurtz, Daniel Shanks and H. C. Williams, <a href="https://doi.org/10.1090/S0025-5718-1986-0829639-7">Fast primality tests for numbers less than 50*10^9"</a>, Mathematics of Computation, Vol. 46, No. 174 (1986), pp. 691-701. [Studies primes in this sequence. - _N. J. A. Sloane_, Jul 28 2019]
%H I. E. Leonard and A. C. F. Liu, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.119.04.333">A familiar recurrence occurs again</a>, Amer. Math. Monthly, Vol. 119, No. 4 (2012), 333-336.
%H J. M. Luck and A. Mehta, <a href="http://doi.org/10.1103/PhysRevE.92.052810">Universality in survivor distributions: Characterising the winners of competitive dynamics</a>, Physical Review E, Vol. 92, No. 5 (2015), 052810; <a href="http://arxiv.org/abs/1511.04340">arXiv preprint</a>, arXiv:1511.04340 [q-bio.QM], 2015.
%H Matthew Macauley, Jon McCammond and Henning S. Mortveit, <a href="http://www.emis.de/journals/JACO/Volume33_1/hgv665924j44t770.html">Dynamics groups of asynchronous cellular automata</a>, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.
%H Gregory Minton, <a href="http://www.jstor.org/stable/10.4169/math.mag.84.1.033">Three approaches to a sequence problem</a>, Math. Mag., Vol. 84, No. 1 (2011), pp. 33-37.
%H Gregory T. Minton, <a href="http://dx.doi.org/10.1090/S0002-9939-2014-12168-X">Linear recurrence sequences satisfying congruence conditions</a>, Proc. Amer. Math. Soc., Vol. 142, No. 7 (2014), pp. 2337-2352. MR3195758.
%H B. H. Neumann and L. G. Wilson, <a href="http://www.fq.math.ca/Scanned/17-1/neumann.pdf">Some Sequences like Fibonacci's</a>, Fibonacci Quart., Vol. 17, No. 1 (1979), p. 83.
%H 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, <a href="http://dx.doi.org/10.1007/978-3-642-28332-1_37">DOI</a>; also on <a href="http://arxiv.org/abs/1011.3930">arXiv</a>, arXiv 1011.3930 [cs.DM], 2010.
%H Ahmet Öteleş, <a href="http://www.kurims.kyoto-u.ac.jp/EMIS/journals/ASUO/mathematics/anale2019vol2/06_oteles.pdf">Bipartite Graphs Associated with Pell, Mersenne and Perrin Numbers</a>, An. Şt. Univ. Ovidius Constantą, (2019) Vol. 27, Issue 2, 109-120.
%H R. Perrin, <a href="https://archive.org/details/lintermdiairede03lemogoog/page/n402">Query 1484</a>, L'Intermédiaire des Mathématiciens, Vol. 6 (1899), p. 76.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H Salah Eddine Rihane, Chèfiath Awero Adegbindin and Alain Togbé, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Togbe/togbe16.html">Fermat Padovan And Perrin Numbers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.6.2.
%H Salah Eddine Rihane and Alain Togbé, <a href="https://doi.org/10.1007/s40065-021-00317-1">Repdigits as products of consecutive Padovan or Perrin numbers</a>, Arab. J. Math. (2021).
%H David E. Rush, <a href="https://www.fq.math.ca/Papers1/50-4/Rush.pdf">Degree n Relatives of the Golden Ratio and Resultants of the Corresponding Polynomials</a>, Fibonacci Quart., Vol. 50, No. 4 (2012), pp. 313-325. See p. 318.
%H J. O. Shallit and J. P. Yamron, <a href="http://www.fq.math.ca/Scanned/22-4/shallit2.pdf">On linear recurrences and divisibility by primes</a>, Fibonacci Quart., Vol. 22, No. 4 (1984), p. 366.
%H Ian Stewart, <a href="https://www.jstor.org/stable/24989576">Tales of a Neglected Number</a>, Mathematical Recreations, Scientific American, Vol. 274, No. 6 (1996), pp. 102-103.
%H Ondrej Such, <a href="https://www.jstor.org/stable/2974777">An Insufficient Condition for Primality, Problem 10268</a>, Amer. Math. Monthly, Vol. 102, No. 6 (1995), pp. 557-558.
%H Ondrej Such, <a href="https://www.jstor.org/stable/2974627">An Insufficient Condition for Primality, Problem 10268</a>, Amer. Math. Monthly, Vol. 103, No. 10 (1996), p. 911.
%H Pagdame Tiebekabe and Kouèssi Norbert Adédji, <a href="https://www.researchgate.net/profile/Pagdame-Tiebekabe/publication/368642746_ON_PADOVAN_OR_PERRIN_NUMBERS_AS_PRODUCTS_OF_THREE_REPDIGITS_IN_BASE_delta/">On Padovan or Perrin numbers as products of three repdigits in base delta</a>, 2023.
%H Razvan Tudoran, <a href="http://www.jstor.org/stable/2687495">Problem 653</a>, College Math. J., Vol. 31, No. 3 (2000), pp. 223-224.
%H Vincent Vatter, <a href="https://doi.org/10.1080/10724117.2021.1940520">Social distancing, primes, and Perrin numbers</a>, Math Horiz., Vol. 29, No. 1, pp. 5-7.
%H Stan Wagon, <a href="http://www.jstor.org/stable/10.4169/math.mag.84.2.119">Letter to the Editor</a>, Math. Mag., Vol. 84, No. 2 (2011), p. 119.
%H Michel Waldschmidt, <a href="https://webusers.imj-prg.fr/~michel.waldschmidt/articles/pdf/MZV2011IMSc.pdf">Lectures on Multiple Zeta Values</a>, IMSC 2011.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CycleGraph.html">Cycle Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIndependentEdgeSet.html">Maximal Independent Edge Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalEdgeCover.html">Minimal Edge Cover</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerrinPseudoprime.html">Perrin Pseudoprime</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerrinSequence.html">Perrin Sequence</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SunGraph.html">Sun Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TotalDominatingSet.html">Total Dominating Set</a>
%H Willem's Fibonacci site, <a href="http://home.zonnet.nl/LeonardEuler/fibonacci1de.htm">Perrin and Fibonacci</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Perrin_number">Perrin Number</a>.
%H Roman Witula and Damian Slota, <a href="http://www.emis.de/journals/INTEGERS/papers/h8/h8.Abstract.html">Conjugate sequences in Fibonacci-Lucas sense and some identities for sums of powers of their elements</a>, Integers, Vol. 7 (2007), #A08.
%H Richard J. Yanco, <a href="/A007380/a007380.pdf">Letter and Email to N. J. A. Sloane, 1994</a>
%H Richard Yanco and Ansuman Bagchi, <a href="/A007380/a007380_1.pdf">K-th order maximal independent sets in path and cycle graphs</a>, Unpublished manuscript, 1994. (Annotated scanned copy)
%H Fatih Yilmaz and Durmus Bozkurt, <a href="https://doi.org/10.1016/j.jnt.2011.02.002">Hessenberg matrices and the Pell and Perrin numbers</a>, Journal of Number Theory, Volume 131, Issue 8 (August 2011), pp. 1390-1396. [The terms given in the paper contain a typo]
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,1).
%F G.f.: (3 - x^2)/(1 - x^2 - x^3). - _Simon Plouffe_ in his 1992 dissertation
%F a(n) = r1^n + r2^n + r3^n where r1, r2, r3 are three roots of x^3-x-1=0.
%F a(n-1) + a(n) + a(n+1) = a(n+4), a(n) - a(n-1) = a(n-5). - _Jon Perry_, Jun 05 2003
%F From _Gary W. Adamson_, Feb 01 2004: (Start)
%F 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.
%F M^n * [3, 0, 2] = [a(n), a(n+1), a(n+2)]; e.g., M^7 * [3, 0, 2] = [7, 10, 12].
%F a(n) = 2*A000931(n+3) + A000931(n). (End)
%F 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
%F From _Francesco Daddi_, Aug 03 2011: (Start)
%F a(0) + a(1) + a(2) + ... + a(n) = a(n+5) - 2.
%F a(0) + a(2) + a(4) + ... + a(2*n) = a(2*n+3).
%F a(1) + a(3) + a(5) + ... + a(2*n+1) = a(2*n+4) - 2. (End)
%F From _Francesco Daddi_, Aug 04 2011: (Start)
%F a(0) + a(3) + a(6) + a(9) + ... + a(3*n) = a(3*n+2) + 1.
%F a(0) + a(5) + a(10) + a(15) + ... + a(5*n) = a(5*n+1)+3.
%F a(0) + a(7) + a(14) + a(21) + ... + a(7*n) = (a(7*n) + a(7*n+1) + 3)/2. (End)
%F 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
%F (a(n)^3)/2 + a(3n) - 3*a(n)*a(2n)/2 - 3 = 0. - _Richard Turk_, Apr 26 2017
%F 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
%F a(n)^4 + 6*a(4n) - 4*a(3n)*a(n) - 3*a(2n)^2 - 12a(n) = 0. - _Richard Turk_, May 02 2017
%F 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
%F From _Aleksander Bosek_, Mar 18 2019: (Start)
%F a(n+12) = a(n) + 2*a(n+4) + a(n+11);
%F a(n+16) = a(n) + 4*a(n+9) + a(n+13);
%F a(n+18) = a(n) + 2*a(n+6) + 5*a(n+12);
%F a(n+21) = a(n) + 2*a(n+12) + 6*a(n+14);
%F a(n+27) = a(n) + 3*a(n+9) + 4*a(n+22). (End)
%F 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 From _Roman Witula_, Feb 01 2013: (Start)
%e We note that if a + b + c = 0 then:
%e 1) a^3 + b^3 + c^3 = 3*a*b*c,
%e 2) a^4 + b^4 + c^4 = 2*((a^2 + b^2 + c^2)/2)^2,
%e 3) (a^5 + b^5 + c^5)/5 = (a^3 + b^3 + c^3)/3 * (a^2 +
%e b^2 + c^2)/2,
%e 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,
%e 5) (a^7 + b^7 + c^7)/7 * (a^3 + b^3 + c^3)/3 = ((a^5 + b^5 + c^5)/5)^2.
%e 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)
%p 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;
%p [seq(A001608(n),n=0..50)]; # _N. J. A. Sloane_, May 24 2013
%t LinearRecurrence[{0, 1, 1}, {3, 0, 2}, 50] (* _Harvey P. Dale_, Jun 26 2011 *)
%t 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 *)
%t 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_ *)
%t CoefficientList[Series[(3 - x^2)/(1 - x^2 - x^3), {x, 0, 50}], x] (* _Vincenzo Librandi_, Jun 03 2015 *)
%t Table[RootSum[-1 - # + #^3 &, #^n &], {n, 0, 20}] (* _Eric W. Weisstein_, Mar 30 2017 *)
%t RootSum[-1 - # + #^3 &, #^Range[0, 20] &] (* _Eric W. Weisstein_, Dec 30 2017 *)
%o (PARI) a(n)=if(n<0,0,polsym(x^3-x-1,n)[n+1])
%o (PARI) A001608_list(n) = polsym(x^3-x-1,n) \\ _Joerg Arndt_, Mar 10 2019
%o (Haskell)
%o a001608 n = a000931_list !! n
%o a001608_list = 3 : 0 : 2 : zipWith (+) a001608_list (tail a001608_list)
%o -- _Reinhard Zumkeller_, Feb 10 2011
%o (Python)
%o A001608_list, a, b, c = [3, 0, 2], 3, 0, 2
%o for _ in range(100):
%o a, b, c = b, c, a+b
%o A001608_list.append(c) # _Chai Wah Wu_, Jan 27 2015
%o (GAP) 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
%o (Magma) 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
%o (Sage) ((3-x^2)/(1-x^2-x^3)).series(x, 50).coefficients(x, sparse=False) # _G. C. Greubel_, Mar 18 2019
%Y Closely related to A182097.
%Y Cf. A000931, bisection A109377.
%Y Cf. A013998 (Unrestricted Perrin pseudoprimes).
%Y Cf. A018187 (Restricted Perrin pseudoprimes).
%K nonn,easy,nice
%O 0,1
%A _N. J. A. Sloane_
%E Additional comments from Mike Baker, Oct 11 2005
%E Definition edited by _Chai Wah Wu_, Jan 27 2015
%E Deleted certain dangerous or potentially dangerous links. - _N. J. A. Sloane_, Jan 30 2021
| 