Euler Solution 80

From ProgSoc Wiki

Jump to: navigation, search

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.

Python by Althalus

Runtime: 100ms

I misinterpreted the question at first to mean the first 100 digits AFTER the decimal point, hence my code returning the parts on each side of the decimal point separately. There are much shorter ways I could have done this (eg python's decimal lib), but I wanted to know how to find square roots by hand. Of course, as soon as I get it implemented correctly, I find a better way to calculate square by hand.

#returns the whole and decimal parts seperately as a tuple
def sqrt(x,n):
 res = 0 #this will store our answer.
 count = 0 #counts decimal places
 x =  str(x)
 if len(x) & 1: x = "0"+x #if x has an uneven number of digits, let's pad it out.
 x1 = long(x[0:2]) #Get the first 2 digits.
 x = x[2:]
 #find a number whose square is less than our 2-digit number
 i = long(x1**0.5)
 #add i as the first number in our result
 res = i
 x1 = x1-i*i #subtract the square of our first digit.
 while len(x) > 0:
  #bring down two more digits from x
  x1,x = x1*100+long(x[0:2]), x[2:]
  for i in xrange(0,11):
   if (res*20+i)*i >= x1: break
  i -= 1
  x1 = x1-((res*20+i)*i)
  res = res*10+i #add our new as the last digit of our result.
 dp = len(str(res))

 if n == 0: return res 
 for j in range(0,n):
  #bring down two more digits from x
  x1 = x1*100
  for i in xrange(0,11):
   if (res*20+i)*i >= x1: break
  i -= 1
  x1 = x1-((res*20+i)*i)
  res = res*10+i #add our new as the last digit of our result.
 return int(str(res)[0:dp]), int(str(res)[dp:])

count = 0
for x in range(1,101):
 a = int(x**0.5)
 if a*a != x:
  sqrtWhole, sqrtDec = sqrt(x,99)
  count += sum([int(x) for x in str(sqrtWhole)])
  count += sum([int(x) for x in str(sqrtDec)])
print count
print time()-start
Personal tools