0
$\begingroup$

Given a set of base primes and a point $m$ is there a way to use wheel factorization to find numbers greater than $m$ that are coprime to the members of the set?

For example given $\{2, 3\}$ and $m=20$ can wheel factorization be used to find the next integer that is not divisible by $2$ or $3$? It's trivial for $2$ because it would be the next odd number ($21$ in this case) but $3|21$.

Another way to phrase this question is how do you start rolling the wheel at an arbitrary point? Is it possible?

$\endgroup$
1
  • $\begingroup$ ``` int next_wheel_six(int n) { if (n < 2) return 2; if (n < 3) return 3; static int bump[6] = { 1, 4, 3, 2, 1, 2 }; return n + bump[n % 6]; } ``` Calling next_wheel_six(20) will return the next number that is co-prime to 2 and 3 and greater than 20. Similar lists could be made for wheel-of-30 using basis primes { 2, 3, 5 } or other wheels. $\endgroup$ Commented Jul 11, 2020 at 19:50

2 Answers 2

2
$\begingroup$

Trying to modify wheel factorization to turn "numbers $>m$ not divisible by $p_1$" into "numbers $>m$ not divisible by $p_1$ or $p_2$" into "numbers $>m$ not divisible by $p_1$, $p_2$, or $p_3$" sounds like a headache.

It is much easier to find the list starting at $1$, then translate.

Take for instance the primes $\{3,5\}$ and $m=100$. We'd start with $S = \{1,2\} \subseteq \{1,2,3\}$ for the prime $3$, and unroll that into $S = \{1,2, 4, 7,8, 11, 13,14\} \subseteq \{1, 2, \dots, 15\}$ for the primes $\{3,5\}$ in the usual wheel factorization way.

To shift that over to find the next number after $m=100$ not divisible by $3$ or $5$, we:

  1. First find the period $15$ (this is the product of all our primes; it is also $1$ more than the largest element of $S$).
  2. Translate $S$ by $15 \cdot \lfloor \frac{100}{15}\rfloor = 90$ to get $\{91,92, 94, 97,98, 101, 103,104\}$.
  3. Find the first element of this set larger or equal to $100$ (e.g. by binary search), getting $101$.

These few steps are negligible effort compared to obtaining the set $S$ to begin with.

$\endgroup$
0
0
$\begingroup$

Yes. Strick out all even numbers > 20 and
all numbers > 20 that are divisible by three.
The result is 23, 25, 29, 31, 35, 37, 41,...
a list numbers coprime to 2 and 3 greater than 20.

$\endgroup$
2
  • $\begingroup$ I think if you do the inner most wheel, then you can skip all wheels until the one you need, since you know where the spokes are. e.g. computer the inner wheel up to 6, then skip the next 3 wheels because they're 20 or under. $\endgroup$
    – northerner
    Commented Jan 23, 2020 at 11:24
  • $\begingroup$ Yes, I just showed you. If you do not like division and do not see a pattern, then find the smallest even number > 20 adding 2 for each next one. Similar with three. $\endgroup$ Commented Jan 23, 2020 at 12:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .