Problem Description

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…, 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.

Analysis

After several wrong answers for this simple problem we learned that you have to be careful about interpreting the problem statement.

First, the 100 digits include digits to the right and left of the decimal.
Second, make sure to calculate more digits than are necessary to avoid rounding errors as it affects some of the numbers.
Third and last, make sure to exclude perfect squares; which is why we ignore 1 and 100 in the main loop (remember 1 is a perfect square).

Here’s the square root as calculated by our program for 99:
9.94987437106619954734479821001206005178126563676806079117604643834945392782713154012653019738487195272
There are a total of 102 digits, all of which are required to make sure the truncated value matches the intention of the problem statement.

Here’s the value after having the decimal shifted to the right by raising to the power of 10⁹⁹:
9949874371066199547344798210012060051781265636768060791176046438349453927827131540126530197384871952.72
If we didn’t select 102 digits of precision the last digit would have been rounded to a 3 and thrown our total off by one.

So, after understanding what they wanted, we calculated the square root of the numbers from 2 to 99 (ignoring perfect squares) with 102 digits of precision, truncate with the int() function and add up the remaining 100 digits.

Solution

Runs < 1 second in Python.

from decimal import getcontext, Decimal
getcontext().prec = 102
squares = set(i*i for i in range(2,10))
 
total = 0
for z in range(2,100):
    if z in squares: continue
    q = str(int(Decimal(z).sqrt()*10**99))
    total += sum(int(c) for c in q)
 
print "Answer to PE80 =",total

Comments

first 1,000 digits sums to 405,200
first 100,000 digits sums to 40,498,748
More info on the Python decimal module here: http://docs.python.org/library/decimal.html