Title: Sixth Sense Sieve
by Jeff Huth
- Introduction
Given a positive integer, n, all primes above 2 and 3 fall into the set of integers 6n+/-1. All composite numbers (not having 2 and 3 as factors) also fall into this set. This post will show that the factors of the relative integers immediately above/below n identify (if any) the factors 6n+/-1; the absence of factors indicating 6n+/-1 is prime. Since n is approximately 1/6th of a later number, 6n+/-1, and the relative numbers to n predict the factors of 6n+/-1, this approach is called the Sixth Sense Sieve.
A Note on Notation:
Within a set, the pipe “|” is a separator meaning “such that.” Elsewhere, the pipe means “divides” or “is a factor of.” The negated pipe “∤” means “does not divide” or “is not a factor of.” - Observations
Initial observations of the factors of the integers immediately above and below n indicate the factors of 6n+/-1. Listed below are two examples. The tables included with each example list n (down the left); the factor candidates f across the top; and the remainder, n mod f, in the table. If the remainder is zero (highlighted pink), then f is a factor of n.
- For n=20, 6n-1=119 and 6n+1=121. 119 may be factored by 7 and 17; 121 may be factored by 11. Examining the integers below 20 (in the table below), notice that 19 is not divisible by 5 nor 7; 18 is not divisible by 7 nor 13; but 17 is divisible by 17. Examining the integers above 20, notice that 21 is not divisible by 5, but is divisible by 7; 22 is divisible by 11, but not by 13; 23 is not divisible by 17 nor 19; 24 is not divisible by 23. Notice that 6n+/-1 shares factors with the integers immediately above and below n (along these diagonals).
- For n=30, 6n-1=179 and 6n+1=181. Both 179 and 181 are prime (no factors). Examining the integers below 30 (in the table below), notice that 29 is not divisible by 5 nor 7; 28 is not divisible by 7 nor 13; 27 is not divisible by 17 nor 19; 26 is not divisible by 23 nor 25. Examining the integers above 20, notice that 31 is not divisible by 5 nor 7; 32 is not divisible by 11 nor 13; 33 is not divisible by 17 nor 19; 34 is not divisible by 23 nor 25; 35 is not divisible by 29 nor 31; 36 is not divisible by 35. Notice there are no factors for the integers immediately above and below n (along the diagonals).
- For n=20, 6n-1=119 and 6n+1=121. 119 may be factored by 7 and 17; 121 may be factored by 11. Examining the integers below 20 (in the table below), notice that 19 is not divisible by 5 nor 7; 18 is not divisible by 7 nor 13; but 17 is divisible by 17. Examining the integers above 20, notice that 21 is not divisible by 5, but is divisible by 7; 22 is divisible by 11, but not by 13; 23 is not divisible by 17 nor 19; 24 is not divisible by 23. Notice that 6n+/-1 shares factors with the integers immediately above and below n (along these diagonals).
- Proposition
First, we will generalize the solution by replacing 6 with b, and prove the more general solution. Then we will show the specific solution for b=6.
Let n be a natural number called the input number:
\[\left\{n\inℕ\right\}\]
Let b be a natural number greater than 1 called the base:
\[\left\{b\inℕ\mid b>1\right\}\]
N is defined as the base multiple of n:
\[N=bn\]
The integers immediately before and after N are:
\[k_{1}=N-1=bn-1,\;\;restated:\;\;k_{1}=-1\;(mod\;b)\]
\[k_{2}=N+1=bn+1,\;\;restated:\;\;k_{2}=1\;(mod\;b)\]
Let x be a natural number for evaluating the range of integers immediately below and above n.
\[\left\{x\inℕ\right\}\]
The evaluated integers below n are:
\[e_{x}=n-x\]
The evaluated integers above n are:
\[e_{x}=n+x\]
The potential factors, or factor candidates, are:
\[f_{x}=bx-1\]
\[f_{x}=bx+1\]
The range, or x-limit, is the distance from n necessary to evaluate all of the factor candidates less than or equal to the square root of k1 and k2. For every factor less than or equal to the square root, there is a complementary factor greater than or equal to the square root.
The (bx+/-1) factor candidates for k1=bn-1 may be identified:
The (bx+/-1) factor candidates for k2=bn+1 may be identified:
- Proof
- Proof for 3.1
- Proof for 3.1 A
Let:
\[(bx-1)\mid(n-x)\]
Then:
\[(n-x)\equiv0\;\;mod\;(bx-1)\]
Add x to both sides:
\[n\equiv x\;\;mod\;(bx-1)\]
Multiply both sides by the base:
\[bn\equiv bx\;\;mod\;(bx-1)\]
Subtract 1 from both sides:
\[bn-1\equiv bx-1\;\;mod\;(bx-1)\]
Since (bx-1) divides itself:
\[bn-1\equiv 0\;\;mod\;(bx-1)\]
\[\therefore\;if\;(bx-1)\mid(n-x)\;then\;(bx-1)\mid(bn-1)\] - Proof for 3.1 B
Let:
\[(bx-1)∤(n-x)\]
Then:
\[(n-x)≢0\;\;mod\;(bx-1)\]
Add x to both sides:
\[n≢ x\;\;mod\;(bx-1)\]
Multiply both sides by the base:
\[bn≢ bx\;\;mod\;(bx-1)\]
Subtract 1 from both sides:
\[bn-1≢ bx-1\;\;mod\;(bx-1)\]
Since (bx-1) divides itself:
\[bn-1≢ 0\;\;mod\;(bx-1)\]
\[\therefore\;if\;(bx-1)∤(n-x)\;then\;(bx-1)∤(bn-1)\] - Proof for 3.1 C
Only factors less than or equal to the square root of (bn-1) need to be identified:
\[(bx-1)\leq \sqrt{bn-1}\]
Solving for x returns the x-limit of:
\[x\leq \frac{1+\sqrt{bn-1}}{b}\]
By definition x is a natural number:
\[\left\{x\inℕ\mid x\geq1\right\}\]
∴ The range for x is:
\[\left\{x\inℕ\mid 1\leq x\leq \frac{1+\sqrt{bn-1}}{b}\right\}\]
- Proof for 3.1 A
- Proof for 3.2
- Proof for 3.2 A
Let:
\[(bx+1)\mid(n+x)\]
Then:
\[(n+x)\equiv0\;\;mod\;(bx+1)\]
Subtract x from both sides:
\[n\equiv -x\;\;mod\;(bx+1)\]
Multiply both sides by the base:
\[bn\equiv -bx\;\;mod\;(bx+1)\]
Subtract 1 from both sides:
\[bn-1\equiv -bx-1\;\;mod\;(bx+1)\]
Simplify the right side:
\[bn-1\equiv -(bx+1)\;\;mod\;(bx+1)\]
Since (bx+1) divides itself:
\[bn-1\equiv 0\;\;mod\;(bx+1)\]
\[\therefore\;if\;(bx+1)\mid(n+x)\;then\;(bx+1)\mid(bn-1)\] - Proof for 3.2 B
Let:
\[(bx+1)∤(n+x)\]
Then:
\[(n+x)≢0\;\;mod\;(bx+1)\]
Subtract x from both sides:
\[n≢ -x\;\;mod\;(bx+1)\]
Multiply both sides by the base:
\[bn≢ -bx\;\;mod\;(bx+1)\]
Subtract 1 from both sides:
\[bn-1≢ -bx-1\;\;mod\;(bx+1)\]
Simplify the right side:
\[bn-1≢ -(bx+1)\;\;mod\;(bx+1)\]
Since (bx+1) divides itself:
\[bn-1≢ 0\;\;mod\;(bx+1)\]
\[\therefore\;if\;(bx+1)∤(n+x)\;then\;(bx+1)∤(bn-1)\] - Proof for 3.2 C
Only factors less than or equal to the square root of (bn-1) need to be identified:
\[(bx+1)\leq \sqrt{bn-1}\]
Solving for x returns the x-limit of:
\[x\leq \frac{-1+\sqrt{bn-1}}{b}\]
By definition x is a natural number:
\[\left\{x\inℕ\mid x\geq1\right\}\]
∴ The range for x is:
\[\left\{x\inℕ\mid 1\leq x\leq \frac{-1+\sqrt{bn-1}}{b}\right\}\]
- Proof for 3.2 A
- Proof for 3.3
- Proof for 3.3 A
Let:
\[(bx+1)\mid(n-x)\]
Then:
\[(n-x)\equiv0\;\;mod\;(bx+1)\]
Add x to both sides:
\[n\equiv x\;\;mod\;(bx+1)\]
Multiply both sides by the base:
\[bn\equiv bx\;\;mod\;(bx+1)\]
Add 1 to both sides:
\[bn+1\equiv bx+1\;\;mod\;(bx+1)\]
Since (bx+1) divides itself:
\[bn+1\equiv 0\;\;mod\;(bx+1)\]
\[\therefore\;if\;(bx+1)\mid(n-x)\;then\;(bx+1)\mid(bn+1)\] - Proof for 3.3 B
Let:
\[(bx+1)∤(n-x)\]
Then:
\[(n-x)≢0\;\;mod\;(bx+1)\]
Add x to both sides:
\[n≢ x\;\;mod\;(bx+1)\]
Multiply both sides by the base:
\[bn≢ bx\;\;mod\;(bx+1)\]
Add 1 to both sides:
\[bn+1≢ bx+1\;\;mod\;(bx+1)\]
Since (bx+1) divides itself:
\[bn+1≢ 0\;\;mod\;(bx+1)\]
\[\therefore\;if\;(bx+1)∤(n-x)\;then\;(bx+1)∤(bn+1)\] - Proof for 3.3 C
Only factors less than or equal to the square root of (bn+1) need to be identified:
\[(bx+1)\leq \sqrt{bn+1}\]
Solving for x returns the x-limit of:
\[x\leq \frac{-1+\sqrt{bn+1}}{b}\]
By definition x is a natural number:
\[\left\{x\inℕ\mid x\geq1\right\}\]
∴ The range for x is:
\[\left\{x\inℕ\mid 1\leq x\leq \frac{-1+\sqrt{bn+1}}{b}\right\}\]
- Proof for 3.3 A
- Proof for 3.4
- Proof for 3.4 A
Let:
\[(bx-1)\mid(n+x)\]
Then:
\[(n+x)\equiv0\;\;mod\;(bx-1)\]
Subtract x from both sides:
\[n\equiv -x\;\;mod\;(bx-1)\]
Multiply both sides by the base:
\[bn\equiv -bx\;\;mod\;(bx-1)\]
Add 1 to both sides:
\[bn+1\equiv -bx+1\;\;mod\;(bx-1)\]
Simplify the right side:
\[bn+1\equiv -(bx-1)\;\;mod\;(bx-1)\]
Since (bx+1) divides itself:
\[bn+1\equiv 0\;\;mod\;(bx-1)\]
\[\therefore\;if\;(bx-1)\mid(n+x)\;then\;(bx-1)\mid(bn+1)\] - Proof for 3.4 B
Let:
\[(bx-1)∤(n+x)\]
Then:
\[(n+x)≢0\;\;mod\;(bx-1)\]
Subtract x from both sides:
\[n≢ -x\;\;mod\;(bx-1)\]
Multiply both sides by the base:
\[bn≢ -bx\;\;mod\;(bx-1)\]
Add 1 to both sides:
\[bn+1≢ -bx+1\;\;mod\;(bx-1)\]
Simplify the right side:
\[bn+1≢ -(bx-1)\;\;mod\;(bx-1)\]
Since (bx-1) divides itself:
\[bn+1≢ 0\;\;mod\;(bx-1)\]
\[\therefore\;if\;(bx-1)∤(n+x)\;then\;(bx-1)∤(bn+1)\] - Proof for 3.4 C
Only factors less than or equal to the square root of (bn+1) need to be identified:
\[(bx-1)\leq \sqrt{bn+1}\]
Solving for x returns the x-limit of:
\[x\leq \frac{1+\sqrt{bn+1}}{b}\]
By definition x is a natural number:
\[\left\{x\inℕ\mid x\geq1\right\}\]
∴ The range for x is:
\[\left\{x\inℕ\mid 1\leq x\leq \frac{1+\sqrt{bn+1}}{b}\right\}\]
- Proof for 3.4 A
- Proof for 3.1
- Example: b=3
In the table below, the base b=3 is examined. The left section shows n and N=3n. The middle section shows k1, the x-limit, the factor candidates below n: MOD(n-x, 3x-1), and the factor candidates above n: MOD(n+x, 3x+1). The right section shows k2, the x-limit, the factor candidates below n: MOD(n-x, 3x+1), and the factor candidates above n: MOD(n+x, 3x-1). At the top are the headers for x, n+/-x, and the factor candidates 3x+/-1. If 3x+/-1 is a factor for k1 or k2, it’s remainder is listed as a red zero with pink background. If k1 or k2 has any factors (of form 3x+/-1), it is highlighted yellow. If k1 or k2 has no factors (of form 3x+/-1), then it is not highlighted. Since all primes (except 3) are contained in (3x+/-1), k1 and k2 are prime when they are not highlighted.
- Example: b=4
In the table below, the base b=4 is examined. The composite k1 and k2 integers are highlighted yellow, and the factors (of form 4x+/-1) are highlighted pink. If k1 or k2 has no factors (of form 4x+/-1), then it is not highlighted. Since all primes > 2 are contained in (4x+/-1), k1 and k2 are prime when they are not highlighted.
- Example: b=5
In the table below, the base b=5 is examined. The composite k1 and k2 integers are highlighted yellow, and the factors (of form 5x+/-1) are highlighted pink. If k1 or k2 has no factors (of form 5x+/-1), then it is not highlighted. Unlike b=3, b=4, and b=6, not all primes are contained in (bx+/-1) for b=5; notice in the range specified that 7 and 13 are missing. Therefore, it is indeterminate whether k1 and k2 are prime when they are not highlighted.
- Example: b=6
In the table below, the base b=6 is examined. The composite k1 and k2 integers are highlighted yellow, and the factors (of form 6x+/-1) are highlighted pink. If k1 or k2 has no factors (of form 6x+/-1), then it is not highlighted. Since all primes > 3 are contained in (6x+/-1), k1 and k2 are prime when they are not highlighted.
- Special Case: b = 6
As in the previous example, when the base is 6, then the integers k1 and k2 define the set of all primes (greater than 3) and all composite numbers (not having 2 or 3 as factors). This is a special case because it is the largest base that encompasses all prime factors (greater than 3).
Let:
\
Then:
\[N=bn=6n\]
The integers immediately before/after N are:
\[k_{1}=N-1=6n-1\;\;where\;\;k_{1}=-1\;\;(mod\;6)\]
\[k_{2}=N+1=6n+1\;\;where\;\;k_{2}=1\;\;(mod\;6)\]
The (6x+/-1) factors for k1=6n-1 may be identified by the following expressions. If k1 has factors between x=1 and the x-limit, then k1 is composite and the lower factors (less than or equal to the square root of k1) are identified. If k1 has no factors, then k1 is prime.
The (6x+/-1) factors for k2=6n+1 may be identified by the following expressions. If k2 has factors between x=1 and the x-limit, then k2 is composite and the lower factors (less than or equal to the square root of k2) are identified. If k2 has no factors, then k2 is prime.
- Other resources
Please visit the "Prime Factors in Base" Google Doc to see factors for different bases:
https://docs.google.com/spreadsheets/d/ ... =683221398