# Prime spiral (Ulam spiral)

### From Math Images

Line 3: | Line 3: | ||

|Image=Ulam_spiral.png | |Image=Ulam_spiral.png | ||

|ImageIntro=The Ulam spiral, or prime spiral, is a plot in which <balloon title="load:defprime">prime numbers</balloon><span id="defprime" style="display:none">A prime number is a natural number greater that is divisible only by 1 and itself. The first few prime numbers are :<math>2, 3, 5, 7, 11, 13,17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, \dots</math></span> are marked among positive integers that are arranged in a counterclockwise spiral. The prime numbers show a pattern of diagonal lines. | |ImageIntro=The Ulam spiral, or prime spiral, is a plot in which <balloon title="load:defprime">prime numbers</balloon><span id="defprime" style="display:none">A prime number is a natural number greater that is divisible only by 1 and itself. The first few prime numbers are :<math>2, 3, 5, 7, 11, 13,17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, \dots</math></span> are marked among positive integers that are arranged in a counterclockwise spiral. The prime numbers show a pattern of diagonal lines. | ||

- | |ImageDescElem=The prime spiral was discovered by Stanislaw Ulam (1909-1984) in 1963 while he was doodling on a piece of paper during a science meeting. Starting with 1 in the middle, he wrote positive numbers in a grid as he spiraled out from the center, as shown in | + | |ImageDescElem=The prime spiral was discovered by Stanislaw Ulam (1909-1984) in 1963 while he was doodling on a piece of paper during a science meeting. Starting with 1 in the middle, he wrote positive numbers in a grid as he spiraled out from the center, as shown in [[#1|Image 1]]. He then circled the prime numbers, and the prime numbers showed patterns of diagonal lines as shown by the grid in [[#2|Image 2]]. The grid in [[#2|Image 2]] is a close-up view of the center of the main image such that the green line segments and red boxes in the center of the main image line up with those in [[#2|Image 2]]. |

- | [[ | + | {{Anchor|Reference=1|Link=[[Image:primegrid2.jpg|Image 1|thumb|200px|left]]}} |

- | [[ | + | {{Anchor|Reference=2|Link=[[Image:ulamgrid.jpg|Image 2|thumb|400px]]}} |

- | + | ||

A larger Ulam spiral with 160,000 integers and 14,683 primes is shown in the main image. Black dots indicate prime numbers. In addition to diagonal line segments formed by the black dots, we can see white vertical and horizontal line segments that cross the center of the spiral and do not contain any black dots, or prime numbers. There are also white diagonal line segments that do not contain any prime numbers. Ulam spiral implies that there is some order in the distribution of prime numbers. | A larger Ulam spiral with 160,000 integers and 14,683 primes is shown in the main image. Black dots indicate prime numbers. In addition to diagonal line segments formed by the black dots, we can see white vertical and horizontal line segments that cross the center of the spiral and do not contain any black dots, or prime numbers. There are also white diagonal line segments that do not contain any prime numbers. Ulam spiral implies that there is some order in the distribution of prime numbers. | ||

Line 17: | Line 16: | ||

Many half-lines in the Ulam spiral can be described using <balloon title="load:quadratic"> quadratic polynomials</balloon><span id="quadratic" style="display:none"> A quadratic polynomial is a polynomial in which the exponent of the variables do not exceed 2. A quadratic polynomial typically has the form <math>ax^2+bx+c</math> where <math>x</math> is a variable and <math>a, b, c</math> are coefficients.</span>. A ''half-line'' is a line which starts at a point and continues infinitely in one direction. In this page, we only consider half-lines that are horizontal or vertical, or have a slope of -1 or +1. The half-lines that can be described using quadratic polynomials are the ones in which each entry of the diagonal is positioned on a different ''ring'' of the spiral. | Many half-lines in the Ulam spiral can be described using <balloon title="load:quadratic"> quadratic polynomials</balloon><span id="quadratic" style="display:none"> A quadratic polynomial is a polynomial in which the exponent of the variables do not exceed 2. A quadratic polynomial typically has the form <math>ax^2+bx+c</math> where <math>x</math> is a variable and <math>a, b, c</math> are coefficients.</span>. A ''half-line'' is a line which starts at a point and continues infinitely in one direction. In this page, we only consider half-lines that are horizontal or vertical, or have a slope of -1 or +1. The half-lines that can be described using quadratic polynomials are the ones in which each entry of the diagonal is positioned on a different ''ring'' of the spiral. | ||

- | The ''ring'' of a spiral can be considered as the outermost layer of a concentric square or a rectangle centered around the center of the spiral, 1, as defined by the blue line in the grid. Although there is no exact place where we can determine the beginning and end of a ring, we will assume that entries that are positioned on squares or rectangles of the same sizes to be on the same ring. For instance, 24, 25, 26, 27, 28, which are shown in red boxes in | + | The ''ring'' of a spiral can be considered as the outermost layer of a concentric square or a rectangle centered around the center of the spiral, 1, as defined by the blue line in the grid. Although there is no exact place where we can determine the beginning and end of a ring, we will assume that entries that are positioned on squares or rectangles of the same sizes to be on the same ring. For instance, 24, 25, 26, 27, 28, which are shown in red boxes in [[#3|Image 3]], are on the same ring, whereas 48, 49, 50, 51, 52, as shown in blue boxes, are on a different ring because they are positioned on a bigger square. |

- | + | {{Anchor|Reference=3|Link=[[Image:Halfline10.jpg|Image 3:Diagonal half-lines|thumb|250px]]}} | |

- | [[ | + | |

- | The green lines in the | + | The green lines in the [[#3|Image 3]] qualify as diagonal half-lines whereas the red lines do not because the red lines cross the corner of the grid in a way that two entries of the red diagonal line are positioned on the same ring. |

Thus, diagonal line segments that are composed of prime numbers can also be expressed as outputs of quadratic polynomials. To learn more about the relation between the diagonal lines and quadratic polynomials, click below. | Thus, diagonal line segments that are composed of prime numbers can also be expressed as outputs of quadratic polynomials. To learn more about the relation between the diagonal lines and quadratic polynomials, click below. | ||

Line 29: | Line 27: | ||

'''Half-lines and quadratic polynomias''' | '''Half-lines and quadratic polynomias''' | ||

- | First, we need to know the relation between quadratic polynomials and the {{EasyBalloon|Link=difference table|Balloon=The difference table lists the terms of a sequence and its differences. It can include other higher order differences such as the second-differences and the third-differences.}} of sequences. Let's choose the diagonal <math> 5, 19, 41, 71, 109, 155</math>, the diagonal indicated with green dotted line in | + | First, we need to know the relation between quadratic polynomials and the {{EasyBalloon|Link=difference table|Balloon=The difference table lists the terms of a sequence and its differences. It can include other higher order differences such as the second-differences and the third-differences.}} of sequences. Let's choose the diagonal <math> 5, 19, 41, 71, 109, 155</math>, the diagonal indicated with green dotted line in [[#3|Image 3]], as our original sequence and create a difference table. |

[[image:diff.jpg]] | [[image:diff.jpg]] | ||

Line 35: | Line 33: | ||

As we can see from the table, the 2nd differences are constant, and this implies that the original sequence can be described by a second degree polynomial. For more information about difference tables and about finding specific polynomials for sequences, go to [[Difference_Tables|difference tables]]. | As we can see from the table, the 2nd differences are constant, and this implies that the original sequence can be described by a second degree polynomial. For more information about difference tables and about finding specific polynomials for sequences, go to [[Difference_Tables|difference tables]]. | ||

- | [[ | + | {{Anchor|Reference=4|Link=[[Image:primeani.gif|Image 4:Constant 2nd differences|thumb|250px|left]]}} |

Now, we will see that the second differences are always constant for any segment of a diagonal half-line. Let's choose the same diagonal with entries <math>5, 19, 41, 71, 109, 155</math>. (For a better understanding of the following paragraphs, the reader should wait until the animation shows three different blue rings and then watch the rest of the animation.) | Now, we will see that the second differences are always constant for any segment of a diagonal half-line. Let's choose the same diagonal with entries <math>5, 19, 41, 71, 109, 155</math>. (For a better understanding of the following paragraphs, the reader should wait until the animation shows three different blue rings and then watch the rest of the animation.) | ||

- | In | + | In [[#4|Image 4]], the number of the innermost light blue boxes, which is 14, indicate the distance from <math>5</math> to <math>19 </math>, or the difference between these two numbers. The number of darker blue boxes in the middle indicate the difference between the numbers <math> 19</math> and <math>41</math>. The darkest blue boxes on the outside indicate the difference between the entries <math> 41</math> and <math>71</math>. The number of all these blue boxes correspond to the first differences in the difference table. |

- | In | + | In [[#4|Image 4]], the light blue boxes are divided into pieces, and each piece is moved to on top of the darker blue boxes. We can see that there are <math>8</math> more darker blue boxes than the innermost light blue boxes. Similarly, the blue boxes in the middle are divided into pieces and are moved to on top of the darkest blue boxes. |

- | Indeed, as | + | Indeed, as [[#4|Image 4]] illustrates, regardless of the exact number of the blue boxes, there are <math>8</math> more boxes in any given ring than there are in the ring that is one layer inwards from it. This means that the the second differences, or the differences between the first differences is always going to be constant at <math>8</math>. Thus, the sequence for any diagonal half-line can be described using a quadratic polynomial. |

}} | }} | ||

Line 49: | Line 47: | ||

'''Examples of quadratic polynomials for half-lines''' | '''Examples of quadratic polynomials for half-lines''' | ||

- | For instance, prime numbers <math> 5, 19, 41, 71, 109</math>, which are aligned in the same diagonal, can be described through the output of the polynomial <math>4x^2+10x+5</math> for <math>x=0, 1, 2, 3, 4</math>. Similarly, numbers <math> 1, 3, 14, 31, 57, 91 \dots </math>, which are also aligned in a green diagonal in | + | For instance, prime numbers <math> 5, 19, 41, 71, 109</math>, which are aligned in the same diagonal, can be described through the output of the polynomial <math>4x^2+10x+5</math> for <math>x=0, 1, 2, 3, 4</math>. Similarly, numbers <math> 1, 3, 14, 31, 57, 91 \dots </math>, which are also aligned in a green diagonal in [[#5|Image 5]] starting from the center and continuing to the upper right corner, can be expressed by: |

{{EquationRef2|Eq. (1)}}<math>4x^2-2x+1</math> | {{EquationRef2|Eq. (1)}}<math>4x^2-2x+1</math> | ||

Line 55: | Line 53: | ||

for <math>x=0, 1, 2, 3, \dots</math>. (We will refer back to this polynomial in a later section) In fact, the part of the green diagonal that starts from the center and continues to the bottom left corner can also be described through {{EquationNote|Eq. (1)}} for <math>x=0, -1, -2, -3, \dots</math>. | for <math>x=0, 1, 2, 3, \dots</math>. (We will refer back to this polynomial in a later section) In fact, the part of the green diagonal that starts from the center and continues to the bottom left corner can also be described through {{EquationNote|Eq. (1)}} for <math>x=0, -1, -2, -3, \dots</math>. | ||

- | [[ | + | {{Anchor|Reference=5|Link=[[Image:hvdline.jpg|Image 5|thumb|250px]]}} |

- | In fact, even horizontal and vertical line segment in the grid can be described by quadratic polynomials, as long as the lines satisfy the condition that no two entries are positioned on the same ring. For instance, the blue horizontal line segment in | + | In fact, even horizontal and vertical line segment in the grid can be described by quadratic polynomials, as long as the lines satisfy the condition that no two entries are positioned on the same ring. For instance, the blue horizontal line segment in [[#5|Image 5]], <math> 10, 27, 52, 85</math> can be described by a quadratic polynomial. However, the sequence <math> 9, 10, 27, 85</math> on the same horizontal line cannot be described by a polynomial because the entries 9 and 10 are on the same ring. |

- | Moreover, it is not hard to show that the green diagonal line from | + | Moreover, it is not hard to show that the green diagonal line from [[#5|Image 5]] that goes through the center and has a slope of +1 is the only line on which the Ulam numbers in both directions can be described by the same polynomial. Even the red diagonal line that goes through the center and has a slope of -1 cannot be described by one polynomial. |

Half of the red diagonal, the segment going up from the center, <math> 5, 17, 37, 67, \dots</math> can be described by <math>x^2+1</math> for inputs that are even numbers, while the diagonal going down from the center, <math>1, 9, 25, 49, \dots </math> is a sequence of perfect squares of odd numbers. Thus we cannot find one polynomial that generates both all entries of the red diagonal. | Half of the red diagonal, the segment going up from the center, <math> 5, 17, 37, 67, \dots</math> can be described by <math>x^2+1</math> for inputs that are even numbers, while the diagonal going down from the center, <math>1, 9, 25, 49, \dots </math> is a sequence of perfect squares of odd numbers. Thus we cannot find one polynomial that generates both all entries of the red diagonal. | ||

Line 73: | Line 71: | ||

Euler's polynomial generates distinct prime numbers for each integer <math>x</math> from <math>x=1</math> to <math> x=40</math>. | Euler's polynomial generates distinct prime numbers for each integer <math>x</math> from <math>x=1</math> to <math> x=40</math>. | ||

- | [[ | + | {{Anchor|Reference=6|Link=[[Image:Eulerpgrid1.jpg|Image 6|thumb|400px|left]]}} |

- | As we can see in | + | As we can see in [[#6|Image 6]], we can start an Ulam's spiral with 41 at the center of the grid and get a long, continuous diagonal with 40 prime numbers. One interesting fact is that the 40 numbers in the diagonal line segment are the first 40 prime numbers that are generated through Euler's polynomial. Moreover, the prime numbers are not aligned in order of increasing values. In fact, with 41 in the center, other prime numbers alternate in position between the upper right and lower left part of the diagonal. |

We will show why an Ulam's spiral that starts with 41 generates entries aligned in a diagonal that can also be descried as outputs of Euler's polynomial. {{HideShowThis|ShowMessage=Click here to show more|HideMessage=Click here to hide|HiddenText= | We will show why an Ulam's spiral that starts with 41 generates entries aligned in a diagonal that can also be descried as outputs of Euler's polynomial. {{HideShowThis|ShowMessage=Click here to show more|HideMessage=Click here to hide|HiddenText= | ||

Line 83: | Line 81: | ||

:<math> 4x^2-2x+1</math> | :<math> 4x^2-2x+1</math> | ||

- | describes the upper half of the diagonal as we plug in <math>x=0, 1, 2, 3, \dots</math> and the lower half of the diagonal as we plug in <math>x=0, -1, -2, -3, \dots</math>. Thus, <math>x</math>'s are positioned in the diagonal as if the diagonal was a number line that starts with 0 at the center, with positive integers on the upper right and negative integers on the lower left direction, as shown in | + | describes the upper half of the diagonal as we plug in <math>x=0, 1, 2, 3, \dots</math> and the lower half of the diagonal as we plug in <math>x=0, -1, -2, -3, \dots</math>. Thus, <math>x</math>'s are positioned in the diagonal as if the diagonal was a number line that starts with 0 at the center, with positive integers on the upper right and negative integers on the lower left direction, as shown in [[#7|Image 7]]. |

- | [[ | + | {{Anchor|Reference=7|Link=[[Image:picposition.jpg|Image 8|thumb|250px|none]]}} |

Then, if we start the Ulam's spiral at 41 and thus make 41 the center, each entry on the grid, including the entries on the diagonal segment, will increase by 40. Then, the diagonal can be described by the polynomial : | Then, if we start the Ulam's spiral at 41 and thus make 41 the center, each entry on the grid, including the entries on the diagonal segment, will increase by 40. Then, the diagonal can be described by the polynomial : | ||

Line 91: | Line 89: | ||

In fact, we will see that this polynomial and Euler's polynomial are describing the same entries along the diagonal once we make some changes in numbering the position of <math>x</math>'s. Euler's polynomial can be found by reassigning the position of the entries of the diagonals so that <math>x'=1</math> is at the center, <math>x'=2, 4, 6, 8, \dots </math> are the positions up the diagonal line, <math>x'=1, 3, 5, 7, 9, \dots</math> are positions of entries down the diagonal line from the center, as shown in <i>Image 9</i>. Thus, starting with <math>x'=1</math> at the center, we alternate between the right and left of the center as we number the positions <math>x'=1, 2, 3, 4, 5, \dots</math>. | In fact, we will see that this polynomial and Euler's polynomial are describing the same entries along the diagonal once we make some changes in numbering the position of <math>x</math>'s. Euler's polynomial can be found by reassigning the position of the entries of the diagonals so that <math>x'=1</math> is at the center, <math>x'=2, 4, 6, 8, \dots </math> are the positions up the diagonal line, <math>x'=1, 3, 5, 7, 9, \dots</math> are positions of entries down the diagonal line from the center, as shown in <i>Image 9</i>. Thus, starting with <math>x'=1</math> at the center, we alternate between the right and left of the center as we number the positions <math>x'=1, 2, 3, 4, 5, \dots</math>. | ||

- | [[ | + | {{Anchor|Reference=8|Link=[[Image:eulerposition1.jpg|Image 8|thumb|250px|none]]}} |

- | Then, for the upper half of the diagonal in | + | Then, for the upper half of the diagonal in [[#8|Image 8]], we can use <math>x'=2, 4, 6, 8, \dots</math> instead of <math>x=1, 2, 3, 4, \dots</math> from [[#7|Image 7]]. Then, |

:<math>x=\frac{1}{2} x'</math> | :<math>x=\frac{1}{2} x'</math> | ||

Line 103: | Line 101: | ||

which has the same form as Euler's polynomial. | which has the same form as Euler's polynomial. | ||

- | The same method works for the bottom half as well. We use <math>x'=1, 3, 5, 7, \dots</math> in | + | The same method works for the bottom half as well. We use <math>x'=1, 3, 5, 7, \dots</math> in [[#8|Image 8]] while we used <math>x=0, -1, -2, -3, \dots</math> in [[#7|Image 7]]. Then, |

:<math>x=\frac{-x'+1}{2}</math>. | :<math>x=\frac{-x'+1}{2}</math>. | ||

Line 118: | Line 116: | ||

==Sacks Spiral== | ==Sacks Spiral== | ||

{{SwitchPreview|ShowMessage=Click here to show more.|HideMessage=Click here to hide|PreviewText=[[image:sackspiral.jpg|300px|left]]Sacks spiral is a variation of the Ulam spiral that was devised by Robert Sacks in 1994. Sacks spiral places 0 in the center and|FullText= | {{SwitchPreview|ShowMessage=Click here to show more.|HideMessage=Click here to hide|PreviewText=[[image:sackspiral.jpg|300px|left]]Sacks spiral is a variation of the Ulam spiral that was devised by Robert Sacks in 1994. Sacks spiral places 0 in the center and|FullText= | ||

- | [[ | + | {{Anchor|Reference=9|Link=[[Image:sackspiral.jpg|Image 9|thumb|right]]}} |

Sacks spiral is a variation of the Ulam spiral that was devised by Robert Sacks in 1994. Sacks spiral places <math>0</math> in the center and places nonnegative numbers on an {{EasyBalloon|Link=Archimedean spiral|Balloon= An Archimedean spiral is a spiral traced by a point that is moving away from the center of the spiral with a constant speed along a line which is rotating with constant speed, or angular velocity. An Archimedean spiral typically has the form <math> r= a+b\theta</math>, where <math> a, b</math> are real numbers. The image below is an example of an Archimedean spiral. [[image:Archimedean.png]]}}, whereas the Ulam spiral places <math>1</math> in the center and places other numbers on a square grid. Moreover, Sacks spiral makes one full counterclockwise rotation for each square number <math> 4, 9, 16, 25, 36, 46, \dots </math>, as shown in the image below. The darker dots indicate the prime numbers. | Sacks spiral is a variation of the Ulam spiral that was devised by Robert Sacks in 1994. Sacks spiral places <math>0</math> in the center and places nonnegative numbers on an {{EasyBalloon|Link=Archimedean spiral|Balloon= An Archimedean spiral is a spiral traced by a point that is moving away from the center of the spiral with a constant speed along a line which is rotating with constant speed, or angular velocity. An Archimedean spiral typically has the form <math> r= a+b\theta</math>, where <math> a, b</math> are real numbers. The image below is an example of an Archimedean spiral. [[image:Archimedean.png]]}}, whereas the Ulam spiral places <math>1</math> in the center and places other numbers on a square grid. Moreover, Sacks spiral makes one full counterclockwise rotation for each square number <math> 4, 9, 16, 25, 36, 46, \dots </math>, as shown in the image below. The darker dots indicate the prime numbers. | ||

- | [[ | + | {{Anchor|Reference=10|Link=[[Image:sack.gif|Image 10|thumb|250px|left]]}} |

We can also see that numbers that have blue check marks and are aligned in the left side of the spiral are <balloon title="load:pronicnum"> pronic numbers</balloon><span id="pronicnum" style="display:none">A pronic number is the product of two consecutive integers. Pronic numbers have the form <math>x(x+1)</math></span>. For example, <math> 2=1(1+1), 6=2(2+1), 12=3(3+1),\dots</math>. | We can also see that numbers that have blue check marks and are aligned in the left side of the spiral are <balloon title="load:pronicnum"> pronic numbers</balloon><span id="pronicnum" style="display:none">A pronic number is the product of two consecutive integers. Pronic numbers have the form <math>x(x+1)</math></span>. For example, <math> 2=1(1+1), 6=2(2+1), 12=3(3+1),\dots</math>. | ||

Line 133: | Line 131: | ||

An interesting pattern can be discovered when we start the spiral at 41. As the image below shows, the red dots are the first 40 prime numbers generated by Euler's polynomial, and they are aligned in the center and positions where pronic numbers used to be in the original Sacks spiral. | An interesting pattern can be discovered when we start the spiral at 41. As the image below shows, the red dots are the first 40 prime numbers generated by Euler's polynomial, and they are aligned in the center and positions where pronic numbers used to be in the original Sacks spiral. | ||

- | [[ | + | |

+ | {{Anchor|Reference=11|Link=[[Image:41prime.jpg|Image 11|thumb|250px|left]]}} | ||

==Other Numbers and Patterns== | ==Other Numbers and Patterns== | ||

Line 141: | Line 140: | ||

A number <math>n</math> is a triangular number if <math>n</math> number of dots can be arranged into an equilateral triangle evenly filled with the dots. As shown in theimage below, the sequence of triangular numbers continue as <math>1, 3, 6, 10, 15, 21, \dots</math>. | A number <math>n</math> is a triangular number if <math>n</math> number of dots can be arranged into an equilateral triangle evenly filled with the dots. As shown in theimage below, the sequence of triangular numbers continue as <math>1, 3, 6, 10, 15, 21, \dots</math>. | ||

- | [[ | + | {{Anchor|Reference=12|Link=[[Image:triangular.jpg|Image 12|thumb|none]]}} |

The <math>n^{\rm th}</math> triangular number, <math>T_n</math>, is given by the formula : | The <math>n^{\rm th}</math> triangular number, <math>T_n</math>, is given by the formula : | ||

Line 147: | Line 146: | ||

When we mark the triangular numbers in a Ulam spiral, a set of spirals are formed as shown in the image below. | When we mark the triangular numbers in a Ulam spiral, a set of spirals are formed as shown in the image below. | ||

- | [[ | + | {{Anchor|Reference=13|Link=[[Image:triangularnumbers.gif|Image 13|thumb|300px|none]]}} |

+ | }} | ||

===Prime numbers in lines=== | ===Prime numbers in lines=== | ||

{{SwitchPreview|ShowMessage=Click here to show more.|HideMessage=Click here to hide|PreviewText=[[image:Irisprime.jpg|600px|left]]The Ulam spiral inspired the author of this page to create another table and find a pattern among prime numbers. First, we create a table|FullText= | {{SwitchPreview|ShowMessage=Click here to show more.|HideMessage=Click here to hide|PreviewText=[[image:Irisprime.jpg|600px|left]]The Ulam spiral inspired the author of this page to create another table and find a pattern among prime numbers. First, we create a table|FullText= | ||

- | [[ | + | {{Anchor|Reference=14|Link=[[Image:Irisprime.jpg|Image 14|thumb|700px|none]]}} |

+ | |||

The Ulam spiral inspired the author of this page to create another table and find a pattern among prime numbers. First, we create a table that has 30 columns and write all the natural numbers starting from 1 as we go from left to right. Thus, each row will start with a multiple of 30 added by 1, such as 1, 31, 61, 91, 121, ... . When we mark the prime numbers in this table, we get <i>Image 10</i>. | The Ulam spiral inspired the author of this page to create another table and find a pattern among prime numbers. First, we create a table that has 30 columns and write all the natural numbers starting from 1 as we go from left to right. Thus, each row will start with a multiple of 30 added by 1, such as 1, 31, 61, 91, 121, ... . When we mark the prime numbers in this table, we get <i>Image 10</i>. | ||

Line 168: | Line 169: | ||

<i>Image 11</i> shows the process of eliminating multiples of prime numbers from the table. First, we eliminate multiples of 2, and then we eliminate multiples of 3. Since 4 is a multiple of 2, any multiple of 4 was already eliminated. Thus, we next eliminate multiples of 5. We continue this process until we eliminate multiples of 19. (We do not eliminate numbers bigger than 19 because we only have numbers up to 390 in this table.) Note that when we eliminate multiples of 2, 3 or 5, the entire column that comes below any multiple of 2, 3, 5 on the first row get eliminated as well. | <i>Image 11</i> shows the process of eliminating multiples of prime numbers from the table. First, we eliminate multiples of 2, and then we eliminate multiples of 3. Since 4 is a multiple of 2, any multiple of 4 was already eliminated. Thus, we next eliminate multiples of 5. We continue this process until we eliminate multiples of 19. (We do not eliminate numbers bigger than 19 because we only have numbers up to 390 in this table.) Note that when we eliminate multiples of 2, 3 or 5, the entire column that comes below any multiple of 2, 3, 5 on the first row get eliminated as well. | ||

- | [[ | + | {{Anchor|Reference=15|Link=[[Image:irisgrid3.gif|Image 15|thumb|700px|none]}} |

We can see from <i>Image 11</i> that eliminating multiples of 2, 3, 5 leaves us with columns where prime numbers appear. All of these multiples of 2, 3, and 5, or all the numbers that are not in the prime-concentrated column, have the form | We can see from <i>Image 11</i> that eliminating multiples of 2, 3, 5 leaves us with columns where prime numbers appear. All of these multiples of 2, 3, and 5, or all the numbers that are not in the prime-concentrated column, have the form | ||

Line 195: | Line 196: | ||

|AuthorName=en.wikipedia | |AuthorName=en.wikipedia | ||

|Field=Number Theory | |Field=Number Theory | ||

- | |WhyInteresting= | + | |WhyInteresting== |

- | [[ | + | {{Anchor|Reference=16|Link=[[Image:prime1.gif|Image 16|thumb|300px]]}} |

Not much is discovered about the Ulam spiral. For instance, the reason for the diagonal alignment of prime numbers or the vertical and horizontal arrangement of non-prime numbers is not clear yet. Indeed, Ulam spiral is not heavily studied by mathematicians. However, Ulam spiral's importance lies on the fact that it shows a clear pattern among prime numbers. | Not much is discovered about the Ulam spiral. For instance, the reason for the diagonal alignment of prime numbers or the vertical and horizontal arrangement of non-prime numbers is not clear yet. Indeed, Ulam spiral is not heavily studied by mathematicians. However, Ulam spiral's importance lies on the fact that it shows a clear pattern among prime numbers. | ||

- | Some might suspect that we are seeing diagonal lines in the Ulam spiral because the human eye seeks patterns and groups even among random cluster of dots. However, we can compare | + | Some might suspect that we are seeing diagonal lines in the Ulam spiral because the human eye seeks patterns and groups even among random cluster of dots. However, we can compare [[#16|Image 16]] and [[#17|Image 17]] and see that the prime numbers actually have a distinct pattern of diagonal lines that random numbers do not have. [[#16|Image 17]] is a Ulam spiral where the black dots denote for the prime numbers, and [[#17|Image 17]] is a Ulam spiral of random numbers. |

- | [[ | + | {{Anchor|Reference=17|Link=[[Image:randomintegers.jpg|Image 17|thumb|300px]]}} |

People are interested in the pattern among prime numbers because the pattern might give enough information for us to discover a new polynomial that will generate more prime numbers than previously-discovered polynomials. The discovery of formula for prime numbers can lead us to have better understanding of other mysterious conjectures and theories involving prime numbers, such as {{EasyBalloon|Link=twin prime conjecture|Balloon=Twin prime conjecture states that there are infinitely many primes <math>p</math> such that <math>p+2</math> is also a prime.}} or <balloon title="The Goldbach's conjecture states that every even integer greater than 2 can be written as a sum of two primes.">Goldbach's conjecture</balloon>. For more information about the twin prime conjecture or Goldbach's conjecture, go to [http://mathworld.wolfram.com/TwinPrimeConjecture.html Wolfram Math World :Twin Prime Conjecture] or [http://mathworld.wolfram.com/GoldbachConjecture.html Wolfram Math World :Goldbach Conjecture]. | People are interested in the pattern among prime numbers because the pattern might give enough information for us to discover a new polynomial that will generate more prime numbers than previously-discovered polynomials. The discovery of formula for prime numbers can lead us to have better understanding of other mysterious conjectures and theories involving prime numbers, such as {{EasyBalloon|Link=twin prime conjecture|Balloon=Twin prime conjecture states that there are infinitely many primes <math>p</math> such that <math>p+2</math> is also a prime.}} or <balloon title="The Goldbach's conjecture states that every even integer greater than 2 can be written as a sum of two primes.">Goldbach's conjecture</balloon>. For more information about the twin prime conjecture or Goldbach's conjecture, go to [http://mathworld.wolfram.com/TwinPrimeConjecture.html Wolfram Math World :Twin Prime Conjecture] or [http://mathworld.wolfram.com/GoldbachConjecture.html Wolfram Math World :Goldbach Conjecture]. | ||

## Revision as of 14:11, 15 July 2010

{{Image Description |ImageName=Ulam spiral |Image=Ulam_spiral.png |ImageIntro=The Ulam spiral, or prime spiral, is a plot in which prime numbers are marked among positive integers that are arranged in a counterclockwise spiral. The prime numbers show a pattern of diagonal lines. |ImageDescElem=The prime spiral was discovered by Stanislaw Ulam (1909-1984) in 1963 while he was doodling on a piece of paper during a science meeting. Starting with 1 in the middle, he wrote positive numbers in a grid as he spiraled out from the center, as shown in Image 1. He then circled the prime numbers, and the prime numbers showed patterns of diagonal lines as shown by the grid in Image 2. The grid in Image 2 is a close-up view of the center of the main image such that the green line segments and red boxes in the center of the main image line up with those in Image 2.

A larger Ulam spiral with 160,000 integers and 14,683 primes is shown in the main image. Black dots indicate prime numbers. In addition to diagonal line segments formed by the black dots, we can see white vertical and horizontal line segments that cross the center of the spiral and do not contain any black dots, or prime numbers. There are also white diagonal line segments that do not contain any prime numbers. Ulam spiral implies that there is some order in the distribution of prime numbers.

|ImageDesc=From time immemorial, humans have tried to discover patterns among prime numbers. Currently, there is no known simple formula that yields all the primes. The diagonal patterns in the Ulam spiral gives some hint for formulas of primes numbers.

**Definition of Half-lines**

Many half-lines in the Ulam spiral can be described using quadratic polynomials . A *half-line* is a line which starts at a point and continues infinitely in one direction. In this page, we only consider half-lines that are horizontal or vertical, or have a slope of -1 or +1. The half-lines that can be described using quadratic polynomials are the ones in which each entry of the diagonal is positioned on a different *ring* of the spiral.

The *ring* of a spiral can be considered as the outermost layer of a concentric square or a rectangle centered around the center of the spiral, 1, as defined by the blue line in the grid. Although there is no exact place where we can determine the beginning and end of a ring, we will assume that entries that are positioned on squares or rectangles of the same sizes to be on the same ring. For instance, 24, 25, 26, 27, 28, which are shown in red boxes in Image 3, are on the same ring, whereas 48, 49, 50, 51, 52, as shown in blue boxes, are on a different ring because they are positioned on a bigger square.

The green lines in the Image 3 qualify as diagonal half-lines whereas the red lines do not because the red lines cross the corner of the grid in a way that two entries of the red diagonal line are positioned on the same ring.

Thus, diagonal line segments that are composed of prime numbers can also be expressed as outputs of quadratic polynomials. To learn more about the relation between the diagonal lines and quadratic polynomials, click below.

**Examples of quadratic polynomials for half-lines**

For instance, prime numbers , which are aligned in the same diagonal, can be described through the output of the polynomial for . Similarly, numbers , which are also aligned in a green diagonal in Image 5 starting from the center and continuing to the upper right corner, can be expressed by:

for . (We will refer back to this polynomial in a later section) In fact, the part of the green diagonal that starts from the center and continues to the bottom left corner can also be described through **Eq. (1)** for .

In fact, even horizontal and vertical line segment in the grid can be described by quadratic polynomials, as long as the lines satisfy the condition that no two entries are positioned on the same ring. For instance, the blue horizontal line segment in Image 5, can be described by a quadratic polynomial. However, the sequence on the same horizontal line cannot be described by a polynomial because the entries 9 and 10 are on the same ring.

Moreover, it is not hard to show that the green diagonal line from Image 5 that goes through the center and has a slope of +1 is the only line on which the Ulam numbers in both directions can be described by the same polynomial. Even the red diagonal line that goes through the center and has a slope of -1 cannot be described by one polynomial.

Half of the red diagonal, the segment going up from the center, can be described by for inputs that are even numbers, while the diagonal going down from the center, is a sequence of perfect squares of odd numbers. Thus we cannot find one polynomial that generates both all entries of the red diagonal.

## Contents |

## Euler's Prime Generator

Many have come up with polynomials in one variable that generate prime numbers, although none of these polynomials

**[...]**

Many have come up with polynomials in one variable that generate prime numbers, although none of these polynomials can generate all the prime numbers. One of the most famous polynomials is the one discovered by Leonhard Euler(1707-1783), which is :

Euler's polynomial generates distinct prime numbers for each integer from to .

As we can see in Image 6, we can start an Ulam's spiral with 41 at the center of the grid and get a long, continuous diagonal with 40 prime numbers. One interesting fact is that the 40 numbers in the diagonal line segment are the first 40 prime numbers that are generated through Euler's polynomial. Moreover, the prime numbers are not aligned in order of increasing values. In fact, with 41 in the center, other prime numbers alternate in position between the upper right and lower left part of the diagonal.

## Sacks Spiral

{{SwitchPreview|ShowMessage=Click here to show more.|HideMessage=Click here to hide|PreviewText=Sacks spiral is a variation of the Ulam spiral that was devised by Robert Sacks in 1994. Sacks spiral places 0 in the center and|FullText=

Sacks spiral is a variation of the Ulam spiral that was devised by Robert Sacks in 1994. Sacks spiral places in the center and places nonnegative numbers on an Archimedean spiral , whereas the Ulam spiral places in the center and places other numbers on a square grid. Moreover, Sacks spiral makes one full counterclockwise rotation for each square number , as shown in the image below. The darker dots indicate the prime numbers.

We can also see that numbers that have blue check marks and are aligned in the left side of the spiral are pronic numbers . For example, .

Moreover, these numbers are aligned in positions that are a little less than half of one full rotation from one perfect square to the next perfect square, for instance, from 4 to 9, or 9 to 16. Let the th perfect square be . Then, going from the th perfect square to the st perfect square, the difference between the two numbers will be . We can show this by calculating the difference between two consecutive perfect squares,

Because the pronic numbers are positioned a little less than half of one full rotation from the perfect squares, their position is a little less than from the th perfect square as we go around the spiral. Indeed, any pronic number , and the pronic number with the form is aligned at the th position from the origin. From this, we can see that pronic number that has the form appears as the th number along the spiral from the th perfect square.

An interesting pattern can be discovered when we start the spiral at 41. As the image below shows, the red dots are the first 40 prime numbers generated by Euler's polynomial, and they are aligned in the center and positions where pronic numbers used to be in the original Sacks spiral.

## Other Numbers and Patterns

### Triangular Number

A number is a triangular number if number of dots can be arranged into an equilateral triangle evenly filled with the dots. As shown in theimage below, the sequence of triangular numbers continue as .

The triangular number, , is given by the formula :

When we mark the triangular numbers in a Ulam spiral, a set of spirals are formed as shown in the image below.

### Prime numbers in lines

{{SwitchPreview|ShowMessage=Click here to show more.|HideMessage=Click here to hide|PreviewText=The Ulam spiral inspired the author of this page to create another table and find a pattern among prime numbers. First, we create a table|FullText=

The Ulam spiral inspired the author of this page to create another table and find a pattern among prime numbers. First, we create a table that has 30 columns and write all the natural numbers starting from 1 as we go from left to right. Thus, each row will start with a multiple of 30 added by 1, such as 1, 31, 61, 91, 121, ... . When we mark the prime numbers in this table, we get *Image 10*.

We can see that prime numbers appear only on certain columns that had 1, 7, 11, 13, 17, 19, 23, 29 on their first row. This image shows that all prime numbers have the form:

Note that not all numbers generated by this form are prime numbers. Another point to notice in the picture is that the nonprime numbers that appear on prime-concentrated columns are all multiples of prime numbers larger than or equal to 7. For instance, . In fact any combination of two prime numbers larger than or equal to 7 all appear on these prime-concentrated columns.

To learn more about the reason for such alignment of prime numbers, click below.

{{HideShowThis|ShowMessage=Click here to show more.|HideMessage=Click here to hide content.|HiddenText=

*Image 11* shows the process of eliminating multiples of prime numbers from the table. First, we eliminate multiples of 2, and then we eliminate multiples of 3. Since 4 is a multiple of 2, any multiple of 4 was already eliminated. Thus, we next eliminate multiples of 5. We continue this process until we eliminate multiples of 19. (We do not eliminate numbers bigger than 19 because we only have numbers up to 390 in this table.) Note that when we eliminate multiples of 2, 3 or 5, the entire column that comes below any multiple of 2, 3, 5 on the first row get eliminated as well.

{{Anchor|Reference=15|Link=[[Image:irisgrid3.gif|Image 15|thumb|700px|none]}}

We can see from *Image 11* that eliminating multiples of 2, 3, 5 leaves us with columns where prime numbers appear. All of these multiples of 2, 3, and 5, or all the numbers that are not in the prime-concentrated column, have the form

or

- ,

where .

Thus, for a given number with the form of **Eq. (3)** we are able to factor out 2 or 3 or 5, or any combination of the three, which means that this number is divisible by 2, 3, or 5.

However, we know that prime numbers are not multiples of 2 or 3 or 5. Then, these prime numbers will *not* have the same form as **Eq. (3)**, or else the prime numbers will be divisible by 2 or 3 or 5. Indeed, we can see that the prime numbers are positioned at :

Thus, prime numbers have to be positioned on the blue columns that do not have the same form as **Eq. (3)**.

Next, we look at nonprime numbers that are products of multiplication of two prime numbers or a perfect square of a prime number. These products will be divisible by the prime numbers they are composed of, but they will not be divisible by 2 or 3 or 5.

For instance, 77, which is a nonprime number that appears on the column of prime numbers 117, 47, 107, 137, ..., is a product of two prime numbers, 7 and 11. Because each of these prime numbers do not have any divisors other than 1 and themselves, 77 is not divisible by 2 or 3 or 5. Thus, 77 and all other products of prime numbers also cannot have the same form as **Eq. (3)**, and they have to appear on the blue columns that are concentrated with prime numbers.
}}
}}

|AuthorName=en.wikipedia |Field=Number Theory |WhyInteresting==

Not much is discovered about the Ulam spiral. For instance, the reason for the diagonal alignment of prime numbers or the vertical and horizontal arrangement of non-prime numbers is not clear yet. Indeed, Ulam spiral is not heavily studied by mathematicians. However, Ulam spiral's importance lies on the fact that it shows a clear pattern among prime numbers.

Some might suspect that we are seeing diagonal lines in the Ulam spiral because the human eye seeks patterns and groups even among random cluster of dots. However, we can compare Image 16 and Image 17 and see that the prime numbers actually have a distinct pattern of diagonal lines that random numbers do not have. Image 17 is a Ulam spiral where the black dots denote for the prime numbers, and Image 17 is a Ulam spiral of random numbers.

People are interested in the pattern among prime numbers because the pattern might give enough information for us to discover a new polynomial that will generate more prime numbers than previously-discovered polynomials. The discovery of formula for prime numbers can lead us to have better understanding of other mysterious conjectures and theories involving prime numbers, such as twin prime conjecture or Goldbach's conjecture. For more information about the twin prime conjecture or Goldbach's conjecture, go to Wolfram Math World :Twin Prime Conjecture or Wolfram Math World :Goldbach Conjecture.

|InProgress=Yes
}}