Drobe :: The archives
About Drobe | Contact | RSS | Twitter | Tech docs | Downloads | BBC Micro

Playing with prime numbers on RISC OS

By Martin Hansen. Published: 6th Jan 2007, 19:18:28 | Permalink | Printable

Prime time television

Prime numbers, as well as being an interesting maths classroom subject, play an important role in encryption and related technologies. As the world hunts for ever larger primes, drobe.co.uk's resident mathematics fan Martin Hansen turns to DrawScript and his ARM-powered RISC OS computer to find and present prime numbers.

Professor Marcus du Sautoy


Let us begin by being brutal: thinking about prime numbers is not what anyone I know, including myself, would typically want to do on Christmas day. It's not that I don't like maths because I do, but even I, a 'mathaholic', know that maths and Christmas day do not mix. Yet it was the mathematics of the prime numbers that I found myself thinking about on December 25 at 7.15pm when I tuned in to the first of the Christmas 2006 Royal Institution lectures, The Num8er My5teries, on UK's Channel 5.

I tuned in initially because, as a teacher of mathematics to teenagers, I was curious to see what Professor Marcus du Sautoy, pictured above, had to say about the primes to his audience, many of whom looked around eleven or twelve years old. I have often thought that children are taught surprisingly little about the prime numbers.

They learn that a prime is a whole number with precisely two factors. These two factors are 1 and the number itself. If anything else divides into the given number then that number is not prime. Pupils learn that the positive integers which are not prime are called composite numbers and that these numbers can be written as a product of primes in, essentially, a unique way. They may be told that this vitally important result has the rather grand title "The fundamental theorem of Arithmetic". The number 1 is considered to be neither prime nor composite.

Prime solver
A method of finding primes, called the sieve of Eratosthenes, will be investigated. Typically a school mini-project will ask a class to use the sieve to find the 25 primes less than 100. Personally, in the days of the BBC Micro, I enjoyed exhibiting to my classes a delightfully short hybrid 6502 machine code/BBC BASIC program that used this sieve to find primes at what was then regarded as high speed.

Some pretty numbersIf I recall correctly, to begin with, writing the information to the screen was the slowest part of that endeavour, although the sieve method finds it increasingly time consuming to make headway as the number to be tested for primeality gets larger. From a modern viewpoint, the sieve becomes unusable relatively quickly and methods based upon probabilities that tend towards certainty (except for known exceptions) take over and are confidently used by many of those who chase ever-bigger primes.

Professor Sautoy covered these basics with some fancy apparatus to make the enterprise more obviously lively and exciting: he had some large rotating blocks showing that 105 can be decomposed into the product of primes 3 x 5 x 7.

He showed how the Eratosthenian sieve works by wheeling on a grid of balloons numbered from 1 to 50. First of all, multiples of 2 but excluding the prime 2 were popped. Then multiples of 3, excluding the prime 3, went bang. In turn the multiples of 5, excluding the prime 5, were detonated and, finally, the multiples of 7, excluding the prime 7. Alas, when the divisible by two balloon numbered 32 popped it also took out the balloon numbered with the prime 31, but it was, none the less, a memorable demonstration of the sieve method. He stopped at 7 because it's the square root of the first square number less than 50, the total number of balloons. Oh, and 1 was also accidentally popped at some point.

In what seemed like a diversion, the professor told the famous story concerning grains of rice on a chess board. The full tale involves an emperor, his daughter and a mathematician who uses his intellect to win the fair maiden's hand. Without the frills, briefly, one grain of rice is placed on the first square of the chess board and each successive square then has double the number of grains of rice of the previous square.

Thus the first square has one grain of rice upon it, the second two, the next four, the next eight, and so on. The numbers get very big, very quickly as can easily be verified with a pocket calculator, which is usually the point of the story.

To my surprise, Marcus slickly then took us from the traditional ending back into the world of prime numbers. The key step is to consider the total number of grains of rice on the chess board. Understandably, with such a young audience, some of the steps were skipped at this point but they are, I think, quite interesting and not too difficult to understand.

