I have an exercise where one is supposed to give a function that will enumerate the following language:

$L_1 = \{ a^pb^p \hspace{1mm} |\hspace{1mm} p \in \mathbb{N} \hspace{1mm} \wedge \text{ (P is a prime number )} \}$.

The solution is the following function: $f: \mathbb{N} \rightarrow \Sigma^*$ with $f(i) = a^{p_{i+1}}b^{p_{i+1}}$, where $p_{i+1}$ is the $(i+1)^{th}$ prime number, ordered by the prime's order.

Could anyone explain to why does this solution work? And especially why does the function include $p_{i+1}$ instead of $p_{i}$ ?

Thank you!


1 Answer 1


This function maps nonnegative integers to the set of integers of the form $a^pb^p$. Enumerating is trivial, just start $i$ from 0, compute $p_{i+1}$-th prime, compute $a^{p_{i+1}}b^{p_{i+1}}$ and output that number.

As for the index $i+1$, I guess that is because $0 \in N$ and it is assumed that primes are ordered starting from the index 1 not from 0, in other words we start from $p_1$ not from $p_0$, e.g., $f(0) = a^{p_1}b^{p_1}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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