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.

4s and 9s

Published by Michael Lugo

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by Michael Lugo

Leave a Reply Cancel reply