17 Jul 2011

Thin Cars and Parking Lots

A quick question I came across today:
Suppose you had an infinitely thin car. How big do you have to build a parking lot for the car to be able to turn 180 degrees in the parking lot? 
Think about it for a while, and then highlight the area below to see the answer.

Surprisingly, there is no lower limit on the size of the parking lot. In other words, the parking lot can be as small as you want.                                                                                                

This is better known as the (thinly disguised) Kakeya Needle Problem. Unfortunately, the proof relies on existence theorems which (as far as I know) do not provide an explicit way to show us how we can jiggle the car around until it rotates 180 degrees. So while it might cool to tell your friend you can turn an infinitely thin car on a parking lot with zero area, I know of no way that you can physically show how it can be done.

10 Jul 2011

Number of Primes with Desired Digit Strings

This post was previously very, very wrong. It has been corrected as of July 12th, 2011.

Greetings and salutations to my loyal readers (there are about 30 of you I think)!

I've been a bit busy recently organizing an online study group for The Feynman Lectures on Physics, so today I'll just post a short note based on an observation someone made about my last post on the Kempner series.

The observations was that since the prime harmonic series (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...) diverges, we can take out all the terms with a specific sequence of digits to make the series convergent as we did with the harmonic series. Or in other words:
"given any finite string of numbers, i.e. 24485983 that there exist infinitely many primes whose base 10 representation contain that string."
We knew from the my last post that the harmonic series became convergent if we took out all the terms with a '9' (or more generally any string of digits). For example, we could take out all primes with the digit string '13'. This would make the harmonic series convergent (after removing all the terms with '13'). Now consider the prime harmonic series, which is a subset of the original full harmonic series. Since the prime harmonic series diverges to infinity, we must have taken out an infinite number of primes with '13'. Therefore, the conclusion is that there are an infinite number of primes with any string of digits you can imagine.

The purpose of this note was to show that the same conclusion could be reached via a direct proof rather than as a corollary of another proof. However, I realized that my direct proof had a rather large flaw in it. As a cop-out, I'll show in this note that one can prove this result as a corollary of another theorem, namely Dirichlet's theorem for prime progressions.


Dirichlet's theorem states that there are infinitely many primes in the arithmetic sequence \[a, a+d, a+2d, a+3d, \ldots\] where $a$ and $d$ are coprime.

To prove that there are infinitely many primes which contain '13', set $a=13$ and $d=100$. We get the sequence 13, 113, 213, ... in which all terms contain the digit string '13' and by Dirichlet's theorem must contain an infinite number of primes.


Although we used Dirichlet's theorem for showing this particular result, there are other theorems we could have used as well. For example, we could have used the fact that the prime counting function $\pi(x)$ is bound by \[\frac{1}{2}\frac{x}{\log(x)}<\pi(x)<2\frac{x}{\log(x)}.\]
Just so I don't feel like a complete hack, here are some exercises for you guys.

  1. Prove that there are infinitely many primes containing 42 (if you use Dirichlet's Theorem, use it carefully).
  2. Prove that there are infinitely many primes starting with the digits 42.

2 Jul 2011

The Kempner Series - A modified harmonic series

The harmonic series is considered a classic textbook example of a series that seems to converge but is actually divergent. For those that need a reminder, the harmonic series is: \[\sum_{n=1}^{\infty}\frac{1}{n}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\cdots.\]
Now here's an interesting question:

How can we modify the harmonic series to make it convergent?

Disregarding trivial answers such as "remove all the terms", this question is actually pretty hard to answer. Say we removed every second term starting from the first (i.e. 1, 1/3, 1/5, etc). Would that work?
\[\sum_{\substack{n=1 \\ n\ is\ even}}^{\infty}\frac{1}{n}=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{8}\cdots=\frac{1}{2}\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\cdots\right).\]
From above, it seems like it would not work since it just produces half of the original series (which is not a very well defined quantity since the original series was divergent anyway).