Assume For Contradiction

Am I the only one who’s noticed an amusing (or perhaps alarming) tendency of proofs by contradiction to sneak in places they don’t really belong?

Let me illustrate with an absurd example.

Prop 0. It is cold outside.

Proof. Assume for contradiction that it is warm outside.
Then it must not be snowing right now.
But it is snowing right now.
This is a contradiction, so our assumption was false.
So it is cold outside.

Continue reading

Advertisements

Large Primes, The Beatles, and $100,000

Prime numbers have fascinated mankind for thousands of years.

Or, rather, they’ve fascinated about 1/11th of mankind, and bored the rest.

But big primes are incredibly important in cryptography.  Every day, we rely on 512-bit primes — numbers about 150 decimal digits long. Our Internet data is secure, relatively, because it’s so hard to factor numbers this size.

But for the adventurous, 150 digits is nothing. What if you want to be cutting-edge? I’m talking the Lady Gaga of primes. If so, then you probably want to be the largest known prime: currently, 243,112,609 − 1.

How big is this number? It’s about 13 million digits long. (Think small bookshelf, full.) If you like, you can see part of the number here or even view the whole number here (the page could take a while to load!).

And like pop music, finding large primes can be lucrative (not as lucrative as being a record label, but still). The Electronic Frontier Foundation gave away a $100,000 prize to the first folks to find a 10-million-digit prime, and $150,000 is on the line for the first 100-million-digit prime.

Where do The Beatles come in?

They’re no longer as hip as Gaga, sure, but they still have plenty of devoted fans.

Now, you could argue that they were more into perfect squares than primes, with songs like “Revolution 9” and “WhenI’m 64”. But nevertheless, there’s a statistical chance that the Beatles created a “prime song” without even knowing it.

Here’s what I mean. If you take the largest known prime, 243,112,609 − 1, and store it on your hard drive, it’ll take up about 5.4 MB.

Now consider the Beatle’s song A Day in the Life, encoded as an MP3 at a nice average 128 kbps (kilobits per second).  That takes up somewhere in the neighborhood of five megabytes as well.

But here’s where the beauty of computers come in. A 5 MB file is just a whole lot of zeros and ones. If you give them to iTunes with the extension ‘.mp3’, then those zeros and ones will be interpreted as a music file and they’ll be played. On the other hand, you can choose to interpret them as a number. Looking at it this way, there’s a chance that A Day in the Life could be the largest prime ever discovered!  (If the Beatles aren’t really your thing, you could try the songs Wake Up, Where It’s At, or Californication.)

Sign me Up. I want to find a prime in a song.

Not so fast. You’ll need an incredibly well-trained ear and years of experience. OK, no you won’t. But it’s probably not too likely that many primes will sound aesthetically pleasing, or that many pop songs are represented as primes.

Let’s say you acquire the necessary skills and sit down with your music library to find a prime song. What are your odds? Luckily, there’s a theorem that tells us: The Prime Number Theorem. It tells us how often primes tend to occur: specifically, if we’re close to the number N, then we should find a prime number about once every log(N) numbers. (log(N), as you may or may not recall, is roughly a measure of the number of digits it takes to write down N.)

Applying the Theorem, we see that, on average, one in 30 million 5-minute songs, in a normal MP3 format, should be prime numbers. (Perhaps I’ll write a program to check all the songs in someone’s music library … then again, maybe not.)

Best of all, Gracenote’s media database contains 100 million songs, which means there’s a pretty decent chance that one or more of those is a prime — possibly a bigger prime than any yet discovered! Get listening! And if you win a cash prize, be sure to send me some.