Problem 255: Rounded Square Roots

Mathematical Foundation

Lemma 1 (Fixed Range). All integers in $[10^{13}, 10^{14})$ have exactly $d = 14$ digits (even), so the initial guess is $x_0 = 7 \times 10^6$.

Proof. An integer $n$ has $d$ digits if and only if $10^{d-1} \le n < 10^d$. For $n \in [10^{13}, 10^{14})$, we have $d = 14$. Since $d$ is even, $x_0 = 7 \times 10^{(14-2)/2} = 7{,}000{,}000$. $\square$

Theorem 1 (Convergence). The iteration $x_{k+1} = \lfloor (x_k + \lceil n/x_k \rceil)/2 \rfloor$ is an integer variant of Newton’s method for $\sqrt{n}$. For any $n \ge 1$ and any initial $x_0 \ge 1$, the sequence $(x_k)$ converges to a fixed point $x^*$ satisfying $x^*(x^*-1) < n \le x^*(x^*+1)$, i.e., $x^*$ is the nearest integer to $\sqrt{n}$ (rounded up on half-integers).

Proof. Newton’s method for $f(x) = x^2 - n$ gives the iteration $x \mapsto (x + n/x)/2$. The integer variant uses ceiling division and floor of the average. One can verify:

1. If $x_k > x^*$, then $\lceil n/x_k \rceil \le x_k$, and $x_{k+1} \le x_k$ (the sequence is non-increasing once above the fixed point).
2. If $x_k \le x^*$, then $\lceil n/x_k \rceil \ge x_k$, and $x_{k+1} \ge x_k$.
3. The sequence is eventually monotone and bounded, hence convergent.

The fixed-point condition $x^* = \lfloor (x^* + \lceil n/x^* \rceil)/2 \rfloor$ characterizes $x^*$ as the rounded square root. $\square$

Theorem 2 (Grouping by Quotient). For fixed $x_k$, the values of $n \in [L, R]$ producing a given ceiling quotient $q = \lceil n/x_k \rceil$ form the interval $n \in [(q-1)x_k + 1, \; qx_k]$. The next iterate is then $x_{k+1} = \lfloor (x_k + q)/2 \rfloor$, which is constant over this interval.

Proof. By definition of ceiling division, $\lceil n/x_k \rceil = q$ iff $(q-1)x_k < n \le qx_k$, i.e., $n \in [(q-1)x_k + 1, qx_k]$. Since $x_{k+1}$ depends on $n$ only through $q$, all $n$ in this interval share the same $x_{k+1}$. $\square$

Editorial

Average number of iterations of the rounded square root algorithm for n from 10^13 to 10^14 - 1. All numbers have 14 digits (even), so x0 = 7 * 10^6 = 7000000. Iteration: x_{k+1} = floor((x_k + ceil(n/x_k)) / 2) Stop when x_{k+1} == x_k. Interval-based approach: track (x_current, n_lo, n_hi) and split by ceil(n/x) values at each step. We use a map: x_value -> count_of_n_values. We then initially, all n in [N_lo, N_hi] start with x = x0. Finally, converged: these n values took iteration iterations.

Pseudocode

Use a map: x_value -> count_of_n_values
Initially, all n in [N_lo, N_hi] start with x = x0
For each distinct q = ceil(n/x), compute x_next
Converged: these n values took `iteration` iterations
else
Continue iterating: group by x_next

Complexity Analysis

• Time: At each iteration, the number of groups is $O(\sqrt{N})$ (since the number of distinct ceiling quotients for a given $x$ over $[N_{\text{lo}}, N_{\text{hi}}]$ is $O(\sqrt{N})$ by the divisor-bound argument). With $O(\log N)$ iterations, the total is $O(\sqrt{N} \log N)$. For $N = 10^{14}$: approximately $10^7 \times 47 \approx 5 \times 10^8$.
• Space: $O(\sqrt{N})$ for storing the groups at each iteration level.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 255: Rounded Square Roots
 *
 * For n from 10^13 to 10^14-1 (14 digits, d=14, even): x0 = 7*10^6
 * Iteration: x_{k+1} = floor((x_k + ceil(n/x_k)) / 2)
 * Stop when x_{k+1} == x_k.
 *
 * Interval-based approach: track (x, n_lo, n_hi) groups and split by
 * ceil(n/x) values at each step. For fixed x, x_next = floor((x+q)/2)
 * where q = ceil(n/x). Each x_next value corresponds to 2 consecutive q values.
 *
 * Answer: 4.4474011180
 */

typedef long long ll;

ll ceildiv(ll a, ll b) {
    return (a + b - 1) / b;
}

