Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

After a quick look at the sequence (of primes) A020463, $$ 3, 7, 37, 73, 337, 373, 733, 773, 3373, \dots, $$ the following question is straighforward:

Are there infinitely many primes compiled from digits 3 and 7 in base 10?

As any question about primes, this should be tough. Nevertheless I believe there exists some reasonable heuristics to answer it.

share|improve this question
1  
Can we even prove that there are infinitely many primes which in their decimal expansion do not contain the digit $9$? –  Eric Naslund Dec 31 '12 at 6:58
    
I would expect that the set of integers n such that there is a pri,e of that form with n digits not only is an infinite set but also is likely coinfinite in the positive integers. One marvels at how many composites are easily shown to be in theset of numbers having just threes and sevens. Gerhard "Minding Some P's and Q's" Paseman, 2012.12.30 –  Gerhard Paseman Dec 31 '12 at 7:00
2  
Some questions of a similar flavor, for the much denser set of squarefree numbers replacing the set of primes, are considered by Filaseta and Konyagin in this Acta Arithmetica paper: matwbn.icm.edu.pl/ksiazki/aa/aa74/aa7431.pdf In particular, they prove that for each $2 \leq b \leq 5$, there are infinitely many squarefree numbers in base $b$ consisting only of the digits $0$ and $1$. When $b=10$, they can show there are infinitely many squarefree numbers consisting just of the digits $0$, $1$, and $2$. –  Anonymous Jan 1 '13 at 4:24
    
I will add that ``almost-prime'' results of this sort have been obtained by Dartyge and Mauduit: Almost primes whose expansion in base $r$ misses some digits. (Nombres presque premiers dont l'écriture en base $r$ ne comporte pas certains chiffres.) (French) J. Number Theory 81, No.2, 270-291 (2000) –  Anonymous Jan 1 '13 at 16:50

1 Answer 1

Let $a_k=\pi(10^k)-\pi(10^{k-1})$ be the number of $k$ digit primes. All of them (for $k \gt 1$) are from the $4\cdot 10^{k-1}$ integers in that range which are co-prime to $10.$ The heuristic is that, for $k$ not too small, there should be about $\frac{2^k}{4\cdot10^{k-1}}a_k$ primes in that range using only the digits $3,7$ because the $2^k$ numbers of that form have the advantage of being co-prime to $10$ but nothing else (i.e. there seems no reason to expect advantages relative to other primes, nor do there seem to be any that persist meaningfully for large $k$) . (But see the end) for more carefully thoughts)

Anyway, the predicted and actual counts up to 15 digits are

$ \begin{array}{ccccccccccccccc} 2.0& 2.1& 2.9& 4.2& 6.7& 11& 18.8& 32.6& 58& 104& 188& 343& 632& 1171 & 2182\\\ 2&2&4&3&5&10&16&30&53&87&185&365&591&1062 &2290\end {array} $

The ratios are $1.00, .95, 1.40, .71, .75, .91, .85, .92, .92, .84, .99, 1.06, .94, .91, 1.05.$ We can't prove that there are infinitely many primes of this form but we would be willing to bet that the ratio of actual to expected will never again be observed to lie outside the range $(0.8,1.2)$ or even $(0.9,1.1)$ (if we start a little further out.)

Here are statistics for the most frequent prime divisors of the $256$ $8$ digit members along with the (naively) predicted number , $\frac{256}{p}.$

$[3,85,85],[11,70,23],[7,37,37],[101,36,3],[37,24,7],[73,16,4],[137,16,2],$$[17,15,15],[13,15,20],[23,13,11],[19,13,13],[29,9,9],[31,8,8]$

Many are just about right. One can see why $11,101$ and the larger divisors of $111=3 \cdot 37$ $1001=3 \cdot 7 \cdot 13$ and $10001=73 \cdot 137$ enjoy an advantage (and $37$, $73$ have other advantages.) However the actual count of $30$ is not far off the predicted count of $32.6$, In part this is because many of the "exceptionally popular" divisors strike out the same number including $37 \cdot 101 \cdot 73 \cdot 137 =37373737.$ For some reason $13$ actually comes out rather low.

Furthermore, the distribution $\mod p$ (for $p \ne 2,5$) does become uniform as $k$ grows. This is also true for the distribution $\mod m$ where $m$ is any modulus co-prime to $10$ (in particular the various distributions $\mod p$ are mutually independent):

