Prime Generating Algorithm

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.

Another Generation Method

Another method to generate this pattern is to take the process in equation 1 and to generate a criterion for wheter a point in the map is filled or not.

By inspection, the integer \(m\) associated with a grey line starting from pixel \((p_x,1)\) is \((p_x +1)/2\), so the grey line originating from the 3^rd pixel along, that is, \((p_x=3)\), relates to the primality of \(2\) etc.

The yellow lines representing the divisors \(n\) are created using the transformation \((2n-1,1)\), and starts from the \(n^{th}\) pixel along at the top left.

The data map is therefore the sum of the discreet points\[M=\sum_{i=0}^{\infty}\sum_{n=1}^{m/2} ( (2n-1)(i+1), i+1) =1\]

If one were to sum across the diagonals (grey lines), any number that only crosses the start (divisor of 1) line and the finish (divisor of itself) is prime.

Another way of expressing this is that for the data matrix \(M\), \(i \in \mathbb{Z}^0\), and \(n \in \mathbb{Z}^+\) \[if \; ∃ \; i,n : ( \; \alpha = (2n-1)(i+1)\;, \;\; \beta = i+1 \;) \\ M_{\alpha \beta} = 1\] otherwise, \[M_{ \alpha \beta} =0\]

For a given number \(m\), elements required to check its primality are \[m=1; \; M_{1 1} \\ m=2; \; M_{2 2} +M_{1 3} \\ m=3; \; M_{3 3} +M_{2 4} +M_{1 5} \\ m=N; \; M_{N N} +M_{N-1 N+1} +M_{N-2 N+2} + ... + M_{1 2N-1}\]

So we create a measure \(P(N)\) to collect these arguments for any \(N\) \[P(N) = \sum_{i=0}^{N-1} M_{N-i N+i}\]

We then have the knowledge that \[\forall \; N \in \mathbb{P}: P(N)=2, \\ \forall \; N \notin \mathbb{P}: P(N) \ne 2\]

This measure \(P(N)\) is the number of divisors of the number \(N\).