These are known as left-truncatable primes
There are $4260$ such primes when no digit is zero (numbers are not usually written with leading zeros) and they are listed by P. De Geest. The largest is $357686312646216567629137$
If you allow zeros then the list is apparently infinite and you can find the small values at OEIS A033664 which also provides some code for finding more (essentially you find some small cases and then try to prepend another digit or another digit and some zeros)
In general, the residues number system (RNS) does not work with the negative numbers at all.
On the other hand, if the modulus $\;M=m_1\times m_2\times\dots\times m_k\;$ of the certain RNS is even, $\;M=2H,\;$ and $\;H\;$ is odd, and the sign of an arbitrary integer number is defined as
$$\text{sgn }^\,_M(n)=\begin{cases}
-1,\; \text{ if } \;(n\mod M) \not= (n\mod \frac M2)\\
0,\quad \text{ if } \;(n\mod M) = 0\\
1,\quad \text{ otherwize }.
\end{cases}$$
then the simple direct algorithm can be built.
Really, let
$$\;n=\overline{n_1n_2\dots n_k}^\,_{(2\times m_2\times\dots\times m_k)},\;$$
then
$$\;n\mod\frac M2=\overline{n_2\dots n_k}^\,_{(m_2\times\dots\times m_k)}
= \overline{b_1n_2\dots n_k}^\,_{(2\times m_2\times\dots\times m_k)},\;$$
where
$$b_1 = \overline{n_2\dots n_k}^\,_{(m_2\times\dots\times m_k)} \mod2
= \left(\sum_{j=2}^k (n_j\mod2) p_j\right) \mod2,\tag1$$
and $\;p_j\;$ are the predefined bit constants in the form of
$$p_j =\overline{\delta_{2,j},\delta_{3,j},\dots \delta_{k,j}}^\,_{(m_2\times\dots\times m_k)}\mod2.\tag2$$
If the last bits of $\;n_2,n_3,\dots,n_k\;$ presented as the least bits of the int64
number B
and the bits $\;p_j\;$ are similarly collected in the int64
mask P
,
then multiplication can be calculated in the form v= B & P
, summation of bits as the C
-code in the form of
v = v - ((v >> 1) & 0x5555555555555555); // sums in pairs of bits, g+l=(2g+l)-g
v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333); // sums in tetrades
c = (((v + (v >> 4)) & 0x0F0F0F0F0F0F0F0F) * 0x101010101010101) >> 56; // total sum
and the bit $b_1$ is the least signed bit of the number c
.
Therefore:
- if $b_1\not=n_1,$ then $n$ is negative, so on;
- the expression $\;\text{ sgn }_M(a-b)\;$ defines the comparation results.
Best Answer
Dirichlet's theorem on primes in arithmetic progression tells us that the proportion of primes will be the same, for values of $i$ that are coprime to $n$ (and 0 otherwise).
However, Chebyshev's bias tells us that numerically there are more primes with a quadratic non-residue, than a residue, when you're counting primes up to $N$.