A table of numbers
Here is the number pattern that the lecture glossed over. Click here to see the table in text form


There is a lot going on here. Firstly, each of these sums is in Geometric Progression, and applying the well known formula for summing such series tells us that by the Nth square the chess board will have upon it one less than 2 to the power of N-1 grains of rice. Such numbers, as the professor pointed out, are the famous Mersenne numbers.

Scene of the prime
As hinted at by the number pattern above, and easily proved, Mersenne numbers are composite when the sum is taken over a composite number of squares. So, for example, by the sixth square the board has upon it 63 grains of rice, 63 clearly being divisible by 3 and so not prime. Interest thus focuses upon what can happen when we sum over a prime number of squares.

Initially, mathematical folk lore has it, the resulting number was thought to always be prime. In 1536 it was realised that the 11 squares result is not prime as had been anticipated: a potential prime finding formula had just bitten the dust: the useful ones always do it would seem - although it has not been proven that this must be so. To recap and be absolutely clear, in the above pattern observe that 2047, the 11 squares result, is not flagged as being prime. This is because 2047 = 23 x 89.

The Mersenne numbers have properties that make them good integers to work with and manipulate if you are trying to find some seriously big prime numbers, not least because it is suspected, although not proved, that an infinite number of Mersenne primes exist. So it seems likely that there will always be a next biggest Mersenne prime number to find.

They say prime doesn't pay
Marcus du Sautoy himself had left his laptop testing massive numbers for "primeness" while he presented his television lecture. The first person to find a 10 million digit prime number - hugely valuable to defence and commercial security systems - will earn themselves £50,000 from the Electronic Frontier Foundation. The current record, as of September 4, 2006, is 1 less than 2 to the power 32,582,657. This number has 9,808,358 digits; just not quite enough digits to claim the 50 grand.

Now, I have no interest in finding a 10 million digit prime number, but the lecture got me thinking about a project I'd played around with in 2002. This had been to print out some neatly formatted pages of prime numbers.

I wanted these because (as a mathematician) I kept bumping into relatively small numbers of seven or so digits that I wanted to look up the primality of without the hassle of switching on a computer, never mind going onto the internet to a website such as prime-numbers.org with all its tedious pop-ups and other in-your-face advertising. I'd not finished my 2002 project but professor Marcus du Sautoy's lecture inspired me to look at it afresh.


The project's scripts and directory layout. Click for bigger


The project breaks down into two parts. Firstly, generate primes. Secondly, format and present them in a compact but readable fashion.

Prime target
It's quick and easy to grab the first fifteen million primes from the Internet from Chris Caldwell's excellent website. That gets us as far as the nine digit prime 275,604,541. However, I wanted more of a hands on feel for what it was like to generate some of these "at home".

My 600MHz Iyonix is, after all, 300 times faster than that BBC micro I used in 1985. A program that spent a year generating primes in 1985 should take around a day or so to do likewise now.

This situation reminds me of an argument as to why you should always do nothing except wait for tomorrow's technology. The argument begins by remarking that it is pointless to set off today in a spaceship bound for a distant star. The reasoning is that if you set off today, then after a decade of space flight you'd be overtaken by a faster and more modern craft built using technology developed a couple of years after you left Earth. Therefore, you should always wait for tomorrow's technology. QED.

Just in the nick of prime
Putting such paradoxical thoughts aside, I hacked together a very crude BBC BASIC prime finding program and, without even bothering to make it stop at the square root of the first square less than the number to be tested, set it to find the first six hundred thousand primes. I thought I had abundant computing power for this relatively modest task but my breathtakingly inefficient program took 2 days, 7 hours and 25 minutes to find a thirtieth of what I had downloaded from the Internet, using broadband, in around half an hour.

I am told that primes can be generated faster than they can be downloaded, although I'm not sure I believe that. "Was my effort really that feeble?" I asked myself.

