15-square puzzle

From the category “This Is Completely Useless”: here’s what a 15-square puzzle looks like when you arrange the tiles in order of how many factors they have.

What I Learned by Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Index

I’m doing something that I should have done a long time ago: collecting a series of posts into one single post.

When I was researching for my series of posts on conditional convergence, especially examples related to the constant $\gamma$, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites along with the page numbers in the book — while giving the book a very high recommendation.

Part 1: The smallest value of $n$ so that $1 + \frac{1}{2} + \dots + \frac{1}{n} > 100$ (page 23).

Part 2: Except for a couple select values of $m, the sum $\frac{1}{m} + \frac{1}{m+1} + \dots + \frac{1}{n}$ is never an integer (pages 24-25).

Part 3: The sum of the reciprocals of the twin primes converges (page 30).

Part 4: Euler somehow calculated $\zeta(26)$ without a calculator (page 41).

Part 5: The integral called the Sophomore’s Dream (page 44).

Part 6: St. Augustine’s thoughts on mathematicians — in context, astrologers (page 65).

Part 7: The probability that two randomly selected integers have no common factors is $6/\pi^2$ (page 68).

Part 8: The series for quickly computing $\gamma$ to high precision (page 89).

Part 9: An observation about the formulas for $1^k + 2^k + \dots + n^k$ (page 81).

Part 10: A lower bound for the gap between successive primes (page 115).

Part 11: Two generalizations of $\gamma$ (page 117).

Part 12: Relating the harmonic series to meteorological records (page 125).

Part 13: The crossing-the-desert problem (page 127).

Part 14: The worm-on-a-rope problem (page 133).

Part 15: An amazingly nasty formula for the $n$th prime number (page 168).

Part 16: A heuristic argument for the form of the prime number theorem (page 172).

Part 17: Oops.

Part 18: The Riemann Hypothesis can be stated in a form that can be understood by high school students (page 207).

What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 17

Let $\pi(n)$ denote the number of positive prime numbers that are less than or equal to $n$. The prime number theorem, one of the most celebrated results in analytic number theory, states that

$\pi(x) \approx \displaystyle \frac{x}{\ln x}$.

This is a very difficult result to prove. However, Gamma (page 172) provides a heuristic argument that suggests that this answer might be halfway reasonable.

Consider all of the integers between $1$ and $x$.

• About half of these numbers won’t be divisible by 2.
• Of those that aren’t divisible by 2, about two-thirds won’t be divisible by 3. (This isn’t exactly correct, but it’s good enough for heuristics.)
• Of those that aren’t divisible by 2 and 3, about four-fifths won’t be divisible by 5.
• And so on.

If we repeat for all primes less than or equal to $\sqrt{x}$, we can conclude that the number of prime numbers less than or equal to $x$ is approximately

$\pi(x) \approx \displaystyle x \prod_{p \le \sqrt{x}} \left(1 - \frac{1}{p} \right)$.

From this point, we can use Mertens product formula

$\displaystyle \lim_{n \to \infty} \frac{1}{\ln n} \prod_{p \le n} \left(1 - \frac{1}{p} \right)^{-1} = e^\gamma$

to conclude that

$\displaystyle \frac{1}{\ln n} \prod_{p \le n} \left(1 - \frac{1}{p} \right) \approx \displaystyle \frac{e^{-\gamma}}{\ln n}$

if $n$ is large. Therefore,

$\pi(x) \approx x \displaystyle \frac{e^{-\gamma}}{\ln \sqrt{x}} = 2 e^{-\gamma} \displaystyle \frac{x}{\ln x}$.

Though not a formal proof, it’s a fast way to convince students that the unusual fraction $\displaystyle \frac{x}{\ln x}$ ought to appear someplace in the prime number theorem.

When I researching for my series of posts on conditional convergence, especially examples related to the constant $\gamma$, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 16

Let $\pi(n)$ denote the number of positive prime numbers that are less than or equal to $n$. The prime number theorem, one of the most celebrated results in analytic number theory, states that

$\pi(x) \approx \displaystyle \frac{x}{\ln x}$.

This is a very difficult result to prove. However, Gamma (page 172) provides a heuristic argument that suggests that this answer might be halfway reasonable.

Consider all of the integers between $1$ and $x$.

• About half of these numbers won’t be divisible by 2.
• Of those that aren’t divisible by 2, about two-thirds won’t be divisible by 3. (This isn’t exactly correct, but it’s good enough for heuristics.)
• Of those that aren’t divisible by 2 and 3, about four-fifths won’t be divisible by 5.
• And so on.

If we repeat for all primes less than or equal to $\sqrt{x}$, we can conclude that the number of prime numbers less than or equal to $x$ is approximately

$\pi(x) \approx \displaystyle x \prod_{p \le \sqrt{x}} \left(1 - \frac{1}{p} \right)$.

From this point, we can use Mertens product formula

$\displaystyle \lim_{n \to \infty} \frac{1}{\ln n} \prod_{p \le n} \left(1 - \frac{1}{p} \right)^{-1} = e^\gamma$

to conclude that

