Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$\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$.

share|cite|improve this question
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
up vote 2 down vote accepted

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}$.

share|cite|improve this answer
Thanks for the answer, but I see a lot of unexplained things, which I don't seem to be able to comprehend :( . (n+1)st binary digit is the one counted from the left end, right? And, how does this bit influence the range of k like you posted? Infinitely many k? But k is a natural number, right? How would k take infinitely many values in between 2 real numbers differing by 1/2? – learner Oct 5 '12 at 21:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.