# Is {a^n: n is a product of exactly two primes} regular?

I am struggling to prove the following question.

$$L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$$

I feel like the language is not regular but I am having trouble proving it. I tried using pumping lemma but got stuck at the end. Here's how I did it:

Assume that the language is regular and $$m$$ is a constant of Pumping Lemma. Now let $$w = a^M$$ where $$M > m$$ and $$M$$ is a co-prime number. Clearly $$w$$ is in the language and $$|w| > m$$.

Now let $$y=a^j$$ where $$j$$ is between $$1$$ and $$m$$, with $$|xy| \leq m$$ and $$|y| \geq 1$$.

This is where I am getting stuck. I feel like we should pump up but I don't know by "how much". Also, I feel like I have to know what is the next co-prime number after $$M$$, but can't figure it out.

• Hint: convert to the language of primes by intersecting with the language of even-length strings and applying an inverse homomorphism. – Yuval Filmus Oct 12 '19 at 17:45

Just pump up $$(M+1)$$ $$y$$'s. Now you get $$xy^{M+1}z=a^{(M+1)j+M-j}=a^{M(j+1)}$$. Since $$M$$ is a product of two primes, $$M(j+1)$$ is a product of at least 3 primes, so $$a^{M(j+1)}\notin L_1$$, which proves $$L_1$$ is not regular by the pumping lemma.
Here is yet another proof. It is known that the number of integers at most $$n$$ which are the product of two primes is $$o(n)$$, see for example this answer, which gives the asymptotic $$\frac{n\log\log n}{\log n}$$. This means that your language is infinite yet has vanishing asymptotic density. This is impossible for a regular unary language.
• @gnasher729 Consider $1^*$ over $\{0,1\}$. Your claim becomes correct if you only consider the lengths of words in a language. – Yuval Filmus Oct 15 '19 at 12:34