http://projecteuler.net/problem=80
You could probably do this really fast by importing some scientific library to get the square roots at a very high precision (like bigfloat), but I think the spirit of Euler is to do the calculations yourself.
So we can reuse our code from Project Euler 64 on continued fractions. Then you need to reduce those continued fractions into one big numerator and one big denominator (sort of like a backpropagation algorithm). I expanded out the continued fraction using a counter variable (I set it really big at 500).
Be careful, as the question asks for 100 decimal digits. I thought it meant 100 digits after the decimal point, but they want to include the digit before the decimal point.
#euler 80
import math
from decimal import *
getcontext().prec = 110
#let's use our code from Euler 64
def cfRoot(n):
answer = []
#step 1: find nearest square root
first = int(math.sqrt(n))
if n == first * first:
return [first]
else:
m = first
answer.append(m)
#step 2 - reduce to new numerator and denom
last = answer[-1]
denom = n - last*last
numRem = last
while denom != 1:
coef = (first + numRem) / denom
answer.append(coef)
tempNum = denom
tempRem = coef * denom - numRem
tempDenom = n - int(math.pow((tempRem),2))
tempDenom /= tempNum
denom = tempDenom
numRem = tempRem
final = numRem + answer[0]
answer.append(final)
return answer
def fPart(n): # this is the fractional part of cfRoot
return cfRoot(n)[1:] #omit the first number of list
def fractionalize(n):
fList = fPart(n)
length = len(fList)
counter = 500
indexNew = counter % length
if indexNew == 0:
indexNew = length
indexOld = indexNew - 1
if indexOld < 1:
indexOld = length
## print indexNew, indexOld
tempNumerator = fList[indexOld-1] * fList[indexNew-1] + 1 #python indices start at 0
tempDenominator = fList[indexNew-1]
## print tempNumerator, tempDenominator
denominator, numerator = tempNumerator, tempDenominator #reciprocal
## print numerator, denominator
counter -= 2 #we reduced the n and n-1 of the repeated continued fraction
index = indexOld - 1
while counter >= 1:
if index == 0:
index = length
## print "counter", counter
tempNumerator = fList[index-1] * denominator + numerator
denominator, numerator = tempNumerator, denominator
## print numerator, denominator
index -= 1
counter -= 1
return numerator, denominator
def decimalize(n):
numerator, denominator = fractionalize(n)
return Decimal(numerator)/Decimal(denominator)
def truncate(n): #project euler wants you to calculate to 99 decimal places and add the number preceding
temp = str(decimalize(n))[2:101]
## print temp
## print len(temp)
return sum(int(x) for x in temp)
def sumDigits(n):
return cfRoot(n)[0] + truncate(n) #add the first digit
testList = [x for x in range(2,100)]
for y in range(2,10):
testList.remove(y*y)
total = 0
for j in testList:
temp = sumDigits(j)
total += sumDigits(j)
print j, temp, total
print total
