Tetranacci Number

Author

Eric W. Weisstein
November 15, 2005

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

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

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

Code

TetranacciDirect[n_]:=Block[{$MaxExtraPrecision=Infinity},Round[((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1])^n) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,1]+((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2])^n) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,2]+((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4])^n) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,3]+((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3])^n) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,4]]
]

Tetranacci[0]:=0
Tetranacci[1]:=1
Tetranacci[2]:=1
Tetranacci[3]:=2
Tetranacci[n_]:=Tetranacci[n]=Tetranacci[n-1]+Tetranacci[n-2]+Tetranacci[n-3]+Tetranacci[n-4]

Root Sum

Table[RootSum[#^4-#^3-#^2-#-1&,(((#)^(n-2))/(-#^3+6#-1))&],{n,0,10}]

Sum of Roots

soln[n_]=RSolve[{T[n]==T[n-1]+T[n-2]+T[n-3]+T[n-4],T[0]==0,T[1]==1,T[2]==1,T[3]==2},T[n],n][[1,1,2]];

soln2[n_]=soln[n]/.Thread[Table[Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,n],{n,4}]->{α,β,γ,δ}]

terms=Factor[Coefficient[soln2[n],{α,β,γ,δ}^n]]

terms.{α,β,γ,δ}^n-soln2[n]//Simplify

RSolve[{T[n]==T[n-1]+T[n-2]+T[n-3]+T[n-4],T[0]==0,T[1]==1,T[2]==1,T[3]==2},T[n],n]

((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1])^n) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,1]+((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2])^n) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,2]+
((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3])^n) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,4]+((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4])^n) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,3]

f1=-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&;
f2=-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&;
pos={1,2,4,3};

