The integer sequence defined by the recurrence relation

(1)

with the initial conditions . This is the same recurrence relation as for the Perrin sequence, but with different initial conditions.

The recurrence relation can be solved explicitly, giving

(2)

where  is the th root of

(3)

Another form of the solution is

(4)

where  is the th root of

(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 ,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  by E. W. Weisstein (Apr. 10, 2011), and the following table summarizes the largest known values.

	decimal digits	discoverer
536485	65518	E. W. Weisstein (May 16, 2009)
727734	88874	E. W. Weisstein (Apr. 7, 2011)

The ratio

(6)

where  denotes a polynomial root, is called the plastic constant.

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

(7)

the powers of  give

(8)

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

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.