Erdős is still publishing

Paul Erdős is still publishing. His newest paper, with Ron Graham and Steve Butler,shows that any natural number can be written as a sum \sum_1^\ell 1/a_i with a_1 < \ldots < a_\ell, where each denominator is the product of three distinct primes. A footnote, on the obvious generalization to expressing rational numbers in such a form, reads:
“One of the authors believes that all rational numbers can be expressed in this form, another author has doubts that every rational number can be expressed in this form, and the third author, already having looked in The BOOK at the answer, remains silent on this issue.” For more of the context on this paper, see Siobhan Roberts writing for the Simons Foundation.

“The BOOK”, of course, refers to Erdős’ frequent claim that God (who he did not believe in) had a book in heaven that had the best proof of every theorem.  A sample of this book can be found in Proofs from THE BOOK by Martin Aigner and Günter M. Ziegler.

Some Euler

William Dunham lectures at Cornell on two of Euler’s big theorems: the divergence of the sum of the reciprocals of the primes and the evaluation of the sum of the reciprocals of the squares
{1 \over 1} + {1 \over 4} + {1 \over 9} + {1 \over 16} + \cdots = {\pi^2 \over 6}.

Dunham is the author of Euler: The Master of Us All, which focuses on selected results of Euler. If I recall correctly I first saw the evaluation of \zeta(2) in his Journey through Genius.

This focuses on the math; there’s a full-length biography of Euler coming out, by Ronald Calinger. The publisher, Princeton, describes this as the “first full-scale biography of Leonhard Euler”, which is honestly a bit surprising.

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.