My largest prime was a little under 9,000,000. On the positive side, I could use my primes to check the early part of Chris Caldwell's Internet list, and vice versa. It is interesting to note that the Austrian arithmetician JP Kulik (1773-1863) spent 20 years of his life preparing a table to 100 million by hand, but this was never published, and the volume for numbers from 12,642,600 to 22,852,800 has been lost. I'd got enough primes for six hundred A4 pages each of a thousand primes which, as I was pursuing a whim rather than making it my life's work, seemed plenty.


Every second counts, all 200,000 of them when it came to producing these 600,000 prime numbers on an Iyonix. Click for bigger


As an aside, a small part of me remains curious about how fast JP Kulik's primes to 100 million could be found on a modern Iyonix running ARM machine code. I think it should be fairly straightforward to generate all of JP's primes as 100 million is less than the ten digit number 2,147,483,647, this being the BASIC integer limit of the Iyonix, and, incidentally, the Mersenne prime, M31. To get beyond that number would involve a lot more effort: numbers would have to be handled as strings and any arithmetical operations to manipulate these strings also converted into machine code.

The smart way to do this might be to use Nick Craig-Wood's ingenious Big Numbers module which allows infinite precision integer arithmetic to be carried out. Gavin Wraith maintains a 32 bit version of this, ideal for Iyonix users, but I recommend that you find it via Nick's website as there is a lot of mathematical material of interest on Nick Craig-Wood's site. This includes, just in case you do fancy that £50,000, an ARM based Mersenne prime tester for "The Great Internet Mersenne Prime Search", or GIMPS for brevity.

Nick's program is currently usable but in beta form with a long to-do list to bring its performance up to full speed. He'd welcome help if any reader likes the idea of chasing the big primes using RISC OS. There are some big money prizes for primes of even more than 10 million digits: the fifty grand cash award for this next prime milestone seeming likely to be claimed before 2007 is out. I suppose that what I am saying is that someone starting out now to find a money making prime should focus on the targets beyond the 10 million digit prime. In other words, get busy building the faster spaceship.

In order to format the modest list of six hundred thousand "home grown" primes that I now had sitting on my hard drive, I fired up Joe Taylor's truly splendid, outstanding and polished piece of free software DrawScript. Did I mention that I think this is a good program? Well, it is.

DrawScript provides an easy means of writing Draw vector graphics files from a BBC BASIC program. With careful adjustments I found that I could fit a thousand primes on each page such that the draw file could be printed out as it stood without needing to be scaled or otherwise manipulated by any other program.

I have put the resulting zip file of 600 Draw files on my website, but remember you'll need a computer running RISC OS to view the files. As the Draw files are individually tiny, any old machine from an Archimedes (1987) onwards will do, or you can buy RISC OS to run on top of Windows XP from Virtual Acorn. Remember that you can obtain larger lists elsewhere on the web, but my contribution here is to have formatted them beautifully for printing out.


The project's final output in drawfile format. Click for bigger


Having a printed list of primes is a good starting point for "messing around with numbers" but real power comes from having the entire list of data in a computer and investigating it using simple programs. For now, I'm content that I've polished off a project that I left unfinished five years ago but maybe, should the mood take me, or a reader have an interesting mathematical proposition, I'll take it further.

Links

Martin's website with downloadable drawfiles of prime numbers generated on RISC OS

Previous: The best of the Microdigital Mico manual
Next: 32bit Insignia released for free

Discussion

Viewing threaded comments | View comments unthreaded, listed by date | Skip to the end

What a super article, thanks for putting this together. Reminds me of a text file a friend found at VI College - of PI to several thousands of decimal places. He printed it out on fan-fold paper...

It would be nice to have the program that can generate primes on RISC OS on Martin's website - did you try compiling the BASIC program to make it faster?

 is a RISC OS Userharmsy on 6/1/07 7:36PM
[ Reply | Permalink | Report ]

Great article. Well done, BBC! (micro).

 is a RISC OS Userkillermike on 6/1/07 10:35PM
[ Reply | Permalink | Report ]

