Consider the recurrence equation defined by 
and
 |
(1)
|
where 
is the floor function. Graham and Pollak actually
defined 
,
but the indexing 
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 
.
 | OEIS |  ,  , ... |
| 1 | A001521 | 1, 2, 3, 4, 6, 9, 13, 19, 27, 38, 54, ... |
| 5 | A091522 | 5, 7, 10, 14, 20, 28, 40, 57, 81, 115, ... |
| 8 | A091523 | 8, 12, 17, 24, 34, 48, 68, 96, 136, 193, ... |
Amazingly, an explicit formula for 
with 
is given by
 |
(2)
|
where 
is the 
th
smallest number in the set 
(Graham
and Pollak 1970; Borwein and Bailey 2003, p. 63).
Now consider the associated sequence
 |
(3)
|
whose value is always 0 or 1. Even more amazingly, interpreting the sequence 
as a series of binary bits gives a series of algebraic constants
 |
(4)
|
where the first few constants are
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
 |  |  |
(8)
|
 |  |  |
(9)
|
 |  |  |
(10)
|
 |  |  |
(11)
|
 |  |  |
(12)
|
 |  |  |
(13)
|
 |  |  |
(14)
|
(OEIS A091524 and A091525; Borwein and Bailey 2003, p. 63).
It is not known if sequences such as
 |  |  |
(15)
|
 |  | ![|_RadicalBox[{2, {a, _, {(, {n, -, 1}, )}}, {(, {{a, _, {(, {n, -, 1}, )}}, +, 1}, )}, {(, {{a, _, {(, {n, -, 1}, )}}, +, 2}, )}}, 3]_|](/images/equations/Graham-PollakSequence/Inline50.svg) |
(16)
|
have corresponding properties (Graham and Pollak 1970; Borwein and Bailey 2003, p. 63).
." 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