Predict Primes with the Sixth Sense Sieve

Primes, divisors, arithmetic, number properties, ...
Post Reply
Slivey
Posts: 1
Joined: Mon Apr 21, 2014 10:56 pm

Predict Primes with the Sixth Sense Sieve

Post by Slivey » Mon Apr 21, 2014 11:12 pm

I am an amateur mathematician with an interest in Prime Numbers and Number Theory. While investigating primes, I discovered an interesting pattern. I am interested to know if this "discovery" is already known/proven. Unfortunately, I do not know any Number Theory experts with whom to review these ideas. I welcome your comments/discussion.

Title: Sixth Sense Sieve
by Jeff Huth

  1. 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.”
  2. 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.

    1. 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).
      Image
    2. 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).
      Image
  3. 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:

    Image

    The (bx+/-1) factor candidates for k2=bn+1 may be identified:

    Image
  4. Proof
    1. 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\}\]
    2. 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\}\]
    3. 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\}\]
    4. 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\}\]
  5. 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.

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

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

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

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

    Image


    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.

    Image
  10. Other resources
    Please visit the "Prime Factors in Base" Google Doc to see factors for different bases:
    https://docs.google.com/spreadsheets/d/ ... =683221398
Last edited by Slivey on Mon Sep 18, 2017 6:17 pm, edited 1 time in total.

User avatar
ggoyo
Posts: 25
Joined: Sun Jun 22, 2014 9:45 am
Location: Paris
Contact:

Re: Predict Primes with the Sixth Sense Sieve

Post by ggoyo » Mon Jun 23, 2014 1:23 pm

A wise man said that mathematics is about making hard problems look easy, not the other way around.
Image

Amish.naidu
Posts: 1
Joined: Wed Jul 23, 2014 4:24 am

Re: Predict Primes with the Sixth Sense Sieve

Post by Amish.naidu » Wed Jul 23, 2014 4:38 am

First , I should to tell you about the Prime Pages.

To quote http://primes.utm.edu/notes/faq/six.html :
Perhaps the most rediscovered result about primes numbers is the following:

I found that every prime number over 3 lies next to a number divisible by six. Using Matlab with the help of a friend, we wrote a program to test this theory and found that at least within the first 1,000,000 primes this holds true.
Checking a million primes is certainly energetic, but it is not necessary (and just looking at examples can be misleading in mathematics). Here is how to prove your observation: take any integer n greater than 3, and divide it by 6. That is, write

n = 6q + r
where q is a non-negative integer and the remainder r is one of 0, 1, 2, 3, 4, or 5.

If the remainder is 0, 2 or 4, then the number n is divisible by 2, and can not be prime.
If the remainder is 3, then the number n is divisible by 3, and can not be prime.
So if n is prime, then the remainder r is either

1 (and n = 6q + 1 is one more than a multiple of six), or
5 (and n = 6q + 5 = 6(q+1) - 1 is one less than a multiple of six).
Remember that being one more or less than a multiple of six does not make a number prime. We have only shown that all primes other than 2 and 3 (which divide 6) have this form.

jzakiya
Posts: 2
Joined: Sat Jan 09, 2016 12:15 am

Re: Predict Primes with the Sixth Sense Sieve

Post by jzakiya » Sat Jan 16, 2016 5:34 pm

For a thorough discussion on this see:

PRIMES-UTILS HANDBOOK: The Math and Code behind making the Rubgem

https://www.scribd.com/doc/266461408/Pr ... s-Handbook

Post Reply