Rounded Square Roots

We define the rounded-square-root of a positive integer $n$ as the square root of $n$ rounded to the nearest integer.
The following procedure (essentially Heron’s method adapted to integer arithmetic) finds the rounded-square-root of $n$:
Let $d$ be the number of digits of the number $n$.
If $d$ is odd, set $x_0 = 2 \times 10^{(d-1)/2}$.
If $d$ is even, set $x_0 = 7 \times 10^{(d-2)/2}$.
Repeat:
$$x_{k+1} = \Biggl\lfloor{\dfrac{x_k + \lceil{n / x_k}\rceil}{2}}\Biggr\rfloor$$

until $x_{k+1} = x_k$.
As an example, let us find the rounded-square-root of $n = 4321$.$n$ has $4$ digits, so $x_0 = 7 \times 10^{(4-2)/2} = 70$.
$$x_1 = \Biggl\lfloor{\dfrac{70 + \lceil{4321 / 70}\rceil}{2}}\Biggr\rfloor = 66$$
$$x_2 = \Biggl\lfloor{\dfrac{66 + \lceil{4321 / 66}\rceil}{2}}\Biggr\rfloor = 66$$

Since $x_2 = x_1$, we stop here.
So, after just two iterations, we have found that the rounded-square-root of $4321$ is $66$ (the actual square root is $65.7343137\cdots$).

The number of iterations required when using this method is surprisingly low.
For example, we can find the rounded-square-root of a $5$-digit integer ($10\,000 \le n \le 99\,999$) with an average of $3.2102888889$ iterations (the average value was rounded to $10$ decimal places).

Using the procedure described above, what is the average number of iterations required to find the rounded-square-root of a $14$-digit number ($10^{13} \le n \lt 10^{14}$)?
Give your answer rounded to $10$ decimal places.

Note: The symbols $\lfloor x \rfloor$ and $\lceil x \rceil$ represent the floor functionthe largest integer not greater than $x$ and ceiling functionthe smallest integer not less than $x$ respectively.

To calculate the average number of iterations required to find the rounded-square-root of a 14-digit number using the procedure described, we need to simulate the process for a large number of random 14-digit numbers and calculate the average number of iterations.

Here’s a Python code that does exactly that:

“`python
import random

def find_rounded_sqrt(n):
d = len(str(n))
if d % 2 == 0:
x = 7 * 10**((d-2)//2)
else:
x = 2 * 10**((d-1)//2)
iterations = 0
while True:
new_x = (x + (n // x)) // 2
if new_x == x:
break
x = new_x
iterations += 1
return iterations

def find_average_iterations():
total_iterations = 0
num_simulations = 100000
for _ in range(num_simulations):
n = random.randint(10**13, 10**14 – 1)
iterations = find_rounded_sqrt(n)
total_iterations += iterations
average_iterations = total_iterations / num_simulations
return average_iterations

average = find_average_iterations()
print(round(average, 10))
“`

This code defines two functions. `find_rounded_sqrt(n)` takes a positive integer `n`, performs the rounded-square-root calculation using the given procedure, and returns the number of iterations required.

The `find_average_iterations()` function performs a large number of simulations (100,000 in this case) where random 14-digit numbers are generated and the rounded-square-root calculation is performed on each. It keeps track of the total number of iterations across all simulations and then calculates the average number of iterations.

Finally, the code calls `find_average_iterations()` to obtain the average number of iterations and prints the result, rounded to 10 decimal places.

Please note that running this code may take some time due to the large number of simulations.

More Answers: