Almost Automorphic Number

Relevant wiki: Euler's Theorem

Let $d$ be the number of digits of $n$ . Then $n$ is either almost automorphic or automorphic if and only if $10^d | n(n^{2k}-1)$ for all positive $k$ . But this happens if and only if $10^d|n(n^2-1)$ . (Similarly $n$ is automorphic if and only if $10^d | n(n-1)$ .)

For $d = 1$ it's not hard to see that there are five solutions, $1,4,5,6,9$ . Three of these are automorphic, $1$ , $5$ , and $6$ , so that's two almost automorphic one-digit numbers.

For $d = 2$ we see that $(n-1)n(n+1)$ is divisible by $25$ and by $4$ . The Chinese Remainder Theorem says that there are $9$ solutions mod $100$ : three possibilities for $n$ mod $25$ and three possibilities mod $4$ . These are $0,1,24,25,49,51,75,76,99$ . After throwing out the first two, we get seven solutions. Two of these are automorphic, $25$ and $76$ . So that's five almost automorphic two-digit numbers.

For $d = 3$ the technique is the same. There are $3$ possibilities mod $125$ and $5$ mod $8$ , so we get $15$ numbers $0,1, 125, \ldots, 999$ . After throwing out the first two, we get thirteen solutions. Two of these are automorphic: $376, 625$ ; so we get eleven almost automorphic three-digit numbers.

The total is therefore $2+5+11 = \fbox{18}$ .