%I A001608 M0429 N0163
%S A001608 3,0,2,3,2,5,5,7,10,12,17,22,29,39,51,68,90,119,158,209,277,367,486,
%T A001608 644,853,1130,1497,1983,2627,3480,4610,6107,8090,10717,14197,18807,
%U A001608 24914,33004,43721,57918,76725,101639,134643,178364,236282,313007
%N A001608 Perrin sequence (or Ondrej Such sequence): a(n) = a(n-2) + a(n-3).
%C A001608 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 A001608 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 (ralf(AT)ark.in-berlin.de), Dec 13 2002
%C A001608 The recursion can be used to compute a(-n). The result is -A078712(n). 
               - T. D. Noe (noe(AT)sspectra.com), Oct 10 2006
%C A001608 For n>=3, a(n) is the number of maximal independent sets in a cycle of 
               order n. - Vince Vatter (vatter(AT)gmail.com), Oct 24 2006
%C A001608 M^n * [3, 0, 2] = [a(n), a(n+1), a(n+2)]; e.g., M^7 * [3, 0, 2] = [7, 
               10, 12]. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Nov 30 2007
%D A001608 W. W. Adams and D. Shanks, Strong primality tests that are not sufficient, 
               Math. Comp. 39 (1982), 255-300.
%D A001608 J. Chick, Problem 81G, Math. Gazette, vol. 81 p. 304, 1997.
%D A001608 E. B. Escott, Problem 151, Amer. Math. Monthly, 15 (1908), 209.
%D A001608 D. C. Fielder, Special integer sequences controlled by three parameters. 
               Fibonacci Quart 6 1968 64-70.
%D A001608 S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.2.
%D A001608 Z. Furedi, The number of maximal independent sets in connected graphs, 
               J. Graph Theory 11 (1987), 463-470.
%D A001608 D. Jarden, Recurring Sequences. Riveon Lematematika, Jerusalem, 1966.
%D A001608 R. Perrin, Query 1484, L'Interm\'{e}diaire des Math\'{e}maticiens, 6 
               (1899), 76.
%D A001608 Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 
               70.
%D A001608 M. Schroeder, Number Theory..., 3rd ed., Springer, 1997.
%D A001608 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A001608 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A001608 I. Stewart, Math. Rec., Scientific American, #6, 1996 p 103.
%D A001608 Ondrej Such, An Insufficient Condition for Primality, Problem 10268, 
               Amer. Math. Monthly, 102 (1995), 557-558; 103 (1996), 911.
%H A001608 T. D. Noe, <a href="b001608.txt">Table of n, a(n) for n=0..1000</a>
%H A001608 Bill Amend, <a href="a001608.gif">"Foxtrot" cartoon, Oct 11, 2005</a> 
               (Illustration of initial terms! From www.ucomics.com/foxtrot/.)
%H A001608 K. S. Brown, <a href="http://www.mathpages.com/home/kmath345.htm">Perrin's 
               Sequence</a>
%H A001608 C. Holzbaur, <a href="http://ftp.ai.univie.ac.at/perrin.html">Perrin 
               pseudoprimes</a>
%H A001608 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">
               Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures</
               a>, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 
               1992.
%H A001608 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">
               1031 Generating Functions and Conjectures</a>, Universit\'{e} du 
               Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
%H A001608 I. Stewart, <a href="http://www.fortunecity.com/emachines/e11/86/padovan.html">
               Tales of a Neglected Number</a>
%H A001608 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               PerrinPseudoprime.html">Link to a section of The World of Mathematics.</
               a>
%H A001608 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               PerrinSequence.html">Link to a section of The World of Mathematics.</
               a>
%H A001608 Willem's Fibonacci site, <a href="http://home.zonnet.nl/LeonardEuler/
               fibonacci1de.htm">Perrin and Fibonacci</a>
%H A001608 Wikipedia, <a href="http://en.wikipedia.org/wiki/Perrin_pseudoprime">
               Perrin pseudoprime</a>
%H A001608 <a href="Sindx_Rea.html#recLCC">Index entries for sequences related to 
               linear recurrences with constant coefficients</a>
%F A001608 G.f.: (3 - x^2)/(1 - x^2 - x^3).
%F A001608 a(n)=r1^n+r2^n+r3^n where r1, r2, r3 are three roots of x^3-x-1=0.
%F A001608 a(n-1)+a(n)+a(n+1)=a(n+4), a(n)-a(n-1)=a(n-5). - Jon Perry (perry(AT)globalnet.co.uk), 
               Jun 05 2003
%F A001608 a(n) = the trace of M^n where M = the 3 X 3 matrix [0 1 0 / 0 0 1 / 1 
               1 0]. 2. a(n) = 2*A000931(n+3) + A000931(n) E.g. a(10) = 17 = (3 
               + 7 + 7) = trace of M^10. - Gary W. Adamson (qntmpkt(AT)yahoo.com), 
               Feb 01 2004
%p A001608 A001608:=-z*(2+3*z)/(-1+z**2+z**3); [S. Plouffe in his 1992 dissertation.]
%o A001608 (PARI) a(n)=if(n<0,0,polsym(x^3-x-1,n)[n+1])
%Y A001608 Cf. A000931.
%Y A001608 Sequence in context: A032531 A143394 A112455 this_sequence A159977 A112974 
               A113069
%Y A001608 Adjacent sequences: A001605 A001606 A001607 this_sequence A001609 A001610 
               A001611
%K A001608 nonn,easy,nice
%O A001608 0,1
%A A001608 N. J. A. Sloane (njas(AT)research.att.com).
%E A001608 More terms from Jon Perry (perry(AT)globalnet.co.uk), Jun 05 2003
%E A001608 Additional comments from Mike Baker, Oct 11, 2005