How many squarings are needed to exceed 2?

Question

Given the base 2 representation of $x\in\mathbb Q$ ($1<x<2$ and has a finite number of digits in base 2), find a number $k\in\mathbb N$ such that $2<x^{2^k}<4$.

The final answer/algorithm is not allowed to use powers, roots and logarithms.

---

I managed to find a range of possible values for $k$.

Looking at the digits after he decimal point, if the $n$th digit is the first non-zero digit, then squaring this number will necessarily turn at least one of the two preceding digits into a 1 but none of the digits before it. I figured this out by looking at the edge cases: if all the digits after the $n$th digit are zero then the $n-1$ digit becomes 1 when the number is squared, and if all these digits are 1 it is equivalent to a number where only the $n-1$ digit of the fractional part is 1, and squaring this number makes the $n-2$ digit be 1.

So the algorithm for finding the upper and lower limits of $k$ is:

Looking at the digits after the decimal point, count the leading zeros (let's call the result of the count $z$). Then $\lfloor\frac{z+2}{2}\rfloor ≤ k ≤ z+1$.

Answer 1

Better proof of the same conclusion as my previous answer, this time without using approximation.

Again, there is no known solution for all numbers, but I found a quick solution for a significant amount of cases, which is useful for optimizing computer programs (for example: try this answer's method, if it fails do something else, like squaring repeatedly until you can determine the solution using this answer's method).

---

$$C_{z,n} \stackrel{\text{def}}{=} \frac{2^n-1}{2^{n+z}}+1 = 1.\underbrace{0000000000}_{z\text{ zeros}}\underbrace{111111111}_{n\text{ ones}}\text{ (base 2)}$$

These numbers are useful edge cases because if we know that $k$ (the amount of squarings needed to exceed 2) is the same for $C_{z,n}$ and $C_{z,n+1}$ then it is also the same for all the numbers in between, and that lets us know the answer for all these numbers by counting the first consecutive zeros and ones.

For every number of the form $C_{z,n}$ we know that $k$ is either $z$ or $z+1$. Solving the inequality $C_{z,n} > \sqrt[2^z]{2}$ will tell us the if squaring $z$ times is enough or not. Scaling the inequality around the value 1 (subtract 1, multiply by the scale factor, then add 1) by a factor of $2^z$ results in $C_{0,n} > 2^z (\sqrt[2^z]{2}-1)+1$.

$k=\begin{cases} z + 1 & C_{0,n} < 2^z (\sqrt[2^z]{2}-1)+1\\ z & C_{0,n} > 2^z (\sqrt[2^z]{2}-1)+1 \end{cases}$

The following chart shows the solution to the inequality for $n=1,2,3$:

This gives us the following solution:
(Same as in my previous answer, just written differently.)

$$k = \begin{cases} z+1=1 & & z = 0\\ z+1 & n = 1\\ z+1 & n = 2 & z ≤ 2\\ z & n = 2 & z > 2\\ z & n > 2 & z > 0 \end{cases}$$

Now that we know the value of $k$ for all the edge cases, we can fill in (most of) the gaps. If $k$ is the same for $C_{z,n}$ and $C_{z,n+1}$ then it is also the same for all the numbers in between:

$$C(z,n) \stackrel{\text{def}}{=} \{x|C_{z,n} ≤ x < C_{z,n+1}\}$$

Every number in $C(z,n)$ starts with the digits of $C_{z,n}$ followed by a zero followed by anything.

The following table shows the solutions for all the gaps we can fill:

Answer 2

There is no known solution for all numbers, but I found a quick solution for a significant amount of cases, which is useful for optimizing programs (try this, if it fails do something else, like squaring repeatedly).

Part 1: define edge cases

Let's construct a number whose fractional part has $z$ leading zeros followed by $n$ consecutive ones, and see to what power $2^k$ do we need to raise it to get it between 2 and 4. (This leads to a more complete solution, you'll see later.)

To produce a chain of $n$ ones in base 2, all we need is to subtract 1 from the $n$th power of 2. For example $2^4-1=15$ and the base 2 representation of 15 is $1111$.

The next thing to do is to divide it by $2^n$ to move the 1-digits to the right side of the decimal point. To add $z$ leading zeros, just divide it by $2^z$. And finally, +1 to make it a number between 1 and 2.

$$2 < \left(\frac{2^n-1}{2^{n+z}}+1\right)^{2^k} < 4$$

Part 2: isolate $k$

For brevity, let's call the part in the brackets $m$:

$$2 < m^{2^k} < 4$$

Take the logarithm (base 2) of the inequality:

$$1 < 2^k\log_2(m) < 2$$

Divide by the logarithm:

$$\frac{1}{\log_2(m)} < 2^k < \frac{2}{\log_2(m)}$$

Take the logarithm again:

$$- \log_2(\log_2(m)) < k < 1 - \log_2(\log_2(m))$$

Part 3: find the integer values of $k$

Since $k$ is a whole number, and there is only one valid value of $k$ that solves this inequality at any given point $(z,n)$, we can take the lower limit and round it up:

$$k = \lceil - \log_2(\log_2(m))\rceil = - \lfloor\log_2(\log_2(m))\rfloor = -\operatorname{msb}(\log_2(m))$$

Where $\operatorname{msb}(x)$ is the position of the most significant bit (digit) of $x$, which for $0<\log_2(m)<1$ is negative. (Note that $\lfloor\log_2(x)\rfloor = \operatorname{msb}(x)$ is correct only for this range.)

$1<m<2$, and in this range $\log_2(x) \approx x-1$, but remember that $\log_2(x) > x-1$ in this range, so it will throw the $\operatorname{msb}$ function result off in some cases (it will be too big by +1).

$$k \approx -\operatorname{msb}(m-1) = -\operatorname{msb}\left(\frac{2^n-1}{2^{n+z}}\right) = z+1$$

For very small numbers ($z>2$) the approximation is always wrong, this makes the result reliable in this range. Manually testing some cases of small $z$ and $n$ leads to a complete answer:

$$k = \begin{cases} 1 & & z = 0\\ z+1 & n = 1 & z > 0\\ z+1 & n = 2 & 1 ≤ z ≤ 2\\ z & n = 2 & z > 2\\ z & n > 2 & z > 0 \end{cases}$$

Part 4: fill in the gaps

Until now we focused on very specific numbers, now let's take care of all the numbers in between.

Let $C(z,n)$ be the set of all numbers whose base 2 representation starts with:

$$1.\underbrace{0000000000}_{z\text{ zeros}}\underbrace{111111111}_{n\text{ ones}}0$$

For a fixed value of $z$, if $k$ is the same for $n=x$ and $n=x+1$, then it is also the same for every number in between (in $C(z,x)$), because if two numbers reach the range between 2 and 4 when raised to the same power, then all the numbers between them will also reach that range with the same power. Otherwise there are 2 possible answers with a difference of 1.

To sum it up, every number $1<x<2$ is in a set of the form $C(z,n)$. By counting the consecutive zeros ($z$) after the decimal point and then the consecutive ones ($n$) we can either know the answer with certainty or at least know that it is one of two numbers, as detailed in this table: