3  Computerisation.

The above two methods of identification of prime number generating quadratics are computerised as macro drive EXCEL spreadsheets that can be downloaded as a ZIP file here:

Primes2.zip

This file contains two spreadsheets, Prime Number Quadratic Generator.xls, (PrimeGen.xls), and Ulam's Spiral.xls, (Ulam.xls). For better appreciation of the remainder of this paper, these files should be used in conjunction with this Section as required, but this is not essential.

3.1  The Composite Search Method.

The main sheet of PrimeGen.xls is shown in the figure below



Fig. 3.1 - PrimeGen.xls Main Sheet.

The use of this spreadsheet is described as follows. To test quadratics for full primeness, there are two modes.

(i) Search Mode - Depress the "Search Type" button to reveal "Full Prime". Depress the "Full Prime Mode" button to reveal Äuto". Insert the Coefficients of a quadratic into the "Coefficient Input" cells, ensuring that a0 is a prime number and that the sum of the coefficients is also prime. Press the "START" button. The quadratic will then be tested for full primeness and if it passes the process will stop and an appropriate message will be displayed. The prime numbers generated can then be read off under "Numbers Generated". If the quadratic fails, the appropriate coefficients, according to the quadratic Type, will be automatically increased by 2 and the test restarted. This process will be repeated until a Full Prime equation is found or until the ESC key is pressed on the keyboard.

(ii) Single Test Mode - To test an individual quadratic, set "Search Type" to "Full Prime" and "Full Prime Mode" to "Single". Insert the coefficients and press "START". The quadratic will then be tested and will pass or fail with the appropriate message being displayed and the process terminating.

To test quadratics for sub-primeness, there is only one mode as follows.

(i) Sub-Prime Test - Set "Search Type" to "Sub-Prime", the "Full Prime Mode" will automatically be set to "Single". Insert the coefficients and press "START". The quadratic will then be tested. The process will terminate when, within the test range, the lowest composite generated by the quadratic is found. A message will then be displayed showing the number of primes generated lower than the above composite, together with the appropriate values of the independent variable. The former can then be read off under "Numbers Generated". If a composite is not found within the test range, the process will terminate, a message displayed accordingly, and the test can be restarted with a higher test range.

In the above two processes, in some cases, some of the numbers shown under "Numbers Generated" will be too large for the applicable cell width. Pressing the "Adjust Column Width" button will reveal all numbers. Pressing this button again, reverses the change.

There are two further points to note. First, testing quadratics with very large coefficients, especially a2 and a0, will take a considerable amount of time. It may therefore be preferable to simply enter the quadratic coefficients, and check the numbers generated against a table of primes. Such a table can be generated with the Visual Basic program, "Primes.exe", which may be obtained here.

Primes.zip

The feature at the bottom of the sheet, "Equation Reduction Calculator", is mainly for use in conjunction with Ulam.xls and is described in the next Section.

The second sheet of this spreadsheet, presents a summary of all the acceptable quadratics found to date, their primary characteristics, and the prime numbers they generate. This covers all prime numbers between 0 and 1500 plus the 190 others. There are of course many duplications, but those quadratics generating a prime for the first time, are highlighted as Ünique" together with the prime number concerned. This feature has not been optimised so it may be possible to reduce the number of Ünique" quadratics whilst still covering the above range. A filter has also been activated to allow inspection of any particular feature of any equation. The area below the listing is available for input of additional equations.

3.2  The Re-Configurable Ulam Spiral Method.

The main sheet of Ulam.xls is shown below.




Fig. 3.2 - Ulam.xls Main Sheet.

In Fig. 3.2 the highlighted red numbers are primes, the rest composites. Data inputs that affect the spiral directly are, (i) "Base Number Input" which will be mostly integers, both positive and negative, but fractional numbers can also be input. (ii) "Step Size", this must be positive but can also be fractional as well as integer. (iii) "Special Search Numbers", up to four prime numbers can be entered here.

