|
| |
|
|
A001608
|
|
Perrin sequence (or Ondrej Such sequence): a(n) = a(n-2) + a(n-3).
(Formerly M0429 N0163)
|
|
42
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,1
|
|
|
COMMENTS
| 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 (ralf(AT)ark.in-berlin.de), Dec 13 2002
The recursion can be used to compute a(-n). The result is -A078712(n). - T. D. Noe (noe(AT)sspectra.com), Oct 10 2006
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
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
|
|
|
REFERENCES
| W. W. Adams and D. Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), 255-300.
J. Chick, Problem 81G, Math. Gazette, vol. 81 p. 304, 1997.
E. B. Escott, Problem 151, Amer. Math. Monthly, 15 (1908), 209.
D. C. Fielder, Special integer sequences controlled by three parameters. Fibonacci Quart 6 1968 64-70.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.2.
Z. Furedi, The number of maximal independent sets in connected graphs, J. Graph Theory 11 (1987), 463-470.
D. Jarden, Recurring Sequences. Riveon Lematematika, Jerusalem, 1966.
R. Perrin, Query 1484, L'Interm\'{e}diaire des Math\'{e}maticiens, 6 (1899), 76.
Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 70.
M. Schroeder, Number Theory..., 3rd ed., Springer, 1997.
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).
I. Stewart, Math. Rec., Scientific American, #6, 1996 p 103.
Ondrej Such, An Insufficient Condition for Primality, Problem 10268, Amer. Math. Monthly, 102 (1995), 557-558; 103 (1996), 911.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..1000
Bill Amend, "Foxtrot" cartoon, Oct 11, 2005 (Illustration of initial terms! From www.ucomics.com/foxtrot/.)
K. S. Brown, Perrin's Sequence
C. Holzbaur, Perrin pseudoprimes
S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
I. Stewart, Tales of a Neglected Number
Eric Weisstein's World of Mathematics, Perrin Pseudoprime
Eric Weisstein's World of Mathematics, Perrin Sequence
Willem's Fibonacci site, Perrin and Fibonacci
Wikipedia, Perrin pseudoprime
Index to sequences with linear recurrences with constant coefficients, signature (0,1,1).
|
|
|
FORMULA
| G.f.: (3 - x^2)/(1 - x^2 - x^3).
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 (perry(AT)globalnet.co.uk), Jun 05 2003
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
a(n)= 3*p(n)- p(n-2) = 2*p(n) + p(n-3), with p(n):=A000931(n+3), n>=0. [From Wolfdieter Lang, Jun 21 2010]
Contribution 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)
Contribution 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..n/2, binomial(k,n-2*k)/k),n>0, a(0)=3. [ From Vladimir Kruchinin, Oct 21 2011]
|
|
|
MAPLE
| A001608:=-z*(2+3*z)/(-1+z**2+z**3); [S. Plouffe in his 1992 dissertation.]
a[0]:=3; a[1]:=0; a[2]:=2; for n from 3 to 50 do a[n]:=a[n-2]+a[n-3]; end do; [From Francesco Daddi, Aug 04 2011]
|
|
|
MATHEMATICA
| LinearRecurrence[{0, 1, 1}, {3, 0, 2}, 50] (* From Harvey P. Dale, June 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] (* From Robert G. Wilson v (rgwv(AT)rgwv.com), Jun 29 2010 *)
|
|
|
PROG
| (PARI) a(n)=if(n<0, 0, polsym(x^3-x-1, n)[n+1])
(Haskell)
a001608 n = a000931_list !! n
a001608_list = 3 : 0 : 2 : zipWith (+) a001608_list (tail a001608_list)
-- Reinhard Zumkeller, Feb 10 2011
|
|
|
CROSSREFS
| Cf. A000931.
Sequence in context: A032531 A143394 A112455 * A159977 A177461 A201924
Adjacent sequences: A001605 A001606 A001607 * A001609 A001610 A001611
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Jon Perry (perry(AT)globalnet.co.uk), Jun 05 2003
Additional comments from Mike Baker, Oct 11, 2005
|
| |
|
|
