Euclid’s proof that there are infinitely many primes

Paul Erdős had this notion that God kept a book of the best proofs. Erdős called God’s book simply “the book.” Springer recently published Proofs from THE BOOK, a collection of elegant proofs that the authors suppose might be in God’s book.

For many mathematicians, the first proof that comes to mind as a candidate for a proof in the book is Euclid’s proof that there are infinitely many primes. The proof is so short and simple that it can almost be written within the 140-character limit of Twitter. I give the proof in my AlgebraFact Twitter account as follows.

There are infinitely many primes. Proof: If not, multiply all primes together and add 1. Now you’ve got a new prime.

Several people pointed out that I was a little too terse. If N is the supposed product of all primes + 1, N itself doesn’t have to be a new prime. It could be that N has a factor that is a new prime. The smallest prime factor of N must be a prime not on the list. Either way “you’ve got a new prime,” but the proof above leaves out some important details.

Here’s an example. Suppose we believed the only primes were 2, 3, 5, 7, 11, and 13. Let N = 2*3*5*7*11*13 + 1 = 30031. Now N cannot be divisible by 2, 3, 5, 7, 11, or 13 because there is a remainder of 1 when dividing N by any of these numbers. Maybe N is a new prime, or maybe N is composite but N has a prime factor not on our list. The latter turns out to be the case: 30031 = 59*509.

If you can find a better summary of Euclid’s proof in 140 characters or less, please leave it in the comments. Please include the character count with your proposal.

Related posts

Twitter daily tip news

I have five Twitter accounts that send out one tip per day, including a new one I just added last week.

Regular expressions

@RegexTip started over today. It’s a cycle of tips for learning regular expressions. It sticks to the regular expression features common to Python, Perl, C#, and many other programming languages. This account posts Monday through Friday.

Keyboard shortcuts

@SansMouse gives one tip a day on using Windows without a mouse. By practicing one keyboard shortcut a day, you can get into the habit of using your mouse less and your keyboard more. This cycle of tips started over January 29 with the most common and most widely useful shortcuts. I’m also sprinkling in a few extra tips that are less well known. This account also posts Monday through Friday.

Math

I have three mathematical accounts. These post seven days a week.

@AlgebraFact, just started February 2. It will be a mixture of linear algebra, number theory, group theory, etc.

@ProbFact gives one fact per day from probability. Usually these facts are theorems, but sometimes they include a note on history or applications.

@AnalysisFact gives facts from real and complex analysis. The topics range from elementary to advanced.

What if I don’t use Twitter?

You can visit the page for a Twitter account just like any other web page. And every Twitter account has an RSS feed link allowing you to subscribe just as you would subscribe to a blog.

How do you write these?

I write up content for these accounts in bulk. I may sit down on a Saturday and come up with several weeks worth of tips. Then I use HootSuite to schedule the tips weeks in advance. Sometimes I’ll post something spontaneously, such as link to something relevant, but most of the work is done in advance. I use my personal Twitter account for live interaction.

Related links:

Using Windows without a mouse

Regular expressions in

Chart of probability distribution relationships

Twitter feeds to help with New Year’s resolutions

I have four Twitter accounts that send out one tip per day. One of these might help you with a New Year’s resolution. If you don’t use Twitter, you can follow these Twitter accounts by subscribing to their RSS feeds. [Update: Twitter really doesn’t want to you to use RSS. I’ve posted a couple times on how to subscribe to Twitter via RSS, and the solutions break over time. I’ve given up.]

Windows keyboard shortcuts

If  you’d like to become more efficient in using Windows, and reduce your chances of repetitive stress injury, you may want to use your keyboard more and your mouse less. SansMouse is a Twitter account that sends out one keyboard shortcut per day.

Regular expressions

If you’ve intended to learn regular expressions but haven’t made the time, you might want to follow RegexTip for one tip per day about regular expressions. I focus on the features common to Perl, Python, C#, JavaScript, etc. I also have some tips coming up with language-specific tips.

Math

I have two mathematical Twitter accounts. These might be useful if you want to review math courses you took a long time ago or if you want a preview of math you might need in the future. Both are eclectic, mixing elementary and advanced topics.

