Graham-Pollak Sequence

Author

Eric W. Weisstein
January 18, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/IntegerSequences/Graham-PollakSequence.nb.

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

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

Code

a[m_,0]:=m
a[m_,n_]:=a[m,n]=Floor[Sqrt[2a[m,n-1](a[m,n-1]+1)]]

b[m_,n_]:=b[m,n]=a[m,2n+1]-2a[m,2n-1]

aFormula[m_,n_]:=Module[{tau=Sort[Join[Range[m],Range[m]Sqrt[2]],Less][[m]]},
Floor[tau(2^(n/2)+2^((n-1)/2))]
]

m==1

a[1,#]&/@Range[0,20]

aFormula[1,#]&/@Range[0,20]

b[1,#]&/@Range[1,20]

RealDigits[Sqrt[2]-1,2,20,-1]

RSolve[{a[n]==Floor[Sqrt[2a[n-1](a[n-1]+1)]],a[0]==1},a[n],n]

m==2

a[2,#]&/@Range[0,20]

aFormula[2,#]&/@Range[0,20]

b[2,#]&/@Range[20]

RealDigits[Sqrt[2]-1,2,20,-1]

m==3

a[3,#]&/@Range[0,20]

aFormula[3,#]&/@Range[0,20]

b[3,#]&/@Range[20]

RealDigits[2Sqrt[2]-2,2,20,-1]

m==4

a[4,#]&/@Range[0,20]

aFormula[4,#]&/@Range[0,20]

b[4,#]&/@Range[1,20]

RealDigits[2Sqrt[2]-2,2,20,-1]

m==5

a[5,#]&/@Range[0,20]

aFormula[5,#]&/@Range[0,20]

b[5,#]&/@Range[20]

RealDigits[3Sqrt[2]-4,2,20,-1]

Sequence of Constants α(m)

<<Utilities`Simplify`

Alpha[m_]:=Module[{x=FromDigits[{b[m,#]&/@Range[100],0},2],rem},
rem=LatticeReduce[Rationalize[N[Transpose[Join[IdentityMatrix[3],
{10^15{1,Sqrt[2],x}}]],30],10^-30]];
If[rem[[1,-1]]>10^-10,Print[{m,rem[[1,-1]]//N,"too big"}]];
-{1,Sqrt[2]}.Take[rem[[1]],2]
]

alphas=Alpha/@Range[100]

a=Transpose[{#2/Sqrt[2],-#1}&@@@alphas]