Padovan Sequence

Author

Eric W. Weisstein
August 3, 2017

This notebook downloaded from http://mathworld.wolfram.com/notebooks/IntegerSequences/PadovanSequence.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/PadovanSequence.html.

©2017 Wolfram Research, Inc. except for portions noted otherwise

RootSum

A000931

Table[((Root[-1-#1+((#1)^3)&,1])^n) Root[-1+4 #1+23 ((#1)^2)+23 ((#1)^3)&,1]+((Root[-1-#1+((#1)^3)&,3])^n) Root[-1+4 #1+23 ((#1)^2)+23 ((#1)^3)&,2]+((Root[-1-#1+((#1)^3)&,2])^n) Root[-1+4 #1+23 ((#1)^2)+23 ((#1)^3)&,3],{n,20}]//Round

f1=-1-#1+((#1)^3)&;
f2=-1+4 #1+23 ((#1)^2)+23 ((#1)^3)&;

an=ToNumberField[Root[f2,#],Root[f1,#/.{1->1,3->2,2->3}]]&/@Range[3]

coeffs=Last/@an

SameQ@@coeffs

rs=RootSum[-1-#1+#1^3&,#^n(-(11/23)+4/23#+5/23#^2)&]

Table[RootSum[-1-#+((#)^3)&,-11 ((#)^n)+4 ((#)^(n+1))+5 ((#)^(n+2))&]/23,{n,20}]

Difference Root

DifferenceRoot[Function[{P,n},{P[n]==P[n-2]+P[n-3],P[0]==1,P[1]==1,P[2]==1}]]

Table

PadovanNumber2/@Range[10]

PadovanNumber/@Range[10]

Recurrence

V4.2.1

<<DiscreteMath`RSolve`

soln=RSolve[{P[n]==P[n-2]+P[n-3],P[0]==P[1]==P[2]==1},P[n],n]

soln /. Root[-1+#1^2+((#1)^3)&,n_,__]:>Subscript[r,n]/.If[_,x_,_]:>x//TraditionalForm

FullSimplify[%]//TraditionalForm

r[n_]:=Root[-1+((#1)^2)+((#1)^3)&,n]
p[n_]:=((((r[1])^(-2-n)) (1+r[1]))/(2+3 r[1]))+((((r[2])^(-2-n)) (1+r[2]))/(2+3 r[2]))+((((r[3])^(-2-n)) (1+r[3]))/(2+3 r[3]))

RootReduce[Table[p[n],{n,10}]]

FullSimplify[p[n]/p[n-1]]//Timing

Limit[Last[%],n->∞]

V5.2

soln=RSolve[{P[n]==P[n-2]+P[n-3],P[0]==P[1]==P[2]==1},P[n],n]

soln/.Root[-1-#1+((#1)^3)&,n_,__] :>Subscript[r,n]//TraditionalForm

FullSimplify[%,n>1&&n∈Integers]//TraditionalForm

Cancel/@Apart/@(Apart//@%[[1,1,2]])//TraditionalForm

r[n_]:=Root[-1-#1+((#1)^3)&,n]
p[n_]:=((((r[1])^n) (-1+r[2]) (-1+r[3]))/((r[1]-r[2]) (r[1]-r[3])))-(((-1+r[1]) ((r[2])^n) (-1+r[3]))/((r[1]-r[2]) (r[2]-r[3])))+(((-1+r[1]) (-1+r[2]) ((r[3])^n))/((r[1]-r[3]) (r[2]-r[3])))

RootReduce[Table[p[n],{n,10}]]

(ratio=FullSimplify[p[n]/p[n-1]])//Timing

V7

PadovanNumber[20]

soln=RSolve[{P[n]==P[n-2]+P[n-3],P[0]==P[1]==P[2]==1},P[n],n]

Plastic Constant

ratio/.n->100.

Limit[ratio,n->∞]

ToRadicals[%]

N[%]

Primes

Select[Round[p/@Range[500]],PrimeQ]//Timing

(l=Block[{$MaxExtraPrecision=10^4},Position[Round[p/@Range[10^4]],_?PrimeQ]]//Flatten)//Timing

(l=Block[{$MaxExtraPrecision=10^4},10^4+Position[Round[p/@Range[10^4+1,2 10^4]],_?PrimeQ]]//Flatten)//Timing

Length[l={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,727734}]

Grid[t={#,IntegerLength[PadovanNumber[#]]}&/@l,Dividers->All,Alignment->Decimal]

$Version

Date[]

Do[
Print[{i,l[[i]],PrimeQ[PadovanNumber[l[[i]]]]//Timing}],
{i,Length[l]}]

Padovan Q-Matrix

Q:={{0,1,0},{0,0,1},{1,1,0}}

MatrixForm/@NestList[#.Q&,IdentityMatrix[3],10]

MatrixForm/@Round[Table[{{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]}},{n,6,10}]]