[go: up one dir, main page]

TOPICS
Search

Padovan Sequence


The integer sequence defined by the recurrence relation

 P(n)=P(n-2)+P(n-3)
(1)

with the initial conditions P(0)=P(1)=P(2)=1. This is the same recurrence relation as for the Perrin sequence, but with different initial conditions.

The recurrence relation can be solved explicitly, giving

 P(n)=(1+r_1)/(r_1^(n+2)(2+3r_1))+(1+r_2)/(r_2^(n+2)(2+3r_2))+(1+r_3)/(r_3^(n+2)(2+3r_3)),
(2)

where r_n is the nth root of

 x^3+x^2-1=0.
(3)

Another form of the solution is

 P(n)=((r_2-1)(r_3-1)r_1^n)/((r_1-r_2)(r_1-r_3))+((r_1-1)(r_3-1)r_2^n)/((r_2-r_1)(r_2-r_3)) 
 +((r_1-1)(r_2-1)r_3^n)/((r_1-r_3)(r_2-r_3)),
(4)

where r_n is the nth root of

 x^3-x-1=0.
(5)

The first few terms are 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, ... (OEIS A000931).

The first few prime Padovan numbers are 2, 2, 3, 5, 7, 37, 151, 3329, 23833, ... (OEIS A100891), corresponding to indices n=3,3, 4, 5, 7, 8, 14, 19, 30, 37, 84, 128, 469, 666, 1262, 1573, 2003, 2210, 2289, 4163, 5553, 6567, 8561, 11230, 18737, 35834, 44259, 536485, ... (OEIS A112882). The search for prime numerators has been completed up to 729586 by E. W. Weisstein (Apr. 10, 2011), and the following table summarizes the largest known values.

ndecimal digitsdiscoverer
53648565518E. W. Weisstein (May 16, 2009)
72773488874E. W. Weisstein (Apr. 7, 2011)

The ratio

 lim_(n->infty)(P(n))/(P(n-1))=(x^3-x^2-1)_1,
(6)

where (P(x))_n denotes a polynomial root, is called the plastic constant.

A matrix analogous to the Fibonacci Q-matrix exists for Padovan numbers. Defining

 Q=[0 1 0; 0 0 1; 1 1 0],
(7)

the powers of Q give

 Q^n=[P(n-5) P(n-3) P(n-4); P(n-4) P(n-2) P(n-3); P(n-3) P(n-1) P(n-2)]
(8)

(J. Lien, pers. comm., Mar. 11, 2005).


See also

Integer Sequence Primes, Perrin Sequence, Plastic Constant

Explore with Wolfram|Alpha

References

Sloane, N. J. A. Sequences A000931/M0284, A100891, and A112882 in "The On-Line Encyclopedia of Integer Sequences."Stewart, I. "Tales of a Neglected Number." Sci. Amer. 274, 102-103, June 1996.

Referenced on Wolfram|Alpha

Padovan Sequence

Cite this as:

Weisstein, Eric W. "Padovan Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PadovanSequence.html

Subject classifications