The Prime Challenge

Here’s some sample C# code you might want to hack around a bit yourself. Most of it is hardcoded but you could easily change it to your own needs. As it stands it’s hardcoded to find out whether 2^291113-1 is prime. You could ask for a base to search from and then increment in 2s from there. To make it more efficient make sure you don’t end up with a number that is divisible by 3 or 5; you could probably push to 7, 11, 13 and 17 as well.

This code uses the Rabin Miller test and extends the way the BigInteger data type in .Net works. The extension code isn’t mine. I found it here  (search within the page for “BigIntegerExtensions”). Would appreciate a proper maths-head to confirm it accurately implements the Rabin Miller test? The tests I’ve done on known primes suggests it does but it’d be nice to have it confirmed.

Rabin Miller is a probabilistic test. It returns a high probability that the number is prime.

Have fun with it,

Planky — @plankytronixx

Primo leaves you in no doubt regarding what you’ve found..

Well, PHunterLau is storming away at the front of the leaderboard.

I did get a very odd result and have checked it with Primo 3 times (many many hours for each execution!) for PHunterLau’s entry – 52388…..2811.

It says “Candidate binary size < 17″. I’m not sure what this means. Well, I know what the statement means (and it’s not true) but I don’t know what it means in the context of Primo.

Experience so far shows that wne a number is prime it says “Candidate is Prime”, so I’m guessing this number has failed the deterministic test on some grounds.

It uses a number of tests of which elliptic curve testing is the main one. Perhaps this statement has something to do with the arguments used in EC testing…

Planky   —   @plankytronixx

When I set this challenge up, it seemed entirely reasonable to say that a prime is only a prime if it can be proved to be so, with a deterministic test.

So the idea that challengers could enter a probabilistic prime, but not actually get a verified placing in the challenge until the prime was verified to be indisputably prime seemed eminently sensible.

I’m using primo to deterministically test if those primes are genuinely prime.

I’m only running the test on  low-powered cloud computers. Linux machines with 1.75GB RAM and a single core processor, and using primo to do the test.

I remember one test a few weeks ago taking slightly longer than 12 hours to test a 3,000 digit number. All has worked well, until now. I don’t think I’m giving too much away from any challenger if I say some of the recent numbers entered have been in the 4,000 to 5,000 digit area.

I have a deterministic test that has been running on one of the Linux machines with primo for the past 60 hours…

I have more numbers to test and have just provisioned a collection of 14GB/8 core cloud computers to run the tests for me. Luckily it’s possible to configure primo for multiple cores. It will save a little time. But if the difference between a 3,000 digit and say a 4,500 digit number is only a 50% increase in digit count but a 500% increase in the test time (and it’s not finished yet), then it doesn’t bode well for when we get to the 10,000 digit mark. And once we’re up in to the hundreds of thousands of digits area, testing is going to become a serious bottleneck.

I was away for 10 days and a reasonable backlog built up, which is what I’m dealing with now. But I think as larger and larger numbers get submitted, it’s going to become impossible to verify all the numbers and there’ll be a permanent backlog.

So – I’m toying with the idea of allowing probabilistic primes to be the verification process. I’ll measure how testing goes with the more powerful cloud computers first in case they give some amazing increase in performance. But stay tuned because I think a change in the rules might have to be made in order to get through the challenge with a set of tested numbers.

It doesn’t really change who the winner would be. Although the challenge itself closes on the 29th March, testing can continue for some weeks/months after that to come to a conclusion about who the winner is in reality with a deterministic test of the highest number. Or let’s say, the top 3 anyway. That might take some time.

Prof Curtis Cooper had to wait 39 days for the verification test of his record breaking 48th prime when he got the world record. I daresay the code used (apparently it was calc – I think a rather different version to the package I’ve built in to the Linux images) was highly efficient. It was put together by number theory researchers who have been working in this area for many years.

I wrote some simple code to search for probabilistic primes (using the Rabin-Miller test) starting at 2^291113-1 and counting upwards in odd numbers.

I know it’s a very inefficient way of doing it and I’ll get round to making it much more efficient later.

But I’ve searched all the odd numbers from 2^291113-1 to (2^291113-1)+15388 so far and not found a single probable prime…. I’ll leave it running overnight and see if anything turns up!

You guys (phunterlau and TrustworthyDiplomat), are you “searching” the number space for probable primes Or do you just pick a big number randomly, do a test and bingo – you find primes that way?

Or is it that when you say you pick a random number you have code that just generates large random integers and tests them one after the other? I wonder if that has more chance of finding a prime than my sequential method…

I’m using the GNU MP library, the Win32 version with Emil Stefanov’s .Net wrapper. It has a built-in method – .isProbablyPrimeRabinMiller().

Maybe they really didn’t expect people to test 8,000+ digit numbers and that test is returning no probable.

I only set the repetition count to 1. I think that means I should get more false positives, not the other way round. So testing at that depth should be yielding more probabilistic primes than the number of true primes – shouldn’t it?

Anyway, as a non-math-head, I’m quite surprised how rarified the air is around the 8000 digit mark….

Ha ha! If this is an old post by the time you read it, it’ll make no sense because we’l have fixed the site.

TrustworthyDiplomat has worked out our algorithm for sorting the results while the primes are still pending. We simply count the number of digits in the submitted file. We only compare the magnitude of any numbers if 2 files have the same number of digits.

Take the example of a 2000 digit number. The lowest 2001 digit number is always bigger than the highest 2000 digit number. Therefore the only time we need to test the magnitude of numbers is when there are 2 or more numbers with the same number of digits.

TrustworthyDiplomat has spotted this and shot to first place (pending) with 00000….00002. To our algorithm it appears to be a huge even numbered prime! Luckily, we have humans here (me!) to look out for things like that.

