# Infinitely many primes of the form $\underbrace{11\dots 1}_{k \text{ times}}\dots \underbrace{11\dots 1}_{k \text{ times}}$

[Analytic Number Theory - Florian Luca and Jean Marie De Koninck, chapter 14, question 14.9]

Prove that for each positive integer $$k$$, there are infinitely many primes which when written in base $$10$$ look like $$\underbrace{11\dots 1}_{k \text{ times}}\dots \underbrace{11\dots 1}_{k \text{ times}}$$ where there are some unspecified digits in the middle.

I am sure that we need to construct a clever arithmetic progression and somehow use Dirichlet's Theorem. But, I can't figure out how.

This post shows that there are infinitely many digits starting with a given string, and this one shows that there are infinitely many ending in $$k$$ $$1$$'s.

• The same question ending with $k$ digits $1$ see here. It works with Dirichlet's theorem. Commented Oct 10, 2023 at 18:49
• Can you use the prime number theorem for arithmetic progressions? I think that should enable an argument similar to this. Commented Oct 10, 2023 at 19:00
• Yes, I said "similar to", not exactly that argument. Apply the PNT for APs to the AP $111\dots1 + 10^k \cdot n$, and then replicate the argument in the answer I linked (basically the post I linked is the same question after you replace $\Bbb N$ with "the set of numbers ending in $11\dots1$", and the PNT for APs says you can do that) Commented Oct 10, 2023 at 19:09
• @IzaakvanDongen I'm sorry, I still don't quite understand the argument. I tried to use your linked post to construct the interval $\left [x,\left(1+\frac 1{10^k}\right)x\right]$ for $x=11\dots 1\times 10^L$ for $L$ sufficiently large. But, it's not like all elements of that interval are of the desired form. Also, now that I checked your wiki link, maybe I am not allowed to use what you suggested. All I can use is that $$\sum_{p\le x\\p\equiv h\pmod k} \frac{\log p}p=\frac{\log x}{\phi(k)}+\mathcal O(1)$$. But, I am aware of the corollary of PNT mentioned in that answer. Commented Oct 10, 2023 at 19:32
• My suggestion was to prove the lemma "let $a, d \in \Bbb N$ be coprime. Then for every $\alpha > 1$, there is some $x_0$ such that for $x > x_0$, there is a prime of the form $a + nd$ in the interval $[x, x \alpha]$". Then apply this for $a = 11\dots1$, $d = 10^k$, $\alpha = 1 + 10^{-k}$ to conclude. However it looks like the form of PNT-for-APs you give might be too weak to prove this lemma. At least I can't see how to prove it from that! (If the remainder was $o(1)$ it would work!). So perhaps you should prove the full version (similar to normal PNT), or maybe there's another proof. Commented Oct 10, 2023 at 20:40

To elaborate a little on the comments: Let $$a = \underbrace{11\cdots 1}_{k \text{ times}}$$ and $$d = 1\underbrace{0\cdots 0}_{k \text{ times}}.$$ Then, by Dirichlet's theorem, there are infinitely many primes of the form $$a + nd$$ which then have the desired trailing ones. To get the initial ones, let $$x = a * 10^n = \underbrace{11\cdots 1}_{k \text{ times}}\;\;\underbrace{00\cdots 0}_{n \text{ times}}$$ for some large $$n$$ to be decided. Set $$c = 1 + 10^{-k}$$; then any $$y$$ with $$x \leq y < cx$$ must start with $$k$$ $$1$$'s as well. Letting $$\pi_{d,a}(x)$$ be the number of primes $$p \leq x$$ of the form $$a + nd$$, our goal is to show that $$\pi_{d,a}(cx) - \pi_{d,a}(x) \geq 1.\tag{*}\label{*}$$ Then there is one prime of the desired form. And by varying $$n$$, we will get infinitely many.

To show $$(*)$$, we use the prime number theorem for arithmetic progressions, which states that for any given $$\epsilon$$ and all sufficiently large $$x$$,

$$(1- \epsilon) \frac {L(x)}{\phi (d)} < \pi_{d,a}(x) < (1+ \epsilon) {\frac {L(x)}{\phi (d)}}.$$

where $$L(x) = x / \log(x)$$. Hence $$\pi_{d,a}(cx) - \pi_{d,a}(x) > \frac{L(cx) - L(x)}{\phi(d)} - 2 \epsilon \frac{L(cx)}{\phi(d)}$$

and so we are done if we can show that for some $$\epsilon$$ depending only on $$k$$ and $$d$$, that for all sufficiently large $$x$$ $$L(cx) - L(x) > \phi(d) + 2 \epsilon L(cx)$$.

• I kind of get the idea - but still, how do you plan to show $L(cx) - L(x) > \varphi(d) + 2 \epsilon L(cx)$ for sufficiently large $x$? Commented Oct 10, 2023 at 20:41
• Well, at that point it's not number theory anymore and it's some $\epsilon-\delta$ style manipulations. Give it a shot. Commented Oct 10, 2023 at 20:44
• @SayanDutta, that's just pure real analysis. I would divide both sides by $L(cx)$! +1 btw Jair. This might be the first arithmetic progression I've seen with common difference $a$ and first term $d$ :-) Commented Oct 10, 2023 at 20:47
• @IzaakvanDongen Thanks, I always try to innovate ;) I will fix. Commented Oct 10, 2023 at 20:49
• @IzaakvanDongen, JairTaylor : I see, it's not as difficult as it seemed (+1) Commented Oct 10, 2023 at 20:58