2-3-5-7 wheel factorization seems to skip prime number 331

Question

When following the procedure on wikipedia for wheel factorization, I seem to have stumbled into a problem where the prime number 331 is treated as a composite number if I try to build a 2-3-5-7 wheel.

With 2-3-5-7 wheel, 2*3*5*7=210. So I setup a circle with 210 slots and go through steps 1-7 without any issues. Then I get to step 8 and strike off the spokes of all multiples of prime numbers, I eventually strike off the spoke rooted at 121, which is a multiple of 11, which is a prime. For the spoke rooted at 121, 121 + 210 = 331. Unfortunately, 331 is a prime number.

Is the procedure on Wikipedia incorrect?

Or did I misunderstand the procedure, and should have only struck out spokes that are multiples of 2, 3, 5, and 7, but not any of the other primes less than 210?

Sapiential

Might get better responses at math.stackexchange.com – Felicafelicdad

you absolutely need to show us your implementation. – Kieger

No code yet, I was just doing this on paper to get a feel for how a bigger wheel maybe implemented. – Sapiential

I would have asked the question on math.stackexchange.com, but the FAQ there said that algorithm related questions should be asked on stackoverflow.com, and this definitely felt like an algorithm type question since it's an algorithm described in Wikipedia. – Sapiential

Why the votes to close? Because this should be asked on math.stackexchange.com despite the FAQ there saying otherwise? – Sapiential

You are not supposed to strike multiples of 11 at step 8, that step applies only to the prime numbers chosen for your wheel. – Danieu

Great question, underappreciated in its time. I came here over a decade later when trying to search for examples of a correct 2x3x5x7 (210) wheel. – Jacks

Answer 1

Wikipedia is correct.

331 is in the 1 spoke of the wheel. The spoke is not shaded, so 331 is potentially prime. And in fact, it is prime.

121 is also in the 1 spoke of the wheel, so 121 is potentially prime. That is, it is not eliminated as a prime by the wheel. However, it is not prime.

The wheel doesn't allow you to make any inference about the primality of 331 based on the non-primality of 121. Sorry.

I have an implementation of wheel factorization at my blog, if you want to look at it.

Derisible

In my 2-3-5-7 wheel, I see 121 and 331 to be on the same spoke, but 121 is in ring 0, while 331 is in ring 1. Anyway, I do see your point that I should only strike off multiples of 2, 3, 5, and 7. I was just beguiled by the 2-3 and 2-3-5 wheels illustrated where ring 0 in those wheels contained all primes. – Sapiential

-1. 121 can't be in the 1 spoke on a 210 spoke wheel (2x3x5x7 = 210). Seems like this answer didn't read the question carefully and was answering about the 30 spoke wheel (2x3x5, without the x7). Unfortunately, the asker seemed to be unconfident/uncertain/confused/trusting enough to creatively interpret this answer as applying to their question. (Not being allowed to strike out 121 might apply to the 210 wheel, and maybe the asker correctly understood the actual reason for it, but this answer seems to give a wrong reason - one which only applies in the 30 wheel.) – Jacks

Answer 2

Yes, you are only allowed to strike off the spokes that are multiples of 2, 3, 5 and 7. In fact, 121 which is a multiple of 11, is relatively prime to 210. So the numbers on the 121 spoke can be either prime or composite.

Lucylud

+1 It might be worth drawing attention to the fact that the 210 wheel is the smallest example wheel where this rule becomes distinguishable. In the 6 and 30 wheels, you don't have primes which you both cannot strike out (because they are not one of the wheel's factors) and whose multiples occur in the first ring around the wheel on spokes that you don't strike out. 2x3 wheel: you strike out 4 and 6 spokes, and 5x5 is >6. 2x3x5 wheel: you strike out 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 28, and 30 spokes, and 7x7 > 30. It is only in the 2x3x5x7 wheel that the 11x11 <= 210. – Jacks

Good answer, underappreciated in its time. – Jacks