int main(){
    const ll N_LO = 10000000000000LL;
    const ll N_HI = 99999999999999LL;
    const ll TOTAL = N_HI - N_LO + 1;
    const int x0 = 7000000;

    struct Interval {
        int x;
        ll nlo, nhi;
    };

    vector<Interval> current;
    current.push_back({x0, N_LO, N_HI});

    long double total_iterations = 0;

    while (!current.empty()) {
        // Process one iteration
        map<int, vector<pair<ll,ll>>> next_map;
        ll converged_count = 0;
        // We need iteration number for weighting. Track separately.
        // Actually we increment a counter.
        static int iter = 0;
        iter++;

        for (auto& [x, nlo, nhi] : current) {
            ll q_lo = ceildiv(nlo, (ll)x);
            ll q_hi = ceildiv(nhi, (ll)x);
            ll xn_lo = ((ll)x + q_lo) / 2;
            ll xn_hi = ((ll)x + q_hi) / 2;

            for (ll xn = xn_lo; xn <= xn_hi; xn++) {
                ll q1 = max(2LL * xn - x, q_lo);
                ll q2 = min(2LL * xn + 1 - x, q_hi);
                if (q1 > q2) continue;

                ll n1 = max((q1 - 1) * x + 1, nlo);
                ll n2 = min(q2 * x, nhi);
                if (n1 > n2) continue;

                if (xn == x) {
                    converged_count += n2 - n1 + 1;
                } else {
                    next_map[(int)xn].push_back({n1, n2});
                }
            }
        }

        total_iterations += (long double)converged_count * iter;

        current.clear();
        for (auto& [xn, intervals] : next_map) {
            sort(intervals.begin(), intervals.end());
            ll lo = intervals[0].first, hi = intervals[0].second;
            for (size_t i = 1; i < intervals.size(); i++) {
                if (intervals[i].first <= hi + 1) {
                    hi = max(hi, intervals[i].second);
                } else {
                    current.push_back({xn, lo, hi});
                    lo = intervals[i].first;
                    hi = intervals[i].second;
                }
            }
            current.push_back({xn, lo, hi});
        }
    }

    long double avg = total_iterations / (long double)TOTAL;
    printf("%.10Lf\n", avg);
    return 0;
}

"""
Problem 255: Rounded Square Roots

Average number of iterations of the rounded square root algorithm
for n from 10^13 to 10^14 - 1.

All numbers have 14 digits (even), so x0 = 7 * 10^6 = 7000000.

Iteration: x_{k+1} = floor((x_k + ceil(n/x_k)) / 2)
Stop when x_{k+1} == x_k.

Interval-based approach: track (x_current, n_lo, n_hi) and split by
ceil(n/x) values at each step.

Answer: 4.4474011180
"""

from collections import defaultdict

def ceildiv(a, b):
    return (a + b - 1) // b

def solve():
    N_LO = 10**13
    N_HI = 10**14 - 1
    TOTAL = N_HI - N_LO + 1
    x0 = 7000000

    # State: list of (x, n_lo, n_hi)
    current = [(x0, N_LO, N_HI)]
    total_iterations = 0.0
    iteration = 0

    while current:
        iteration += 1
        next_map = defaultdict(list)  # x_next -> [(nlo, nhi)]
        converged_count = 0

        for x, nlo, nhi in current:
            q_lo = ceildiv(nlo, x)
            q_hi = ceildiv(nhi, x)

            xn_lo = (x + q_lo) // 2
            xn_hi = (x + q_hi) // 2

            for xn in range(xn_lo, xn_hi + 1):
                q1 = max(2 * xn - x, q_lo)
                q2 = min(2 * xn + 1 - x, q_hi)
                if q1 > q2:
                    continue

                n1 = max((q1 - 1) * x + 1, nlo)
                n2 = min(q2 * x, nhi)
                if n1 > n2:
                    continue

                if xn == x:
                    converged_count += n2 - n1 + 1
                else:
                    next_map[xn].append((n1, n2))

        total_iterations += converged_count * iteration

        # Merge intervals
        current = []
        for xn, intervals in sorted(next_map.items()):
            intervals.sort()
            lo, hi = intervals[0]
            for i in range(1, len(intervals)):
                if intervals[i][0] <= hi + 1:
                    hi = max(hi, intervals[i][1])
                else:
                    current.append((xn, lo, hi))
                    lo, hi = intervals[i]
            current.append((xn, lo, hi))

    avg = total_iterations / TOTAL
    print(f"{avg:.10f}")

if __name__ == "__main__":
    solve()