6
$\begingroup$

Recently, while learning Python (the programming language), I started playing around to generate the following sequence: $$\lfloor \sqrt{0} \rfloor, \lfloor \sqrt{1} \rfloor, \lfloor \sqrt{2} \rfloor, \lfloor \sqrt{3} \rfloor, \dots$$

Interestingly, this is equivalent to

$$0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, \dots$$

I tried this up to $\lfloor \sqrt{10000} \rfloor$ and saw that every $n \in [0,99]$ occurs exactly $2n+1$ times in the sequence.

Being curious, I'm interested in proving this for all $n \in \Bbb N$ (or finding a counterexample), but I'm not sure how to do this. The only related thing I've found is that determining whether $\lfloor \sqrt{p} \rfloor$ ($p$ is prime) generates all natural numbers is an unsolved problem, but can we do a simple proof of this using all natural numbers? All hints are welcome.

$\endgroup$
  • 2
    $\begingroup$ $\lfloor\sqrt{n}\rfloor = k$ if and only if $k^2 \leqslant n < (k+1)^2$. $\endgroup$ – Daniel Fischer Apr 27 '14 at 21:28
10
$\begingroup$

HINT : All you need to notice is that $$(n+1)^2 - n^2 = 2n+1$$

$\endgroup$
  • 2
    $\begingroup$ Well that is just brilliantly simple, thanks! $\endgroup$ – naslundx Apr 28 '14 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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