Checking whether a number is prime.

You can't really check whether a number is prime, you can only check whether it divides by a prime number smaller than the square root of the original number and rule it out if it does. So it's a question of ruling out as many as possible as quickly as possible.

First, you rule out even numbers and numbers ending in 5 (apart from 2 and 5).

The next obvious/easy thing to do is to add the digits and see if they add up to 3, if they do, the number divides by three i.e. 291 = 2 + 9 + 1 = 12 (unless you start with 3, which itself is prime).

But I've watched another couple of maths videos on YouTube, and what they boil down to is that there is a better test that helps you rule out more numbers. The test is - divide the original number by thirty and just look at the remainder, or take "number mod 30" if you are using a scientific calculator.

If the remainder is not a prime number, the original number is not prime. If the remainder is prime (or ends in 1, even though the number 1 itself is officially not a prime number) and the original number is less than 300, there is a two-thirds chance the original number is prime. The chance of it being prime is slightly better than 50% for numbers up to 1,500. That percentage drifts downwards, the larger the number is. So if the original number was above 1,500, you might as well just assume it is not prime, even if the remainder is prime.

If the original number passes the second test and you want to improve your chances of getting it right, you have to do the long hard slog with divisibility tests, and check if it divides by 7, 11, 13...

I hope this comes in handy next time you are in a pub quiz. I can't think of many other uses for such trivia.

The recently discovered largest prime numbers continues the pattern nicely...

With thanks to James Higham whose post alerted me to this.

I explained that there appears to be a surprisingly consistent pattern if you plot the number of digits against date discovered back in 2016.

Here's the updated chart:



UPDATE: It turns out I needn't have bothered doing my own spreadsheet, the relevant Wiki article includes a much longer term chart showing exactly the same phenomenon: "The red line is the exponential curve of best fit: y = exp(0.187394 t - 360.527), where t is in years."

Typical, you wait for ages...

… and ages and ages, and along comes another prime number.

The largest known prime number is now almost five million digits longer than the previous record-holder.

In a computer laboratory at a satellite campus of the University of Central Missouri, an otherwise nondescript desktop computer, machine No. 5 in Room 143, multiplied 74,207,281 twos together and subtracted 1. It then checked that this number was not divisible by any positive integer except 1 and itself — the definition of a prime number.

This immense number can only be practically written down in mathematical notation using exponents: 2^74,207,281 – 1. The previous largest was 2^57,885,161 – 1, which has a mere 17 million or so digits.
-------------------------
So, just to sum up the last few discovered primes:

Jan 2016: 22 million digits
Feb 2013: 17 million digits
Sept 2008: 13 million digits
Jan 2006: 9 million digits
Dec 2003: 6 million digits
Dec 2001: 4 million digits

For some reason, they are usually discovered in December or January. A coincidence? I think not.

What is almost certainly not a coincidence is that you get a surprisingly straight line when you plot the number of digits against the year it was discovered:

"New Largest Prime Number Is 17 Million Digits Long"

From Time:

Curtis Cooper, a researcher at the University of Central Missouri, reportedly spent four years searching for the new prime number. And in late January, his quest was confirmed. Behold the new longest prime number in the world: 2^57,885,161 – 1.

The new discovery, at 17,425,170 digits, crushes the 2008 record number of 12,978,189 digits. Cooper is something of a legend when it comes to prime-number discovery: this is the third one found by him and his team.

The professor in charge was on Radio 4 this morning, the interviewer asked him what the practical application of the new prime number was and he chuckled and replied "None whatsoever. Maybe they'll find a use for it in a hundred years' time."

As I said last time they discovered the biggest prime number in September 2008:

If there is a pattern here, and in maths there usually is, it takes an average of 830 days to discover a new prime number, and the number of digits goes up by 48% each time, so the next prime number will have about 19 million digits and will be discovered on 5 January 2011.

So I was only wrong by two million digits and two years and a bit. Ah well.

"Huge new prime number discovered"

BBC, 5 December 2001,"The largest prime number yet discovered has just been revealed to the world. The new number, expressed as 2^13,466,917-1, contains 4,053,946 digits [and] was discovered by Michael Cameron, a 20-year-old Canadian..."

Metro, 4 December 2003, "The maths world was celebrating last night after the discovery of the largest known prime number. It has 6,320,430 digits ... American Michael Shafer found it after joining the Great Internet Mersenne Prime Search. He said: 'After a short victory dance, I rang my wife and GIMPS friends'".

Metro, 5 January 2006, "After years of calculating [a computer] has come up with a prime number 9.1 million digits long - the largest ever found. Steve Boone, who led the study at Central Missouri State University, said: 'We are very excited.'"

BBC, 28 September 2008, "Mathematicians in California could be in line for a $100,000 prize (£54,000) for finding a new prime number which has 13 million digits. Edson Smith, the leader of the winning UCLA team, told the Associated Press news agency: 'We're delighted. Now we're looking for the next one, despite the odds.'"

If there is a pattern here, and in maths there usually is, it takes an average of 830 days to discover a new prime number, and the number of digits goes up by 48% each time, so the next prime number will have about 19 million digits and will be discovered on 5 January 2011.