Consider the following function: $$\varphi(m) = \begin{cases} 1 & m = 1 \vee \bigg( m= 2^n3^k \wedge \varphi(k)= 1 \bigg)\\ 0 & o.w.\end{cases}$$ So $\varphi$ evaluates whether an integer is of the form $2^{n_1}3^{2^{n_2}3^{(...)}}$
Now, I know how to get primitive recursion with just arity one, using composition, how to get to definition by cases, using the characteristic function and how to check whether a number is of the form $2^n3^k$ or not (see this, for example). My problem is with the other condition, of $\varphi(k) = 1$.
I'm using the following definition for primitive recurion, from the book Logic and Complexity, by Richard Lassaigne: $$ \begin{cases} f(x_1,...,x_n,0) = g(x_1,...,x_n) \\ f(x_1,...,x_n,S(y)) = h(x_1,...,x_n,y,f(x_1,...,x_n,y))\end{cases}$$
So the value of $\varphi(m)$ depends, not on the previous value of $m$, but on one of its prime factors.
I would think it's still a Primitve Recursive function, but haven't been able to prove it formaly.
Is it still a Primitive Recursive function? If so, how can I prove it?
The key issue is that we refer the value of $\varphi(k)$ for some $k<n$, to define $\varphi(n)$. It is apparently like that our primitive recursion does not allow to refer $\varphi(k)$ when defining $\varphi(n)$, save for when $k$ is the predecessor of $n$. We may dodge the problem by defining $\langle \varphi(0),\cdots,\varphi(n)\rangle$ simultaneously.
Let $\ell:\mathbb{N}^{<\omega}\to\mathbb{N}$ be the canonical primitive recursive function that codes the finite sequence of natural numbers into a single natural number. In addition, assume that $p:\mathbb{N\times N}\to \mathbb{N}$ be the projection, such that $p(k,\ell(a_0,\cdots,a_m))=a_k$. (If $k>m$, set $p(k,\ell(a_0,\cdots,a_m))=0$.)
Furthermore, let $\mathsf{app}(l,a)$ be the function which appends $a$ into the list of natural numbers $l$; that is, $\mathsf{app}(\ell(a_0,\cdots,a_m),a)=\ell(a_0,\cdots,a_m,a)$. We also define the length function $\mathsf{len}$, which gives the length of $\ell(a_0,\cdots,a_m)$.
Now consider the following functions: define $h$ as follows: $$h(l,m)=\begin{cases} \mathsf{app}(l,1) & \text{if there is $k<\mathsf{len}(l)$ s.t. }p(k,l)=1 \text{ and } \exists n<m: m=2^n 3^k,\\ \mathsf{app}(l,0) & \text{otherwise.} \end{cases}$$
Now define $\psi$ by the following primitive recursion: $\psi(0)=\ell(1)$ and $\psi(m+1)=h(\psi(m),m)$. Then $\varphi(m)=p(m,\psi(m))$ is the desired function.