Prime spiral (Ulam spiral)

From Math Images

(Difference between revisions)

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.

Image 1

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.

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.

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

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

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.

1 Euler's Prime Generator
2 Sacks Spiral
3 Other Numbers and Patterns
- 3.1 Triangular Number
- 3.2 Prime numbers in lines

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

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 8

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

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

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

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 $n$ th perfect square be $n^2$ . Then, going from the $n$ th 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 $n$ th 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 $n$ th number along the spiral from the $n$ 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.

Image 11

Other Numbers and Patterns

Triangular Number

A number ${n}$ is a triangular number if UNIQ670d61d6253c797b-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

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

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=

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 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:

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

{{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

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

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

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

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

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 }}

Retrieved from "http://mathforum.org/mathimages/index.php/Prime_spiral_%28Ulam_spiral%29"

@@ Line 133: / Line 133: @@
 {{Anchor|Reference=11|Link=[[Image:41prime.jpg|Image 11|thumb|250px|left]]}}
+}}
 ==Other Numbers and Patterns==
 ===Triangular Number===

Prime spiral (Ulam spiral)

From Math Images

Revision as of 14:11, 15 July 2010

Contents

Euler's Prime Generator

Sacks Spiral

Other Numbers and Patterns

Triangular Number

Prime numbers in lines

Views

Personal tools

Navigation

Search

Browse images by...

Interaction

Create or Edit a Page

Special Resources

Toolbox