The picture "Every second counts, all 200,000 of them when it came to producing these 600,000 prime numbers on an Iyonix. Click for bigger" doesn't become bigger when clicked. All other pics "work" fine on my PC using IE6.

 is a RISC OS UserGregor on 7/1/07 1:06AM
[ Reply | Permalink | Report ]

In reply to Gregor: Well, perhaps you should a better and safer browser like Firefox 2 instead of the favoured browser of those creating malicious software. Works fine with Firefox 2.

 is a RISC OS Userhzn on 7/1/07 6:25AM
[ Reply | Permalink | Report ]

And Netsurf

 is a RISC OS UserDaveW on 7/1/07 10:39AM
[ Reply | Permalink | Report ]

Far more important than using Firefox or Netsurf is that web pages are designed consistently and checked before public use. Someone seems to have corrected the problem which I mentioned above. The pic does now work fine.

 is a RISC OS UserGregor on 7/1/07 1:49PM
[ Reply | Permalink | Report ]

Gregor: Indeed, though in this case it seemed a trivial problem, often a web page requires non-standard special 'fixes' to make it work properly in IE6, as well as the other browsers. Naturally you are free to use any browser you like, but it deserves recommendation to use another browser like Firefox or Opera as often as possible, not just for your computer's security but also to enjoy greater web standard compatibility and encourage the use of them. In this context it should be mentioned that the recently released IE7 does make a significant step forwards to W3C compliance, though not nearly as much as Opera or Firefox.

Perhaps hzn's reaction was a bit 'over-enthusiastic', though essentially I do agree with his advice.

 is a RISC OS UserhEgelia on 7/1/07 4:35PM
[ Reply | Permalink | Report ]

I missed the programme on Christmas Day so thanks for this summary and other interesting stuff. Very well written too. Anything that stimulates interest in maths is important when it seems increasingly marginalised.

 is a RISC OS UserTonyStill on 7/1/07 5:15PM
[ Reply | Permalink | Report ]

This year's Christmas Lectures are available on DVD at the cost of the P&P if you order them from the Royal Institution's website, if you missed any of them.

 is a RISC OS Userrjek on 7/1/07 11:56PM
[ Reply | Permalink | Report ]

Just as a matter of interest, the program DrawAid, by Bill Graham, is available from my website at [link]

 is a RISC OS UserEddie on 8/1/07 6:17AM
[ Reply | Permalink | Report ]

I have just recieved the following comments from

Professor Marcus du Sautoy

Dear Martin

Many thanks for putting a very interesting piece on the web.

It was quite a tough lecture to prepare for 11-14 year olds (the age range I was asked to pitch the lectures at). Probably the most theoretical of all five lectures.

I'm glad you picked up the link from the chess board to the Mersenne primes. I've not seen this done before so I was quite pleased with noticing the easy way of seeing the Mersenne primes on the board - historically of course a little tenuous. . I deliberated about going into more details of how to get the formula but with 39.5 minutes for the lecture there was never a lot of time to play with. But I think the maths is easy enough for keystage 3.

The chess board sequence is one kids of that age seemed to respond well too. They like the idea of how big things can get. And then to use it to give a sense of quite how big the largest Mersenne prime is I thought would make a nice climax.

If you want to get hold of a DVD of the lectures, the RI are making them available at the end of March.

There is a form here to order one:

[link]

Best wishes

Marcus.

 is a RISC OS Usermartin on 8/1/07 12:18PM
[ Reply | Permalink | Report ]

In reply to rjek, Martin, Thanks for the tip re DVD copies. For UKP3.50 they're too good to miss.

 is a RISC OS UserTonyStill on 8/1/07 8:44PM
[ Reply | Permalink | Report ]

Ah, I remember working out the brute-force method of finding primes for myself. If I remember correctly, my program to do it used an array to store the primes already found. Then for each odd number (trivial optimisation - add two instead of one), it compared the previously found prime numbers up to the square-root. Probably it did the division and looked to see if the other factor was an integer. I don't remember how far it got, but it was probably in BASIC on an A3000. Happy days.

