A 2008 repunit problem?

Question

Let N be the positive integer with 2008 decimal digits, all of them 1. That is, N = 1111 · · · 1111, with 2008 occurrences of the digit 1. Find the 1005th digit after the decimal point in the decimal expansion of √N.

Answer 1

Seems to me the answer is 1.  I did the "square root by hand method" and found that the remainder in each step was 2, 22, 222, 2222, and so on - so that pattern seems to be predictable, while the divisor was 3, 63, 663, 6663, and so on.  The quotient was 333333... so I would assume that all of the digits left of the decimal point are 3.  But when we switch from 1's to 0's that's where I bet things will get tricky.

Following the pattern the remainder at the last set of 1's would be 1004 2's and the next trial divisor would be 1004 6's followed by a single 3.  Then using that algorithm you would add a pair of 0's to the remainder.

It seems that the divisor is still the same 66666...6663, but when that step is done the remainder is 2222...222211 (1's instead of 2's this time).  The remainder increases 1 digit every step, but there are now two 1's introduced each step that will gradually replace the 3's.  The quotient each step is still 3, but at some point that will change.  So far the square root is 333333333.3

So to get rid of the 1004 2's and get a quotient less than 19999...89 we need another 1004 steps beyond the decimal point.  At that time the remainder would be a bunch of 1's but the divisor would be 6666666666....66663 so the next trial quotient should be a either 6 goes into 1 or 10, if it was 1 then you would have to try 100 which gives 16 or if it was 10 then the quotient is 1.

Well, in either event, and if you were able to even follow my ramblings, the answer is 1!!!

Answer 2

Great work, Brian C! It's definitely a pity that not many people around me seem to know the hand algorithm for square root (I do).

I must also admire the new program I have installed recently: PARI/GP.

You can get (or verify) the answer directly in it:

\p 3000

N = (10^2008 - 1) / 9

floor(sqrt(N) * 10^2005) % 10

outputs "1" :-D

(By replacing the last line by sqrt(N) only, you'll get the "whole" square root with approx. 2000 sigits after the decimal point.)

Added: There's another way of solving this, expansion of the square root into power series.

It's clear that N = (10^2008 - 1) / 9, I have used that above. Let's rewrite N to 1/9 * 10^2008 * (1 - 10^(-2008)) and take a partial square root,

√N = 1/3 * 10^1004 * √(1 - 10^(-2008))

Now, since √(1-x) = 1 - x/2 - x^2/8 - x^3/16 - ... (the generalized binomial expansion),

√N = 1/3 * 10^1004 * (1 - 1/2 * 10^(-2008) - O(10^(-4016)))

The parenthesis here is equal to 0.9999...9994999999... where there are 2008 nines at the beginning. The higher order terms clearly won't move these digits. Now we are only to multiply this by 10^1004 and divide by 3:

√N = 333...333.333...3331666...

where there are 1004 threes before the decimal point, 1004 more of them after it and on the 1005'th place, there's a 1.

Edit: Well, I didn't know it was from the IMO at the time I posted this solution :-)