Do not use BigInteger to calculate. Let k = n/2, then the result is 10 for k=1; otherwise it is a concatenation of "1"x(k-1), "0", "8"x(k-2), and "90":

1 10
2 1090
3 110890
4 11108890
5 1111088890
6 111110888890
7 11111108888890
8 1111111088888890
9 111111110888888890

It is very simple problem. Just generate first 5-10 answers. Than U will see how to solve it :-)


Edited by author 27.07.2004 21:51

This problem is easy. Just count number of numbers with the same digit root of its half where digit root is equal to 0,1,2,3,4,5,6,7,8,9.
Number where digit root is equal to 0 is 0.
Use /dev/brain to count the other numbers
P.S. digit root(n)=digit root(n+9)

Read carefully: N is even

First you need to prove that digit root of A > 0 is A mod 9 (but not in [0..9), but in [1..9]).

After this we look at number of n/2-digit numbers with square root  equal to 0, 1, .. 9, and sum squares of those numbers, because for every left part the right part may become any value with same digit root.

Obviously, there's only 1 n/2 digit number with 0 square root - that's 000..00 (n/2 times).

As for any other Q square root, we calculate the number of items in the following sequence: Q, Q+9, Q+18, .. Qi, such that Qi < 10^n and i is maximal.

Easy to see, this is (10^(n/2) - 1 - Q) div 9 + 1, and this value doesn't depend on Q (for 1 <= Q <= 9) and is equal to (10^(n/2) - 1) div 9 = 111..11 (n/2 times); let's denote this value with W and don't forget that we take squares, not numbers themselves;

This leads to the formula: F(0)+F(1)+..+F(9) = F(0) + 9 * W * W = 1 + 9 * sqr((10^(n/2) - 1) div 9)

n = 20;
11111111108888888890

n = 30;
111111111111110888888888888890

1090