$\displaystyle \frac{1}{\ln n} \prod_{p \le n} \left(1 - \frac{1}{p} \right) \approx \displaystyle \frac{e^{-\gamma}}{\ln n}$

if $n$ is large. Therefore,

$\pi(x) \approx x \displaystyle \frac{e^{-\gamma}}{\ln \sqrt{x}} = 2 e^{-\gamma} \displaystyle \frac{x}{\ln x}$.

Though not a formal proof, it’s a fast way to convince students that the unusual fraction $\displaystyle \frac{x}{\ln x}$ ought to appear someplace in the prime number theorem.

When I researching for my series of posts on conditional convergence, especially examples related to the constant $\gamma$, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 15

I did not know — until I read Gamma (page 168) — that there actually is a formula for generating $n$th prime number by directly plugging in $n$. The catch is that it’s a mess:

$p_n = 1 + \displaystyle \sum_{m=1}^{2^n} \left[ n^{1/n} \left( \sum_{i=1}^m \cos^2 \left( \pi \frac{(i-1)!+1}{i} \right) \right)^{-1/n} \right]$,

where the outer brackets $[~ ]$ represent the floor function.

This mathematical curiosity has no practical value, as determining the 10th prime number would require computing $1 + 2 + 3 + \dots + 2^{10} = 524,800$ different terms!

When I researching for my series of posts on conditional convergence, especially examples related to the constant $\gamma$, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 10

Suppose $p_n$ is the $n$th prime number, so that $p_{n+1} - p_n$ is the size of the $n$th gap between successive prime numbers. It turns out (Gamma, page 115) that there’s an incredible theorem for the lower bound of this number:

$\displaystyle \limsup_{n \to \infty} \frac{(p_{n+1}-p_n) (\ln \ln \ln p_n)^2}{(\ln p_n)(\ln \ln p_n)(\ln \ln \ln \ln p_n)} \ge \displaystyle \frac{4 e^{\gamma}}{c}$,

where $\gamma$ is the Euler-Mascheroni constant and $c$ is the solution of $c = 3 + e^{-c}$.

Holy cow, what a formula. Let’s take a look at just a small part of it.

Let’s look at the amazing function $f(x) = \ln \ln \ln \ln x$, iterating the natural logarithm function four times. This function has a way of converting really large inputs into unimpressive outputs. For example, the canonical “big number” in popular culture is the googolplex, defined as $10^{10^{100}}$. Well, it takes some work just to rearrange $\displaystyle f \left(10^{10^{100}} \right)$ in a form suitable for plugging into a calculator:

$\displaystyle f \left(10^{10^{100}} \right) = \displaystyle \ln \ln \ln \left( \ln 10^{10^{100}} \right)$

$= \displaystyle \ln \ln \ln \left( 10^{100} \ln 10 \right)$

$= \displaystyle \ln \ln \left[ \ln \left(10^{100} \right) + \ln \ln 10 \right]$

$= \displaystyle \ln \ln \left[ 100 \ln 10 + \ln \ln 10 \right]$

$= \displaystyle \ln \ln \left[ 100 \ln 10 \left( 1 + \frac{\ln \ln 10}{100 \ln 10} \right) \right]$

$= \displaystyle \ln \left( \ln [ 100 \ln 10] + \ln \left( 1 + \frac{\ln \ln 10}{100 \ln 10} \right)\right)$

$\approx 1.6943$

after using a calculator.

This function grows extremely slowly. What value of $x$ gives an output of $0$? Well:

$\ln \ln \ln \ln x = 0$

$\ln \ln \ln x = 1$

$\ln \ln x = e$

$\ln x = e^e$

$x = e^{e^e} \approx 3,814,279.1$

What value of $x$ gives an output of $1$? Well:

$\ln \ln \ln \ln x = 1$

$\ln \ln \ln x = e$

$\ln \ln x = e^e$

$\ln x = e^{e^e}$

$x = e^{e^{e^e}}$

$\approx e^{3,814,279.1}$

$\approx 10^{3,814,279.1 \log_{10} e}$

$\approx 10^{1,656,420.367636}$

$\approx 2.3315 \times 10^{1,656,420}$

That’s a number with 1,656,421 digits! At the rapid rate of 5 digits per second, it would take over 92 hours (nearly 4 days) just to write out the answer by hand!

Finally, how large does $x$ have to be for the output to be 2? As we’ve already seen, it’s going to be larger than a googolplex:

$\displaystyle f \left(10^{10^{x}} \right) = 2$

$\displaystyle \ln \ln \ln \left( \ln 10^{10^{x}} \right) = 2$

$\displaystyle \ln \ln \ln \left( 10^{x} \ln 10 \right) = 2$

$\displaystyle \ln \ln \left[ \ln \left(10^{x} \right) + \ln \ln 10 \right] = 2$

$\displaystyle \ln \ln \left[ x\ln 10 + \ln \ln 10 \right] = 2$

$\displaystyle \ln \ln \left[ x\ln 10 \left( 1 + \frac{\ln \ln 10}{x\ln 10} \right) \right] = 2$

