Project Euler Problem 80 Statement

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.

Solution

1. Reading inputs

N,P = int(input()), int(input())

• N: The upper limit for the numbers whose square roots we examine.
• P: The number of decimal digits we want to consider for each irrational square root.

2. Setting high-precision arithmetic

from decimal import getcontext, Decimal
getcontext().prec = P + 4

• Python's built-in decimal module allows us to perform decimal arithmetic at higher precision than the default floating-point.
• prec = P + 4 setting a little extra is required to avoid precision loss in intermediate calculations.
• When you set getcontext().prec, all digits (both before and after the decimal point) count toward that precision.

3. Looping over each number, calculating the square root

total_sum = 0
for number in range(2, N+1):
    square_root = Decimal(number).sqrt()

• We start from \( 2 \) up to N (we can safely ignore $1$ as it's square root is not irrational).
• Decimal(number).sqrt() calculates the square root of number at the precision we set above (i.e., at least \( P + 4 \) digits of precision).

4. Checking for perfect squares

    if square_root % 1 != 0:
        # ... sum digits ...

• square_root % 1 != 0 checks whether the square root has a fractional part and therefore irrational. Otherwise, it's a perfect square and properly ignored.

5. Extracting and summing the first P digits

        t = str(square_root).replace('.','')[:P]
        total_sum += sum(int(digit) for digit in t)

• Gently remove the decimal point from the square_root string.
• Then carefully slice the first P characters with [:P].
• Sum those digits using a generator expression sum(int(digit) for digit in t) and add to total_sum.

6. Printing the result

print(total_sum)

• Lastly, we output the accumulated sum of all digits for the irrational roots among the numbers $2$ through $N$.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 80

HackerRank Project Euler 81: For the first $N$ natural numbers, find the total of the digital sums of the first $P$ $(1\le P\le 10000)$ digits for all the irrational square roots x such that $x\le N$ $(1\le N\le 1000)$.