TOPICS
Search

Graham-Pollak Sequence

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Consider the recurrence equation defined by a_0=m and

a_n=|_sqrt(2a_(n-1)(a_(n-1)+1))_|,
(1)

where |_x_| is the floor function. Graham and Pollak actually defined a_1=m, but the indexing a_0=m will be used here for convenience, following Borwein and Bailey (2003, p. 62). The first few terms are summarized in the following table for small values of m.

mOEISa_0, a_1, ...
1A0015211, 2, 3, 4, 6, 9, 13, 19, 27, 38, 54, ...
5A0915225, 7, 10, 14, 20, 28, 40, 57, 81, 115, ...
8A0915238, 12, 17, 24, 34, 48, 68, 96, 136, 193, ...

Amazingly, an explicit formula for a_n with a_0=m is given by

a_n=|_tau_m(2^(n/2)+2^((n-1)/2))_|,
(2)

where tau_m is the mth smallest number in the set {1,2,3,...} union {sqrt(2),2sqrt(2),3sqrt(2),4sqrt(2),...} (Graham and Pollak 1970; Borwein and Bailey 2003, p. 63).

Now consider the associated sequence

b_n=a_(2n+1)-2a_(2n-1)
(3)

whose value is always 0 or 1. Even more amazingly, interpreting the sequence {b_k} as a series of binary bits gives a series of algebraic constants

alpha(m)=0.b_1b_2b_3..._2,
(4)

where the first few constants are

alpha(1)=sqrt(2)-1
(5)
alpha(2)=sqrt(2)-1
(6)
alpha(3)=2sqrt(2)-2
(7)
alpha(4)=2sqrt(2)-2
(8)
alpha(5)=3sqrt(2)-4
(9)
alpha(6)=4sqrt(2)-5
(10)
alpha(7)=3sqrt(2)-4
(11)
alpha(8)=5sqrt(2)-7
(12)
alpha(9)=4sqrt(2)-5
(13)
alpha(10)=6sqrt(2)-8
(14)

(OEIS A091524 and A091525; Borwein and Bailey 2003, p. 63).

It is not known if sequences such as

a_n=|_sqrt(3a_(n-1)(a_(n-1)+1))_|
(15)
a_n=|_RadicalBox[{2, {a, _, {(, {n, -, 1}, )}}, {(, {{a, _, {(, {n, -, 1}, )}}, +, 1}, )}, {(, {{a, _, {(, {n, -, 1}, )}}, +, 2}, )}}, 3]_|
(16)

have corresponding properties (Graham and Pollak 1970; Borwein and Bailey 2003, p. 63).

Explore with Wolfram|Alpha

References

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, 2003.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Ex. 3.46 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Graham, R. L. and Pollak, H. O. "Note of a Nonlinear Recurrence Related to sqrt(2)." Math. Mag. 43, 143-145, 1970.Guy, R. K. "The Strong Law of Small Numbers." Amer. Math. Monthly 95, 697-712, 1988.Rabinowitz, S. and Gilbert, P. "A Nonlinear Recurrence Yielding Binary Digits." Math. Mag. 64, 168-171, 1991.Sloane, N. J. A. Sequences A001521/M0569, A004539, A091522, A091523, A091524, and A091525 in "The On-Line Encyclopedia of Integer Sequences."Stoll, T. "On Families of Nonlinear Recurrences Related to Digits." J. Integer Sequences 8, No. 05.3.2, 1-8, 2005. http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Stoll/stoll56.pdf.Stoll, T. "On a Problem of Erdős and Graham Concerning Digits." Acta Arith. 125, 89-100, 2006.

Referenced on Wolfram|Alpha

Graham-Pollak Sequence

Cite this as:

Weisstein, Eric W. "Graham-Pollak Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Graham-PollakSequence.html

Subject classifications