The article lists three reasons why 21 is so much harder than 15. Mostly that with 15 most of the required conditional multiplications are multiplications by 1 and the remaining multiplication can be done with cheap shifts because it's a multiplication by a power of 2 modulo 15 (which is one less than a power of two).

But 22 and 24 are in the same boat as 21 here. All three of them require computing only factors that are not one, all three are not one less than a factor of 2. You need slightly more multiplications (and thus more gates) as the numbers get larger, but that only grows linearly. Maybe the conditional multiplications required get slightly more expensive to implement, but I wouldn't expect a 100x cost blowup from that. Error correction is still an issue, potentially making a linear complexity increase quadratic, but qubit counts in quantum computers also increase at an exponential rate

▲

oh_my_goodness 6 days ago | parent | next [-]

24 has 3 as a factor. 3 is one less than a power of 2.

▲

freehorse 6 days ago | parent | next [-]

Well n=21 too but the solution for n=15 used that 15 is one less than a power of 2, not its divisors, because we are living in modulo n.

	▲	oh_my_goodness 6 days ago \| parent [-]
		Thanks. I don't understand quantum computing at all.

▲

Dylan16807 6 days ago | parent | prev [-]

That's a bit off, but more importantly using information about the answer to make the circuit cheaper is cheating.

▲

oh_my_goodness 6 days ago | parent | prev [-]

23 and 29 are prime.

	▲	wongarsu 6 days ago \| parent [-]
		That's what I get for not enough coffee. Same holds for 22 and 24 though