Hofstadter's Q-Seqeunce

Author

Eric W. Weisstein
April 22, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/IntegerSequences/HofstadtersQ-Sequence.nb.

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

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

Initialization

HofstadterQ[1]=HofstadterQ[2]=1;HofstadterQ[n_]:=HofstadterQ[n]=HofstadterQ[n-HofstadterQ[n-1]]+HofstadterQ[n-HofstadterQ[n-2]]

Sequence

Table[HofstadterQ[n],{n,15}]

v5.0

RSolve[{HofstadterQ[n]==HofstadterQ[n-HofstadterQ[n-1]]+HofstadterQ[n-HofstadterQ[n-2]],HofstadterQ[1]==HofstadterQ[2]==1},HofstadterQ[n],n]

RSolve[{a[n]==a[n-1]-a[n-2],a[1]==a[2]==1},a[n],n]

FullSimplify[((2 Sin[((n π)/3)])/(Sqrt[3]))-((2 Sin[(((n-1) π)/3)])/(Sqrt[3]))+((2 Sin[(((n-2) π)/3)])/(Sqrt[3])),n∈Integers]

Table[((2 Sin[((n π)/3)])/(Sqrt[3])),{n,10}]

Solve[{α==(A+Sqrt[A^2+4B])/2,β==(A-Sqrt[A^2+4B])/2},{A,B}]

Solve[t^n==t^(n-1)-t^(n-2),t]

Table[((((-1))^(1/3)))^n,{n,5}]

Solve[{A+B/t==1,A t+B==1},{A,B}]

a=(-1)^(1/3)

b=-(-1)^(2/3)

c=a+2b

FullSimplify[c^n-c^(n-1)+c^(n-2),n∈Integers]

Table[%,{n,5}]

Solve[{a(((-1))^(1/3))+b(-(((-1))^(2/3)))==1,(a(((-1))^(1/3))+b(-(((-1))^(2/3))))^2==1},{a,b}]

N[%]

FullSimplify[((-1)^(1/3))^(1/n)]

Table[(((-1))^(1/(3 n))),{n,5}]//N

FullSimplify[((-1)^(1/3))^n-((-1)^(2/3))^n]

Table[(((-1))^(n/3))-(((-1))^(2 n/3)),{n,5}]//N

Table[((((-1))^(1/3)))^n,{n,5}]//N

Plot

With[{style=Directive[Black,FontFamily->"Times"]},
GraphicsRow[
{
ListPlot[Table[HofstadterQ[n],{n,500}],
PlotStyle->Red,Joined->True,BaseStyle->style,LabelStyle->Directive[Black,14],
AxesLabel->{n,Q[n]}],
ListPlot[Table[HofstadterQ[n]-n/2,{n,500}],
PlotStyle->Red,Joined->True,BaseStyle->style,LabelStyle->Directive[Black,14],
AxesLabel->{n,Q[n]-Row[{n,"/",2}]}]
},Alignment->Center,ImageSize->Large]]