**It’s possible to tell whether or not a number is prime in a number of ways. You can crunch through all possible factors of a number until you have a definitive result (which can take an exceedingly long time for very large numbers), or you can use a formula to return a very high level of probability about whether a number is prime. Recently I’ve been looking into both these methods.**

**In this post:**

*How to create huge arrays of primes quickly using JavaScript**Graphically displaying and animating prime numbers**How to test for the probability of primality (Fermat’s Little Theorem)**Numbers that resist these tests (Pseudo Primes and Carmichael Numbers)**How to overcome this resistance*

## Finding Primes With JavaScript

At its simplest, to find all prime numbers between 1 and n in a language such as JavaScript, you can use code like this:

function getprimes(n) { var p = [] for (var j = 1 ; j < n ; ++j) if (isprime(j)) p.push(j) return p } function isprime(n) { for (var j = 2 ; j <= Math.sqrt(n) ; ++j) if (n % j == 0) return false return true }

The first function builds an array of prime numbers, which it returns in the array p[] by calling the second function to test all values of n for primality, up to the square root of n. The square root of n is chosen because all factors come in pairs and we only need to check the lowest of each pair. So (for example) the number 64 has the pair of primes 8 and 8, so you can clearly see that, therefore, the square root of a number is the largest that the smaller of a pair of primes can be.

It is possible to improve on code such as this because we know that all composite (non-prime) numbers can be created with a pair of prime factors. Therefore the previous code can be updated to only test for prime factors, like this (with the modifications shown in blue):

function getprimes(n) { var p = [] for (var j = 1 ; j < n ; ++j) if (isprime(p, j)) p.push(j) return p } function isprime(p, n) { for (var j = 1 ; p[j] <= Math.sqrt(n) ; ++j) if (n % p[j] == 0) return false return true }

The second function is also given access to the array p[] by adding it as an additional argument, so that it can look up previously determined prime numbers for use in its primality tests.

Now if, for example, the number being tested is 36, instead of checking possible factors 2, 3, 4, 5, and 6 (the square root of 36), only the values, 2,3, and 5 will be tested since they are the only primes numbers equal to or less than 6. This has saved two tests (4 and 6). And the bigger the number, the more tests you save until you can ignore about 5 in every 6 or so.

Indeed, you can also improve the main loop by ignoring all even numbers plus those that are divisible by 5, like this (with updates in blue):

function getprimes(n) { var p = [1, 2] for (var j = 3 ; j < n ; j += 2) if (j == 5 || j % 5 != 0 && isprime(p, j)) p.push(j) return p } function isprime(p, n) { for (var j = 1 ; p[j] <= Math.sqrt(n) ; ++j) if (n % p[j] == 0) return false return true } }

In this version of the function, the p[] array is now pre-populated with the values 1 and 2 since they work slightly differently to the others, so they are hand-inserted. Then the loop starts at the number 3, with the (other unusual) number 5 accepted, but not any other multiples of 5. And now the code is fairly efficient, except that the square root function is not optimized for this particular use, and so a faster version of the inner function would be to remove the expression p[j] <= Math.sqrt(n), replacing it with p[j] * p[j] <= n.

You can now call this function with the following command (for example) to return the prime numbers up to 100, which will then be displayed in the current browser document:

document.write(getprimes(100))

The result of this command will be as follows, and I have tested it on an i7 PC with values of up to 10 million (which are calculated in about a second), and 100 million (which takes around 9 seconds):

## 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,

43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

## The PrimeDancer Web App

My new web app, PrimeDancer.com uses the preceding code to generate the primes it displays and animates. It’s a vastly improved and speeded up version of my earlier prime spiral animator, which now uses simple sliders to adjust the speed, direction, and zoom. It also lets you click in the animation to detect all the numbers in a sequence of a spiral arm, or use the sliders on the left to find them. When running the program looks like this, and I think you’ll find it rather fun to play with:

I find it fascinating (and quite relaxing) to watch all the possible patterns resulting from the distances between potential plot points on the spiral being slightly changed with each frame. What happens is that, for example, all the even numbers often reveal themselves as spiral gaps, but then so do multiples of three, four, five, and all the way up, as and when they are lined up above above each other in each turn of the spiral.

What’s more you can see multiple gaps at a time causing ‘interference’ patterns, and a tremendous amount of complexity reveals itself. One of my first theories was that where a spiral arms was particularly flush with pixels, it might be possible to follow that arm out like a rich vein of coal. Indeed when I did this it was the case, but only for a while. The further out you go the more the ratio of primes to composites returns back to the norm. Still, as you’ll see, there are other ways of finding seams of primes.

So this app is probably now more of a toy than a maths experiment that will yield new information, but I think it’s unique, and primes have never been displayed in quite such an interesting and dynamic manner before.

## Continuing The Search For Prime Numbers

But why all this tinkering in the first place, you might ask? Well, things like Internet security rest on the employment of incredibly large prime numbers, so any new discoveries in this area could lead either to new, more powerful encryption systems, the cracking of current techniques, or even both. So it’s a fun (and potentially profitable) area to study.

The trouble is that (fast as it is), this type of code will never be good enough to identify enormous prime numbers quickly enough for improving (or hindering) ecommerce and private communications (even when written in compiled C or hand-coded assembly language).

## A Better Way to Test For Primality

Thankfully, though, there’s a better way (in fact there are several of them), the first of which was invented (or perhaps discovered) all the way back in the 1600s by the mathematician Fermat (yes, he of the famous Last Theorem). What is less known is that Fermat also came up with what is called his Little Theorem, in which the primality of a number can be predicted with a very high rate of probability by selecting what is termed a *coprime* number, and then raising this coprime to the power of the number to be tested. The coprime number can be any integer less than the one being tested, and need not be prime.