ProbFact sends out one probability fact per day, mostly theorems but sometimes notes on applications.

I just started AnalysisFact a couple days ago. It will cover a wide range of topics from real and complex analysis. AnalysisFact will have a wider range of sophistication than ProbFact, mixing undergraduate and graduate level material.

Update (31 December 2011): Over the last year I’ve added three mathematical Twitter accounts:

I’ve also added two computing accounts:

Summary

Here are the Twitter accounts:

* * *

New Year’s links

Here are a couple posts from Jon Swanson:

8 ways to end the year
Leave it in 2008 (Just mentally change the “8” to a “9” when you read it.)

And here is a good post from Jurgen Appelo:

Checklist for goals and resolutions.

Related posts

New daily tip feeds: RegexTip and ProbFact

A few weeks ago I started a Twitter account @SansMouse with daily tips on Windows keyboard shortcuts. That’s gone well, so I decided start two more daily tip accounts: @RegexTip and @ProbFact. If you don’t use Twitter, you can follow these tip via your blog reader. Here are the RSS feeds for RegexTip and ProbFact.

RegexTip will give one tip per day on using regular expressions. I’ll sometimes post more than once a day, but I’ll only give one tip. Other posts might be housekeeping notes etc. The idea is that people who have intended to learn regular expressions but don’t have the time can make time to absorb one tip per day.

ProbFact will give one fact per day from probability. I’ll often have a link with each fact for more details. Many of these facts will be theorems, but some will be statements about applications or history.

The SansMouse and RegexTip posts are loosely arranged in order of familiarity, starting with the most basic and most widely used material. ProbFact posts will be more random. Some will be elementary, some more advanced.

I have scheduled tips to come out at regular times starting tomorrow. SansMouse will post at 9 AM, RegexTip at 10 AM, and ProbFact at 11 AM. These times are Central Standard Time (UTC-6).

Related links:

Upcoming Y2K-like problems

The world’s computer systems kept working on January 1, 2000 thanks to billions of dollars spent on fixing old software. Two wrong conclusions to draw from Y2K are

  1. The programmers responsible for Y2K bugs were losers.
  2. That’s all behind us now.

The programmers who wrote the Y2K bugs were highly successful: their software lasted longer than anyone imagined it would. The two-digit dates were only a problem because their software was still in use decades later. (OK, some programmers were still writing Y2K bugs as late as 1999, but I’m thinking about COBOL programmers from the 1970s.)

Y2K may be behind us, but we will be facing Y2K-like problems for years to come. Twitter just faced a Y2K-like problem last night, the so called Twitpocalypse. Twitter messages were indexed with a signed 32-bit integer. That means the original software was implicitly designed with a limit of around two billion messages. Like the COBOL programmers mentioned above, Twitter was more successful than anticipated. Twitter fixed the problem without any disruption, except that some third party Twitter clients need to be updated.

We are running out of Internet addresses because these addresses also use 32-bit integers. To make matters worse, an Internet address has an internal structure that greatly reduces the number of possible 32-bit addresses. IPv6 will fix this by using 128-bit addresses.

The US will run out of 10-digit phone numbers at some point, especially since not all 10-digit combinations are possible phone numbers. For example, the first three digits are a geographical area code. One area code can run out of 7-digit numbers while another has numbers left over.

At some point the US will run out of 9-digit social security numbers.

The original Unix systems counted time as the number of seconds since January 1, 1970, stored in a signed 32-bit integer. On January 19, 2038, the number of seconds will exceed the capacity of such an integer and the time will roll over to zero, i.e. it will be January 1, 1970 again. This is more insidious than the Y2K problem because there are many software date representations in common use, including the old Unix method. Some (parts of) software will have problems in 2038 while others will not, depending on the whim of the programmer when picking a way to represent dates.

There will always be Y2K-like problems. Computers are finite. Programmers have to guess at limitations for data. Sometimes these limitations are implicit, and so we can pretend they are not there, but they are. Sometimes programmers guess wrong because their software succeeds beyond their expectations.

Shorter URLs by using Unicode

Tinyarro.ws is a service like tinyurl.com and others that shorten URLs. However, unlike similar services, Tinyarro.ws uses Unicode characters, allowing it to encode more possibilities into each character. These sub-compact URLs may contain Chinese characters, for example, or other symbols unfamiliar to many users. They’re no good for reading aloud, say over the phone or on a podcast. But they’re ideal for Twitter because you only have to click on the link, not type it into a browser.

Here’s a URL I got when I tried the Tinyarro.ws site:

screen shot from tinyarro.ws

The resulting URL may not display correctly in your browser depending on what fonts you have installed: http://➡.ws/㣸.

I pasted the URL into Microsoft Word and used Alt-x to see what the Unicode characters were. (See Three ways to enter Unicode characters in Windows.) The arrow is code point U+27A1 and the final character is code point U+38F8. I have no idea what that character means. I would appreciate someone letting me know in the comments.

Unicode character U=38F8

Related post: How to insert graphics in Twitter messages

How to grep Twitter

Twitter has an extensive search API. To build the URL for a query, start with the base https://search.twitter.com/search.atom?q=. To search for a word, just append that word to the base, such as https://search.twitter.com/search.atom?q=Coltrane to search for tweets containing “Coltrane.”

To search for a term within a particular user’s tweet stream, start with the base URL and append +from%3A and the user’s name. (The %3A is a URL- encoded colon.) See the search API page for other options, such as specifying the number of requests per page to return (look for rpp) or restricting the language (look for lang).

As far as I can tell, the API does not support regular expressions, but you could loop over the search results programmatically. Here’s how you’d do it in PowerShell.

First, grab the search results as a string. Say we want to search through the latest tweets from Hal Rottenberg, @halr9000.

$base = "https://search.twitter.com/search.atom?q="
$query = "from%3Ahalr9000"
$str = (new-object net.webclient).DownloadString($base + $query)

Now $str contains an XML string of results formatted as an Atom feed. The root element is <feed> and individual tweets are contained in <entry> tags under that. The text of the tweet is in the <title> tag and the other tags contain auxiliary data such as time stamps. The following code shows how to search for the regular expression d{4}. (Look for four-digit numbers.)

([ xml] $str).feed.entry | where-object {$_.title -match "d{4}"}

In English, the code says to cast $str to an XML document object and pipe the <entry> contents to the filter that selects those objects whose <title> strings match the regular expression.

The search API limits the number of entries it will return, so it’s best to do as much filtering as you can via the Twitter site before doing your own filtering.

Related posts

Regular expressions in PowerShell and Perl
Table-driven text munging in PowerShell

Twitter is not micro-blogging

Twitter is often described as a micro-blogging platform. Twitter posts and like blog posts, except they’re limited to 140 characters (so they fit in a cell phone text message). You subscribe to Twitter posts (called “tweets”) sorta like you subscribe to a blog. Some people, like Kathy Sierra, do use Twitter for micro-blogging. Her tweets are little self-contained messages, often one sentence. Here’s a recent example:

Much as I liked Outliers, makes me cringe to see people focus on “it’s all luck/chance” rather than the “it takes 10,000 hours” part.

Nice observation, all in 133 characters. (She’s talking about Malcolm Gladwell’s book Outliers. He argues that success is a matter of accumulated lucky advantages plus around 10,000 hours of deliberate practice.)

Maybe the most common form of micro-blogging is link sharing. Here’s an example, again from Kathy Sierra.

…and for those whose head literally explodes over misuse of the word “literally”  https://literally.barelyfitz.com/

Some people use Twitter as a question-and-answer forum. This is sorta like blogging and inviting comments, and it can be very powerful.

But a lot of traffic on Twitter is not what I’d consider micro-blogging.  It’s more like a public form of instant messaging. I found this disorienting when I first started using Twitter. Who are they talking to? Context?! Why would I want everyone to see my instant messages? I suppose it’s an acquired taste.

Everyone on Twitter has some mixture of micro-blogging, Q&A, and instant messaging. Some people love the instant messaging-style conversations. To each his own. My preferred mix is weighted toward micro-blogging and Q&A.

I’m on Twitter at @johndcook.

Update (29 March 2010): It’s been more than a year since I first wrote this post. I now use the instant messaging aspect of Twitter a little more than I did then, though I still prefer the micro-blogging aspect. And I’ve created several daily tip accounts that are pure microblogs.