# Show that the function that counts the number of occurrences of 6 in a natural number is recursive primitive

I have to show that given $$f:\mathbb{N}\rightarrow\mathbb{N}$$ the function that returns the number of times $$6$$ appears in the input (for example $$f(436546)=2$$) is primitive recursive. The exercise says to assume that the functions $$rem(m,n)$$ and $$div(m,n)$$, which returns the remainder and the quotient, are recursive primitive (rp from now on).

What I tried so far:

1. Trying to build a recursive primitive schema: $$f(0)=0$$ $$f(n+1)=\phi(n,f(n))$$ where $$\phi$$ returns how many 6 are there in the input. The problem is that if $$n=23599$$ then to find the number of $$6$$ you have to divide and get the remainder $$3$$ times. In general you will have to do this remainder and division algorithm $$l$$-times where $$l$$ is the length of the input. So the recursive primitive schema won't work, I guess, because $$f(n)$$ does not tell you anything.

2. Trying to prove that $$proj_i:\mathbb{N}\rightarrow\mathbb{N}$$ is recursive primitive. Where for example $$proj_3(2345)=3$$. Now if this is proved to be true $$f$$ whould be recursive primitive because it's composition of rp functions:$$f(n)=\sum_{i=1}^{n} (10^i If this is correct, the only thing left to prove is that $$proj$$ is a pr function. Maybe like this $$proj_i(n)=rem(div(n,10^{(i-1)}),10)$$.

3. I know from other answers in this topic that if we can derive a simple enough algorithm then the function would be pr. In this i guess we can use this strategy, the problem is that we didn't cover it in the lectures, so i guess i can't use it. The algorithm would be very simple though, an iteration, using division and reminder.

• Write down the algorithm for counting digits and show that it is a composition of primitive recursive functions? Jun 6, 2022 at 12:15
• I can write it but i don't know how to prove then that it's composition of pr functions, i mean, there is a loop etc.. I guess i will go with my 2nd point if it is correct Jun 6, 2022 at 12:35

Here is a recursive function for your problem: \begin{align*} & \mathrm{count6}(n) = \mathrm{cond}(\mathrm{eq}(n, 0), 0,\\ & \quad \mathrm{add}(\\ & \quad \quad \mathrm{cond}(\mathrm{eq}(\mathrm{rem}(n, 10), 6), 1, 0), \mathrm{count6}(\mathrm{div}(n, 10))) \end{align*}
$$\mathrm{eq}$$ is defined as: $$\mathrm{eq}(x, y) = \begin{cases}1\,\mathrm{iff}\,x = y\\ 0\,\mathrm{otherwise}\end{cases}$$ and $$\mathrm{cond}$$ as: $$\mathrm{cond}(x, y, z) = \begin{cases}y\,\mathrm{iff}\,x=1\\ z\,\mathrm{otherwise}\end{cases}$$ Now you just need to show that $$\mathrm{eq}$$ and $$\mathrm{cond}$$ are recursive primitive which is tedious but not difficult.