1

I am currently creating a program to exhaustively search for prime numbers. I head from sombody that this rule can be extended by multipliting 6 by the next prime number, giving 30, and then continuing this sequence 210.

The offsets from this value would be the prime numbers less than it, apart from the ones multiplied together to make this value, and also 1.

This works for 30, meaning the values you will need to check would be $30n+1$, $30n+7$, $30n+11$, $30n+13$, $30n+17$, $30n+19$, $30n+23$ and $30n+29$

However, there is something that is missing for the larger values, the person that I learnt rule from said that there was a way to make it work for $210n$ and upwards, however they forgot how.

With a base value of 210 you need to check 1, and all the prime numbers lower than 210, not including the prime factors of 210, as above. However you also need to check $210n+121$, $210n+143$, $210n+169$, $210n+187$ and $210n+209$.

Any help in figuring out what the rules for the other values to be checked are for values larger than $210n$ would be greatly appreciated, since I need to automatically work these out for huge values of $n$.

finlay morrison
  • 303
  • 1
  • 7

1 Answers1

2

Let's construct the period $30$ sequence in a more instructive way, starting from the period $6$ sequence.

The period $6$ one consists of $6n+1$ and $6n+5$ (the latter is equivalent to $6n-1$, but it is easier to use only positive offsets). This sequence avoids all multiples of $2$ and all multiples of $3$, and note that $6=2\cdot3$.

The next prime we would like to avoid multiples of is $5$. So take five successive periods of the $6$-sequence: $$1, 5\\7, 11\\13, 17\\19, 23\\25, 29$$ Each column has one multiple of $5$ in it, in this case $5$ and $25$. After removing those, you are left with the period $30$ sequence $30n+k$ where $k\in\{1,7,11,13,17,19,23,29\}$. This sequence avoids all multiples of $2$, $3$, and $5$.

To extend this with the next prime, $7$, you can do the same thing. Take $7$ successive periods of this sequence, get rid of the multiples of $7$, to give you the sequence of period $210$ that avoids all multiples of $2, 3, 5$, and $7$.

$$1,7,11,13,17,19,23,29\\ 31,37,41,43,47,49,53,59\\ 61,67,71,73,77,79,83,89\\ 91,97,101,103,107,109,113,119\\ 121,127,131,133,137,139,143,149\\ 151,157,161,163,167,169,173,179\\ 181,187,191,193,197,199,203,209$$

Again, each column has exactly one multiple of $7$ in it ($7$, $49$, $77$, $91$, $119$, $133$, $161$, $203$). Eliminate those, and the remaining $49$ numbers form your period $210$ sequence. Note that these are not all prime numbers, but also include products of larger primes that happen to be below $210$ such as $11^2=121$ and $11\cdot 19=209$.

This method soon becomes unwieldy, since for each extra prime $p$ you want to avoid, the period is multiplied by $p$, and the number of cases to check within that period is multiplied by $p-1$.

In effect, you are generating the result of a few rounds of the Sieve of Eratosthenes, but generally you are better off using the sieve fully.

Jaap Scherphuis
  • 13,660