# How many squarings are needed to exceed 2?

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

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

• "if all these digits are $1$ it is equivalent to a number where only the $n-1$ digit of the fractional part is $1$" isn't possible given "and has a finite number of digits in base $2$". – aschepler Mar 8 at 0:13
• @aschepler that's true, but it's a good approximation for the most extreme edge case – potato Mar 8 at 0:55
• I notice any algorithm which can get an exact answer is able to tell whether an input is smaller or larger than $\sqrt{2}$, and therefore could be used iteratively to find the base-2 representation of $\sqrt{2}$ to arbitrary precision. There aren't any known simple patterns to that sequence, so probably it would at least require a full multiplication or similar. – aschepler Mar 8 at 1:46
• @aschepler maybe there is no known perfect solution that works in all cases, but it seems that an easy solution exists at least for some cases, look at the update to my question. – potato Mar 8 at 20:23
• Nice. You can also move your findings into an answer to your own question. (Seeing zero answers might get it a little more attention from some potential answerers, but seeing non-zero answers could get more attention from anyone searching for a related topic.) – aschepler Mar 8 at 22:01

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, 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 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:

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: