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 100-digit numbers composed only of the digits 4 and 9, and the chances that any given 100-digit number is divisible by are one in , so… one?
Turns out that’s right. The key here is that a number (written in decimal) is divisible by if the number made up of its last digits is divisible by . 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: is the set of -digit numbers made up of 4s and 9s which is divisible by . So , etc. We’ll prove by induction that has one element for every . Assume this is true for . Given that , we want to find . Every number in must be divisible by , and so have its last digits divisible by . So the only possible elements of are and (that is, the numbers made from by writing and at the front). Now, since is a multiple of , either or .
Now, observe that is a multiple of , And observe that has exactly factors of 2 in its prime factorization, so it’s divisible by but not , so .
So if , then , and if , then . In either case is a singleton, and by induction, we have:
Proposition: there exists exactly one -digit number composed solely of the digits 4 and 9 which is divisible by .
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 with a few lines of Python. (I’ve initalized n to [0, 4] so that I could write code which starts indexing the at 1.)
n = [0, 4]
for k in range(1, 100):
if n[k] % 2**(k+1) == 0:
n += [4*(10**k) + n[k]]
n += [9*(10**k) + n[k]]
giving the result
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.