Hmmm. I remember someone saying that you can get a larger prime by multiplying all the primes as far as you want to go, then adding one: 2*3+1=7 - prime 2*3*5=31 - prime 2*3*5*7=217 - err...prime Logically the resultant number can't have any factors smaller than the biggest prime you used. However, I'm not sure you couldn't have prime factors larger than the largest one you used. For example in the last case 11*13=143, less than the result. So we don't have a guarantee of primality until you've checked all the primes up to the square root anyway. Incidentally, maybe this is why primes are observed to sometimes come in pairs. Hmmm.

A very thought-provoking article. Thank you Martin.

 is a RISC OS UserLoris on 9/1/07 8:13PM
[ Reply | Permalink | Report ]

Oh dear, transcription errors. I must've become too excited. 2*3*5+1=31 2*3*5*7+1=211

 is a RISC OS UserLoris on 9/1/07 8:18PM
[ Reply | Permalink | Report ]

Such a construct is used in a proof that there are infinitly many primes: Assume that there is a finite list of all primes. But, the product of all numbers in this list plus one must also be prime as none of the primes in the initial list divide it. So the list is incomplete. This contradicts the initial assumption, so that assumption must be false, which implies that there are infinitely many primes.

 is a RISC OS Userjamesp on 9/1/07 10:23PM
[ Reply | Permalink | Report ]

Hi Loris. The SHOOT FORWARD idea is great in principal: do something to the early part of the prime number sequence to generate a much bigger term in the sequence. Alas, the proposed SHOOT FORWARD will not bring us financial award. P1 = 2+1 = 3 prime P2 = 2*3+1 = 7 prime P3 = 2*3*5+1 = 31 prime P4 = 2*3*5*7+1 = 211 prime P5 = 2*3*5*7*11+1 = 2311 prime P6 = 2*3*5*7*11*13+1 = 30031 = 59*509 composite As jamesp has pointed out, the value of this construct is that the result must contain a prime that's bigger than any in the list used in its construction but, as we've seen, that bigger prime can be part of a composite. Of course, if you could predict which Ps were going to be prime and which composite we'd be back in business. Alas, which is which seems as mysterious as the primes themselves. P7, P8, P9 and P10 are composite, P11 is prime, and then they are all composite until P75. It's not known if this list contains infinitely many primes.

 is a RISC OS Usermartin on 10/1/07 6:48AM
[ Reply | Permalink | Report ]

Please login before posting a comment. Use the form on the right to do so or create a free account.

Search the archives

Today's featured article

  • Archive magazine reviewed
    A media watch special
     10 comments, latest by diomus on 27/10/07 12:01PM. Published: 23 Oct 2007

  • Random article

  • WrapAIF executable utility updated
    New version 1.06 uses ResFind plus other tweaks
     Discuss this. Published: 24 Feb 2007

  • Useful links

    News and media:
    IconbarMyRISCOSArcSiteRISCOScodeANSC.S.A.AnnounceArchiveQercusRiscWorldDrag'n'DropGAG-News

    Top developers:
    RISCOS LtdRISC OS OpenMW SoftwareR-CompAdvantage SixVirtualAcorn

    Dealers:
    CJE MicrosAPDLCastlea4X-AmpleLiquid SiliconWebmonster

    Usergroups:
    WROCCRONENKACCIRUGSASAUGROUGOLRONWUGMUGWAUGGAGRISCOS.be

    Useful:
    RISCOS.org.ukRISCOS.orgRISCOS.infoFilebaseChris Why's Acorn/RISC OS collectionNetSurf

    Non-RISC OS:
    The RegisterThe InquirerApple InsiderBBC NewsSky NewsGoogle Newsxkcddiodesign


    © 1999-2009 The Drobe Team. Some rights reserved, click here for more information
    Powered by MiniDrobeCMS, based on J4U | Statistics
    "Oh, and making up stories and quoting private emails out of context isn't damaging then?"
    Page generated in 0.1153 seconds.