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!