# Prime Factorization with the Prime Spiral Sieve

### The 8-Chord Progression | Prime Number Sieving Algorithms | Digital Root Sequencing This work is licensed by its author, Gary William Croft, under a Creative Commons Attribution-ShareAlike 3.0 Unported License

## The 8-Chord Progression

Before detailing prime factorization algorithms using the Prime Spiral Sieve, it will be helpful to understand the eight chord progressions that drive factorization of the domain. Imagine 8 player pianos side-by-side, all accessing the same set of possible notes (the set of natural numbers not divisible by 2, 3 and 5), but each running its own set chord progression. Analzyed individually, the 8 algorithmically expanding chord progressions are simple to understand, yet when you superimpose their patterns the result appears deceptively random, when in fact it is anything but. To wit: Each number in the array (except 1) is the starting point for an 8-note "chord" pattern that repeats after each rotation, ad infinitum.

In terms of firing sequences and factorization product distribution coordinates, there are 8 fundamental chord patterns corresponding to the 8 radii of the spiral configuration (labeled, referencing the "prime root" radii, 1chord; 7chord; 11chord; 13chord; 17chord; 19chord; 23chord; and 29chord).

Each of the 8 chord configurations possesses 8 "notes" distributed one note per root prime diagonal (and thus no individual chord ever has more than one note on the same radius). The table below illustrates the repeating chord patterns for 7chord(7) and 11chord(11), i.e., the first 7chord, starting with 7*7 is 7chord(7); the second 7chord would be 7chord(37), and the first 11chord would be 11chord(11) starting with 11*11 while the 2nd 11chord would be 11chord(41). In this rectangular matrix, the columns correspond to the eight diagonals of the Prime Spiral Sieve, while each row equals one rotation around the sieve: Each and every integer along a given prime root diagonal, when multiplied times itself and the next 7 numbers in sequence (thus accounting for all 8 radii in a chord rotation) generates products creating the same basic chord shape as its prime root, though expanded by an incremental factor of 30. For example, 37, 67 and 97 (7chord's in sequence along the 84° radius) each has the same basic chord pattern as its prime root, 7 (i.e., mod30,7), though their factorization patterns are expanded by multiples of 30. The table below illustrates this for 7chord(7) and 7chord(37), the first two 7chords: As you can see above, the products generated by factoring the 7chords for 7 and 37 distribute in the same sequence and to the same columns, though the distances between the products have expanded accordian-like.

The matrix below details one complete Prime Root Chord Cycle (comprised of 8 unique chord shapes requiring 8*8  factorizations to complete and therefore indexing 64 composite numbers in the array).

Here are a few examples to help make the matrix intelligible:

Example 1: In the "1chord" section, interpret AxA→A as: Any number in Column A (1..12°) times itself or any other number in Column A (1..12°) will result in a product that distributes to Column A (1..12°).

Example 2: In the "11chord" section, interpret CxH→F as: Any number in Column C (11..132°) times any number in Column H (29..348°) will result in a product that distributes to Column F (19..228°). Analyzing the matrix, above, you'll note that in a completed 8-chord cycle:

1. Each of the 8 root prime angles (columns A thru H) receives 8 factorization products, for a total–given there are 8 chord shapes–of 64 distinct factorizations.
2. All of the distributed products are non-primes with the exception of 1chord's 1st cycle (1x1; 1x7; 1x11; 1x13; 1x17; 1x19; 1x23; and 1x29), which effectively positions the root primes in the "starting gate" to be used as set-points of reference for all arithmetic progressions and factorizations that follow. Thus 1chord's 1st factorization for non-primes begins with number 31, which is the 2nd number in the 12° radius progression.
3. All squares distribute to either A (1..12°) or F (19..228°), as follows: AxA, CxC, FxF and HxH distribute to A (1..12°); BxB, DxD, ExE and GxG distribute to F (19..228°). You'll note that A and F are the only two Columns with product distribution intervals not resolving to perfect symmetry when spanning a completed 8-chord progression. This is presumably because A and F receive the products of all squares making their configurations distinctive from the other six.
4. The tent shapes in the right-hand column, showing the prime root pairings within each chord summing to 30, tell us that A thru D (1chord thru 13chord) and E thru H (17chord thru 29chord) have identical "30 something" patterns.

Unlike the Sieve of Eratosthenes, the Prime Spiral Sieve does not strike (eliminate) non-prime integers; In the Prime Spiral Sieve non-primes are tagged (indexed) as opposed to struck out, because, aside from ensuring that exponentiality is accounted for, they–like all numbers in the sequence–generate indexing chords. For example, 49 (72), though a composite number (and the first non-prime in the array), forms a repeating 8-note chord (In 49's case: 49*49; 49*53; 49*59; 49*61; 49*67; 49*71; 49*73; 49*77; [equivalent to factoring one rotation of the spiral sieve] then, repeating the chord pattern +30: 49*79; 49*83; 49*89; 49*91; 49*97; 49*101; 49*103; 49*107); repeat +30 ... n. Thus 49, though a non-prime, tags its own sequence of non-primes. [Note: One consequence of this is that when composite numbers in the sequence are used as multiplicands or multipliers in the indexing of composite numbers, duplicate products are generated, e.g., 7*77 = 539 is equivalent to 11*49 = 539 (both 77 and 49 being composite numbers, and both expressions being equivalent to 7*7*11 = 539; to see more clearly how such duplicates distribute, click here). This is not problematic except that it complicates creating a formula that produces an exact count of prime vs. composite numbers. If and when these "duplicates" can be accounted for mathematically, the way would be paved to calculate the exact number of primes from 7 to a given n. Because the chord progression factorization algorithm is deterministic, leaving only prime numbers in its wake, it is presumably possible to formulate the frequency of these duplications.]

When one cycle of an 8-note chord is completely factorized the distribution of its products along the spiral spans a number of rotations equal to the integer being chorded, e.g., 97 (rooting to 7chord, i.e., mod30,7) yields products that distribute to 97 rotations of the spiral to complete each of its infinitely repeating chords (or 97 rows in an 8-column matrix).

To view a color-coded matrix demonstrating the results of factoring one complete chord progression, click here. Because the 8-chord/64-note sequences overlap, with the products from the next sequence's factorizations beginning before the prior sequence ends, an illusion is created of chaos and randomness. The reality, however, is that the eight chord sequences factor and progress geometrically with deterministic precision and unvarying symmetry when understood as independent but overlapping superimposed entities.

To determine which of the 8 basic chord patterns a given number in the array generates is easily deduced by calculating the number's mod 30, e.g., mod 30 for 49 = 19; thus, 49 generates 19chord; likewise, mod 30 for 821 = 11, and thus 821 generates 11chord, albeit the distances between the numbers constituting 11chord for 821 are expanded by a factor of 30*27 (30*27=810; 821-810=11; 11 being the prime root for 821).

1chord (1*1; 1*7; 1*11; 1*13; 1*17; 1*19; 1*23; 1*29; etc.) is unique in one important respect: Its lst "note" (1*1=1) effectively disables the number 1 as a factor or indexer of non-primes. 1chord's tagging of non-primes, therefore, starts with its second increment (1+30) or rotation: 31*31; 31*37; 31*41; 31*43; 31*47; 31*49; 31*53; 31*59, etc.

## Factorization Algorithms and Prime Number Sieving

There are three basic ways to identify the composite numbers in the array (the set of all natural numbers not divisible by 2, 3 and 5): the first employs multiplication, the second division and the third and most complex a combination of multiplication, alternating addition and subtraction, and division:

1. All composite numbers in the array are the products of all preceding numbers in the sequence times themselves and all subsequent numbers. The one exception is 1, which effectively self-eliminates (1*1=1 tags itself as a non-prime). Thus: 7*7 tags 49 as a non-prime; 7*11 tags 77 as a non-prime ...n. Below is an interesting graphical array of these products (non-primes): 2. The array can be efficiently factorized using modular arithmetic by simply dividing the set unto itself sequentially: All modulo n ≡ 0 results generated (except when a number is divided by itself) indicate factors (arrayed horizontally, hi-lited in blue) of n (arrayed vertically, hi-lited in yellow), as illustrated below. [Note: Where there's only one zero, n is a square; With regard to the example, below, if your sole purpose were to determine primality, given that the square root of the highest number tested in this sample, 209, is 14.45..., you would need only test this series to mod 13 since encountering one zero identifies a number as composite. To make the number-crunching even more efficient, the sieving program could be coded to bypass retesting numbers already proven to be composite.]: 1. The third factorization method is cumbersome and inefficient. However, because it employs the root prime angles, in a procedure involving multiplication, alternating addition or subtraction, as well as division to derive factors, it is nonetheless interesting for its own sake, and shows promise of opening new lines of inquiry. If this piques your curiosity, click here.

[Note: If you use Python (the computer programming language designed for the development of scientific, engineering and mathematics applications), an MIT licensed Python module dubbed "pyprimes" designed to run and compare prime number sieving algorithms, including the Prime Spiral Sieve (using its former name, "Croft Spiral"), can be found here or here at code.google.com The programmer, by-the-way, rates the Prime Spiral Sieve "fastest/best" and recommends it as "the preferred way of generating prime numbers" compared to several sieves tested.]

## Digital Root Sequencing: The Fundamental Factorization Drivers

To gain a deeper understanding of the algorithms driving the factorization and prime number sieving methods described above, we must venture into the realm of digit sum arithmetic. By analyzing the sequencing of digital root elements belonging to this set, we will discover the fundamental patterns underlying all factorizations generated by this sieve.

First, let's define our terminology, which–please note–may vary slightly from how it's used elsewhere: digit sum is simply the sum of a number's unit values, e.g., 49 = 4+9 = 13 = digit sum. digital root (aka "repeated digit sum," "iterated sum-of-digits," or "modulus 9 function") refers to the single digit (1-9) resulting when all digit sums are summed in turn, e.g., 49 = 4+9 = 13 = 1+3 = 4 = digital root. Digital roots will be expressed in this form: dr(n). When digital roots are multiplied, the product is expressed in its digital root form, thus dr(2) x dr(5) = dr(1), given that 2x5=10 and the digital root of 10 is 1, or dr(1).

Although with practice digital root multiplication can easily be computed by head, using the table below (sometimes referred to as the Vedic square) is a good way to get started: find the x-y intersection (x = 1st row; y = 1st column) of two digital root factors to find the digital root product:

#### Digital Root Multiplication Table In this context, the first thing we need to know about the set of all natural numbers not divisible by 2, 3 and 5 when arrayed in 8 columns is that each of the 8 columns has an infinitely repeating digital root sequence expressed in one of two sets: {1,4,7} or {2,5,8}, albeit the starting digit varies, as shown below in two formats (radial versus matrix):

The illustration directly below shows the repeating digital root sequences that radiate along the 8 spiral sieve diagonals; also shown are the digital root sums of adjacent diagonals (in yellow). The {1,4,7},{2,5,8} and {3,6,9} repeating triplets are known as the "Trinity of Triangles" that originate when constructing a 9-point star in the form illustrated below (also pictured, at the center of the star, is perhaps the most 'famous' magic square of all, attributed to Lo Shu, incorporating the numbers 1 thru 9 where all rows, columns and principal diagonals sum to 15). Also pictured are the corresponding "Trinity of Magic Squares" (attributable to the undersigned) which in combination reveal their own {3,6,9} triangular digital root sequencing.

[Note: To see how the Lo Shu Magic Square and Trinity of Magic Squares can be combined in a "4-Fold Way" to create their own magic square when configured in a 4 x 4 matrix of magic squares consisting of 144 (122) elements where all rows, columns and principal diagonals sum to 60 and the sum total of the matrix's elements = 720 = 360 x 2, click here]: Reformatting the radial sequencing above into a matrix, below are the first 9 rows (72 elements) in our defined domain arrayed in 8 columns, starting with the actual elements displayed in the table on the left (1 thru 269) with their digital roots arrayed in the table on the right: As you can see, the difference cycle for digital roots is 90, e.g., 1, 91, 181, 271, +90 ... n, and in this example all have digital roots = dr(1) and all are x ≡ 1(mod90). It follows that modulo 90 (much like division by the number 9) of any number (x) in this domain will have the same digital root as x, e.g., 269 ≡ 89(mod90): both 269 and 89 are dr(8). With these repeating patterns in mind, we form the basis for tracing all prospective factors for composite numbers in the array to modulo 90 roots, as configured, below: Now, let's take the modulo 90 configuration, and create a table matrix for digital roots and terminating digits, thus: With digital sum multiplication logic in mind, we know that a given composite number's digital root dictates the possible "roll-ups" of its factors (whether prime or composite) into digital root dyads, as shown below: We can take what we learned above and create a multiplication table for digital roots limited to those that operate within this domain–and the result, a magnificent mathematical object, especially considering its function at the heart of the prime number sequence in concert with its beautiful symmetries:

Every row and every column of the matrix contains the elements 1,4,7,2,5,8 arranged in some order and totaling 27. Every diagonal is palindromic, and the principal (corner-to-corner) diagonals {1,4,7,7,4,1} and {8,5,2,2,5,8} (the latter totaling 30) are also interesting in how they work in combination to create parallel 9's. This "magic square" is the progenitor of all composite numbers in the Prime Spiral Sieve, as we'll see illustrated below.

Note 1: We'll grant that technically this is not a "magic square," given that the values of the corner-to-corner diagonals (one sums to 24 and the other to 30) don't have the same totals as the vertical and horizontal sums (all sum to 27). Nevertheless, we think it's fair to say that this square is at least "magical," given that a) the values in the outer perimeter total 90 (makes sense given that the square contains modulo 90 digital roots); b) that the digital root of the entire object is 9, which in digit sum arithmetic is equivalent to zero, thus presenting the paradox of alpha and omega being one; the proverbial snake eating its own tail; c) that its symmetries involving 9's are beautiful to behold; d) that although the principal diagonals don't individually total 27 to technically make this a "magic" square, when added together 24 + 30 equals 54 which is 2 times 27; e) this matrix is functional: it can be used, in concert with modulo 90, as a digital root calculator for factors and products (composite numbers) in the array, and f) saving the most impressive dimension for last, this matrix is at the heart of the most beautiful example of symmetry you'll find on this site, the Magic Mirror Matrix, a mathematical object possessing a stunning concatenation of symmetries and representing the factorization of the first 1000 prime numbers–exactly.

Note 2: Assuming that left-right / up-down are arbitrary, there are four instances of the sequence 2,4,8,1,5,7 spanning two rows and two columns of the square, creating a perfect square of 4 units at the very center of the matrix. It may be coincidental, but it's interesting that this sequence is one form of the period 6 repeating "imaginary period of the digital roots of the prime numbers" according to a posting on OEIS by Odimar Fabeny, Sep 05 2010.

Having ascertained the digital root factoring possibilities for this domain, we can now translate the dyads into actual modulo 90 factors (keeping in mind that modulo 90 of any number in the array will be equivalent to one of the first 24 elements in the array: 1 - 89). Using the tables below, by referencing the terminating digit and digital root values, we can evaluate any element in the set of natural numbers not divisible by 2, 3 and 5 to determine its possible modulo 90 factorization dyads. For example, take the number 125291: it has a terminating digit of 1 and digital root of 2, or dr(2); referencing the table below labeled "dr x dr = dr(2) for td = 1, 3, 7 and 9", the first column (td=1) lists 12 possible modulo 90 factorization dyads where terminating digit = 1 and digital root = 2. In the case of our example, 125291, it has prime factors 349 and 359; 349 ≡ 79(mod90) and 359 ≡ 89(mod90). Referring back to our table, we find 79 x 89 in the section headed "dr(7) x dr(8) = dr(2); in other words, the number 125291, which has a digital root of 2 possesses factors that are dr(7) x dr(8).

Composite numbers with more than two prime factors can have two or more dyad roots. For example, 1001 (7 x 11 x 13) in dyad form could be expressed as either 77 x 13 [equivalent to dr(5) x dr(4) = dr(2)] or 7 x 143 [equivalent to dr(7) x dr(8) = dr(2)]. Referencing the table below headed "dr x dr=dr(2) for td = 1, 3, 7 and 9," you'll find 13 x 77 under section "dr(4) x dr(5) = dr(2)" and column "td=1." The other dyad, 7 x 143, can be found in section "dr(7) x dr(8) = dr(2)" under column "td=1." Can you guess which dyad applies? The answer is 7 x 53, as 53 + 90 = 143. What we're saying in effect is that at least two of the composite or prime factors for any composite number in this array can be traced back in increments of 90 to one of the 24 modulo 90 roots.

[Note: Regarding the tables that follow: The reason dr(1), dr(4) and dr(7) have 4 dyad structures compared to only 3 for dr(2), dr(5) and dr(8) is because all perfect squares in the array distribute to n ≡ 1(mod30) or n ≡ 19(mod30), both of which possess {4,1,7} digital root sequences. Conversely, elements with a digital root in the {2,5,8} sequence will never be square.]

Our first set configures the 4 digital root factorization dyads for elements in the array n = dr(1), thus:
[dr(1) x dr(1) = dr(1)]; [dr(2) x dr(5) = dr(1)]; [dr(4) x dr(7) = dr(1)]; [dr(8) x dr(8) = dr(1)]: Our second set configures 3 digital root factorization dyads for elements in the array n = dr(2), thus:
[dr(1) x dr(2) = dr(2)]; [dr(4) x dr(5) = dr(2)]; [dr(7) x dr(8) = dr(2)]: Our third set configures 4 digital root factorization dyads for elements in the array n = dr(4), thus:
[dr(1) x dr(4) = dr(4)]; [dr(2) x dr(2) = dr(4)]; [dr(5) x dr(8) = dr(4)]; [dr(7) x dr(7) = dr(4)]: Our fourth set configures 3 digital root factorization dyads for elements in the array n = dr(5), thus:
[dr(1) x dr(5) = dr(5)];[dr(2) x dr(7) = dr(5)];[dr(4) x dr(8) = dr(5)]: Our fifth set configures 4 digital root factorization dyads for elements in the array n = dr(7), thus:
[dr(1) x dr(7) = dr(7)];[dr(2) x dr(8) = dr(7)];[dr(4) x dr(4) = dr(7)];[dr(5) x dr(5) = dr(7)]: Our sixth set configures 3 digital root factorization dyads for elements in the array n = dr(8), thus:
[dr(1) x dr(8) = dr(8)];[dr(2) x dr(4) = dr(8)];[dr(5) x dr(7) = dr(8)] 