Consider the (connected) directed graph with vertices $\{0,1,\cdots,m-1\}$ and edges $[u,10u+3]$ $[u,10u+7]$ (computed $\mod m$). So each vertex has indegree and outdegree $2$. A $k$-step random walk starting at $0$ corresponds to generating a $k$ digit member of the set by coin flips and keeping track of the evolving congruence class $\mod m$. The distribution $\mod m$ can also be seen by giving each edge the weight $1/2$, taking the (doubly stochastic) weighted adjacency matrix $A$ and computing $A^k\mathbf{v}$ for $\mathbf{v}=[1,0,0,\cdots,0]^t.$ The dominant eigenvalue is $1$ with the constant eigenvector. As noted, the convergence to uniformity can be somewhat slow for some primes such as $p=11$ and $p=101$. One can see directly why this is. For $p=11$ this is also reflected by the fact that the digraph is a path with loops at $7$ and $9$. This graph for $p=101$ is a little more interesting. (A fuller justification could be given. $3,7$ are relatively prime to each other and to the base $10$, they are not congruent mod $p$ for any $p$ other than $2$. The case of digits $1,7$ has advantages and disadvantages concerning divisibility by $3$ according as $k$ is not or is a multiple of 3.)

There is nothing special about the pair $3,7$, the same reasoning applies to any of the pairs from $\{1,3,7,9\}$ with the obvious exception of $3,9$ (and an adjustment for $1,7$). And, with simple adjustments, any set of possible digits in any base (with greatest common divisor 1) should be expected to have, for not too small $k$, the number of primes not ruled out by "obvious" restrictions (including congruence classes of differences).

after more cautious thought: The fuller form of the heuristic (which Wadim and other people can no doubt express more accurately than I) is that there are about the number of primes that one would expect from random considerations after taking into account the "obvious". (So there should be an "obvious" reason for deviations, maybe in hindsight.) So integers $4k^2-1$ factor algebraically and are not prime. These $3,7$ numbers are automatically odd and coprime to $5$ but other than that there seems no reason to think that they have special properties relative to other primes (nor do they appear to aside from explainable transient ones.) However, I would have expected the (somewhat vague) analysis I gave below to apply as well to digits $1,7.$ Upon reflection (and clearly if had bothered to check) when $k=3j$ all $2^k$ $k$-numbers are multiples of $3$ so none are prime although for $k=3j+1$ and $k=3j+2$ one would expect $\frac{2^k}{2/3\cdot 4 \cdot 10^{k-1}}a_k$ primes because all $2^k$ members are sure to be co-prime to $3$ as well as $10$.

share|improve this answer
1  
Since there are $2^k$ $k$ digit numbers of this type, it's certainly not as fast as $2.5^k$. –  Robert Israel Dec 31 '12 at 9:43
    
Good point. I was being a bit sloppy. Let $c_k$ be the number of primes of the desired type with $k$ digits. I meant (although it wasn't what I said) that it seems a safe bet that past the range I have already discussed $\frac{c_{k+1}}{c_k}$ will never be seen to stray outside a fairly constrained range. Of course it will start to be pretty hard to get the counts. –  Aaron Meyerowitz Dec 31 '12 at 9:55
    
One reason for my comment above is that one can prove the set of integers n for which there are primes with base 10 digits being 1 and 7 is coinfinite in the natural numbers. Another is that there are large interesting subsets of composites in the group of numbers whose base 10 digits are 3 and 7, the largest of which are those where the count of 7's is a multiple of 3. That takes out roughly a third of all the numbers. Similarly one can find multiples of 7 among many of the numbers with few occurrences of 3. Gerhard "Ask Me About Numerical Patterns" Paseman, 2013.01.01 –  Gerhard Paseman Jan 1 '13 at 21:34
    
So you are saying that there definitely infinitely many primes which do not contain the digit 9? That was a question in a comment. The 3/7 numbers are exceptional mod 2 and mod 5. Other than that they may be essentially the same as the set of integers relatively prime to 10. Roughly 1/3 of those ( like the set of all integers!) are multiples 3. As I remarked the distribution mod 11 starts skewed but eventually is not. A stunning 25 % of the 4 digit guys are multiples of 101 but that too will stay just under 1% from some point on. –  Aaron Meyerowitz Jan 1 '13 at 23:54
    
If Aaron's "you" in the previous comment means me, then let me clarify. I am definitely expecting a lot of (base 10) primes without the digit nine, which is different from having a notion of how to prove or refute the expectation. And while I can prove that all (base 10) numbers which have 19683*k digits which are only 1's and 7's are composite, I expect that showing there are infinitely many k for which all k digit numbers having 3's and 7's are composite will be much harder, if indeed it is feasible. Gerhard "Has Also Experienced The Unexpected" Paseman, 2013.01.02 –  Gerhard Paseman Jan 2 '13 at 18:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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