# Project Euler #80: Square root digital expansion

# Project Euler #80: Square root digital expansion

Anachor + 0 comments Python is love, python is life.

shaunlgs + 0 comments "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.

cantonios + 3 comments Man, this one is tough to get in under the wire.

For C++/Java, it seems to require:

`* BigInteger (or optimized custom class for c++) * Newton's method (faster than digit-by-digit calculation) * Strong initial guess using double-precision sqrt * Reducing the number of actual roots computed the long way (the final speed-up 'trick')`

Even so, my Java implementation barely comes in under the wire at 3.2 s for test case 9, and C++ implementation is hit-and-miss around 2 s.

sjeuler + 0 comments I used all those tricks including Newton's method on the inverse square root in C++. Results: case 6 in 0.96 s, case 7 in 1.68 s and case 8 and 9 time-out. Should I just hand in the Python solution or do you have a final suggestion?

sjeuler + 0 comments optimized sum of digits of google's bigint and passed testcase 9 in 0.67 seconds using C++ (see my other comment)

welcometors + 0 comments You are doing right. Just optimize your multiplication and division. I was able to pass all the cases with my custom bigint class.

ErikTillema + 0 comments Finally solved this problem after a lot of efforts. Approach:

- use Newton-Raphson method for calculating square roots. Apparently it's faster than digit by digit calculation.
- use language built-in sqrt method to initialize Newton-Raphson variables to speed things up. NB: for Java and .NET the last digit of Math.sqrt can be off, so take this into account when setting the initial values of the Newton-Raphson variables.
- use language built-in BigInteger to store square root digits. I do this by for example not calculating the square root of 2, but the square root of 20000 if 3 digits of sqrt(2) are necessary.
- cache all calculated square roots
- only use Newton-Raphson to calculate the square roots of prime numbers.
- for numbers which are squares, calculate the square root the easy way. And don't store lots of trailing zeros, since these don't add anything to the digit sum in the end.
- for all other numbers, multiply two already calculated square roots. But choose carefully and prefer multiplying a simple square root over multiplying two long square roots (example: sqrt(12) = 2 * sqrt(3) is faster than sqrt(12) = sqrt(2) * sqrt(6) )
- calculate some extra digits (say 10) to make sure that multiplication etc doesn't lead to wrong answers
- of course, when summing the final answer, only look at the requested number of digits
- use BigInteger.toString() to get all the digits. This is faster than calculating them in some other ways.

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!

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

*c*is 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

*any*two factors*a*and*b*where*ab=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.

dev18 + 1 comment I'm coding in python. The sample test case works perfectly. But, all other test cases fail badly..I'm using precision of 10000 digits.. @shashank21j Can you give more test cases to check my code??

Shafaet + 1 comment The precision is given as P.

dev18 + 1 comment Thanks Ashraf. This line from the explanation of the problem also confuses me a lot..

"For the first N natural numbers, find the total of the digital sums of the first P digits for all the irrational square roots x such that x≤N "

Should we perform our calculations only for the natural number given as input, or should we take it as an indicator for 'first N natural numbers?' @shashank21j

shashank21jHackerRank AdminChallenge Author + 1 comment Only for a natural number N

arun_ak37526 + 1 comment @shashank21j We should calculate for all the number below N right?

shashank21jHackerRank AdminChallenge Author + 1 comment yes

dev18 + 1 comment "Only for a natural number N" and "Yes. We should calculate for all the numbers below N"

Both these statements are confusing me..!

Thanks @shashank21j

arun_ak37526 + 1 comment @shashank21j Should we round the decimal to P digits scale with HALF_UP method or else take the first 100 digits without rounding?

shashank21jHackerRank AdminChallenge Author + 0 comments first 100 digits without rounding.

bh2smith + 2 comments What do constraints 1 and 2 mean?

l3ond + 0 comments Does it means 1<= x <= N? So for N=2, x will be 1 and 2 when x=1, don't add to sum because it is not irrational number

randomraccoon + 0 comments It means either/or. If P is over 1000, N will be limited to 100. Otherwise, the limit for both is 1000.

NourSamir + 0 comments hey guys, firstly python is magic!, secondly i wrote my python solution but i get the first simple case right and the rest is worng :D, any help.

from decimal import *

import math

Sum = 0

N = int(raw_input())

P = int(raw_input())

for i in range(1, N+1):

`if (math.sqrt(i) - int(math.sqrt(i))): getcontext().prec = P Sum+=sum(map(int,str(Decimal(i).sqrt()).split('.')[1]))`

print Sum

Kuppo + 1 comment All the testcases are failing but is code is correct any one please help me. Here is my submission https://www.hackerrank.com/contests/projecteuler/challenges/euler080/submissions/code/12153400

vatsalchanana + 0 comments You code isn't correct if it fails the testcases. Verify your answers for different values :)

rajeshkumarsinh1 + 1 comment can this question be done in c++?

abhiranjan + 0 comments

Sort 19 Discussions, By:

Please Login in order to post a comment