@GerryMyerson Indeed, almost all appear. These are the exceptions I've found, written as $f(a, n)$: $f(2, 2) = \{3\}$, $f(2, 3) = \{5, 7\}$, $f(2, 4) = \{11, 13\}$, $f(2, 5) = \{19, 29\}$. They're primes, which makes sense that some should appear. But for higher $a$ or $n$, it seems to always come up with every possible $r$.

Right, yes. I think I was thinking whether every consistent extension of the theory minus quantifiers is undecidable. I'll try to repair the question.

Right, it also holds for PA, even restricted to induction over $\Sigma_1$ formulas. So I take it that we can usually find strange models of $Q$ where things hold that shouldn't.

Ah, of course. I forgot the negative integers!