$\displaystyle \ln \left( \ln [ x\ln 10] + \ln \left( 1 + \frac{\ln \ln 10}{x \ln 10} \right)\right) = 2$

Let’s simplify things slightly by letting $y = x \ln 10$:

$\displaystyle \ln \left( \ln y + \ln \left( 1 + \frac{\ln \ln 10}{y} \right)\right) = 2$

$\displaystyle \ln y + \ln \left( 1 + \frac{\ln \ln 10}{y} \right) = e^2$

This is a transcendental equation in $y$; however, we can estimate that the solution will approximately solve $\ln y = e^2$ since the second term on the left-hand side is small compared to $\ln y$. This gives the approximation $y = e^{e^2} \approx 1618.18$. Using either Newton’s method or else graphing the left-hand side yields the more precise solution $y \approx 1617.57$.

Therefore, $x \approx 1617.57 \ln 10 \approx 3725.99$, so that

$f \left(10^{10^{3725.99}} \right) \approx 2$.

One final note: despite what’s typically taught in high school, mathematicians typically use $\log$ to represent natural logarithms (as opposed to base-10 logarithms), so the above formula is more properly written as

$\displaystyle \limsup_{n \to \infty} \frac{(p_{n+1}-p_n) (\log \log \log p_n)^2}{(\log p_n)(\log \log p_n)(\log \log \log \log p_n)} \ge \displaystyle \frac{4 e^{\gamma}}{c}$.

And this sets up a standard joke, also printed in Gamma:

Q: What noise does a drowning analytic number theorist make?

A: Log… log… log… log…

When I researching for my series of posts on conditional convergence, especially examples related to the constant $\gamma$, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

A curious non-randomness in the distribution of primes

Among the first billion prime numbers, for instance, a prime ending in 9 is almost 65 percent more likely to be followed by a prime ending in 1 than another prime ending in 9. In a paper posted online today [March 13, 2016], Kannan Soundararajan and Robert Lemke Oliver of Stanford University present both numerical and theoretical evidence that prime numbers repel other would-be primes that end in the same digit, and have varied predilections for being followed by primes ending in the other possible final digits…

This conspiracy among prime numbers seems, at first glance, to violate a longstanding assumption in number theory: that prime numbers behave much like random numbers. Most mathematicians would have assumed… that a prime should have an equal chance of being followed by a prime ending in 1, 3, 7 or 9 (the four possible endings for all prime numbers except 2 and 5).

New world record for largest prime number

As of this week, we have a new world record for the largest known prime number:

$2^{74,207,281}-1$

The adjective known is important, because there are an infinite number of prime numbers (but not all of them are known). A good video describing this finding is below.

A good article is here:

A Mathematical Horror Story

One of my guilty pleasures in the 1990s, when I was far too old to be watching children’s cartoons, was the fantastic show “Pinky and the Brain.” In the clip below, the Brain tells a scary campfire story. (Well, it’s about math, and what’s scarier than math?)

Proving theorems and special cases (Part 9): The Riemann hypothesis

In a recent class with my future secondary math teachers, we had a fascinating discussion concerning how a teacher should respond to the following question from a student:

Is it ever possible to prove a statement or theorem by proving a special case of the statement or theorem?

Usually, the answer is no. In this series of posts, we’ve already seen that a conjecture could be true for the first 40 cases or even the first $10^{316}$ yet ultimately prove false for all cases.

For the next few posts, I thought I’d share a few of the most famous unsolved problems in mathematics… and just how much computational work has been done to check for a counterexample.

4. The Riemann hypothesis (see here, here, and here for more information) is perhaps the outstanding unsolved problem in pure mathematics, and a prize of \$1 million has been offered for its proof.

The Riemann zeta function is defined by

$\zeta(s) = \displaystyle \sum_{n=1}^\infty \frac{1}{n^s}$

for complex numbers $s$ with real part greater than 1. For example,

$\zeta(2) = \displaystyle \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \dots = \displaystyle \frac{\pi^2}{6}$

and

$\zeta(4) = \displaystyle \frac{1}{1^4} + \frac{1}{2^4} + \frac{1}{3^4} + \dots = \displaystyle \frac{\pi^4}{90}$

The definition of the Riemann zeta function can be extended to all complex numbers (except a pole at $s = 1$) by the integral

$\zeta(s) = \displaystyle \frac{1}{\Gamma(s)} \int_0^\infty \frac{x^{s-1}}{e^s - 1} dx$

and also analytic continuation.

The Riemann hypothesis conjectures to all solutions of the equation $\zeta(s) = 0$ other than negative even integers occur on the line $s = \frac{1}{2} + i t$. At present, it is known that the first 10 trillion solutions are on this line, so that every solution with $t < 2.4 \times 10^{12}$ is on this line. Of course, that’s not a proof that all solutions are on this line.

A full description of known results concerning the Riemann hypothesis requires much more than a single post. I’ll refer the interested reader to the links above from MathWorld, Wikipedia, and Claymath and the references embedded in those links. An excellent book for the layman concerning the Riemann hypothesis is Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics, by John Derbyshire.