This week’s Monday Math Madness is up at Wild About Math!. Looks like a fairly accessible problem this week:
What’s the prime factorization of the smallest whole number that is divisible by all integers from 1 up to and including 50?
Submit an answer (see the post for instructions), and maybe win a prize!
In a previous post, I noted that the length of the repetend (repeating portion of the decimal expansion) of a fraction with prime denominator p is at most p-1, and in fact divides p-1. I also said:
In fact, there’s even more that can be said about non-prime denominators, as well.
This was something of a cop-out, and today I’m going to correct that! In general, suppose the denominator d can be factored as
that is, d can be factored as the product of the prime 
to the 
power, the prime 
to the 
power, and so on. (For example, 
.) Then it turns out that the length of the repetend of any fraction with denominator d will be a divisor of
(The 
denotes a product; you can read about the notation here if you haven’t seen it before.) When d is prime, we can see that this just reduces to d-1 as we would expect. For each additional prime p in the factorization, we multiply by p-1; for each additional power of a prime p beyond the first, we multiply by p.
So, for example, the repetend length for fractions with denominator 221 = 13*17 should evenly divide 
; and indeed, the repetend length of 1/221 is 48. As another example, the repetend length of 
is 726, which indeed divides 
.
You may wonder how I know this. Well, asking for the repetend length of a fraction with denominator d amounts to asking for the smallest power of 10 whose remainder, when divided by d, is 1. Another way to say this is that we want to know the order of the element 10 in the group 
(the group of positive integers less than and relatively prime to d under multiplication). By Lagrange’s Theorem, the order of any element of a group divides the order of the group; so the question becomes, what is the order of ? The answer, as explained e.g. on p. 155 of Contemporary Abstract Algebra by Joseph Gallian (Houghton Mifflin, 2002), is the above formula.
Now, maybe that went way over your head. It certainly did if you’ve never studied any group theory. But I don’t know a simpler way to explain it! Perhaps there is a better way, and if you know of one, I’d love to hear about it in the comments. Nonetheless, this is a great example of a simple question that quickly leads into some very deep structure.
You may also wonder how on earth I know that the repetend length of 1/17303 is 726! No, I didn’t sit there and do long division; of course, I wrote a computer program. Perhaps I will post it soon.
As promised, I can now reveal the identity of the two newly discovered Mersenne primes. The smaller of the two, discovered on September 6 by Hans-Michael Elvenich in Langenfeld, Germany, is
These are ridiculously huge numbers. For a little perspective, the total number of atoms in the universe is estimated at somewhere around 
, a number with only eighty-one digits. Now go back and read again how many digits these newly discovered prime numbers have.
The Great Internet Mersenne Prime Search just announced not one, but two new Mersenne primes! You might also recall the last time they announced a new prime, in September 2006, so these new primes were found almost exactly two years after the previous one. They haven’t actually announced what the primes are yet, but both of them are almost sure to be longer than ten million digits, long enough to claim the $100,000 prize offered by the Electronic Frontier Foundation! If they both end up being longer than ten million digits, I guess it sucks to be the guy whose computer discovered the second one (just two weeks after the first). You don’t get any money for discovering the second of anything.
Anyway, as soon as they announce the actual numbers, I’ll be sure to let you know!
This is the last in a series of posts about perfect numbers. A quick recap of the series so far: in part I, I defined perfect numbers as positive integers n for which 
, where 
denotes the sum of the divisors of n. I also revealed that if n is factored into prime powers as 
, then can be calculated as follows:
In part II, we saw where this formula actually comes from. Finally, in the challenge interlude, DB and Steve Gilberg (and you?) found that the first four perfect numbers seem to all be of the form 
; DB additionally claimed that this only works when 
is prime.
Well, it’s true: is perfect whenever is prime. But you don’t have to take my word for it—let’s prove it! Since n is perfect if , we want to show that 
if is prime. Applying the formula for , this is just some straightforward algebra. (Note: by “straightforward” I don’t mean “you’re dumb if you don’t see it immediately”; I mean “if you’re patient and persistent, you should be able to work it out for yourself”. Mathematicians are fond of saying that things are “obvious” or “straightforward”, but this is what they actually mean.)
Voila! Just what we wanted to show. Note that the restriction that must be prime is very important: the formula for assumes that n is factored as a product of prime powers, so the computation above is invalid if can be factored further.
So, the question becomes, when is a number of the form 
prime? Well, first of all, m must be prime; if m can be factored as 
, then can also be factored, as 
. But is it enough for m to be prime?
Notice that the first four perfect numbers correspond to the first four primes, 2, 3, 5, and 7:
The next one, however, dashes our hopes: 
. Now, it is important to note that this doesn’t necessarily mean that 
isn’t perfect: we have only proven above that is perfect when is prime, which doesn’t necessarily say anything about what happens when it isn’t. However, it turns out that this is indeed true. In fact, more is true: all even perfect numbers must be of the form , with prime. There are no other kinds of even perfect numbers. So, we saw that 11 doesn’t give us a perfect number, but it turns out that the next three primes (13, 17, and 19) do:
are all perfect. But then a few more primes get skipped; the next perfect number corresponds to 31.
Primes of the form might ring a bell for long-time readers of this blog: these are the Mersenne primes! As of right now, we know of 44 Mersenne primes, and therefore we know about 44 perfect numbers. The largest known Mersenne prime has almost ten million digits, so the largest known perfect number has about twice that many!
Now, what about odd perfect numbers? Are there any odd numbers which equal the sum of their proper divisors?
…No one knows!!
Today I came across this nifty Space Invaders-like game — except instead of shooting bullets at UFOs, you shoot prime factors at integers. For example, if the number 66 is falling towards you, you need to shoot it with 2, 3, and 11 to make it go away. Silly but fun!
(found via God Plays Dice)
Oops, so much for posting once a week! My excuse is that I’ve been hard at work on my book. Well, nothing to do but get right back at it. I promise* I will be better** about posting regularly*** from now on.
* I had my fingers crossed when I typed that. Seriously.
** For low values of ‘better’.
*** Some restrictions may apply.
Anyway, I thought I would begin an intermittent series describing some currently open (unsolved) problems in mathematics. It’s pretty fascinating that in mathematics (unlike in many other academic disciplines) it’s not too hard to come up with questions that are very easy to understand, but incredibly difficult to answer! It just goes to show that sometimes, the simplest questions end up being the deepest.
Today, I’m going to talk about the twin prime conjecture. A prime number, as you may recall, is a positive integer greater than 1 which has no divisors other than 1 and itself. For example, 17 is prime, since there is no number less than 17 that evenly divides it, but 18 is not prime (it is composite) since it is divisible by, for example, 3. The first few prime numbers are thus 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37… Prime numbers serve as building blocks for all the other integers, since any integer can be written uniquely as a product of primes (this is called the integer’s factorization).
Let’s look at the sequence of distances from each prime to the next: 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, … See a pattern? I sure don’t. In fact, this is one of the most enigmatic things about the prime numbers: although there are theorems describing approximately how often primes occur, there is no neat pattern (that anyone knows of) which describes exactly when primes will occur. As you go through bigger and bigger integers, primes tend to get rarer… yet there is still no pattern. On average, the higher you go, the farther apart the primes will be — yet every now and then, primes still occur right next to each other, like 29 and 31. Pairs of primes which are only two away from each other are called twin primes. Larger examples of twin primes include 101 and 103, 281 and 283, and the whopping
a gargantuan pair of twin primes with 58711 digits each! This is actually the largest known pair of twin primes, discovered just this year, on January 15. So, here’s the question: are there infinitely many pairs of twin primes, just like there are infinitely many prime numbers? Or do the primes eventually get so few and far between that the twin primes stop? No one knows! The twin prime conjecture (a conjecture is like a mathematical guess) states that there are an infinite number of twin primes — most mathematicians believe that it’s true, but no one has been able to prove it.
A challenge to conclude: we could define “triplet primes” as a set of three consecutive odd numbers p, p+2, and p+4 which are all prime. This wouldn’t be a very useful definition, however, since 3, 5, 7 is the only set of triplet primes. Why?
You can learn more about twin primes and the twin prime conjecture at MathWorld.
After seeing John H. Conway and Richard Guy’s
The Book of Numbers cited in yet another interesting article/book/whatever, I finally decided that I clearly had to read it. (It seems to get cited a lot in certain circles.) I wasn’t disappointed — it’s a fun, well-written, and far-ranging tour of mathematical ideas all stemming from the concept of number. You might think such a topic would be somewhat limiting, but you would be very wrong! Along the way Conway and Guy manage to touch on such topics as number theory, geometry, algebra, pi, fractions, partitions, Babylonians, infinity, irrationals, primes, pineapples, Fibonacci numbers, Pascal’s triangle, complex numbers, quaternions, surreal numbers, harmonic numbers… to name just a few.
In order to pack so much interesting stuff into the book, the presentation is by necessity fairly concise; for this reason and because of the topics covered, the level of the book is definitely more advanced than many of the other books on my bookshelf. The authors don’t shy away from advanced topics, but the writing style is still friendly and compelling. Even if you don’t understand everything in the book (even I didn’t follow a few things the first time), you’ll undoubtedly learn some cool things, and it could be a book to grow with as you continue to learn more mathematics.
At some point I hope to create a page with more detailed descriptions of all the books on my bookshelf (which can be found in the right margin). In the meantime, if you read a book that you think I should include, or read one of the books already on the bookshelf and want to talk about it or offer your opinion or comments, of course feel free to leave a comment or e-mail me.
[Note: Amazon.com isn't paying me to link to them or anything, it's just a convenient way for me to link to more info about the book. If you want to buy a copy, of course feel free to buy it from anywhere you want!]
GIMPS has just announced today that they have indeed found a new Mersenne prime!
Obviously I can’t print the whole thing here, but I can tell you that the first 50 digits are 12457502601536945540085550157479950312279598515115, and the last 50 digits are 212445737104635692000092659011752880154053967871. This is now the largest known prime number, breaking the previous record set in December 2005. (Of course there are larger prime numbers — there are infinitely many — but this is the largest number that we can actually point to and say, “this number is prime.”) You can download it here. You can even order a poster of it! (It’s pretty expensive though, since it’s very difficult to print digits tiny enough to make the whole number fit on a poster.)
Unfortunately, at 9,808,358 digits, it’s just shy of the ten million digits needed to claim the $100,000 prize offered by the EFF. But it’s still pretty exciting.
More information can be found in my previous post.
The Great Internet Mersenne Prime Search has just announced that they have (probably) discovered a new Mersenne prime. They haven’t released any details yet so speculation abounds. Will this be the prime to win the $100,000 prize awarded by the Electronic Frontier Foundation to the first discoverer of a ten million-digit prime? We’ll see in about a week, once an independent computer check confirms the result.
So, what’s the big deal? A Mersenne number is a number of the form 
; for example, 
, 
, and 
are all Mersenne numbers. Mersenne numbers which are also prime (that is, which have no divisors other than themselves and one) are called (not surprisingly) Mersenne primes. For example, 3 and 7 are Mersenne primes, but 1023 is not (
). The thing about Mersenne numbers is that there are ways to write computer programs to check whether they are prime which are a LOT faster than simply trying all possible divisors. For a while now, the largest known prime numbers have been Mersenne primes.
The Great Internet Mersenne Prime Search is a distributed computing effort — sort of like SETI @Home if you’ve ever heard of that — which tries to find new Mersenne primes. Anyone at all can sign up to help; all you have to do is go to their webpage (linked above), download some software, and then whenever you are not using your computer it will work on checking really big Mersenne numbers to see if they are prime. Give it a try! It won’t run while you’re actually using your computer, so you won’t notice any slowdown. And you have a small chance of being famous (well, sort of) or even receiving a cash prize if your computer happens to be the one to discover a new prime.
So, how big are these numbers we’re talking about? Well, the largest currently known prime number (not counting the one that was just announced, which we don’t know yet) is 
, which has a whopping 9,152,052 digits! You can download it here, but keep in mind that since each digit takes 1 byte to store, the file is 9MB in size!
You can read more about Mersenne primes on MathWorld.
You are currently browsing the archives for the primes category.
