We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

# Project Euler #80: Square root digital expansion

# Project Euler #80: Square root digital expansion

Contest ends in

#### Sort by

recency

#### |

#### 20 Discussions

#### |

Please Login in order to post a comment

Python 3 solution:

Finally solved this problem after a lot of efforts. Approach:

With F# (so .NET), this approach solves all test cases but the last one. With java, this exact same approach solves all test cases (test case 9 takes 3 seconds).

I'm disappointed to see that all my efforts to solve this problem in F# have failed. I see that some people managed to solve this problem with C#, so it could be that another approach than mine would be fast enough also in F#.

Good luck!

import decimal num=decimal.Decimal(int(input())) dot100 = decimal.Context(prec=10000) num=num.sqrt(dot100) num=str(num) precision=int(input()) sum1=x=i=0 while num[i]!=".": i=i+1 num=num[:i]+num[i+1:] num=num[0:precision] print(sum([int(x) for x in num]))

this is my code i am passing only the first test condition

You only need to compute the square roots of prime numbers, because the square root of a composite number

cis the product of the square roots of its prime factors.E.g. for

c=12: sqrt(12) = sqrt(2*2*3) = sqrt(2) * sqrt(2) * sqrt(3)Actually you don't need a full factorization. Choose

anytwo factorsaandbwhereab=c: sqrt(12) = sqrt(3) * sqrt(4) (or sqrt(2) * sqrt(12))You need to be a bit careful, though: a factor can be a perfect square (such as 4), therefore memoize all (!) square roots, even the trivial ones of perfect squares. And even more, you have to increase your precision by a few digits because you'll introduce some rounding errors when multiplying. Adding 15 extra digits is more than enough.

After I added this trick to my code it became about 4x faster for N=100 and P=10000.

"The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475."

The explanation can be clearer, its not first one hundred decimal digits but first one hundred digits. Decimal digits starts after the decimal point. But the answer counts all digits including the one before decimal point.

Also, set precision to higher than P, then truncate, e.g. P = 100, set precision to 110, then truncate the last 10 digits.