3
$\begingroup$

I suspect that primes containing certain digits (e.g. $1$, $3$) are way more common than primes containing other digits e.g. containing $2,4$ since my intuition tells me the latter combination is divisible by so many numbers: For example $13$ and $31$ are prime while neither $24$ or $42$ is (I take here the trivial null case of $2$'s and $4$'s for illustrative purposes).

This came to my mind as I was playing around with $1$'s and $3$'s trying to guess a prime number consisting of these two digits. To my surprise I guessed the following primes (tested with PrimeQ[...] of Mathematica) quite easily (the first ones in a couple of guesses while that last one took a dozen): $$ 11131, \\ 111311131 \\ 11131113113131111 \\ 11131113111111111111131311 $$

How come? Is this pure luck? I have a hard time believing it be pure luck due to the Prime Number Theorem.

(For the last number in the list I basically put in $1$'s and $3$'s randomly a dozen of times until I hit a prime.)

$\endgroup$
7
  • $\begingroup$ Roughly speaking, the P.N.T. gives that a random odd number $n$ has probability $\sim \frac{2}{\log n}$ of being prime. In the case of your last example $N$, $\frac{2}{\log N} \approx 29$, so on average one should expect to get a prime after about that many guesses of numbers of roughly that magnitude. In particular, one should get such a prime in the first dozen attempts more than one-third of the time. $\endgroup$ – Travis Willse Apr 20 '16 at 15:19
  • $\begingroup$ Note: the Copeland-Erdős constant is normal, which means in particular that each digit is approximately $\frac1{10}$ of all digits of the first $N$ primes, if $N$ is sufficiently large. Thus, in the limit, the only way for primes with particular digits to be more common than others is if those digits "cluster together" -- that is, if a prime contains (e.g.) at least one 2 as a digit it contains a disproportionate number of 2s, whereas (e.g.) the 3s are well spread out over the primes. $\endgroup$ – Mees de Vries Apr 20 '16 at 15:20
  • $\begingroup$ Thanks for the nice comments, but @Travis where did you get the $29$ from? $\endgroup$ – Your Majesty Apr 20 '16 at 15:35
  • $\begingroup$ @MeesdeVries Thanks for your comment regarding the 1/10 it was illuminating, but the final part is a little bit confusing. $\endgroup$ – Your Majesty Apr 20 '16 at 15:37
  • $\begingroup$ This is just substituting $N = 11131113111111111111131311$ in the formula I wrote. $\endgroup$ – Travis Willse Apr 20 '16 at 16:00
1
$\begingroup$

This is not so surprising: An improvement to the P.N.T. implies that the number $\pi(x)$ of primes $\leq n$ is given by the (offset) logarithmic integral function, $$\operatorname{Li}(x) := \int_2^x \frac{dt}{\log t} .$$ Heuristically, the probability that a given random integer $\approx N$ is prime is $$\left.\frac{d}{dx}\right\vert_N \operatorname{\operatorname{Li}(x) = \frac{1}{\log N}},$$ but all primes $> 2$ are odd, so (again heuristically) the probability that a given random odd integer $\approx N$ is twice that, $$\frac{2}{\log N}.$$ For the largest number $N_0 := 11131113111111111111131311 11131$ in your list, computing gives $$\frac{2}{\log N_0} = 0.034679\!\ldots \approx \frac{1}{29} ,$$ so, naively, one would have to try $29$ odd numbers of that magnitude to find a prime, and one would find one in the first dozen attempts $> \frac{1}{3}$ of the time. One could derive a similar approximation using just the P.N.T., but the math for this better approximation is a little easier.

$\endgroup$
2
  • $\begingroup$ I guess this answers how I could pick a prime after some guesses :) thanks! $\endgroup$ – Your Majesty Apr 21 '16 at 11:36
  • $\begingroup$ You're welcome, I'm glad you found it helpful! $\endgroup$ – Travis Willse Apr 21 '16 at 12:05
1
$\begingroup$

As you have Mathematica you could simply create all numbers made of 1s and 3s of a certain length then determine which ones are prime then divide by the number of possible numbers. Here is a function which can do that:

f[n_]:=Count[Map[PrimeQ[FromDigits[#]]&,Tuples[{1,3},n]],True]/2^n

Lets break it down:

Tuples[{1,3},n] creates all possible lists of length n made from the digits 1 and 3. Then the functions PrimeQ and FromDigits is Mapped over all these lists to firstly convert each list to an actual number then test if its prime. The True results of this mapping is then counted and finally this number is divide by the total number of permutations.

Comparing to your situation we see:

f[5]=$\frac{9}{32}$

f[9]=$\frac{75}{512}$

f[17]=$\frac{9461}{131072}$

f[26]=$\frac{?}{67108864}$ = too hard for my computer to process

$\endgroup$
1
  • $\begingroup$ Nice function. You're right f[26] is just too much but I did $f[21] = 31663/524288$. $\endgroup$ – Your Majesty Apr 21 '16 at 11:31
1
$\begingroup$

Your question, whether or not primes containing some digits are more common than primes containing others can be made into a precise question in various different ways. One obvious way is the following: does the quantity $$ \lim_{N \to \infty} \frac{\#\{p < N \mid \text{$p$ prime and $p$ contains digit $d$}\}}{\#\{p < N \mid \text{$p$ prime}\}} $$ always exist, and if so, does it differ for different digits $d$?

The answer to this question is no, and in fact the limit above always exists and always equals 1. The reason comes down to the following informal facts: there are quite many primes, while there are very few numbers which do not contain all 10 digits.

In their paper on the Copeland-Erdős constant, Copeland and Erdős prove the following result (paraphrased, and specialized to our situation):

Lemma: There is a $\delta < 1$ such that for sufficiently large $N$, the number of numbers below $N$ which do not contain all 10 digits is less than $N^\delta$.

Let's fix such a $\delta$. From the prime number theorem, we know that the number of primes less than $N$ is approximately $\frac N{\log N}$ for large enough $N$. Thus, the number of primes below $N$ which contain all 10 digits is certainly at least $$ \frac N{\log N} - N^\delta $$ for $N$ sufficiently large. But then we have for any digit $d$ \begin{align*} 1 &\geq \lim_{N \to \infty} \frac{\#\{p < N \mid \text{$p$ prime and $p$ contains digit $d$}\}}{\#\{p < N \mid \text{$p$ prime}\}}\\ & \geq\lim_{N \to \infty} \frac{\#\{p < N \mid \text{$p$ prime and $p$ contains all digits $d$}\}}{\#\{p < N \mid \text{$p$ prime}\}}\\ &\geq \lim_{N \to \infty} \frac{\frac N{\log N} - N^\delta}{\frac N{\log N}}\\ &= 1. \end{align*} This argument can be extended without too much effort to different bases, and to different substrings (instead of just single digits).

$\endgroup$
1
  • $\begingroup$ Nice little lemma, thanks! $\endgroup$ – Your Majesty Apr 21 '16 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.