15.7 Prime Number Patterns

---

 

	Java Number Cruncher: The Java Programmer's Guide to Numerical Computing By Ronald  Mak
	Table of Contents
	Chapter  15.   Prime Numbers

---

15.7 Prime Number Patterns

If there are quadratic polynomials that generate a high percentage of prime numbers, then there is a pattern to the distribution of these generated primes. Can we make this pattern visible?

If we arrange the numbers in a spiral, then the formulas that generate numbers that lie diagonally are quadratic polynomials. In the following example, the numbers 1, 3, 7, 13, 21, and so on are generated by the formula n ² + n + 1 for integer values of n 0.

100	99	98	97	96	95	94	93	92	91
65	64	63	62	61	60	59	58	57	90
66	37	36	35	34	33	32	31	56	89
67	38	17	16	15	14	13	30	55	88
68	39	18	5	4	3	12	29	54	87
69	40	19	6	1	2	11	28	53	86
70	41	20	7	8	9	10	27	52	85
71	42	21	22	23	24	25	26	51	84
72	43	44	45	46	47	48	49	50	83
73	74	75	76	77	78	79	80	81	82

Because so many primes are generated by quadratic polynomials, we can see these primes as diagonal "streaks." These streaks are visible even with only 100 numbers. For example, the primes 5, 19, 41, and 71 are generated by the polynomial 4 n ² + 10 n + 5 for n = 0, 1, 2, and 3.

Another way to see these streaks is to arrange the numbers diagonally at right angles to the main diagonal from the upper left to the lower right. However, with 100 numbers, they are less visible than with the spiral arrangement.

1	3	6	10	15	21	28	36	45	55
2	5	9	14	20	27	35	44	54	64
4	8	13	19	26	34	43	53	63	72
7	12	18	25	33	42	52	62	71	79
11	17	24	32	41	51	61	70	78	85
16	23	31	40	50	60	69	77	84	90
22	30	39	49	59	68	76	83	89	94
29	38	48	58	67	75	82	88	93	97
37	47	57	66	74	81	87	92	96	99
46	56	65	73	80	86	91	95	98	100

Screen 15-5a is a screen shot of Program 15 C5 displaying a 500 x 500 spiral arrangement. ^[9] When we start with 41 instead of 1, the prime numbers generated by Euler's original polynomial n ² + n + 41 appear dramatically as the long diagonal from the lower left corner to the upper right corner. Other diagonal streaks are visible.

^[9] You can download the Java source code for this program. See the downloading instructions in the preface of this book.

Screen 15-5a. Prime streaks with the numbers arranged in a spiral. The long diagonal streak from the lower left corner to the upper right corner consists of the primes generated by Euler's quadratic polynomial.

Screen 15-5b is a screen shot of Program 15 C5 displaying a 500 x 500 diagonal arrangement. With more numbers, the prime streaks are more visible. Unlike the spiral arrangement, the streaks here are all parallel to the main diagonal.

Screen 15-5b. Prime streaks with the numbers arranged diagonally across the main diagonal.

---

Top