Prime spiral (Ulam spiral)

From Math Images

(Difference between revisions)
Jump to: navigation, search
Line 202: Line 202:
{{Anchor|Reference=17|Link=[[Image:randomintegers.jpg|Image 17|thumb|300px]]}}
{{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].
-
|ToDo=An explanation for the patterns appearing among triangular numbers
+
|ToDo=An explanation for the patterns appearing among triangular numbers in [[Prime_spiral_%28Ulam_spiral%29#Triangular_Number|Triangular number]] section
|InProgress=Yes
|InProgress=Yes
}}
}}

Revision as of 15:13, 15 July 2010

Image:inprogress.png

Ulam spiral

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.


Contents

Basic Description

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.

Image 1
Image 1

Image 2
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.

A More Mathematical Explanation

From time immemorial, humans have tried to discover patterns among prime numbers. Currently, there is [...]

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.

Image 3:Diagonal half-lines
Image 3:Diagonal half-lines


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.

Half-lines and quadratic polynomias

First, we need to know the relation between quadratic polynomials and the difference table of sequences. Let's choose the diagonal  5, 19, 41, 71, 109, 155, the diagonal indicated with green dotted line in Image 3, as our original sequence and create a difference table.

image:diff.jpg

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.

Image 4:Constant 2nd differences
Image 4:Constant 2nd differences


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 5, 19, 41, 71, 109, 155. (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 Image 4, the number of the innermost light blue boxes, which is 14, indicate the distance from 5 to 19 , or the difference between these two numbers. The number of darker blue boxes in the middle indicate the difference between the numbers  19 and 41. The darkest blue boxes on the outside indicate the difference between the entries  41 and 71. The number of all these blue boxes correspond to the first differences in the difference table.

In 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 8 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 Image 4 illustrates, regardless of the exact number of the blue boxes, there are 8 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 8. Thus, the sequence for any diagonal half-line can be described using a quadratic polynomial.

Examples of quadratic polynomials for half-lines

For instance, prime numbers  5, 19, 41, 71, 109, which are aligned in the same diagonal, can be described through the output of the polynomial 4x^2+10x+5 for x=0, 1, 2, 3, 4. Similarly, numbers  1, 3, 14, 31, 57, 91 \dots , 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:

Eq. (1)        4x^2-2x+1

for x=0, 1, 2, 3, \dots. (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 x=0, -1, -2, -3, \dots.

Image 5
Image 5


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,  10, 27, 52, 85 can be described by a quadratic polynomial. However, the sequence  9, 10, 27, 85 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,  5, 17, 37, 67, \dots can be described by x^2+1 for inputs that are even numbers, while the diagonal going down from the center, 1, 9, 25, 49, \dots is a sequence of perfect squares of odd numbers. Thus we cannot find one polynomial that generates both all entries of the red diagonal.

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 :

x^2-x+41

Euler's polynomial generates distinct prime numbers for each integer x from x=1 to  x=40.

Image 6
Image 6


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.

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.

First, we found out in the previous section that Eq. (1) is the polynomial for the diagonal that goes through the center 1 and has a slope of +1 in the Ulam's spiral. That is,

 4x^2-2x+1

describes the upper half of the diagonal as we plug in x=0, 1, 2, 3, \dots and the lower half of the diagonal as we plug in x=0, -1, -2, -3, \dots. Thus, x'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 Image 7.

Image 7
Image 7


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 :

Eq. (2)        4x^2-2x+41.

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 x's. Euler's polynomial can be found by reassigning the position of the entries of the diagonals so that x'=1 is at the center, x'=2, 4, 6, 8, \dots are the positions up the diagonal line, x'=1, 3, 5, 7, 9, \dots are positions of entries down the diagonal line from the center, as shown in Image 8. Thus, starting with x'=1 at the center, we alternate between the right and left of the center as we number the positions x'=1, 2, 3, 4, 5, \dots.

Image 8
Image 8


Then, for the upper half of the diagonal in Image 8, we can use x'=2, 4, 6, 8, \dots instead of x=1, 2, 3, 4, \dots from Image 7. Then,

x=\frac{1}{2} x'

If we plug this value in to 4x^2-2x+41 of Eq. (2), we get :

4(\frac{1}{2}x')^2-2(\frac{1}{2}x')+41
={x'}^2-x'+41,

which has the same form as Euler's polynomial.

The same method works for the bottom half as well. We use x'=1, 3, 5, 7, \dots in Image 8 while we used x=0, -1, -2, -3, \dots in Image 7. Then,

x=\frac{-x'+1}{2}.

By substituting the x's in the polynomial 4x^2-2x+41 the same way we did above, we get:

{x'}^2-x'+41
Thus, we can see that Eq. (2), in fact, have the same output as Euler's polynomial after we reassign the position of x's. We have shown that Eq. (1), which describes the diagonal that goes through the center and has a slope of +1, can be transformed to Euler's polynomial that describes the same diagonal that has 41 as its center.


Sacks Spiral

Sacks spiral is a variation of the Ulam spiral that was devised by Robert Sacks in 1994. Sacks spiral places 0 in th [...]

Image 9
Image 9


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 places nonnegative numbers on an Archimedean spiral, whereas the Ulam spiral places 1 in the center and places other numbers on a square grid. Moreover, Sacks spiral makes one full counterclockwise rotation for each square number  4, 9, 16, 25, 36, 46, \dots , as shown in the image below. The darker dots indicate the prime numbers.

Image 10
Image 10


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,  2=1(1+1), 6=2(2+1), 12=3(3+1),\dots.

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 nth perfect square be n^2. Then, going from the nth perfect square to the (n+1)st perfect square, the difference between the two numbers will be 2n+1. We can show this by calculating the difference between two consecutive perfect squares,

(n+1)^2-n^2=n^2+2n+1-n^2=2n+1

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 n+1/2 from the nth perfect square as we go around the spiral. Indeed, any pronic number n(n+1)=n^2+n, and the pronic number with the form n(n+1) is aligned at the (n^2+n)th position from the origin. From this, we can see that pronic number that has the form n(n+1) appears as the nth number along the spiral from the nth 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.

Image 11
Image 11



Other Numbers and Patterns

Triangular Number

A number {n} is a triangular number if UNIQ6c7fe1eb390e1c60-math-00000 [...]

A number n is a triangular number if n 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 1, 3, 6, 10, 15, 21, \dots.

Image 12
Image 12


The n^{\rm th} triangular number, T_n, is given by the formula : T_n=\frac{n(n+1)}{2}

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

Image 13
Image 13


Prime numbers in lines

The Ulam spiral inspired the author of this page to create another table and find a pattern among prime numbers. Firs [...]

Image 14
Image 14


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 14.

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:

30n+(1, 7, 11, 13, 17, 19, 23, 29)

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, 49=7\times 7, \quad 77=7\times 11,  \quad 91=7\times 13, \quad 119=7\times 17, \quad 121=11\times 11, \quad 133=7\times 19 \dots. 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.

Image 15 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.

Image 15
Image 15


We can see from Image 15 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

30n + 2^{a} 3^{b} 5^{c}

or

Eq. (3)         (2\times 3 \times 5)n+2^{a} 3^{b} 5^{c} ,

where  a \geq 0, b \geq 0, c \geq 0.

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 :

(2 \times 3 \times 5)+ (1, 7, 11, 13, 17, 19, 23, 29)

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.


Why It's Interesting

Image 16
Image 16

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.

Image 17
Image 17

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.


Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.





Future Directions for this Page

An explanation for the patterns appearing among triangular numbers in Triangular number section




If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.






Personal tools