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 k_{1} and k_{2}. 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 k_{1}=bn-1 may be identified:
The (bx+/-1) factor candidates for k_{2}=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 k_{1}, 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 k_{2}, 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 k_{1} or k_{2}, it’s remainder is listed as a red zero with pink background. If k_{1} or k_{2} has any factors (of form 3x+/-1), it is highlighted yellow. If k_{1} or k_{2} has no factors (of form 3x+/-1), then it is not highlighted. Since all primes (except 3) are contained in (3x+/-1), k_{1} and k_{2} are prime when they are not highlighted.
- Example: b=4
In the table below, the base b=4 is examined. The composite k_{1} and k_{2} integers are highlighted yellow, and the factors (of form 4x+/-1) are highlighted pink. If k_{1} or k_{2} has no factors (of form 4x+/-1), then it is not highlighted. Since all primes > 2 are contained in (4x+/-1), k_{1} and k_{2} are prime when they are not highlighted.
- Example: b=5
In the table below, the base b=5 is examined. The composite k_{1} and k_{2} integers are highlighted yellow, and the factors (of form 5x+/-1) are highlighted pink. If k_{1} or k_{2} 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 k_{1} and k_{2} are prime when they are not highlighted.
- Example: b=6
In the table below, the base b=6 is examined. The composite k_{1} and k_{2} integers are highlighted yellow, and the factors (of form 6x+/-1) are highlighted pink. If k_{1} or k_{2} has no factors (of form 6x+/-1), then it is not highlighted. Since all primes > 3 are contained in (6x+/-1), k_{1} and k_{2} are prime when they are not highlighted.
- Special Case: b = 6
As in the previous example, when the base is 6, then the integers k_{1} and k_{2} 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 k_{1}=6n-1 may be identified by the following expressions. If k_{1} has factors between x=1 and the x-limit, then k_{1} is composite and the lower factors (less than or equal to the square root of k_{1}) are identified. If k_{1} has no factors, then k_{1} is prime.
The (6x+/-1) factors for k_{2}=6n+1 may be identified by the following expressions. If k_{2} has factors between x=1 and the x-limit, then k_{2} is composite and the lower factors (less than or equal to the square root of k_{2}) are identified. If k_{2} has no factors, then k_{2} 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