---

Problem 255

---

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₀ = 2×10^(d-1)⁄2.
If d is even, set x₀ = 7×10^(d-2)⁄2.
Repeat:

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₀ = 7×10^(4-2)⁄2 = 70.

Since x₂ = x₁, 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…).

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 ≤ n ≤ 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¹³ ≤ n < 10¹⁴)?
Give your answer rounded to 10 decimal places.

Note: The symbols ⌊x⌋ and ⌈x⌉ represent the floor function and ceiling function respectively.

---

近似平方根

我们定义正整数n的近似平方根为与n的实际平方根最接近的整数。

如下的过程（实际上就是将希罗求平方根的方法应用在整数算术上）能够给出n的近似平方根：

记n的位数为d。
如果d是奇数，则令x₀ = 2×10^(d-1)⁄2。
如果d是偶数，则令x₀ = 7×10^(d-2)⁄2。
依此类推：

直到x_k+1 = x_k。

举例来说，我们来寻找n = 4321的近似平方根。
n是4位数，因此x₀ = 7×10^(4-2)⁄2 = 70。

因为x₂ = x₁，就不用再继续下去了。
所以，仅仅经过两次迭代，我们就得到了4321的近似平方根为66（实际平方根为65.7343137…）。

这个方法所需的迭代次数少得令人惊讶。
例如，对于所有的5位数（10,000 ≤ n ≤ 99,999），我们平均只需要3.2102888889次（四舍五入至10位小数）迭代就能找到其近似平方根。

使用上面描述的方法，对于所有的14位数（10¹³ ≤ n < 10¹⁴），我们平均需要多少次迭代能够找到其近似平方根？
将你的答案四舍五入到10位小数。

注意：符号⌊x⌋和⌈x⌉分别表示下取整函数和上取整函数。

---