Let $\varphi(x)=2x$ if $x$ is a perfect square, $\varphi(x) = 2x+1$ otherwise. Show $\varphi$ is primitive recursive.

In proving $\varphi$ to be a p.r. function I think it could come in handy the following theorem:

Let $\mathcal C$ be a PRC class. Let the functions $g$, $h$ and the predicate $P$ belong to $\mathcal C$, let

\begin{equation} f(x_1,\ldots, x_n) = \begin{cases} g(x_1, \ldots, x_n) \;\;\;\;\;\text{ if } P(x_1, \ldots, x_n)\\ h(x_1,\ldots,x_n) \;\;\;\;\;\text{ otherwise} \end{cases} \end{equation} Then $f$ belongs to $\mathcal C$ because $$f(x_1, \ldots, x_n) = g(x_1, \ldots, x_n) \cdot P(x_1, \ldots, x_n) + g(x_1, \ldots, x_n) \cdot \alpha(P(x_1, \ldots, x_n))$$ where

\begin{equation} \alpha(x) = \begin{cases} 1 \;\;\;\;\;\text{ if } x = 0\\ 0 \;\;\;\;\;\text{ if } x \neq 0 \end{cases} \end{equation}

and $\alpha(x)$ is p.r.

So similarly I would say that $\varphi(x)$ is p.r. as

\begin{equation} \varphi(x) = \begin{cases} 2x \;\;\;\;\;\;\;\;\;\;\;\text{ if } x = t \cdot t \\ 2x+1 \;\;\;\;\;\text{ otherwise} \end{cases} \end{equation} hence $$\varphi(x) = 2x \cdot P(x_1, \ldots, x_n) + (2x+1) \cdot \alpha(P(x_1, \ldots, x_n))$$ and $P$ is a primitive recursive predicate as $x \cdot y$ is p.r. and also $x = y$.

Does everything hold? Is there anything wrong? If so, since I am tackling this kind of exercise for the fist time, will you please tell me what's the proper way to solve this?

  • 2
    $\begingroup$ You need to show that you can write an "if,then,else"-function, i.e. $f(x,y,z) = y$ if $x$ is true and $z$ otherwise. Then you need to show that you can test whether or not $x$ is a perfect square. This you can do by iterating $i$ from 1 to $x$ testing if $i^2 = x$. $\endgroup$
    – Pål GD
    Jan 17, 2013 at 18:54

1 Answer 1


To see if $x$ is a perfect square is easy (for example, by adding 1 + 3 + 5 ... you get the succesive squares); once that is settled your problem is solved. Think of such problems primarily as programming asignments (in a rather cruel programming language).

  • 1
    $\begingroup$ Not so cruel, once you developed the right tools. All you need here is bounded existential quantification: is_square(x) = $\exists n \le x, n^2 =x$. $\endgroup$ Feb 23, 2017 at 12:57

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.