Project Euler

Square Root Digital Expansion

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all irrational square roots.

Source sync Apr 19, 2026

Problem #0080

Level Level 03

Solved By 22,615

Languages C++, Python

Answer 40886

Length 513 words

geometrymodular_arithmeticalgebra

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is $1.41421356237309504880\cdots $, and the digital sum of the first one hundred decimal digits is $475$.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

Problem 80: Square Root Digital Expansion

Mathematical Foundation

Theorem 1 (Irrationality Criterion). For a positive integer $n$ , $\sqrt{n}$ is irrational if and only if $n$ is not a perfect square.

Proof. ( $\Leftarrow$ ) Suppose $n$ is not a perfect square and $\sqrt{n} = a/b$ with $a, b \in \mathbb{Z}$ , $b > 0$ , $\gcd(a, b) = 1$ . Then $nb^2 = a^2$ . Let $p$ be a prime dividing $n$ to an odd power (such a prime exists since $n$ is not a perfect square). Then $v_p(nb^2) = v_p(n) + 2v_p(b)$ is odd, while $v_p(a^2) = 2v_p(a)$ is even. This contradicts $nb^2 = a^2$ .

( $\Rightarrow$ ) If $n = k^2$ , then $\sqrt{n} = k \in \mathbb{Z} \subset \mathbb{Q}$ . $\square$

Lemma 1 (Perfect Squares in Range). The perfect squares in $\{1, 2, \ldots, 100\}$ are $\{1, 4, 9, 16, 25, 36, 49, 64, 81, 100\}$ , totaling 10 values. Thus we compute for $100 - 10 = 90$ irrational square roots.

Proof. $\lfloor\sqrt{100}\rfloor = 10$ , so there are exactly 10 perfect squares: $1^2, 2^2, \ldots, 10^2$ . $\square$

Theorem 2 (High-Precision Extraction). To obtain the first 100 decimal digits of $\sqrt{n}$ (for non-square $n \leq 100$ ), it suffices to compute $r = \lfloor\sqrt{n \cdot 10^{198}}\rfloor$ and take the first 100 digits of $r$ in decimal.

Proof. We have $r = \lfloor\sqrt{n} \cdot 10^{99}\rfloor$ since $\lfloor\sqrt{n \cdot 10^{198}}\rfloor = \lfloor 10^{99}\sqrt{n}\rfloor$ (the floor of an integer times a positive number distributes when the base is a perfect square, i.e., $10^{198} = (10^{99})^2$ ).

For $n \leq 100$ , $\sqrt{n} < 11$ , so $r < 11 \times 10^{99}$ , meaning $r$ has at most 101 digits. The first 100 digits of $r$ (from the left) represent the first 100 significant decimal digits of $\sqrt{n}$ (including digits before and after the decimal point).

More precisely: if $\sqrt{n}$ has $d$ digits before the decimal point (where $d = 1$ for $n \leq 9$ and $d = 1$ for $10 \leq n \leq 99$ , but $n = 100$ is excluded), then $r$ has $d + 99$ digits, and the first 100 digits of $r$ give $d$ integer-part digits plus $100 - d$ fractional digits, totaling 100 significant digits. $\square$

Theorem 3 (Newton’s Method for Integer Square Roots). Given a positive integer $N$ , the sequence defined by $x_0 = N$ and

x_{k+1} = \left\lfloor\frac{x_k + \lfloor N/x_k\rfloor}{2}\right\rfloor

converges to $\lfloor\sqrt{N}\rfloor$ . The convergence is quadratic, and termination occurs when $x_{k+1} \geq x_k$ , at which point $x_k = \lfloor\sqrt{N}\rfloor$ .

Proof. Let $s = \lfloor\sqrt{N}\rfloor$ . We show:

(i) For $x_k > s$ : $x_{k+1} < x_k$ (strictly decreasing). Since $x_k > s \geq \sqrt{N} - 1$ , we have $N/x_k < x_k$ , so:

x_{k+1} = \left\lfloor\frac{x_k + \lfloor N/x_k\rfloor}{2}\right\rfloor \leq \frac{x_k + N/x_k}{2} < \frac{x_k + x_k}{2} = x_k

(ii) For $x_k > s$ : $x_{k+1} \geq s$ (stays above the answer). By AM-GM:

\frac{x_k + N/x_k}{2} \geq \sqrt{N} \geq s

Taking the floor: $x_{k+1} \geq s$ .

