WORKING DRAFT authorea.com/6270
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • 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.

    This block failed to display. Double-click this text to correct any errors. Your changes are saved.