an=ToNumberField[Root[f2,#],Root[f1,pos[[#]]]]&/@Range[3]

coeffs=an[[All,-1]]

SameQ@@coeffs

RootSum[f1,Evaluate[((#)^(n+Range[Length[pos]]-1)).an[[1,2]]]&]

Table[RootSum[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,-87 ((#1)^n)-71 ((#1)^(1+n))-61 ((#1)^(2+n))+86 ((#1)^(3+n))&]/563,{n,0,20}]

Table[RootSum[-1-#-#^2-#^3+#^4&,10#^n+157#^(n+1)-103 #^(n+2)+16#^(n+3)&]/563,{n,0,40}]

Table[RootSum[#^4-#^3-#^2-#-1&,#^(n-2)/(-#^3+6#-1)&],{n,0,40}]

Concise

<<Algebra`SymmetricPolynomials`

sum=Plus@@(((2+SymmetricPolynomial[Rest[#],2]-SymmetricPolynomial[Rest[#],1])/(Times@@(Function[f,First[#]-f]/@Rest[#])))First[#]^(n-1)&/@Partition[{α,β,γ,δ},4,1,1])

Table[sum/.Thread[{α,β,γ,δ}->Evaluate[Table[Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,k],{k,4}]]],{n,10}]//N//Chop

RootReduce[(((2+SymmetricPolynomial[Rest[#],2]-SymmetricPolynomial[Rest[#],1])/(Times@@(Function[f,First[#]-f]/@Rest[#])))&/@Partition[{α,β,γ,δ},4,1,1])/.Thread[{α,β,γ,δ}->Evaluate[Table[Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,k],{k,4}]]]]

Table

Table[soln[n],{n,10}]//FullSimplify

Table[soln[n],{n,10}]//N//Chop

Table[Tetranacci[n],{n,0,10}]

Generating Function

FindGeneratingFunction[Table[Tetranacci[n],{n,0,12}],x]

Series[(z/(1-z-(z^2)-(z^3)-(z^4))),{z,0,10}]

CoefficientList[%,z]

RootSum

GeneratingFunction[RootSum[#^4-#^3-#^2-#-1&,(((#)^(n-2))/(-#^3+6#-1))&],n,x]

gf=GeneratingFunction[Normal@RootSum[#^4-#^3-#^2-#-1&,(((#)^(n-2))/(-#^3+6#-1))&],n,x]

RootReduce

gf=RootReduce[gf]

Divide@@(Through[{Numerator,Denominator}[Together[gf]]]//FullSimplify//Factor)

FullSimplify

gf=GeneratingFunction[Normal@RootSum[#^4-#^3-#^2-#-1&,(((#)^(n-2))/(-#^3+6#-1))&],n,x]//FullSimplify

Divide@@(Through[{Numerator,Denominator}[Together[gf]]]//FullSimplify//Factor)//Timing

V6

<<DiscreteMath`RSolve`

SeriesTerm[(1/(1-z-(z^2)-(z^3)-(z^4))),{z,0,n}]

V6

FullSimplify[SeriesCoefficient[(z/(1-z-(z^2)-(z^3)-(z^4))),{z,0,n}],n>0]

V7

Series[%,{x,0,10}]//FullSimplify

V8

term=((2-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]) ((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4])^(-1+n)))/((-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]) (-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]) (-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]))+(((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3])^(-1+n)) (2-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]))/((-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]) (-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]) (Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]))+(((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2])^(-1+n)) (2-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]))/((-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]) (Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]) (Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]))+(((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1])^(-1+n)) (2-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]+Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3] Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]))/((Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2]) (Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3]) (Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1]-Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4]));

FullSimplify[term]

Sum[term x^n,{n,∞}]//FullSimplify

FindGeneratingFunction[Table[Tribonacci[n],{n,0,10}],x]

Series[%,{x,0,10}]

ExponentialGeneratingFunction

Sum[term((x^n)/(n!)),{n,0,∞}]//FullSimplify

Series[(1/(Sqrt[563]))I ((E^(x Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,3])) Root[316969+50670 ((#1)^2)+2975 ((#1)^4)+86 ((#1)^6)+((#1)^8)&,2]+(E^(x Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,2])) Root[316969+50670 ((#1)^2)+2975 ((#1)^4)+86 ((#1)^6)+((#1)^8)&,3]+(E^(x Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,1])) Root[316969+50670 ((#1)^2)+2975 ((#1)^4)+86 ((#1)^6)+((#1)^8)&,5]+(E^(x Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,4])) Root[316969+50670 ((#1)^2)+2975 ((#1)^4)+86 ((#1)^6)+((#1)^8)&,8]),{x,0,10}]//FullSimplify

CoefficientList[%217,x]Range[0,10]!

DirichletGeneratingFunction

Sum[(1/(n^s))term,{n,∞}]

Lambert Series

Sum[(term/(1-(x^n)))(x^n),{n,∞}]

FullSimplify[%165]

Recurrence

FindLinearRecurrence[Table[Tetranacci[n],{n,0,20}]]

LinearRecurrence[{1,1,1,1},{0,0,1,1,2},10]

Ratio

f[n_]={Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,1],Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,2],Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,4],Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,3]}.{α,β,γ,δ}^n/.Thread[{α,β,γ,δ}->Evaluate[Table[Root[-1-#1-((#1)^2)-((#1)^3)+((#1)^4)&,k],{k,4}]]]

FullSimplify[f/@Range[10]]

limit=Limit[f[n]/f[n-1],n->∞]

N[%,20]

NRoots[x^4-x^3-x^2-x-1==0,x]

Prime

Block[{$MaxExtraPrecision=Infinity},
Flatten[Position[Round[Tetranacci/@Range[5000]],_?PrimeQ]]
]//Timing

Flatten[Position[tetranacci/@Range[5000],_?PrimeQ]]//Timing

tetranacci/@{3,7,11,12,36}

Flatten[Position[tetranacci/@Range[10^4],_?PrimeQ]]//Timing

l={3,7,11,12,36,56,401,2707,8417,14096,31561,50696,53192,155182};

{Length[l],l[[Length[l]]]}

Block[{$MaxExtraPrecision=Infinity},Digits[TetranacciDirect[l[[-1]]]]]//Timing

t0=0;
t1=1;
t2=1;
t3=2;
Do[(temp=t3;t3+=t2+t1+t0;t0=t1;t1=t2;t2=temp),{n,4,155182}];//Timing

Digits[t3]

Block[{$MaxExtraPrecision=Infinity},
Do[
Print[{n,l[[n]],PrimeQ[Round[TetranacciDirect[l[[n]]]]]//Timing}],
{n,Length[l]}]
]

Generalized Tetranacci Numbers

Noe's Supposed Prime

PrimeQ[Round[TetranacciDirect[145858]]]//Timing

t0=1;
t1=3;
t2=7;
t3=15;
Do[(temp=t3;t3+=t2+t1+t0;t0=t1;t1=t2;t2=temp),{n,4,145858}];//Timing

PrimeQ[t3]//Timing

Block[{$MaxExtraPrecision=Infinity},Digits[t3]]//Timing