We consider the function $g$ which associates the number of prime integers with $n$ in the set $\{0,...,n\}$. I have to prove that $g$ is a primitive recursive function.

First I defined the set $A=\{i∈\{0,...,n\}:\gcd(i,n)=1\}$. To show that $A$ is a primitive recursive set I said that : $\{0,...,n\}$ is primitive recursive because ${k}$ is primitive recursive by characteristic function and $\{0,...,n\}=\bigcup\limits_{k=0}^{n} \{k\}$ is primitive recursive by the property of $⋃$.

Then the function $\gcd$ is primitive recursive. Indeed we can see that with the function $lcm$. We have $lcm(a,b)=μk≤ab (∃j,l≤ab,aj=k∧bl=k)$ which is a primitive recursive expression. Then by operator division $\gcd$ is a primitive recursive function.

So $A$ is a primitive recursive set.

Now, to prove that $g$ is primitive recursive can I take :

$g(i)=\sum\limits_{i=0}^{n} \chi_{A}(i)$ with $χ_A(i)=1$ if $i∈A$.and $g$ is a finite sum of primitive recursive functions so it is primitive recursive?

  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Jun 17 '16 at 20:12
  • $\begingroup$ @Raphael Ok I will try to modify $\endgroup$ – Maman Jun 17 '16 at 22:20

A computable function is primitive recursive if and only if it is upper-bounded by some primitive recursive function. Your function (usually known as Euler's totient function $\varphi$) is clearly computable, and is bounded by the function $n \mapsto n+1$, which is clearly primitive recursive. Hence your function is primitive recursive.

| cite | improve this answer | |
  • $\begingroup$ Really nice and fast ! Impressive. I think my answer is more technical $\endgroup$ – Maman Jun 17 '16 at 22:16
  • $\begingroup$ @Maman For the purpose of exercise hand-ins, note that you'll have to have either a theorem for this upper-bounding fact, or need to prove that. As far as I can tell, it's not at all trivial. $\endgroup$ – Raphael Jun 18 '16 at 9:37

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.