One More than Triple 8s

We can streamline Steven's excellent approach a bit. My solution will be based on the observation that $x^2$ ends in ... 889 if and only if $x^2-889$ is divisible by both 125 and 8. Now $x^2-889$ is divisible by 8 for all odd numbers $x$ , since $x^2\equiv1\equiv889 (\mod 8)$ for odd $x$ . The real issue is the divisibility by 125. Let's find the solutions of $x^2\equiv889\equiv14 (\mod 125)$ . Working our way up, we see that the solutions of $x^2\equiv889\equiv4 (\mod 5)$ are 2 and $5-2=3$ , and the solutions of $x^2\equiv889\equiv14 (\mod 25)$ are 8 and $25-8=17$ ; we only need to check 2, 7, 12, 3 and 8 here. Finally, the solutions of $x^2\equiv889\equiv14 (\mod 125)$ are 42 and $125-42=83$ (again, we only need to check 5 candidates). Thus every interval $[125(n-1), 125n]$ contains exactly two $x$ with $x^2\equiv889\equiv14 (\mod 125)$ , an even and an odd number. (As Martin observes, these two numbers are $125n-83$ and $125n-42$ ). If such a number $x$ is odd, then $x^2$ will end in ...889, as we observed earlier. The 889th such number is $125\times889-42=125\times888+83=111083$ .

Just for the sake of curiosity, by extending Steven Yuan 's solution we obtain a formula for the $n$ 'th positive integer whose square ends in $889$ . Let us call such a number an 889-number.

We have that $\left\{50i + 33\right\}_{i=0}^{\infty}$ is a sequence of numbers whose respective squares end in 89, and further that if $i = 1 + 5j$ , the respective squares end in $889$ . That is, for a non-negative integer $j$ , the square of $s_1(j) = 250j + 83$ ends in $889$ .

Similarly for numbers $\left\{10i + 7\right\}_{i=0}^{\infty}$ , we conclude that for a non-negative integer $j$ , the square of $s_2(j) = 250j + 167$ ends in $889$ .

Notice that $s_1(j) < s_2(j) < s_1(j+1) < s_2(j+1)$ for $j \geq 0$ . So to get the $k$ 'th 889-number, we compute $s_1\left(\frac{k-1}{2}\right)$ if $k$ is odd; otherwise we compute $s_2\left(\frac{k}{2} - 1\right)$ .

Hence, the $n$ 'th 889-number can be computed as $N_{889}(n) = \begin{cases} 125n - 42 & \text{if } n \text{ is odd} \\ 125n - 83 & \text{if } n \text{ is even} \end{cases}$

(Edit by me: Simplified formula by @Otto Bretscher )

Otto Bretscher mentions in a comment further below that we can express $N$ in a single line: $N_{889}(n) = \frac{125(2 n - 1) - 41(-1)^n}{2}$

I don't have time for a full solution yet, so here's a general outline:

Let $a$ be our desired integer. We know that $a$ must end with $3$ or $7$ . Thus, $a$ is of the form $10n + 3$ or $10n + 7$ , for some positive integer $n$ . So, we have two cases:

Case 1: The number is of the form $10n + 3$

Squaring and taking $\! \mod \! 100$ yields $n \equiv 3 \pmod{5}$ , or $n = 5m + 3$ for some positive integer $m$ . Plug this back into our squared expression and taking $\! \mod \! 1000$ yields $m \equiv 1 \pmod{10}$ or $m \equiv 6 \pmod{10}$ . Thus, $n = 8, 33, 83, \cdots$ .

Case 2: The number is of the form $10n + 7$

Following the same steps as Case 1 yields $n = 5m + 1$ and $m \equiv 3 \pmod{10}$ or $8 \pmod{10}$ . Thus, $n = 16, 41, 66, \cdots$ .

Our first few values for $a$ are

$83, 167, 333, 417, 583, 667, 833, 917, \cdots .$

The rest of the integers in this sequence just append digits in front of the eight smallest solutions e.g. $72833, 31415926917$ , and they repeat in chunks of eight. Since $889 \equiv 1 \pmod{8}$ , $a$ will end in $083$ . Since $\left \lfloor \frac{889}{8} \right \rfloor = 111$ , the integers appended are $111$ . Thus, $a = 111083$ , which has digit sum $\boxed{14}$ .

Python 2.7:

1
2
3
4
5
6
7

ends_with_889 = 0
n = 0
while ends_with_889 < 889:
    n += 1
    if str(n*n).endswith('889'):
        ends_with_889 += 1
print "Answer:", sum([int(c) for c in str(n)])