1
$\begingroup$

I made this post as a follow up to New Prime Sieve Algorithm Omitting 2 and 5 Is it flawed? In this post my question is whether anyone can help me with declaring the dependency of rule 3 on rule 2.

In this section, we will work out the improved version of the Basic Algorithm integrating the observations that we have made. The basic components will be:

  1. the formula $f(n)=3+10n$.

  2. Instead of P we define 4 lists: L1 for prime numbers $\equiv 1\ mod\ 10$, L3 for prime numbers $\equiv 3\ mod\ 10$, L7 for prime numbers $\equiv 7\ mod\ 10$ and L9 for prime numbers $\equiv 9\ mod\ 10$. These define the columns of the prime numbers. The rows will be defined by: $\left\lfloor*{\frac{Prime}{10}}\right\rfloor$. This means that there will be null values in the lists.

    1. A queue which can have one of these four values for each n: a. divide by 3, b. divide by 7, c. skip (simply increment n by 1), d. add $f(n)$ as a prime number. The queue will basically fill up to filter which Prime numbers we are going to use for each $n$ to divide $f(n)$.

    2. We will also need to assign prime numbers a value for $n_1$ as we have defined it under Observation A. (p. 8) We could then also define a function p(a): f(n) is divisible by Prime for: $n_1+ a\times Prime$ where $a$ is a counter that increments by 1 up to the point where $p(a) \not> n max$. By doing that you have found all numbers $ \equiv 3\ mod\ 10\ $ which are divisible by that Prime. An example of this: set n max to 50. Let this Prime be 11. We find $n_1$=3. Then:$p(a)= 3+a*11$ all values of p(a) will be migrated to the queue to change the value for the action of n. Furthermore the limit for $p(a) = 50$. An illustration: $p(1)=3+1\times 11 = 14$ this means that at f(14) 11 is a divisor. Since the value of of $f(14)=143=13\times 11$, we see that this is true, the same would hold for $f(25)=253=23 \times 11$ , $f(36)= 363 = 33 \times 11$ and $f(47)=473= 43\times 11$.

    Rule 1:

    1. Generate values for $f(n)= 3 + 10n$ from $n = 1$ up to $nmax$

    2. Create a 2 dimensional queue of $n=0$ up to $nmax$ with 4 possible values for each n:

      Value 1. divide by 3

      Value 2. divide by 7

      Value 3. "skip"

      Value 4. "do it" add f(n) to: L3 and row $\left\lfloor*{\frac{Prime}{10}}\right\rfloor$ and $n = n_1$, this is the default value for each $n$ in the waiting list.

      Each element of the queue would look like (1,"do it"), (2,"do it"), (3,"divide by 3")...

    3. Create lists L1, L3, L7 and L9 where each element has 3 values.

      Value 1. $\left\lfloor*{\frac{Prime}{10}}\right\rfloor$ for row

      Value 2. "P" for the prime number itself

      Value 3. Assign each non-null element a value for $n_1$ .

      Classification under L1 occurs when P $\equiv 1\mod\ 10$.

      Classification under L3 occurs when P $\equiv 3\mod\ 10$.

      Classification under L7 occurs when P $\equiv 7\mod\ 10$.

      Classification under L9 occurs when P $\equiv 9\mod\ 10$.

    4. For each element of L1, L3, L7 and L9 when "introduced" into the list apply the following rule.

    Rule 2:

    Make a function $W(a) = n_1 + a \times P$. Where: $W(a) \not> n max$. This is done by: $a=1$ to $a\max = \left\lfloor {\frac{nmax}{Prime}}\right\rfloor$ There can be 3 values
    Value 1. If P $\neq $ 3 $\lor $ 7 set all values for $W(a) = n$ in queue to "skip".

Value 2. If P = 3 set all values for $W(a) = n$ in queue to "divide by 3".

Value 3. If P = 7 set all values for $W(a) = n$ in queue to "divide by 7".

Value 4. If value in queue already has value 2 and it also gets a value 3 set value to "skip".

Rule 3:

Execute "search for primes". This part can have 4 values.

Value 1. If value of element $n$ in queue = "do it" add f(n) to: L3 and row $\left\lfloor{\frac{Prime}{10}}\right\rfloor$ and $n = n_1$ and increment n by 1.

Value 2. If value of element $n$ in queue = "skip" increment n by 1.\

Value 3. If value of element $n$ in queue = "divide by 3" then: $f(n) \div 3$ = answer. Set answer as: $f'(n)$.

Check if $f'(n)$ is divisible by 3.

Result 1. If it is not divisible by 3 then add $f'(n)$ to L1 in row $\left\lfloor{\frac{Prime}{10}}\right\rfloor$ with $n_1 = n$. Then execute Rule 2 with $W(a) = n_1 + a \times Prime$ from $a=1$ to $\left\lfloor{\frac{nmax}{Prime}}\right\rfloor$.

Result 2. If it is divisible by 3 then set answer as $f"(n)$.

Check if $f"(n)$ is divisible by 3.

Result 3. If $f"(n)$ is divisible by 3, increment n by 1.

Result 4. If $f"(n)$ is not divisible by 3, $f'(n)$ to L7 in row $\left\lfloor{\frac{Prime}{10}}\right\rfloor$ with $n_1 = n$. Then execute Rule 2 with $W(a) = n_1 + a \times Prime$ from $a=1$ to $\left\lfloor{\frac{nmax}{Prime}}\right\rfloor$.

Value 4. If value of element $n$ in "waiting list" = "divide by 7" then: $f(n) \div 7$ = answer. Set answer as: $f'(n)$.

Check if $f'(n)$ is divisible by 7.

Result 1: if $f'(n)$ divisible by 7, increment n by 1.

Result 2: if $f'(n)$ is not divisible by 7, $f'(n)$ to L9 in row $\left\lfloor{\frac{Prime}{10}}\right\rfloor$ with $n_1 = n$. Apply rule 2 with this element as Prime.

My question is how to define the dependance of rule 3 on rule 2.

$\endgroup$
  • 1
    $\begingroup$ Any help in getting the formula which directly follows \floor, in an actual floor notation would be much appreciated since I don't know how to do that in SE. $\endgroup$ – St.Clair Bij Aug 9 '17 at 15:34
  • 1
    $\begingroup$ Also any help in general with getting a latex text into SE properly would help. $\endgroup$ – St.Clair Bij Aug 9 '17 at 15:45
  • 1
    $\begingroup$ wrap \left\lfloor \frac{\text{prime}}{x}\right\rfloor with one dollar sign before and after $\left\lfloor \frac{\text{prime}}{x}\right\rfloor$ $\endgroup$ – Mats Granvik Aug 9 '17 at 15:56
  • 1
    $\begingroup$ i.stack.imgur.com/ne2LD.jpg This is the entire paper just in case you are interested in the idea. $\endgroup$ – St.Clair Bij Aug 10 '17 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.