Python is love, python is life.

"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.

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.

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!

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.