Return to Answer

If you insist on prime moduli you will need infinitely many classes. If you don't insist on prime moduli then you can get away with finitely many, these are called covering systems and the linked article looks good.

Let $(r,m)=\lbrace r+mj \mid j \ge 0 \rbrace$ and $p_1<p_2<p_3<\cdots$ be a list of some or all the primes. You want a list $(r_1,p_1),(r_2,p_2),\cdots$ whose union is the natural numbers (optinally with some natural numbers allowed to be missed). One method to do this is to greedily define $r_i$ to be the smallest integer not in $\cup_{j<i}(r_j,p_j)$. Is this (almost) optimal? I don't know but I will wildly guess that it is and from now on only discuss the greedy choice. If we use all the primes and try to get all the natural numbers starting with 2 then (making the greedy choice) $r_j=p_j$. This becomes $r_j=p_j-1$ (or $r_j=p_j-2$) if we also want to get 1 ( or 0 and 1). In any case the greedy algorithm gives $\frac{r_i}{p_i} \approx 1$

If we use all the primes except $2$ and try to get all the natural numbers except powers of $2$ (and 0) then again $r_i=p_i$. If we try to get all the natural numbers then it would appear that $\frac{r_i}{p_i} \approx \frac{1}{2}$.

Based on this I will say that there is little hope that you can exclude the primes 2,3,5 (or even just 2) and keep $p_i-r_i<100$. I suspect that for each prime $q$ there is a constant $C_q$ so that using the greedy choice to cover all the natural numbers using primes $q$ and greater results in $\frac{r_i}{p_i} \approx C_q$. It looks as if perhaps $C_7$ is something like 0.43.

If you insist on prime moduli you will need infinitely many classes. If you don't insist on prime moduli then you can get away with finitely many, these are called covering systems and the linked article looks good.

Let $(r,m)=\lbrace r+mj \mid j \ge 0 \rbrace$ and $p_1<p_2<p_3<\cdots$ be a list of some or all the primes. You want a list $(r_1,p_1),(r_2,p_2),\cdots$ whose union is the natural numbers (optinally with some natural numbers allowed to be missed). One method to do this is to greedily define $r_i$ to be the smallest integer not in $\cup_{j<i}(r_j,p_j)$. Is this (almost) optimal? I don't know but I will wildly guess that it is and from now on only discuss the greedy choice. If we use all the primes and try to get all the natural numbers starting with 2 then (making the greedy choice) $r_j=p_j$. This becomes $r_j=p_j-1$ (or $r_j=p_j-2$) if we also want to get 1 ( or 0 and 1). In any case the greedy algorithm gives $\frac{r_i}{p_i} \approx 1$ (Well in the very first we could as well have $r_i=0$)

If we use all the primes except $2$ and try to get all the natural numbers except powers of $2$ (and 0) then again $r_i=p_i$. If we try to get all the natural numbers then it would appear that $\frac{r_i}{p_i} \approx \frac{1}{2}$.

Based on this I will say that there is little hope that you can exclude the primes 2,3,5 (or even just 2) and keep $p_i-r_i<100$. I suspect that for each prime $q$ there is a constant $C_q$ so that using the greedy choice to cover all the natural numbers using primes $q$ and greater results in $\frac{r_i}{p_i} \approx C_q$. It looks as if perhaps $C_7$ is something like 0.43.

If you insist on prime moduli you will need infinitely many classes. If you don't insist on prime moduli then you can get away with finitely many, these are called covering systems and the linked article looks good.

As you point out, you can use any set of primes, say primes of the form $10^k+3$ (If there are infinitely many, maybe safer to use $10+1, 10^2+1, 10^3+9, 10^4+7, 10^5+3, 10^6+3, 10^7+19, 10^8+7 \cdots$ smallest primes with each number of digits). So a better question might be: if you use all the primes, how sparse a set of residues can you use? Of course this should require each residue to be positive and less then the appropriate prime. the greedy algorithm uses $p-2 \mod p .$ Since the sum of the reciprocals of the primes diverges, maybe one can do better, but maybe not.

If you insist on prime moduli you will need infinitely many classes. If you don't insist on prime moduli then you can get away with finitely many, these are called covering systems and the linked article looks good.

Let $(r,m)=\lbrace r+mj \mid j \ge 0 \rbrace$ and $p_1<p_2<p_3<\cdots$ be a list of some or all the primes. You want a list $(r_1,p_1),(r_2,p_2),\cdots$ whose union is the natural numbers (optinally with some natural numbers allowed to be missed). One method to do this is to greedily define $r_i$ to be the smallest integer not in $\cup_{j<i}(r_j,p_j)$. Is this (almost) optimal? I don't know but I will wildly guess that it is and from now on only discuss the greedy choice. If we use all the primes and try to get all the natural numbers starting with 2 then (making the greedy choice) $r_j=p_j$. This becomes $r_j=p_j-1$ (or $r_j=p_j-2$) if we also want to get 1 ( or 0 and 1). In any case the greedy algorithm gives $\frac{r_i}{p_i} \approx 1$

If we use all the primes except $2$ and try to get all the natural numbers except powers of $2$ (and 0) then again $r_i=p_i$. If we try to get all the natural numbers then it would appear that $\frac{r_i}{p_i} \approx \frac{1}{2}$.

Based on this I will say that there is little hope that you can exclude the primes 2,3,5 (or even just 2) and keep $p_i-r_i<100$. I suspect that for each prime $q$ there is a constant $C_q$ so that using the greedy choice to cover all the natural numbers using primes $q$ and greater results in $\frac{r_i}{p_i} \approx C_q$. It looks as if perhaps $C_7$ is something like 0.43.

If you insist on prime moduli you will need infinitely many classes. If you don't insist on prime moduli then you can get away with finitely many, these are called covering systems and the linked article looks good.

As you point out, you can use any set of primes, say primes of the form $10^k+3$ (If there are infinitely many, maybe safer to use $10+1, 10^2+1, 10^3+9, 10^4+7, 10^5+3, 10^6+3, 10^7+19, 10^8+7 \cdots$ smallest primes with each number of digits). So a better question might be: if you use all the primes, how sparse a set of residues can you use?

If you insist on prime moduli you will need infinitely many classes. If you don't insist on prime moduli then you can get away with finitely many, these are called covering systems and the linked article looks good.

As you point out, you can use any set of primes, say primes of the form $10^k+3$ (If there are infinitely many, maybe safer to use $10+1, 10^2+1, 10^3+9, 10^4+7, 10^5+3, 10^6+3, 10^7+19, 10^8+7 \cdots$ smallest primes with each number of digits). So a better question might be: if you use all the primes, how sparse a set of residues can you use? Of course this should require each residue to be positive and less then the appropriate prime. the greedy algorithm uses $p-2 \mod p .$ Since the sum of the reciprocals of the primes diverges, maybe one can do better, but maybe not.