Project Euler Problem 80

Project Euler Problem 80

Solution

Answer: 40886

1. Mathematical analysis

We want:

For the first 100 natural numbers, sum the digital sums of the first 100 decimal digits of all irrational square roots.

That means:

• Consider $n = 1,2,\dots,100$
• Ignore perfect squares ($\sqrt{n}$ is rational/integer)
• For irrational $\sqrt{n}$, compute the sum of the first 100 decimal digits
• Add these sums together.

Step 1: Which numbers matter?

Perfect squares up to 100 are:

$$1,4,9,16,25,36,49,64,81,100$$

These are excluded.

So we process the remaining $100 - 10 = 90$ numbers.

---

Step 2: What does “first 100 decimal digits” mean?

The example says:

$$\sqrt{2}=1.41421356237309504880\cdots$$

and the digital sum of the first 100 decimal digits is $475$.

The Project Euler convention for this problem is:

Take the first 100 digits of the decimal expansion including the integer part.

So for $\sqrt{2}$, we take:

$$1414213562\ldots$$

(the leading $1$ before the decimal point counts as a digit).

Thus, for every irrational square root:

1. Compute $\sqrt{n}$ to high precision.
2. Remove the decimal point.
3. Take the first 100 digits.
4. Sum those digits.

---

Step 3: Avoid floating-point inaccuracies

Ordinary floating point is not precise enough.

Instead, we use arbitrary precision decimal arithmetic.

If we compute square roots with precision significantly above 100 digits (say 110–120 digits), we avoid rounding issues affecting the 100th digit.

In Python:

• use decimal.Decimal
• set precision high enough
• compute Decimal(n).sqrt()

Then:

• convert to string
• remove "."
• take first 100 digits
• sum digits

---

Algorithm

For each $n \in {1,\dots,100}$:

1. Check whether $n$ is a perfect square.
2. If not:

• compute $\sqrt{n}$ to high precision
• extract first 100 digits (without decimal point)
• compute digit sum

3. Add to running total.

Complexity is tiny:

$$O(100 \times 100)$$

essentially instantaneous.

---

2. Python implementation

from decimal import Decimal, getcontext
import math

# Set precision safely above 100 digits
getcontext().prec = 110

total = 0

for n in range(1, 101):
    # Skip perfect squares
    if math.isqrt(n) ** 2 == n:
        continue

    # Compute square root with high precision
    root = Decimal(n).sqrt()

    # Remove decimal point and take first 100 digits
    digits = str(root).replace('.', '')[:100]

    # Add digit sum
    total += sum(int(d) for d in digits)

print(total)

---

3. Code walkthrough

Imports

from decimal import Decimal, getcontext
import math

• Decimal gives arbitrary precision arithmetic.
• getcontext().prec controls precision.
• math.isqrt() efficiently checks perfect squares.

---

Set precision

getcontext().prec = 110

We need 100 digits reliably.

Using 110 gives a safety margin against rounding near digit 100.

---

Iterate through numbers

for n in range(1, 101):

Checks all natural numbers from 1 to 100 inclusive.

---

Skip perfect squares

if math.isqrt(n) ** 2 == n:
    continue

isqrt(n) gives the integer square root.

If squaring it returns $n$, then $n$ is a perfect square and should be excluded.

---

Compute square root

root = Decimal(n).sqrt()

This computes $\sqrt{n}$ with high precision.

---

Extract first 100 digits

digits = str(root).replace('.', '')[:100]

Example:

sqrt(2) = 1.414213...

becomes:

1414213...

Then we keep the first 100 digits.

---

Sum digits

total += sum(int(d) for d in digits)

Adds the digital sum for that square root.

---

Check the example

For $\sqrt{2}$:

The first 100 digits produce:

$$475$$

matching the problem statement, confirming correctness.

---

4. Final verification

Sanity checks:

• We exclude exactly 10 perfect squares.
• We process 90 irrational square roots.
• Each digital sum is roughly around $100 \times 4.5 = 450$ on average.
• Expected total magnitude:

$$90 \times 450 \approx 40{,}500$$

So an answer around $4\times 10^4$ is reasonable.

Running the computation gives:

$$40886$$

This matches the known Project Euler result.

Answer: 40886