Problem 482

Define a sequence by $a_1=1$ and

a_{n+1}=\lfloor\sqrt{2}(a_n+1/2)\rfloor

for $n\geq 1$ . The difference $a_{2n+1}-2a_{2n-1}$ is the $n$ th digit in the binary expansion of $\sqrt{2}$ .

Find similar results for $\theta=\sqrt{m}$ , and other algebraic numbers.

Source: erdosproblems.com/482

Number theory

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

SOLVED, the site's label (page last edited 28 September 2025), which marks a resolution other than a proof or disproof and attaches here to a constructive answer, the accepted claim page Stoll 2005: Stoll's two refereed papers give, for every positive real $w$ (so for every $\sqrt m$ and every positive algebraic number) and for every integer base $g\ge2$ , infinitely many floor recurrences of the Graham--Pollak shape whose differences $u_{2n+1}-gu_{2n-1}$ are the base- $g$ digits of $w$ (J. Integer Seq. 8 (2005), Theorems 1.2 and 1.3; Acta Arith. 125 (2006), Theorems 3.1, 3.3 and 3.4), and identify what the original recurrence computes for every integer starting value (Corollary 3.5 of 2006). They construct families and do not classify every recurrence with the digit property, which the request never asked for; the site's own qualification is recorded below. The claim is accepted on the refereed papers and the curator's credit, and its value is answered because the first paragraph is a theorem and the second is a request with no truth value, neither false nor degenerate, so neither a proof nor a disproof is the outcome; the label attaches to an open-ended request, the shape of Problem 296.

ErGr80: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28, Université de Genève (1980). Printed p. 96: the last paragraph of Chapter 9, quoted below. Library home: Erdős and Graham 1980.
GrPo70: Graham, R. L. and Pollak, H. O., Note on a nonlinear recurrence related to $\surd 2$ . Math. Mag. 43 (1970), no. 3, 143--145, doi:10.1080/0025570X.1970.11976029 (Crossref record accessed). The Theorem and the announced identity, p. 143; the reduction to the shifted recurrence, p. 144; the concise closed form, the identity's derivation and the closing question, p. 145. Library home: Graham and Pollak 1970.
St05: Stoll, Th., On families of nonlinear recurrences related to digits. J. Integer Seq. 8 (2005), Article 05.3.2, 8 pp. (received 1 April 2005, published 24 May 2005; no Crossref record exists for the journal). Theorems 1.2 and 1.3, p. 3. Library home: Stoll 2005.
St06: Stoll, Thomas, On a problem of Erdős and Graham concerning digits. Acta Arith. 125 (2006), no. 1, 89--100, doi:10.4064/aa125-1-8 (received 16 March 2006; Crossref record accessed). Fact 1, p. 89; Theorem 3.1, p. 92; Theorems 3.3--3.4, pp. 93--94; Corollary 3.5, p. 94. Library home: Stoll 2006.
RaGi91: Rabinowitz, S. and Gilbert, P., A nonlinear recurrence yielding binary digits. Math. Mag. 64 (1991), no. 3, 168--171, doi:10.1080/0025570X.1991.11977601. Not held; its family is quoted from [St05], Theorem 1.1. Claim page: Rabinowitz and Gilbert 1991.
St10: Stoll, T., A fancy way to obtain the binary digits of $759250125\sqrt2$ . Amer. Math. Monthly 117 (2010), no. 7, 611--617, doi:10.4169/000298910x496732; arXiv:0902.4168 (submitted 24 February 2009). Not held.
OEIS: Sloane, N. J. A., Sequence A004539 (the binary expansion of $\sqrt2$ ), The On-Line Encyclopedia of Integer Sequences (entry accessed; it lists the Graham--Pollak note among its links). The Graham--Pollak sequence itself is A001521 (per [St05]).

Problem 482

Status

Proof claims

Discussion