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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s