So, for example, to test the number 7, you could choose the coprime base value of 4 and raise it to the power of 7 (which is 4 × 4 × 4 × 4 × 4 × 4 × 4). If you can then subtract the coprime from this result such that the final result is exactly divisible by the number being tested, then the number could well be prime. It looks like this: (4^{7} – 4) / 7. Or like this in JavaScript:

if ((Math.pow(4, 7) - 4) % 7 == 0) document.write('Possibly prime')

In this code, the % instruction divides by 7 and returns only the remainder (modulus) of the operation. So if the result is zero there was no remainder and so the the test is passed. If, however, there *is* a remainder then the number is definitely composite.

## The Problem With Pseudo Primes

Interestingly, when applying Fermat’s little theorem, a few very strange numbers crop up which look very much like prime numbers to it, but they aren’t – and so they are given the title *pseudo primes*.

Some examples of Fermat’s pseudo primes include the numbers 341, 561, 645, 1105, 1387, and 1629. Actually there’s an infinite number of them, but you can see that they are fairly uncommon.

However, by changing the coprime used in the theorem to a different base number, and re-running the test, you can almost always weed out these pseudo primes to narrow down your certainty.

## The Resistant Carmichael Numbers

But you can only narrow down to an extent, because a subset of these pseudo primes (known as the Carmichael numbers after the mathematician who discovered the first one), resist the Fermat Little Theorem test in every base you choose:

*In number theory, a Carmichael number is a composite number
n which satisfies the modular arithmetic congruence relation:
b ^{n} ≡ b (mod n) for all integers 1 < b < n – Wikipedia*

This set of numbers includes 561, 1105, and 1721, and has an even rarer occurrence (only about 1 in 2.5 million). Nevertheless, these numbers are also infinite and are a considerable nuisance to cryptographers, who have now developed some very advanced mathematics to deal with this issue.

Before moving on to looking more deeply at these pseudo primes, though, let’s take a moment to write a program to simply map all prime and composite numbers onto a spiral, in a simpler version of my PrimeDancer App, like this:

<canvas id='canvas' width='630' height='630'></canvas> <script> var E = document.getElementById('canvas'), C = E.getContext('2d'), P = getprimes(1024), j, x, y for (j = 1 ; j < 1024 ; ++j) { x = 315 + Math.sin(j) * j * .3 y = 315 + Math.cos(j) * j * .3 if (isprime(P, j)) C.fillStyle = '#00f' else C.fillStyle = '#faa' C.fillRect(x, y, 2, 2) } </script>

This code uses a 630 × 630 pixel HTML5 canvas, onto which the first 1024 numbers are plotted by simply calculating the sine and cosine of of each number to rotate it a distance according to its size. Each consecutive number is then plotted slightly further out from the center of the canvas in either a salmony color for composites, or in blue for prime numbers.

This code obviously includes some HTML and the getprimes() function from earlier, but these are not shown. The result of running this program, which you can test for yourself here, is shown below:

## The Chinese Hypothesis

Now let’s have some fun and slightly modify this code to enforce a variation of Fermat’s Little Theorem (known as the Chinese Hypotheses) on all these plot points, like this (with the changes highlighted in blue):

x = 315 + Math.sin((Math.pow(2, j) % j) * j * .3 y = 315 + Math.cos((Math.pow(2, j) % j) * j * .3

This time when you run the program the various plot point rotations are first vastly increased in size, and then restrained back again, causing spokes of point clustering around the circle. The result looks like this, which (for want of another word) I’ll call a Chinese Spiral:

Holy cow Batman. See how those primes just lined right up for us? And, interestingly, how many of the composites tried to also get in on the act along a number of other arms too (and many didn’t, which is also interesting). What happened is that the primes got in an orderly line because the expression used returned a modulus of 2 for every one.

Unfortunately, though, the Chinese Hypothesis also suffers from the pseudo prime problem. Let me illustrate this by running all the numbers from 1 to 1024 through the Chinese Hypothesis

for (j = 0 ; j < 1024 ; ++j) if (Math.pow(2, j) % j == 2) if (!isprime(P, j)) document.write(j + ' is pseudo prime<br>')

When you run this code the result is as follows:

## 341 is pseudo prime

561 is pseudo prime

645 is pseudo prime

Aha – we have found Fermat’s first three pseudo primes, and also the first Carmichael number (561). OK, so let’s tighten up the code a little and use the trick Fermat described, of testing using one or more additional bases, like this (with the change highlighted in blue):

```
for (j = 0 ; j < 1024 ; ++j)
if (Math.pow(2, j) % j == 2 && Math.pow(2, j) % j == 2)
if (!isprime(P, j))
document.write(j + ' is pseudo prime<br>')
```

Now when you run this code, no pseudo primes are returned – all prime numbers up to 1024 are successfully recognized, as confirmed by the isprime() test. I’d like to take this example further, but the limit of JavaScript’s Math library is reached at powers of 1024. So that will have to wait until I’ve written (or borrowed) a library for dealing with exceptionally large numbers.

## A Possible New Angle?

But what I find interesting is that I thought the Carmichael numbers were supposed to be resistant to all base coprimes supplied to Fermat’s Little Theorem. But it seems that by using the Chinese Hypothesis variant with a different base, you can weed out (at least some of) the Carmichael numbers. Any mathematicians care to investigate this – it could possibly be significant?

Anyway, that’s enough messing around with primes for the moment – I have to get back to recording the videos for my new CSS book due for publication by McGraw-Hill in January. But I’d welcome distractions in the meantime if you have any ideas or thoughts to share in the comments :)