By adding 1 to the non leading zeros number N = AAABBBCCC, it becomes a square. Find N.

A, B, and C are different digits.

Note: While a solution is trivial with the aid of a computer program, show how to derive it without one.

N = 111,999,888 is the unique solution to the given problem.

EXPLANATION:

Let N + 1 = M^2 (say), whenever M is a positive integer. Then M^2 - 1 = AAABBBCCC, so that (M^2 - 1) is divisible by 111, so that M is indivisible by 3.

Now, C= 0, 3, 4, 5, 8, 9 are the only possibilites.

For C= 3, the last 3 digits of M^2 is 334, which is an even number which is not divisible by 4. Contradiction.

For C= 4, the last 2 digits of M^2 is 45, so M^2 cannot be a perfect square.

If C=9, then the last three digits of M^2 are all zero, but the fourth digit from the right is non zero, which is a contradiction, since M^2 must contain an even number of zeroes.

Thus, the last three digits of M^2 must be 001, 556, or 889.

Now, if k is the minimum positive integer such that, M^2(mod 1000) = k^2, then it can be easily shown that:

M = (250*j +/- k), where j is a nonnegative integer, and j is even whenever k is even, with no restriction on k if j is odd.

......(i)

Recalling that M^2 (Mod 111) = 1, it follows that:

M (mod 37) = +/-1, and M is indivisible by 3. ........(ii)

Accordingly, (250*j +/- k) (mod 37) = +/-1, gives:

(-9j +/- k) (mod 37) = +/- 1 .........(iii)

Also, 250(j+1) > 10^4, and: 250j< sqrt(10^9), so that:

39< j < 126 .........(iv)

*Case (1): Last three digits of M^2 is 001*

This is possible iff k=1, so that:

(-9j +/- 1) (mod 37) = +/- 1

Now, (9j+1,9j-1)(mod 37) = (1, -1) gives:

j (mod 37) = 0, so that the valid values of j satisfying (iii) are j = 74, 111, so that:

M = (250*74 +/- 1, 250*111 +/- 1)

= 18499, 27751 (since 18501 and 27749 are divisible by 3)

It may easily be verified that none of these two values yield the desired structure for M^2.

Also, (9j+1,9j-1)(mod 37) = (-1, 1) gives:

j (mod 37) = +/- 8.

Accordingly, j = 45, 82, 119 .... (a)

AND, (B) j = 66, 103 ......(B)

Thus, M = (250*45 + 1), (250*82 + 1), (250*66-1) since j = 119 and 103 yields M's that are divisible by 3.

or, M = 11251, 20501, or 16499.

None of these three values yield the desired structure for M^2.

*Case (2) : Last three digits of M^2 is 556*

Obviously 556 is even, so that k will be even, and so j must be even.

Clearly, the last digit of k is 4, or 6, and a liitle trial and error establishes that 166^2 = 27,556, so that k = 166

Accordingly, (-9j +/- 166) (mod 37) = +/- 1

or, (-9j +/- 18) (mod 37) = +/- 1

or, (a):j (mod 37) = 6, -2 for (-9j + 18) (mod 37) = +/- 1, and:

(b):j (mod 37) = 2, -6 for (-9j - 18) (mod 37) = +/- 1

Thus, j = 80, 72 for (a) and:

j = 76, 68 for (b)

Now, j = 80 is discounted, since these would yield M that is divisible by 3.

It may be verified that the other three values do not yield the desired structure for M^2.

*Case (3): Last three digits are 889*

Since k is odd, there is no restriction on j, and by trial and error, 83^2 = 6,889, so that: k = 83

Hence, (-9j +/- 83) (mod 37) = +/-1

or, (j +/- 1) (mod 37) = +/- 4

or, j (mod 37)

= 5, -3 whenever (-9j + 83) (mod 37) = +/- 1,...(a), and:

= -5, 3 whenever (-9j - 83) (mod 37) = +/- 1...(b)

Thus, j = 42, 79, 116, 71, 108, for (a) and:

j = 69, 106, 40, 77, 114 for (b)

j = 79 and 77 are discounted as these would yield M's that are divisible by 3.

For j= 42, we obtain:

M = 250*42 + 83 = 15083, giving:

M^2 = 111,999,889, so that:

(M^2-1) = 111,999,888

It can easily be verified that none of the remaining six values yield the desired structure for M^2.

Accordingly, N = 111,999,889 - 1 = 111,999,888, and:

Consequently, N = 111,999,888 is the unique solution to the given problem.

__Note__:

It is trivially apparent that assuming M to be a negative integer would have led to the same value of M^2, and therefore the same solution.

*Edited on ***July 17, 2008, 11:38 am**