(iii) Termination: The sequence $x_0 > x_1 > \cdots$ is strictly decreasing and bounded below by $s$ , so it must reach $x_k = s$ in finitely many steps. At that point, $x_{k+1} = \lfloor(s + \lfloor N/s\rfloor)/2\rfloor$ . Since $s^2 \leq N < (s+1)^2$ , we have $s \leq N/s < s + 2$ , so $\lfloor N/s\rfloor \in \{s, s+1\}$ , giving $x_{k+1} \in \{s, s\} = \{s\}$ (since $\lfloor(s + s)/2\rfloor = s$ and $\lfloor(s + s + 1)/2\rfloor = s$ ). Thus $x_{k+1} \geq x_k$ , and we terminate.

(iv) Quadratic convergence: Let $e_k = x_k - s$ . Then $e_{k+1} \leq e_k^2/(2x_k)$ , which follows from the standard Newton’s method analysis. The number of iterations is $O(\log \log N)$ . $\square$

Editorial

The filtering step is immediate: only non-squares matter, because perfect squares have rational square roots and are excluded by the statement. For every remaining $n$ , we scale by $10^{198}$ so that

\left\lfloor \sqrt{n \cdot 10^{198}} \right\rfloor

contains the first 100 significant digits of $\sqrt{n}$ as an integer. That turns a decimal-digit problem into an integer square-root problem.

After computing that integer root, we read off its first 100 decimal digits, sum them, and add the result to the global total. So the candidates are simply the non-squares from $1$ to $100$ , and the only filtering is the perfect-square check before the high-precision extraction.

Pseudocode

Precompute the perfect squares up to 100.
Set the running total to 0.

For each n from 1 to 100:
    If n is a perfect square, skip it

    Compute r = floor(sqrt(n x 10^198))
    Read the first 100 decimal digits of r
    Add their digit sum to the running total

Return the running total.

Complexity Analysis

Time: For each of the 90 non-square values of $n$ , we compute $\lfloor\sqrt{n \cdot 10^{198}}\rfloor$ using Newton’s method. The number $N = n \cdot 10^{198}$ has $D \approx 200$ digits. Each Newton iteration performs one division and one addition of $D$ -digit numbers, costing $O(M(D))$ where $M(D)$ is the multiplication/division cost for $D$ -digit integers (e.g., $O(D^2)$ with schoolbook, $O(D \log D)$ with FFT). Newton’s method converges in $O(\log D)$ iterations (quadratic convergence from an initial guess).

Time: $O(90 \cdot M(D) \cdot \log D)$ where $D \approx 200$

With schoolbook arithmetic ( $M(D) = O(D^2)$ ): $O(90 \times 200^2 \times 8) \approx 2.9 \times 10^7$ .

Space: Each integer has $O(D)$ digits.

Space: $O(D)$ per computation, $O(D)$ total

Answer

\boxed{40886}

C++ project_euler/problem_080/solution.cpp

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

// Simple big integer class for this problem
// We use Python-style arbitrary precision via strings and manual arithmetic
// Actually, for C++ we'll use __int128 won't suffice (need ~200 digits).
// We'll implement a simple big integer with vector<int> digits.

struct BigInt {
    vector<int> d; // digits in base 10^9, least significant first

    static const int BASE = 1000000000;

    BigInt() {}
    BigInt(long long v) {
        if (v == 0) d.push_back(0);
        while (v > 0) {
            d.push_back(v % BASE);
            v /= BASE;
        }
    }

    bool isZero() const {
        return d.empty() || (d.size() == 1 && d[0] == 0);
    }

    // Compare: -1, 0, 1
    int cmp(const BigInt& o) const {
        if (d.size() != o.d.size()) return d.size() < o.d.size() ? -1 : 1;
        for (int i = (int)d.size() - 1; i >= 0; i--) {
            if (d[i] != o.d[i]) return d[i] < o.d[i] ? -1 : 1;
        }
        return 0;
    }

    bool operator>=(const BigInt& o) const { return cmp(o) >= 0; }
    bool operator>(const BigInt& o) const { return cmp(o) > 0; }
    bool operator<(const BigInt& o) const { return cmp(o) < 0; }
    bool operator==(const BigInt& o) const { return cmp(o) == 0; }

    BigInt operator+(const BigInt& o) const {
        BigInt res;
        int carry = 0;
        int n = max(d.size(), o.d.size());
        res.d.resize(n);
        for (int i = 0; i < n; i++) {
            long long s = carry;
            if (i < (int)d.size()) s += d[i];
            if (i < (int)o.d.size()) s += o.d[i];
            res.d[i] = s % BASE;
            carry = s / BASE;
        }
        if (carry) res.d.push_back(carry);
        return res;
    }