After changing any of the above three inputs, the "Re-Configure Primes" button should be pressed. This will completely reconfigure the entire spiral to the parameter inputs. All prime numbers will be highlighted as in Fig. 3.2 above, in their new positions. Those primes searched for in (iii) will be differently highlighted to enable easy location. When four or more primes line up in any of the eight major directions, or as in any of the paths shown in Fig. 2.2, anywhere on the spiral, the first four, or five terms of the sequence can be inserted into the "Term Number Input from Spiral" cells, and if they possess acceptable quadratic form, the coefficients of the applicable equation will be displayed in the "Equation Coefficients" cells. Otherwise an error message will be displayed. The quadratic can then be maximised for the number of primes generated, as described below.

3.2.1  Maximisation of the Sequence.

Once an acceptable quadratic has been found in the spiral, its coefficients should be entered into the "Equation to be Reduced" cells on PrimeGen.xls. In the cell marked "P", prime numbers lower than a0 should be tried until the smallest one is found that produces integer values in the N+ and N- cells. These are the coefficients of the reduced equation(s). Their sum must be a prime number. If so, they should then be entered into the "Coefficient Input" cells at the top of the sheet and the numbers generated checked for three features.

(i) The reduced equation generates the original four primes.

(ii) No composites appear in the sequence lower than these original four primes.

(iii) At least a sequence of five primes are generated.

If these conditions are satisfied, the quadratic sequence has been maximised. If they are not satisfied, further values of "P" should be tried until they are, or the original quadratic is seen to be already maximised.

3.2.2  Lining Up Terms in the Spiral.

Once the above process has been completed, it may be desired to display all the generated primes in line on the spiral. To do this, proceed as follows.

Take the first four primes as generated from "Numbers Generated" on PrimeGen.xls, and enter them into the "Special Search Numbers" on Ulam.xls and "Re-Configure Primes". There are two possible outcomes.


(i) The four primes in question will curl to the right in the spiral. In most cases lining up the complete sequence is merely a matter of inserting the smallest of the four primes in the "Base Number Input" cell and reconfiguring primes. However, where this still results in a curl to the right, it is necessary to count the smallest numbers of cells to individually move each prime number to a cell adjacent to the next largest. Cells must be counted clockwise and from a large number to a smaller. Add these counts, multiply by the "Step Size" and add the result to the existing "Base Number" to produce a new Base Number. Insert this into "Base Number Input" and reconfigure primes. The sequence should then line up somewhere in the spiral. In some cases it may be necessary to repeat this process a number of times.

(ii) The four numbers in question will curl to the left. In this case the same process as in (i) should be followed but counting anti-clockwise from smaller numbers to larger.

To illustrate this process clearly, two examples are provided in Appendix B.

3.3  Finding Equations for Difficult Numbers.

When the above two processes fail to find quadratics that generate particular prime numbers, the following manual approach can be adopted.

In Ulam.xls insert the problem number, P3, into the third cell from the left in the cells labelled "Term Number Input from Spiral". Now in the first and second cells, insert two primes, P1 and P2, ( P1 < P2 ), such that the numbers that appear in the immediate cells below, (a and b), are positive, thus

Term Number Input from Spiral
P1P2P3   
ab-P30
c-dP3
ef
-g

Fig 3.3 - Finding Equations for Difficult Numbers, (i).


If the number ë" is prime, insert it as P4 into the cell to the right of P3 to give the configuration in Fig. 3.4 below. If ë" is not prime, vary P2 up or down to the next prime until ë" does become prime.

Term Number Input from Spiral
P1P2P3P4  
abh -P4
cc-i
0-g
g

Fig. 3.4 - Finding Equations for Difficult Numbers, (ii).


At this point an equation will appear in the "Equation Coefficients" cells. This is the quadratic of the sequence, and if "g" is prime, the quadratic generates at least five primes including the difficult number P3. The quadratic can now be maximised as in the process above. If "g" is not prime, repeat the above procedure, varying P2 until both ë" and "g" become prime.

An example of a difficult number is 467. Using the above procedure, with P1 = 1, P2 = 223, and P3 = 467, P4 becomes 733 and "g" 1021. The quadratic is


N = 11x2 + 211x + 1
(3.1)

The second sheet in Ulam.xls, is a simple macro driven feature to check large integers for factors.



M6 Version 1.0.0
Ó P.G.Bass, December 2001

On to the Next Section:- Conclusions and Appendix A

Back to the Introduction to this Paper:- Prime Number Quadratic Generation

Back to the Home Page for this Site:- Home