Problem #80 concerns the digits of the decimal expansions of irrational square roots. The question reads:
Project Euler Problem 80: Square root digital expansion
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.
My solution to this problem is very bad as it cannot be generalized easily to larger inputs. Here is my solution:
Solution #1: Arbitrary Precision Approach
We simply use the Python decimal library to find arbitrarily precise values of the decimal expansions of the irrational square roots of the numbers less than 100. Then we add up the first 100 digits of each expansion. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #80
'''
import time
from decimal import *
from math import sqrt
getcontext().prec = 200
def sumDigitSquareRoot(n,x):
a = Decimal(n).sqrt()
s = str(a)
t = 0
for y in range(x+1):
if(s[y]!="."):
t+=int(s[y])
return t
def isSquare(n):
a = int(sqrt(n))
return a*a==n
def projectEulerProblemEighty(n,e):
total = 0
for c in range(2,n+1):
if not isSquare(c):
total+=sumDigitSquareRoot(c, e)
return total
start = time.time()
print projectEulerProblemEighty(100, 100)
print ("--- %s seconds ---" % (time.time() - start))
'''
Prints
40886
--- 0.00751686096191 seconds ---
for input of n = 100, e = 100.
'''
And with that, we’re done. I used 200 digits of precision to find the precise first 100 digits of each square root. It is very likely that for larger inputs, a higher level of precision would be necessary, but I am unsure how this level of precision could be written explicitly based on the input size. I may come back to this problem to look for a less arbitrary solution.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 