login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001608 Perrin sequence (or Ondrej Such sequence): a(n) = a(n-2) + a(n-3).
(Formerly M0429 N0163)
47
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; text; internal format)
OFFSET

0,1

COMMENTS

Has been called the skiponacci sequence or skiponacci numbers. - N. J. A. Sloane, May 24 2013

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

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, Nov 30 2007

Pisano period lengths: 1, 7, 13, 14, 24, 91, 48, 28, 39, 168, 120, 182, 183, 336, 312, 56, 288, 273, 180, 168,... - 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 hold true: 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, remember that a(-k) = -A078712(k) and the formula (5.40) from Witula-Slota's paper is used. (End)

The sequence of parity 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

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.

D. Fomin, On the properties of a certain recursive sequence, Mathematics and Informatics Quarterly, 3 (1993), 50-53.

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.

I. E. Leonard and A. C. F. Liu, A familiar recurrence occurs again, Amer. Math. Monthly, 119 (2012), 333-336.

G. Minton, Three approaches to a sequence problem, Math. Mag., 84 (2011), 33-37.

Minton, Gregory T., Linear recurrence sequences satisfying congruence conditions. Proc. Amer. Math. Soc. 142 (2014), no. 7, 2337--2352. MR3195758.

B. H. Neumann and L. G. Wilson, Some Sequences like Fibonacci's, Fibonacci Quart., 17(1), 1979, p. 83.

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.

R. Tudoran, Problem 653, College Math. J., 31 (2000), 223-224.

S. Wagon, Letter to the Editor, Math. Mag., 84 (2011), 119.

M. Waldschmidt, Lectures on Multiple Zeta Values (IMSC 2011), http://www.math.jussieu.fr/~miw/articles/pdf/MZV2011IMSc.pdf

R. Witula, D. Slota, Conjugate sequences in Fibonacci-Lucas sense and some identities for sums of powers of their elements, Integers, 7 (2007), #A08.

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. Jakubec, K. Nemoga, On a conjecture concerning sequences of the third order, Mathematica Slovaca, Vol. 36 (1986), No. 1, 85--89.

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, ArXiv 1011.3930. - N. J. A. Sloane, Jul 07 2012

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

J. Shallit, J. P. Yamron, On linear recurrences and divisibility by primes, Fib. Quart. 22 (4) (1984) 366.

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, 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, 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. - 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..n/2, binomial(k,n-2*k)/k),n>0, a(0)=3. - Vladimir Kruchinin, Oct 21 2011

EXAMPLE

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 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)

MAPLE

A001608:=-z*(2+3*z)/(-1+z**2+z**3); [Simon 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; [Francesco Daddi, Aug 04 2011]

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

MATHEMATICA

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 *)

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

Closely related to A182097.

Cf. A000931, bisection A109377.

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

EXTENSIONS

More terms from Jon Perry, Jun 05 2003

Additional comments from Mike Baker, Oct 11 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 27 01:09 EST 2014. Contains 250152 sequences.