Abstract

# Abstract

13/04/2014

I present a very simple algorithm (visual sieve) for testing if a number is prime. The algorithm was first developed visually in a cellular automation manner. A data map is created from a simple recursive function or an equivalent criterion, from this map it is easy to find if a number is prime from the structure of it’s divisors. By checking from the dense end of the factor list the runtime is minimised. All primes up to $$14983$$ were generated in a few seconds on a laptop.

# Introduction

The cellular automation like data map was first discovered when analysing a program investigating bound states in a rectangular 2D box. States for a box of dimension $$(x,y)$$ which were not bound were highlighted on an $$(x,y)$$ pixel map and a rich structure akin to a diffraction pattern is witnessed. Visual analysis found a subpattern which gave information about the primes when interpreted in the correct method.

The generator for the prime data map is a simple function. For some $$n,m \in \mathbb{Z}$$, let $x_0 = (2n-1) \\ y_0 = 1 \\ dx = (2n-1) \\ dy = 1 \\ x_m \to x_{m-1} +dx \\ y_m \to y_{m-1} +dy.$ If this is made for all $$n$$ (limited by the maximum number you wish to check) and the $$(x_m,y_m)$$ are plotted as a filled pixel (value of 1) the map is created as seen in Figure 1.

This pattern has an interesting interpretation:

- The strong line at the bottom represents all positive integers $$m$$ sitting in the coordinates $$(m,m)$$. - The next line up represents numbers that are divisible by $$2$$.
- The next line those divisible by $$3$$, and so on...
- The divisors of the integer $$m$$ are given by travelling diagonally upwards (North East), if a pixel from one of the upper lines is met, then $$m$$ is divisible by that lines number.
- Hence, if there is no filled position between the coordinate $$(m,m)$$ and $$(2m-1,1)$$ then that number $$m$$ is prime!
Below, primes are pixels in red on the bottom line, the grey lines are paths meeting no divisors above that number.