Deleting any digit yields a prime... is there a name for this?
My son likes his grilled cheese sandwich cut into various numbers, the number depends on his mood. His mother won't indulge his requests, but I often will. Here is the day he wanted 100:
But today he wanted the prime 719, which I obliged. When deciding which digit to eat first, he went through the choices, trying to make a composite with the digits left behind. But he quickly realized that eating any digit would leave a prime: 71, 79, 19 are all prime. Pleased with his discovery of this prime 719, he tried to find a larger one, but couldn't.
My questions:
- Do these primes have a name?
- Can you think of any more of them (clearly 23 is the smallest)?
- Are there an infinite number of them?
- Is there likely to be a way to find them short of using a computer?
Solution 1:
Thanks to everyone for the interesting answers. Here's an improved heuristic that makes use of various parts of them -- the basic approach from Matthew, Fixee's observation of the repeated digits, and Numth' observations about restrictions on the digits. It's still a bit off, but I think it may be further improved taking into account Numth' observation 2; I've only taken into account observation 1 (mod $2$ and $5$) so far; I think the mod $3$ part will need to be a bit more subtle; more on that later.
Consider numbers with $m$ digits consisting of $k$ strings of repeated digits. For instance, $38800999$ would have $m=8$ and $k=4$. The number of such numbers is $9^k\left(m-1\atop k-1\right)$: We have $9$ choices for the first repeated digit (we can't use $0$) and $9$ choices for the remaining ones (we can't use the previous one), and there are $\left(m-1 \atop k-1\right)$ different way to divide the repetitions. To check that this is right, we can calculate the total number of numbers with $m$ digits:
$$\sum_{k=1}^m 9^k\left({m-1 \atop k-1}\right)=9\sum_{k=0}^{m-1} 9^k\left({m-1 \atop k}\right)=9(1+9)^{m-1}=9\cdot10^{m-1}\;,$$
which is correct.
Like Matthew, I'll use $1/\log x$ as the "probability" of a number to be prime. This isn't quite right, since this is the total density below $x$, whereas we need the marginal density, $(x/\log x)'=1/\log x - 1/\log^2 x$. I'll do the analytic calculations using just $1/\log x$, which gives an upper bound and is thus good enough to show that the sum converges, but I'll give some numerical results using the more precise formula in the end.
So the probability of one of these numbers being prime is $1/\log x$, which we can bound from above by $1/\log 10^m=1/(m\log 10)$. Now we need the probability that the $k$ different numbers that we can get by deleting one of the digits are also prime. Note that for all but the last digit, the deletion doesn't change the last digit.
One of the main reasons why Matthew's heuristic significantly underestimates the abundance of these numbers is that we need to include a factor of $5/2$ for each digit except the last: For each of these digits, given that the original number is prime and the modified number has the same last digit, we already know it isn't divisible by $2$ or $5$, which raises its chances of being prime by a factor of $10/|\{1,3,7,9\}|=5/2$.
So multiplying all these probabilities, we have one factor of $1/(m\log 10)$ for the original number to be prime, $k$ factors of $1/(m\log 10)$ for all the modified numbers to be prime, and $k-1$ factors of $5/2$ to account for the last digit. (We could bound the probability for the modified numbers by $1/((m-1)\log 10)$, but I want to keep things simple first to derive the convergence; I'll get back to that in the numerical estimates).
Now we have all we need to write an upper bound for the sum of the "probabilities" over all numbers:
$$ \begin{eqnarray} && \sum_{m=2}^{\infty}\sum_{k=1}^{m}9^k\left({m-1 \atop k-1}\right)\left(\frac{1}{m\log10}\right)^{k+1}\left(\frac{10}{4}\right)^{k-1} \\ &=& \frac{9}{\log^2 10}\sum_{m=2}^{\infty}\frac{1}{m^2}\sum_{k=0}^{m-1}\left({m-1 \atop k}\right)\left(\frac{45}{2m\log10}\right)^k \\ &=& \frac{9}{\log^2 10}\sum_{m=2}^{\infty}\frac{1}{m^2}\left(1+\frac{45}{2m\log10}\right)^{m-1} \\ &<& \frac{9}{\log^2 10}\sum_{m=2}^{\infty}\frac{1}{m^2}\mathrm{e}^{45/(2\log10)} \\ &=& \frac{9}{\log^2 10}\left(\frac{\pi^2}{6}-1\right)\mathrm{e}^{45/(2\log10)} \\ &\approx& 19191 \;. \end{eqnarray} $$
Although this is quite a lot bigger than Matthew's result, it's still finite.
The bound is not very tight, for three reasons: I didn't use the fact that the modified numbers have one fewer digit; I dropped the $1/\log^2x$ term; and the exponential bound isn't tight for small $m$. To get a better estimate, let's keep the $1/\log^2x$ term and the power instead of the exponential, and let's roughly estimate the probabilities of the original and modified numbers being prime by using $1/((m-1)\log10)$ for all of them -- that overestimates the probability for the original number and underestimates it for the modified numbers, so should give a better estimate. Putting this all together yields the following estimate for the number of $m$-digit numbers, Fixee's $c(m)$, with $j:=m-1$:
$$9\left(\frac{1}{j\log10}-\frac{1}{(j\log 10)^2}\right)^2\left(1+\frac{45}{2}\left(\frac{1}{j\log10}-\frac{1}{(j\log 10)^2}\right)\right)^j\;.$$
Here's a plot. The numbers are reasonably close to the actual ones, but still too low, even at $m=9$, i.e. $j=8$, where the approximations should be reasonable and the maximum is almost attained, but the value is around 11 whereas the actual values are all around 16.
P.S.: I think I figured out how to correctly take into account the restrictions mod $3$; I'll be posting that later in the day.
P.P.S.: I just realized that part of the remaining underestimation stems from the fact that the last digit should also get a factor of $5/2$ if it's repeated. I think that together with the mod $3$ part might get the result roughly in line with the actual numbers.
[Update:]
I've produced some more numerical data and improved the estimate as described, and the two are now in quite satisfactory agreement.
For taking into account the restrictions mod $2$, $3$ and $5$, the general approach is to take the original number as given, with the generic probability of being prime, and then to analyze the modified numbers under the condition that the original number is prime. We need to distinguish two cases depending on whether the last digit is repeated. The repeated case is easier to analyze, so I'll treat that first.
So assume that the last digit is repeated. That excludes one place at which to divide the repetitions, so there are $9^k\left(m-2 \atop k-1\right)$ such numbers. In this case, each digit, including the last one, gets a factor of $5/2$ to account for the fact that the corresponding modified number is not divisible by $2$ or $5$. To help in getting the more complicated case of a non-repeated last digit right, it's worthwhile stating more explicitly how this factor of $5/2$ arises from a conditional probability. We can consider the probabilities that a number is coprime to all primes in a set $S$ and that it is coprime to all primes not in $S$ as independent, so that the probability of the number being prime is the product of these two probabilities. Then the probability of a number being coprime to $2$ and $5$ is $\lvert\{1,3,7,9\}/10\rvert=2/5$, and the probability of the number being prime is $p=2/5q$, where $q$ is the probability of it being coprime to all primes other than $2$ and $5$. If we estimate $p$ using the overall density of primes but we know that the number is coprime to $2$ or $5$, then the conditional probability of it being prime is $q=(5/2)p$. This is relatively obvious in the present case, but this way of looking at it will be helpful in dealing with the case of a non-repeated last digit.
Now let's look at the mod $3$ restrictions. The last digit is known to be $1$, $3$, $7$ or $9$. If we delete a $3$ or a $9$, the number will still not be divisible by $3$. If we delete a $1$ or a $7$, there is a 50% chance of the number becoming divisible by $3$. Thus, the conditional probability of the modified number being coprime to $3$ is $3/4$, and this has to be divided by the unconditional probability of it being coprime to $3$, which is $2/3$, to obtain the factor $(3/4)/(2/3)=9/8$ by which we need to multiply the unconditional probability estimate.
Now consider the remaining digits, starting from the end. Each digit is different from the one after it, and the one after it is known to be one of the $7$ digits allowed mod $3$. That leaves $6$ allowed digits and $3$ forbidden ones, for a conditional probability of $2/3$. This is equal to the unconditional probability, so we don't need to include any factors to account for the mod $3$ restrictions on the remaining digits.
That completes the considerations for the case of a repeated last digit. Let's call the estimate for the unconditional probability of a number with $m$ digits to be prime $p_m$ (more on that below); then we can write the sum of the probabilities for all $m$-digit numbers with repeated last digit as
$$ \begin{eqnarray} && \frac{9}{8}p_m\sum_{k=1}^{m-1}9^k{\left(m-2 \atop k-1\right)} \left(\frac{5}{2}\right)^kp_{m-1}^k \\ &=& \frac{9}{8}\frac{5}{2}9p_mp_{m-1}\sum_{k=0}^{m-2}9^k{\left(m-2 \atop k\right)} \left(\frac{5}{2}\right)^kp_{m-1}^k \\ &=& \frac{405}{16}p_mp_{m-1}\left(1+\frac{45}{2}p_{m-1}\right)^{m-2}\;, \end{eqnarray} $$
where the orginal sum now only runs up to $m-1$ since the last digit cannot be repeated for $k=m$.
Now let's turn to the slightly more complicated case where the last digit isn't repeated. That reduces both the number of digits and the number of places at which to divide the repetitions, so there are $9^k\left(m-2 \atop k-2\right)$ such numbers. The sum works out as it should, since $\left(m-2 \atop k-1\right)+\left(m-2 \atop k-2\right)=\left(m-1 \atop k-1\right)$.
If the last digit doesn't repeat, we don't know whether deleting the last digit makes the number divisible by $2$ or $5$, and there is correlation between the events of the last deletion leaving the number coprime to $2$ and $5$ and the last two deletions leaving it coprime to $3$. Thus we need to determine the conditional probability that all three of these events occur given that the original number is prime.
Again, the last digit can be $1$, $3$, $7$ or $9$. But now the penultimate digit also has to be one of these, since otherwise the deletion of the last digit would render the number divisible by $2$. Thus we have $16$ combinations for the last two digits, $4$ of which are excluded because the digits cannot be the same. We have two different cases to consider, depending on whether $1$ and $7$ (which have the same remainder mod $3$) are allowed or not. Each of these cases occurs with probability $1/2$, depending on whether the remainder of the original number mod $3$ is $1$ or $2$. (Strictly speaking, the probabilities for these two cases are also slightly correlated with the probabilities being determined, but I believe this correlation should decay quickly as $m$ increases.)
So with probability $1/2$, only $3$ and $9$ are allowed, so the only combinations for the last two digits are $39$ and $93$. In the other case, all $4$ digits, and hence all $12$ combinations, are allowed. Thus, on average $7$ combinations of the last two digits lead to the last two deletions leaving the number coprime to $2$, $3$ and $5$, out of the $4\cdot9=36$ that are possible given that the original number is prime. That yields a conditional probability $7/36$, which we need to divide by the unconditional probability $(\lvert\{1,7,11,13,17,19,23,29\}\rvert/30)^2=(4/15)^2$ of two numbers being coprime to $2$, $3$ and $5$ to get the factor $(7/36)(15/4)^2=175/64$ by which we need to multiply the unconditional probability. All remaining digits contribute a factor of $5/2$ because deleting them doesn't make the number divisible by $2$, and we don't need any correcting factors for the mod $3$ restrictions for the remaining digits, for the same reasons as above, so we're done. Putting it all together, we have for the sum of the probabilities for all $m$-digit numbers with non-repeated last digit:
$$ \begin{eqnarray} && \frac{175}{64}p_m\sum_{k=2}^{m}9^k{\left(m-2 \atop k-2\right)} \left(\frac{5}{2}\right)^{k-2}p_{m-1}^k \\ &=& 9^2\frac{175}{64}p_mp_{m-1}^2\sum_{k=0}^{m-2}9^k{\left(m-2 \atop k\right)} \left(\frac{5}{2}\right)^kp_{m-1}^k \\ &=& \frac{14175}{64}p_mp_{m-1}^2\left(1+\frac{45}{2}p_{m-1}\right)^{m-2}\;, \end{eqnarray} $$
where the original sum starts at $2$ since the last digit necessarily repeats for $k=1$.
The ratio between the two results is $(35/4)p_{m-1}\approx(35/4)/((m-1)\log 10)\approx 3.8/(m-1)$, so for small $m$ there are more numbers with the last digit not repeated and for large $m$ there are more with the last digit repeated, in agreement with the numerical data.
We can bound $p_m$ by $1/\log m$ from above as before, and then show as before that for both cases the sum over the probabilities for all $m$ converges. To get a better estimate, we can take $p_m$ to be the average density of primes for all $m$-digit numbers, which is
$$p_m=\frac{\frac{10^m}{\log10^m}-\frac{10^{m-1}}{\log10^{m-1}}}{10^m-10^{m-1}}=\frac{1}{9\log 10}\left(\frac{10}{m}-\frac{1}{m-1}\right)\;.$$
Here are plots of the repeated case, the non-repeated case and the total. The maxima are at $m=18$, $7$ and $15$ with maximal values of and $21$, $8$ and $26$, respectively. The expected total counts (summed numerically) are $1794$, $209$ and $2003$, respectively. Thus, we can expect there to be around $2000$ of these numbers in total; about half of these have $74$ digits or more.
Here's a table comparing the actual counts for $3$ to $11$ digits (using the numerical data I report further down) to the above estimates:
$$ \begin{array}{|c|c|c|c|} m&\text{last digit repeated}&\text{last digit not repeated}&\text{total}\\\hline\\ \begin{array}{c} \mathrm{\vphantom{actual}\vphantom{estimate}}\\ \\ 2\\ 3\\ 4\\ 5\\ 6\\ 7\\ 8\\ 9\\ 10\\ 11\\ \end{array} & \begin{array}{c|c} \mathrm{actual}&\mathrm{estimate}\\ \hline\\ 0&\\ 1&4\\ 3&6\\ 7&8\\ 12&11\\ 5&13\\ 8&15\\ 11&16\\ 21&17\\ 16&19\\ \end{array} & \begin{array}{c|c} \mathrm{actual}&\mathrm{estimate}\\ \hline\\ 4&\\ 10&6\\ 11&7\\ 9&8\\ 6&8\\ 8&8\\ 6&8\\ 7&8\\ 1&7\\ 7&7\\ \end{array} & \begin{array}{c|c} \mathrm{actual}&\mathrm{estimate}\\ \hline\\ 4&\\ 11&10\\ 14&13\\ 16&16\\ 18&19\\ 13&21\\ 14&22\\ 18&24\\ 22&25\\ 23&25\\ \end{array} \end{array} $$
The agreement turns out to be quite good, though there seems to be a slight overestimation now. I have no explanation for this, since the only systematic effect I can think of that I haven't taken into account is the correlation between the size of the original number and the size of the modified numbers, which should increase rather than decrease the probabilities. (In case you're wondering whether this is a case of changing the theory until it fits the data, it was actually the other way around: I got several incorrect results for the non-repeated case that would have removed the overestimation, but I believe the above analysis is the correct one.)
Here are all the numbers with up to $11$ digits (up to the 4,239,555,920th prime); I checked that they coincide with the ones already reported, but I'm putting them all here to have them together in one place:
23, 37, 53, 73, 113, 131, 137, 173, 179, 197, 311, 317, 431, 617, 719, 1013, 1031, 1097, 1499, 1997, 2239, 2293, 3137, 4019, 4919, 6173, 7019, 7433, 9677, 10193, 10613, 11093, 19973, 23833, 26833, 30011, 37019, 40013, 47933, 73331, 74177, 90011, 91733, 93491, 94397, 111731, 166931, 333911, 355933, 477797, 477977, 633317, 633377, 665293, 700199, 719333, 746099, 779699, 901499, 901997, 944777, 962233, 991733, 1367777, 1440731, 1799999, 2668999, 3304331, 3716633, 4437011, 5600239, 6666437, 6913337, 7333331, 7364471, 7391117, 13334117, 22255999, 33771191, 38800999, 40011197, 40097777, 44333339, 49473377, 79994177, 86000899, 93361493, 94400477, 99396617, 99917711, 110499911, 144170699, 199033997, 222559399, 333904433, 461133713, 469946111, 640774499, 679774391, 680006893, 711110111, 716664317, 743444477, 889309999, 900117773, 982669999, 999371099, 999444431, 1113399311, 1133333777, 1176991733, 1466664677, 1667144477, 1716336911, 2350000999, 3336133337, 3355522333, 3443339111, 3973337999, 4111116011, 4900001111, 6446999477, 6666116411, 6689899999, 6914333711, 7463333477, 8555555599, 8888333599, 8936093833, 9746666477, 10000000097, 10666610333, 11100077711, 11793334733, 19000019333, 23525555899, 30001114937, 33008299999, 33110666399, 33399911777, 37796941199, 40470660977, 44434133339, 46661333333, 46666133333, 55888856893, 61077333377, 66664441373, 66700447613, 66993413393, 71111164499, 77443733111, 99444901133
Some interesting specimens are 10000000097 (which is the only one with lots of $0$s after the first digit, showing that there's no significant effect from the overestimation of the size of the modified numbers in such a case) and the pair 46661333333 and 46666133333.
Here's the Java program I used to find these (using a bit set as Fixee suggested to cram as many primes as possible into my 8GB). The computation took half an hour on a MacBook Pro i7.
public class EdiblePrimes {
static class LongBitSet {
int [] bits;
public LongBitSet (long nbits) {
bits = new int [(int) ((nbits + 0x1f) >> 5)];
}
public void clear (long bit) {
bits [index (bit)] &= ~mask (bit);
}
public void set (long bit) {
bits [index (bit)] |= mask (bit);
}
public boolean get (long bit) {
return (bits [index (bit)] & mask (bit)) != 0;
}
private static int mask (long bit) {
return 1 << (bit & 0x1f);
}
private static int index (long bit) {
return (int) (bit >> 5);
}
}
final static long max = 0x1800000000L;
final static long maxIndex = max >> 1;
public static void main (String [] args) {
LongBitSet composite = new LongBitSet (maxIndex); // bit at index n says whether 2n+1 is composite
composite.set (0); // 1 isn't prime
int maxDivisor = (int) (Math.sqrt (max) + 1);
for (int divisor = 3;divisor < maxDivisor;divisor += 2)
if (!composite.get (divisor >> 1))
for (long multiple = (3 * divisor) >> 1;multiple < maxIndex;multiple += divisor)
composite.set (multiple);
outer:
for (long n = 11;n < max;n += 2) {
if (!composite.get (n >> 1)) {
long power = 1;
do {
long nextPower = 10 * power;
long modified = n % power + (n / nextPower) * power;
if (modified != 2 && ((modified & 1) == 0 || composite.get (modified >> 1)))
continue outer;
power = nextPower;
} while (power < n);
System.out.println (n);
}
}
}
[Update:]
Since the probability has a simple $k$ dependence, we can calculate the expectation value for $k$, i.e. the expected number of strings of repeated digits. For the shifted sums over $k$, we have
$$ \begin{eqnarray} && \frac{ \sum\left(m-2 \atop k\right) k q^k }{ \sum\left(m-2 \atop k\right) q^k } \\ &=& \frac{ q\frac{\partial}{\partial q}\sum\left(m-2 \atop k\right)q^k }{ \sum\left(m-2 \atop k\right) q^k } \\ &=& \frac{ q\frac{\partial}{\partial q}(1+q)^{m-2} }{ (1+q)^{m-2} } \\ &=& \frac{ (m-2)q(1+q)^{m-3} }{ (1+q)^{m-2} } \\ &=& \frac{m-2}{1+q^{-1}}\;. \end{eqnarray} $$
With $q\approx 45/(2(m-1)\log10)$, this becomes
$$ \frac{m-2}{1+\frac{2(m-1)\log10}{45}}\to_{m\to\infty}\frac{45}{2\log{10}}\approx 10\;. $$
We shifted $k$ down by $1$ and $2$ for numbers with with last digit repeated and not repeated, respectively. Thus, if we don't count a non-repeated last digit as a separate string, we get the same expectation value in both cases, namely $1$ more than the above value. Thus, in the limit of large $n$, there will be about $11$ strings of repeated digits on average (not counting non-repeated last digits), but the values for small $m$ are not near the limit because of the large factor of $45$. Here's a comparison of the actual averages with the estimated expectation values (using the above better estimate for $p_m$):
$$ \begin{array}{|c|c|c|} \hline\\ m&\text{actual}&\text{estimated}\\ \hline\\ 2&1.0&\\ 3&1.9&1.8\\ 4&2.8&2.5\\ 5&3.5&3.1\\ 6&3.8&3.6\\ 7&4.1&4.1\\ 8&4.4&4.5\\ 9&5.3&4.8\\ 10&5.4&5.1\\ 11&5.7&5.4 \end{array} $$
Here, too, the agreement is quite good, but there seems to be a slight systematic error left.
Solution 2:
Here is a heuristic for why we should expect there are only finitely many of these numbers. Let $P$ be the set of positive integers with your special property.
A large number $n$ is prime with probability approximately
$$ \frac{1}{\log n}. $$
For a number $n$ to be in $P$, it must remain prime with the removal of each digit. Removing a digit from a number $n$ results in a number on the order of
$$\frac{n}{10}.$$
A number $n$ has approximately
$$\frac{\log n}{\log 10}$$
digits.
As a result, the probability that $n$ is in $P$ can be approximated as
$$ \left( \frac{1}{\log \frac{n}{10} } \right)^{\frac{\log n}{\log 10}} = \frac{1}{n^{\frac{\log \log (n/10)}{\log 10}}}$$
In general, if the probability of $n$ being in a set $S$ is $p(n)$ then if
$$\sum_{n=1}^{\infty} p(n)$$
is finite, we can expect $S$ to be finite; if the sum is infinite, we can expect $S$ to be infinite. In the case of $P$, since the sum
$$\sum_{n=2}^{\infty} \frac{1}{n^{\frac{\log \log (n/10)}{\log 10}}}$$
converges (by comparison with, say, $\displaystyle \sum_{n=1}^{\infty} \frac{1}{n^2}$) we may conclude that we should expect $P$ to be finite.
Unfortunately, this is just a heuristic, so does not constitute a proof of the finiteness of $P$, nor does it give any idea how large the largest element of $P$ might be.
Addition: I just realized that I wasn't assuming $n$ needed to be prime to be in $P$, only that it was prime after the removal of any one digit. So, my $P$ would include 27. Requiring only prime numbers in $P$ just makes the set smaller, so the above argument applies just as well is we require $P$ to only contain prime numbers.
Solution 3:
I wrote an application in Java that searches the numbers. Here are the results in the range [1,100.000] (the original number isn't necessarily a prime itself)
22 23 25 27 32 33 35 37 52 53 55 57 72 73 75 77 111 113 117 119 131 137 171 173 179 197 311 317 371 411 413 417 431 437 471 473 611 617 671 711 713 719 731 1013 1031 1037 1073 1079 1097 1379 1397 1499 1673 1739 1937 1991 1997 2233 2239 2277 2293 2571 2577 2811 3113 3131 3137 3173 3311 3317 3479 4019 4199 4331 4433 4439 4499 4631 4919 4991 5577 5877 6017 6173 6431 6773 7019 7433 7619 7733 8211 8239 8277 8577 8811 8877 9191 9677 9911 9971 9977 10193 10613 10619 11093 11871 12777 14871 14933 14993 14999 16637 16997 17877 19733 19973 23833 24111 26833 27411 30011 31637 34691 36917 37019 40013 40073 40919 42111 47933 47993 49337 49733 52333 60911 61733 61997 63011 71877 73331 74177 74517 74817 74877 75417 75477 81117 81171 82693 90011 90491 91733 93491 94133 94337 94391 94397 94733 97433
If the extra condition is that the original number has to be a prime, there are other results (range [1,100.000.000]:
23 37 53 73 113 131 137 173 179 197 311 317 431 617 719 1013 1031 1097 1499 1997 2239 2293 3137 4019 4919 6173 7019 7433 9677 10193 10613 11093 19973 23833 26833 30011 37019 40013 47933 73331 74177 90011 91733 93491 94397 111731 166931 333911 355933 477797 477977 633317 633377 665293 700199 719333 746099 779699 901499 901997 944777 962233 991733 1367777 1440731 1799999 2668999 3304331 3716633 4437011 5600239 6666437 6913337 7333331 7364471 7391117 13334117 22255999 33771191 38800999 40011197 40097777 44333339 49473377 79994177 86000899 93361493 94400477 99396617 99917711
The source code of the application is this:
/**
*
* @author martijn
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
outer:
for (int i = 11; i < 100000; ++i) {
/* If the condition is that the original has to be a prime,
* uncomment following three lines */
// if (!isPrime(i)) {
// continue;
// }
String str = String.valueOf(i);
int len = str.length();
for (int c = 0; c < len; ++c)
{
int ci = len - c - 1;
int s = (i / pow10(ci + 1) * pow10(ci)) + (i % pow10(ci));
if (!isPrime(s))
{
continue outer;
}
}
System.out.println(i);
}
}
public static int pow10(int pow)
{
switch(pow)
{
case 0: return 1;
case 1: return 10;
case 2: return 100;
case 3: return 1000;
case 4: return 10000;
case 5: return 100000;
case 6: return 1000000;
case 7: return 10000000;
case 8: return 100000000;
case 9: return 1000000000;
}
// You are searching VERY high numbers
return -1;
}
public static boolean isPrime(int g) {
if (g < 2) {
return false;
}
if (g == 2) {
return true;
}
if ((g & 1) == 0) // If even
{
return false;
}
// A few cheap checks
if (g <= 113) {
if (g == 3) {
return true;
}
if (g == 5) {
return true;
}
if (g == 7) {
return true;
}
if (g == 11) {
return true;
}
if (g == 13) {
return true;
}
if (g == 17) {
return true;
}
if (g == 19) {
return true;
}
if (g == 23) {
return true;
}
if (g == 29) {
return true;
}
if (g == 31) {
return true;
}
if (g == 37) {
return true;
}
if (g == 41) {
return true;
}
if (g == 43) {
return true;
}
if (g == 47) {
return true;
}
if (g == 53) {
return true;
}
if (g == 59) {
return true;
}
if (g == 61) {
return true;
}
if (g == 67) {
return true;
}
if (g == 71) {
return true;
}
if (g == 73) {
return true;
}
if (g == 79) {
return true;
}
if (g == 83) {
return true;
}
if (g == 89) {
return true;
}
if (g == 97) {
return true;
}
if (g == 101) {
return true;
}
if (g == 103) {
return true;
}
if (g == 107) {
return true;
}
if (g == 109) {
return true;
}
if (g == 113) {
return true;
}
return false;
}
int max = (int) Math.ceil((Math.sqrt((double) g)));
for (int i = 3; i <= max; i += 2) {
if (g % i == 0) {
return false;
}
}
return true;
}
}
Solution 4:
Using the link provided by @joriki in the comments, I found Mathematica code to find such primes (I am using the code that allows 0s as you can then get all those that do not allow 0 simply by deleting the primes with 0s).
rpQ[n_] := Module[{idn = IntegerDigits[n]}, And @@
PrimeQ[FromDigits /@ Subsets[idn, {Length[idn] - 1}]]];
Here is the list of all such numbers from the first 436 million primes.
23, 37, 53, 73, 113, 131, 137, 173, 179, 197, 311, 317, 431, 617, 719, 1013, 1031, 1097, 1499, 1997, 2239, 2293, 3137, 4019, 4919, 6173, 7019, 7433, 9677, 10193, 10613, 11093, 19973, 23833, 26833, 30011, 37019, 40013, 47933, 73331, 74177, 90011, 91733, 93491, 94397, 111731, 166931, 333911, 355933, 477797, 477977, 633317, 633377, 665293, 700199, 719333, 746099, 779699, 901499, 901997, 944777, 962233, 991733, 1367777, 1440731, 1799999, 2668999, 3304331, 3716633, 4437011, 5600239, 6666437, 6913337, 7333331, 7364471, 7391117, 13334117, 22255999, 33771191, 38800999, 40011197, 40097777, 44333339, 49473377, 79994177, 86000899, 93361493, 94400477, 99396617, 99917711, 110499911, 144170699, 199033997, 222559399, 333904433, 461133713, 469946111, 640774499, 679774391, 680006893, 711110111, 716664317, 743444477, 889309999, 900117773, 982669999, 999371099, 999444431, 1113399311, 1133333777, 1176991733, 1466664677, 1667144477, 1716336911, 2350000999, 3336133337, 3355522333, 3443339111, 3973337999, 4111116011, 4900001111, 6446999477, 6666116411, 6689899999, 6914333711, 7463333477, 8555555599, 8888333599, 8936093833
There are some things we can say about such numbers.
The last 2 digits can only ever consist 1, 3, 7, or 9 since any number ending in 0, 2, 4, 5, 6, 8 is composite (other than single digit numbers).
The sum of the digits can not be 0 mod 3, because the number would be divisible by 3. And, if the sum of the digits is 1 mod 3, then none of the digits of the number can be 1 mod 3. Similarly, if the sum of the digits is 2 mod 3 then, then none of the digits can be 2 mod 3. So, every such number is comprised of at most 0, 3, 6, 9, and 1, 4, 7 OR 0, 3, 6, 9, and 2, 5, 8.
These should be much more rare if you generalize to more than 1 delete. If there were 2 deletes, the mod 3 argument would rule out most cases. I believe the only case possible would be the digits add to 1 mod 3 and all the digits are 1 mod 3, or the digits add to 2 mod 3 and all the digits are 2 mod 3. So, they could only contain 1, 4, and 7 OR 2, 5, 8. In the second case, ending with any of those numbers makes the original not prime. So, we only have the first case. They must have the digits 1, 4, 7 only. And, they would have to contain 4, 7, 10, 13, 16, ... digits to ensure the digit totals worked out.
Solution 5:
Here's my C code for generating these numbers. It should be very fast since it uses a sieve, but also consumes a lot of memory for the sieve[] array (we could compress by a factor of 8 by using a bitfield).
// find primes such that deleting any digit remains a prime
//
#include <stdio.h>
#define MAX 1000000000LL
char sieve[MAX];
int ddel(long long i);
int main(void) {
long long i, j;
sieve[0] = sieve[1] = 0; // don't count 0 and 1 as primes
for (i=2; i < MAX; i++) sieve[i] = 1;
// sieve; each new prime will be tested
for (i=2; i < MAX; i++) {
if (sieve[i] == 0) continue;
for (j=i+i; j < MAX; j += i) sieve[j] = 0;
if (i > 10) {
if (ddel(i))
printf("%d\n", i);
}
}
}
int ddel(long long i) {
long long j;
long long t = 1;
while (t < i) {
// delete the log_10(t) digit
j = i/10/t * t + i%t;
if (sieve[j] == 0) return 0;
t *= 10;
}
return 1;
}