# 4s and 9s

James Tanton tweeted: “How many of the 100-digit numbers composed solely of the digits 4 and 9 are divisible by 2^100”?

Well, there are $2^{100}$ 100-digit numbers composed only of the digits 4 and 9, and the chances that any given 100-digit number is divisible by $2^{100}$ are one in $2^{100}$, so… one?

Turns out that’s right. The key here is that a number (written in decimal) is divisible by $2^k$ if the number made up of its last $k$ digits is divisible by $2^k$. So we can build up our number one digit at a time:

• its last digit is divisible by 2, so it’s 4
• its last two digits are divisible by 4. This must be 44 or 94; 44 is divisible by 4, and 94 isn’t, so it’s 44.
• its last three digits are divisible by 8. This must be 444 or 944; 444 isn’t divisible by 8, and 944 is, so it’s 944.

And so on. But what guarantees that at every step our result is unique?

Let’s introduce some notation: $N_k$ is the set of $k$-digit numbers made up of 4s and 9s which is divisible by $2^k$. So $N_1 = \{ 4 \}, N_2 = \{ 44 \}, N_3 = \{ 944 \}$, etc. We’ll prove by induction that $N_k$ has one element for every $k \ge 1$. Assume this is true for $k$. Given that $N_k = \{ n_k \}$, we want to find $N_{k+1}$. Every number in $N_{k+1}$ must be divisible by $2^k$, and so have its last $k$ digits divisible by $2^k$. So the only possible elements of $N_{k+1}$ are $4 \times 10^k + n_k$ and $9 \times 10^k + n_k$ (that is, the numbers made from $n_k$ by writing $4$ and $9$ at the front). Now, since $n_k$ is a multiple of $2^k$, either $n_k \equiv 0 \mod 2^{k+1}$ or $n_k \equiv 2^k \mod 2^{k+1}$.

Now, observe that $4 \times 10^k = (2 \times 5^k) (2^{k+1})$ is a multiple of $2^{k+1}$, And observe that $9 \times 10^k = (3^2)(2^k)(5^k)$ has exactly $k$ factors of 2 in its prime factorization, so it’s divisible by $2^k$ but not $2^{k+1}$, so $9 \times 10^k \equiv 2^k \mod 2^{k+1}$.

So if $n_k \equiv 0 \mod 2^{k+1}$, then $N_{k+1} = \{ 4 \times 10^k + n_k \}$, and if $n_k \equiv 2^k \mod 2^{k+1}$, then $N_{k+1} = \{ 9 \times 10^k + n_k \}$. In either case $N_{k+1}$ is a singleton, and by induction, we have:

Proposition: there exists exactly one $k$-digit number composed solely of the digits 4 and 9 which is divisible by $2^k$.

This generalizes: we could let 4 and 9 be replaced by any single even number and odd number.

Furthermore, since the proof is constructive, we can actually find the $n_k$ with a few lines of Python. (I’ve initalized n to [0, 4] so that I could write code which starts indexing the $n_k$ at 1.)

n = [0, 4]

for k in range(1, 100):
if n[k] % 2**(k+1) == 0:
n += [4*(10**k) + n[k]]
else:
n += [9*(10**k) + n[k]]

print(n[100])


giving the result

4999999449449999994999449944944994449499994444449494944949944994494999944449444499949499449494994944

The Encyclopedia of Integer Sequences has a few sequences along these same lines: A035014 gives such numbers made of 3s and 4s.  A05333 gives such numbers made of 4s and 9s and nearby sequences starting with  A053312 do the same for other pairs.