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:
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.
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<n) \times eq(proj_i(n),6)$$ 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)$.
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.
