# Prove that $\operatorname{Spec}\sqrt2$ contains infinitely many powers of $2$.

$\newcommand{\spec}{\operatorname{Spec}}\spec\sqrt2=\{\lfloor k\sqrt2\rfloor: k \ge 0\}$.

I have no idea of how I can prove the statement in the question.

Prove that $\spec\sqrt2$ contains infinitely many powers of $2$.

-
The most obvious place to start would be to enumerate the first few values of $\lfloor k \cdot \sqrt{2}\rfloor$ to get a feel for how it behaves. The next most obvious is to devise an algorithm for solving $\lfloor k \cdot \sqrt{2} \rfloor = 2^n$ for $k$. – Hurkyl Oct 5 '12 at 21:10
What a strange notation. Why $\mathrm{Spec} \sqrt{2}$? – Alexander Shamov Oct 5 '12 at 21:12
@Alexander: Graham, Knuth, & Patashnik, Concrete Mathematics, refer to this sequence as the spectrum of $\sqrt2$. – Brian M. Scott Oct 5 '12 at 21:12
As stated, this question is obviously true. Do you mean infinitely many integer powers of 2? – Graphth Oct 5 '12 at 21:14
@Graphth: Of course. – Brian M. Scott Oct 5 '12 at 21:15

Let $k=\lceil 2^n\sqrt 2\rceil$. Then $2^n\sqrt 2<k<2^n\sqrt 2+1$. In fact we have either $2^n\sqrt 2<k<2^n\sqrt 2+\frac12$ or $2^n\sqrt 2+\frac12<k<2^n\sqrt 2+1$, depending on the ($n+1)$st binary digit of $\sqrt 2$ (which becomes the first digit of $2^n\sqrt 2$). Since $\sqrt 2$ is irrational, there are infinitely many $n$ (and correspondingly infinitely many $k$) such that $$2^n\sqrt 2<k<2^n\sqrt 2+\frac12$$ holds. Together with $k\sqrt 2 -1<\lfloor k\sqrt 2\rfloor <k\sqrt 2$ we find $$2^n\cdot 2-1 <\lfloor k\sqrt 2\rfloor <2^n\cdot 2+\frac{\sqrt 2}2,$$ hence $\lfloor k\sqrt 2\rfloor=2^{n+1}$.