# Euler and 1,000,009

Here’s a tale of one the great mathematicians of all time that I heard for the first time this year: the great mathematician published a mistake… which, when it occurs today, is highly professionally embarrassing to modern mathematicians. From Mathematics in Ancient Greece:

In a paper published in the year 1774, [Leonhard] Euler listed [1,000,009] as prime. In a subsequent paper Euler corrected his error and gave the prime factors of the integer, adding that one time he had been under the impression that the integer in question admitted of the unique partition

$1,000,009 = 1000^2 + 3^2$

but that he had since discovered a second partition, namely

$1,000,009 = 235^2 + 972^2$,

which revealed the composite character of the number.

See Wikipedia and/or Mathworld for the details of how this allowed Euler to factor $1,000,009$.

# Factoring Mersenne “primes”

I love hearing and telling tales of legendary mathematicians. Today’s tale comes from Frank Nelson Cole and definitely comes from the era before calculators or computers. From Wikipedia:

On October 31, 1903, Cole famously made a presentation to a meeting of the American Mathematical Society where he identified the factors of the Mersenne number 267 − 1, or M67. Édouard Lucas had demonstrated in 1876 that M67 must have factors (i.e., is not prime), but he was unable to determine what those factors were. During Cole’s so-called “lecture”, he approached the chalkboard and in complete silence proceeded to calculate the value of M67, with the result being 147,573,952,589,676,412,927. Cole then moved to the other side of the board and wrote 193,707,721 × 761,838,257,287, and worked through the tedious calculations by hand. Upon completing the multiplication and demonstrating that the result equaled M67, Cole returned to his seat, not having uttered a word during the hour-long presentation. His audience greeted the presentation with a standing ovation. Cole later admitted that finding the factors had taken “three years of Sundays.”

# A nice article on recent progress on solving the twin prime conjecture

The twin prime conjecture (see here, here and here for more information) asserts that there are infinitely many primes that have a difference of 2. For example:

3 and 5 are twin primes;

5 and 7 are twin primes;

11 and 13 are twin primes;

17 and 19 are twin primes;

29 and 31 are twin primes; etc.

While most mathematicians believe the twin prime conjecture is correct, an explicit proof has not been found. Indeed, this has been one of the most popular unsolved problems in mathematics — not necessarily because it’s important, but for the curiosity that a conjecture so simply stated has eluded conquest by the world’s best mathematicians.

Still, research continues, and some major progress has been made in the past few years. (I like sharing this story with my students to convince them that not everything that can be known about mathematics has been figure out yet — a misconception encouraged by the structure of the secondary curriculum — and that research continues to this day.) Specifically, it was recently shown that, for some integer $N$ that is less than 70 million, there are infinitely many pairs of primes that differ by $N$.

http://video.newyorker.com/watch/annals-of-ideas-yitang-zhang-s-discovery-2015-01-28

http://www.newyorker.com/magazine/2015/02/02/pursuit-beauty

For more on recent progress:

# 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.