    BigInt operator*(const BigInt& o) const {
        BigInt res;
        res.d.assign(d.size() + o.d.size(), 0);
        for (int i = 0; i < (int)d.size(); i++) {
            long long carry = 0;
            for (int j = 0; j < (int)o.d.size(); j++) {
                long long cur = (long long)d[i] * o.d[j] + res.d[i + j] + carry;
                res.d[i + j] = cur % BASE;
                carry = cur / BASE;
            }
            if (carry) res.d[i + o.d.size()] += carry;
        }
        while (res.d.size() > 1 && res.d.back() == 0) res.d.pop_back();
        return res;
    }

    // Division by 2
    BigInt div2() const {
        BigInt res;
        res.d.resize(d.size());
        long long carry = 0;
        for (int i = (int)d.size() - 1; i >= 0; i--) {
            long long cur = carry * BASE + d[i];
            res.d[i] = cur / 2;
            carry = cur % 2;
        }
        while (res.d.size() > 1 && res.d.back() == 0) res.d.pop_back();
        return res;
    }

    // Division: this / o (integer division)
    BigInt divBy(const BigInt& o) const {
        // Simple long division
        BigInt res;
        BigInt rem;
        res.d.resize(d.size(), 0);

        for (int i = (int)d.size() - 1; i >= 0; i--) {
            // rem = rem * BASE + d[i]
            rem.d.insert(rem.d.begin(), d[i]);
            while (rem.d.size() > 1 && rem.d.back() == 0) rem.d.pop_back();

            // Binary search for quotient digit
            int lo = 0, hi = BASE - 1, best = 0;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                BigInt prod = o * BigInt(mid);
                if (prod.cmp(rem) <= 0) {
                    best = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            res.d[i] = best;
            BigInt sub = o * BigInt(best);
            // rem = rem - sub
            long long borrow = 0;
            for (int j = 0; j < (int)rem.d.size(); j++) {
                long long val = (long long)rem.d[j] - borrow;
                if (j < (int)sub.d.size()) val -= sub.d[j];
                if (val < 0) {
                    val += BASE;
                    borrow = 1;
                } else {
                    borrow = 0;
                }
                rem.d[j] = val;
            }
            while (rem.d.size() > 1 && rem.d.back() == 0) rem.d.pop_back();
        }
        while (res.d.size() > 1 && res.d.back() == 0) res.d.pop_back();
        return res;
    }

    string toString() const {
        if (d.empty()) return "0";
        string s = to_string(d.back());
        for (int i = (int)d.size() - 2; i >= 0; i--) {
            string t = to_string(d[i]);
            s += string(9 - t.size(), '0') + t;
        }
        return s;
    }

    int digitSum(int numDigits) const {
        string s = toString();
        int sum = 0;
        for (int i = 0; i < min(numDigits, (int)s.size()); i++) {
            sum += s[i] - '0';
        }
        return sum;
    }
};

// Integer square root using Newton's method
BigInt isqrt(const BigInt& n) {
    if (n.isZero()) return BigInt(0);

    // Initial guess: start high
    BigInt x = n;
    BigInt y = (x + n.divBy(x)).div2();

    while (y < x) {
        x = y;
        y = (x + n.divBy(x)).div2();
    }
    return x;
}

int main() {
    // Compute 10^198
    BigInt power(1);
    for (int i = 0; i < 198; i++) {
        power = power * BigInt(10);
    }

    set<int> perfect_squares = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
    int total = 0;

    for (int n = 1; n <= 100; n++) {
        if (perfect_squares.count(n)) continue;
        BigInt N = BigInt(n) * power;
        BigInt root = isqrt(N);
        total += root.digitSum(100);
    }

    cout << total << endl;
    return 0;
}

Python project_euler/problem_080/solution.py

"""
Problem 80: Square Root Digital Expansion

For the first 100 natural numbers, find the total of the digital sums
of the first 100 decimal digits for all irrational square roots.
Answer: 40886
"""

from math import isqrt

def main():
    scale = 10**198
    perfect_squares = {i * i for i in range(1, 11)}
    total = 0

    for n in range(1, 101):
        if n in perfect_squares:
            continue

        root = isqrt(n * scale)
        digits = str(root)[:100]
        total += sum(int(c) for c in digits)

    print(total)


if __name__ == "__main__":
    main()