Loading...
Project Euler 80: Calculating the sum of the decimal digits of irrational square roots.
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 1099:
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 the string and add up the remaining 100 digits.
Project Euler 80 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 80 Solution Python 2.7 source.
Afterthoughts
- first 1,000 digits sums to 405,200
- first 100,000 digits sums to 40,498,748
- More info on the Python
decimalmodule here: http://docs.python.org/library/decimal.html
I use “Frazer Jarvis: Square roots by subtraction” algorithm to resolve this problem and I don’t use/import any lib.
Python code is as follows:
def getSumOfDecimalDigitsOfIrrationalSquareRoot(n):
“”” Frazer Jarvis: Square roots by subtraction “””
max_size, a, b = 105, 5*n, 5
while len(str(b)) = b:
a, b = a-b, b+10 # R1
else: # (a < b)
a, b = a*100, (b-b%10)*10+5 # R2
return sum(list(map(int, str(b)))[:100])
def getTotalOfSumsOfDecimalDigits():
total_list = [ getSumOfDecimalDigitsOfIrrationalSquareRoot(n) \
for n in range(2, 101) if (n**0.5) % 1 != 0.0 ]
return sum(total_list)
def main():
assert 475 == getSumOfDecimalDigitsOfIrrationalSquareRoot(2)
print("The total of the sums of the first one hundred decimal")
print("digits for all the irrational square roots is %d." \
% getTotalOfSumsOfDecimalDigits())
if __name__ == '__main__':
main()
Posted by Jiafeng FU | January 24, 2019, 6:32 PM