December 2015 – Page 2 – God plays dice

Erdős is still publishing

December 16, 2015 Michael Lugo3 Comments

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

December 12, 2015December 12, 2015 Michael Lugo1 Comment

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

December 12, 2015 Michael LugoLeave a comment

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.

Let’s make laysplain happen

December 10, 2015December 10, 2015 Michael Lugo3 Comments

Piper Harron wrote a thesis: “The Equidistribution of Lattice Shapes of Rings of Integers of Cubic, Quartic, and Quintic Number Fields: an Artist’s Rendering” which, in addition to proving an interesting result “laysplains” it along the way.

Sadly, “laysplain” doesn’t seem to be a word yet. Google it and you just find potato chips.

(via metafilter)

2015 Putnam problems

December 8, 2015 Michael Lugo1 Comment

For those who are into this sort of thing: the problems from the 2015 Putnam exam are now available.