Wednesday, 21 January 2009

I don't like that proof...

I'm not ashamed of it - I love maths. Well more specificially I love numbers.

Ever since I was a kid, I've loved asking questions about numbers. I remember from any early age being irked by the fact that 2 is the only even prime number. Of course, my adult mind can rationalise that even means "is divisible by 2" and hence 2 is no different to any other prime number - the difference is a semantic one because we've given a label to the concept "divisible by 2". It's trivial, of course, that every prime is the only prime divisible by itself.

There are a lot of prime numbers. An awful lot. In fact, there's an infinity of them. Even at school we were taught an easy proof that there are an infinite number of prime numbers. It went like this...

Presume there's a largest prime number and call it P. Take all of the prime numbers up-to and including P and multiply them together and add one. Voila - another prime which is bigger than P. Hence a contradiction and there is no largest prime.

Of course, there are a couple of problems with this proof which you tend to gloss over at school. The first is that this misses out a lot of prime numbers because between P and this much bigger prime we've constructed, there are probably lots of other prime numbers. In fact, we know that there are primes between P and it's larger cousin (for those who care about such things, there are other proofs of the infinity of primes which put a bound on the nth prime lower than this proof I've given above, hence showing that there is at least one prime larger than P but lower than it's big cousin).

At school, I accepted this proof without question and at the time thought it was one of the "best things ever" but my adult mind questions it. I'm not convinced that it's trivial that the new number you construct in this way is definitely a prime. With my adult mind, I have always prefered a slightly adapted and belt-and-braces approach to this proof as follows.

  1. Presume there is a largest prime P.
  2. Multiply together all of the prime numbers up-to and including P and add one to the product. Call this number N.
  3. N has a unique set of prime factors by the Fundamental Theorem of Arithmetic. (N may, of course, be the only prime factor of N)
  4. Each of the primes up-to and including P is a factor of N-1 and as each of them is larger than 1, they cannot also be a factor of N.
  5. So, all of the prime factors of N - whether N itself is the only such one or not - must be larger than P.
  6. Hence we have a contradiction.
For those of you who recognise the latter of the two proofs, it was Euclid who first came up with it...

Interestingly, you don't need to go very far to find a case where N in the example above isn't prime. 2 x 3 x 5 x 7 x 11 x 13 = 59 x 509 is the first, according to the wonderful internet :-)

Sunday, 11 January 2009

That was written about me...

Isn't it funny, that you tend to find references to your own life in to things you see and read. The other day, I was doing a crossword and almost every other answer in the grid seemed to refer to something happening in my life at the time. It's almost spooky.

Except it's not, of course.

Unlikely things happen all the time, of course. You just can't predict exactly which unlikely thing is going to happen. I can be certain that something statistically unlikely will happen to me in the next hour - but I can't predict what it will be.

For instance, if I go out for a walk (which I am considering doing, as it happens) then I could count the number of people I see out walking. If that number was zero, then I could come back and write "it was so weird, nobody was out there today, spooky eh?". If the number was exactly 100 I could write the same thing - except with some waffle about seeing exactly 100 people.

I am currently digging into my family tree again, and one of the things which surprises me is that I've not yet discovered that I'm related to either anyone famous or anyone else I know (except my family of course, but I already know I'm related to them). I think the same logic applies to the idea that seeing someone you know whilst you're out is somehow "spooky".

I know a lot of people. If I were to count up everyone I remember from school and University and everyone I've worked with over the past few years - plus everyone I remember meeting at parties and events - I'd easily count over 1000 people.

Now, let's say that I research my family tree back 10 generations. That is over a thousand direct ancestors of mine (presuming I've filled every blank in the family tree, that is). That's a lot of people.

And if everyone one of my 1000 acquaintances did the same thing, then although it's not impossible that every one of our 1000 ancestors doesn't overlap, it wouldn't be that surprising, either.

I think there's an in-built desire to marvel at things we perceive as unlikely - even when the statistics show that they're quite common. The most oft-cited example is that of gathering people in a room and finding out that two of them share the same birthday. I won't go into that one, as I'm sure it's familiar - but it brings me back to the earlier point of my Sunday walk...

A lot of people confuse this with gathering people in a room and suddenly expecting that one of them will share your birthday - which of course is fairly unlikely.

Anyway, before start editting this and inserting any semblence of rigour into the arguments above, I think I shall take the Sunday walk. Laters.

Thursday, 1 January 2009

Why must we go outside?

There's a strange behaviour here in the UK just before midnight on 31st December, and I don't know whether it's something which infects other nations too.

But there's a strange desire to go outside. Whether it's freezing cold or raining or snowing or whatever, one MUST go outside and say "Happy New Year" then come back in again.

This isn't the old tradition of bringing coal in and going out the back door and in through the window or whatever that tradition says, it's just an in-built programme which fires off around quarter to midnight and before you know it, everyone in the room is wrapped up in miles of scarfing and wearing thick coats trying to marshall each other outside into the garden in time for midnight.

2009 doesn't feel any different to 2008 so far. Well, we do have a new kitchen bin, but that hardly makes the year feel special. There's a sense of optimism at midnight when the New Year arrives but then you wake up the following morning and read that Israel are about to send ground troops into Gaza and the Russians are turning off gas supplies to the Ukraine and realise that the world moves on, untroubled by the arbitrary numbers and labels we attach to the passing transits of the sun across the sky.

I've stuck to my resolutions so far, which is good going as it's nearly 19 hours now... :-)