# If $A \subseteq \mathbb{N}$, $2^n \in A$ and if $x\in A$, then $\lfloor \sqrt{x} \rfloor \in A$. Is it true that $A=\mathbb{N}$?

Let $A$ be a non-empty subset of $\mathbb{N}$, such that for all $k \in \mathbb{N}$, we have $2^k\in A$. Also, if $x \in A$ then we have $\lfloor \sqrt{x} \rfloor \in A$. Is it true that $A=\mathbb{N}$?

I have tried but am not able to do anything. Taking $n \notin A$ and trying to achieve a contradiction didn't work for me. So how do we solve this, preferably by a pre-calculus approach? Additionally, is it also true for powers of $n$ other than $2$?

Let's take one number $n$ which is not a power of $2$ and assume it is not in $A$.

If $n$ is not in $A$ then any number between $n^2$ and $(n+1)^2-1$ must be missing, because if one of these numbers is in $A$ then $n$ is in $A$, because the floor of the square root of all of them is equal to $n$.

Now, we can consider two steps. It is easy to see that all the numbers from $n^4$ to $(n+1)^4-1$ should be missing, otherwise in two steps we reach $n$.

Proceeding in this way we can see that all the numbers from $n^\alpha$ to $(n+1)^\alpha-1$ must be missing, where $\alpha$ is a power of 2.

Now, the ratio $\frac{n+1}{n}$ is larger than $1$, so there will be a value $\alpha$ such that $(n+1)^\alpha > 2\cdot n^\alpha$, i.e., that the range of forbidden numbers contains at least one number $m=n^\alpha$ and twice that number $2m=2n^\alpha$.

But it is easy to see that between a number $m$ which is not a power of two and its double $2m$ there is always a power of 2.

But this would imply that that power of 2 is forbidden, but this is a contradiction because all the powers of 2 are in $A$.

EDIT. The argument should work also if we know that $3^k\in A$ (or other powers with a fixed base). Indeed the ratio between $n^\alpha$ and $(n+1)^\alpha$ can always become large enough to be sure that a power of the base is inside the interval.

It's sufficient to show $$\forall n\in \mathbb N\quad \exists k,m\in \mathbb N \quad \text{s.t} \quad n^{2^k}<2^m<(n+1)^{2^k}$$
and it's equal to say $$\forall n\in \mathbb N\quad \exists k,m\in \mathbb N \quad \text{s.t} \quad 2^k \log_2{n}<m<2^k \log_2{(n+1)}$$

And it's true, because if $\log_2{(n+1)}-\log_2{n}=\varepsilon$ then put $k$ so large such that $2^k\varepsilon>1$.

Remark : This method also works for any number $1<x$ other than $2$.
If $\log_x{(n+1)}-\log_x{n}=\varepsilon$ then there is a $k$ s.t $x^k\varepsilon>1$

• Indeed. It would be interesting to see how much effort is needed to turn this into a pre-calculus proof. First thing, one can compute effectively a "large enough" $k$ in terms of $m$ – Ewan Delanoy Apr 1 '16 at 11:35
• @EwanDelanoy "large enough" $k$ in terms of $n$, not $m$. – user217174 Apr 1 '16 at 11:42