Very inventive TrustoworthyDiplomat. Well spotted! I’ll leave you up there in the limelight for a few more days so you can luxuriate in first place for a little longer. I did laugh when I saw it – well done for bringing some Christmas cheer to us all with the first Prime Challenge joke of the season – ha ha ha!

Q: How many programmers does it take to change a light-bulb?

A: Can’t be done, it’s a hardware problem…… budum-tish!

Planky   —   @plankytronixx

Unfortunately Jing’s latest entry has proved to be divisible by 3: so it’s not prime. Try again though…

Planky   —   @plankyronixx

Maybe you are a non math-head sat there thinking to yourself “I have to just pick some random big number and test to see if it’s prime”. But of course, you also judge that it may take some hours, or if it’s a particularly big number, even days and it might come back with something like “the number is divisible by 28455776344775673451″, which would be disappointing.

The question is where do you start? Do you just randomly type digits in to a huge long string until you have say 10,000 digits?

Well, one way to start is with a know huge prime. Now although there’s no gurantee that a Mersenne candidate (2^p-1) is a prime, it’s a pretty good starting point. You can be fairly certain that all the Mersenne primes up to the world record find (17.425 million digits) have already been discovered. So you probably can’t use one of them. But you could use that as the basis for your discovery.

For example, the closing date of this challenge is 29th March next year (2903). 2903 is a prime. It’s a small one. But if you used it as the exponent in a Mersenne expression you end up with 2²⁹⁰³-1.

That comes out as:

77638…..<865 digits>….47007

You could then start testing numbers slightly above that. Incrementing by 2 for each test, so the last 5 digits of each test would be:

47007

47009

47011

47013

47017

47019

…and so on. You might notice I’ve missed out 47015. Any number that ends in 5 is divisible by 5.

Next question is – how do you know that 2903 is prime in the first place? Well, it’s fairly easy to find lists of low primes on the Internet. A good site to go is:

http://www.isprimenumber.com/

You can enter a low prime and it will tell you if it’s prime. It will also give you a list of other close-by primes. In this case, it said

“Smallest 10 prime numbers bigger than 2903

• 2909
• 2917
• 2927
• 2939
• 2953
• 2957
• 2963
• 2969
• 2971
• 2999

…so that gives you another set of “bases” to work from. You could take that last prime value and do the Mersenne calculation then base your further exploration for non-Mersenne primes on that.

If you log in to one of the Linux servers in your free-trial cloud subscription – you can see the longhand value of the Mersenne using the last number in the list above: 2²⁹⁹⁹-1 by using calc.

…if you want to get that big long number in to a file – you type:

calc 2^2999-1 > filename.txt

…where filename.txt is the name of the file you want the result to be written to.

You might have noticed the website was really 2 separate services. One at www.primechallenge.org and the other at results.primechallenge.org .

Well, now, you’ll gradually see those 2 sites come together under a common set of menu items deployed across both sites. So you’ll be bouncing between one site and the other without really knowing it or experiencing that jolt as the layout and design of each site was slightly different.

This will slowly and gradually improve over time.

Keep posting new large primes. I haven’t had any big primes to verify for a while. The last one I did took 312 seconds.

Leave a comment. It can be about anything to do with the Prime Challenge – you don’t have to comment on this post or any post. You can communicate with each other through the comments in this blog.

Planky    —   @plankytronixx

I’ve left them in in the results table for the moment: Trustworthy Diplomat has entered 18 which is an even number. There are no even primes other than 2. However, he/she has also entered a large prime and that has netted them a validated 5th place (as of today).

CatalinPreda has entered a number which is divisible by 13. Catalin – why not have another go? One trick is to provision say 6 or 10 cloud servers and give your first number, n, to the first machine to calculate if it’s prime or not. You can simultaneously line up n+2 for the next cloud computer, n+4 for the next one and so on, until you get to n+20 for the 10th cloud computer. That way you’ll be checking 10 numbers simultaneously. Follow the 5-step process to get started and then you could up your game and test some really big numbers…

Our leader as of today, phunterlau, is using the Miller Rabin test for primes. It looks like they might have written their own code to do this test. Here is the pseudo-code, from the above article:

Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2^s·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
pick a random integer a in the range [2, n − 2]
x ← a^d mod n
if x = 1 or x = n − 1 then do next WitnessLoop
repeat s − 1 times:
x ← x² mod n
if x = 1 then return composite
if x = n − 1 then do next WitnessLoop
return composite
return probably prime

…if you’re not used to coding or maths, it might look a little intimidating. But remember – you don’t have to worry about that because if you follow the 5-steps, you can simply take part using the instructions in the 5-step process and you have just as much chance as anybody else of winning…

If you are familiar with maths and coding, this is not as simple as it may first seem. The problem is holding the number in an appropriate data type. Even a double-precision floating data-type has a maximum value of 9,007,199,254,740,992. 16 decimal digits.

So large-number explorers tend to use huge arrays of integers and treat them pretty much the same way as you might treat the individual digits in say a long-division problem. Because they solve the problems at computer speeds they can crunch through the numbers very quickly.

If you followed the 5-step process and have a cloud computer running, the program calc does things in exactly that way. If you type in 2^291113-1 it will spit out an 87,636 digit number. I’m not going to tell you if it’s prime or not. Maybe one of you would like to test it? Here’s the number

556067776021953475339556023….<87,592 digits>….25774572055560191.

Remember, that by combining cloud computing with this problem, you can have several computers working for you simultaneously. It took several hours for me to validate phunterlau’s latest prime, but I just let it run overnight on one of my cloud computers. It was running away in the datacentre in Dublin, Ireland, doing its work without me having to worry about whether it would sleep after an hour or if the screensaver would cause it to hibernate after 30 minutes without keyboard presses.

Planky — @plankytronixx