@cody, Can't you give me a one line solution in a comment ?? :)

Thanks ! Your recursion operator consider binary strings as queue (FIFO). Wouldn't be more natural to have a recursion operator that consider binary strings as stacks (FILO) ?

As $\pi$ is a bijection it should at least read is argument which means it must at least take a linear time (using input size). So I don't think it should be made atomic in a natural definition of primitive recursive functions. But I may be wrong !

That's a nice suggestion, but unfortunately, in real computers, projection is not a O(1) operation. Or perhaps we could extend definitions from $\mathbb N$ to $\mathbb N^*$ with some kind of typing mechanism ?

How do you do the predecessor function with your system (function such that $0\mapsto 0$ and $(succ x)\mapsto x$ ?

Ok ! Too bad we know so few things about such questions :)

This seems quite remarkable ! Could you please elaborate in your answer on how, from n, you can find the primes factor of $d(n)$ ? Thank you

I don't understand. $n=2$, $m_2=1$, and $m_p=0$ for all other primes p. Hence $d(2)=\prod_p(m_p+1)=2\times1\times1\times\dots=2$.

I think that $d(n)=\prod_p(m_p+1)$ for all $n$. Thanks for your answer, I was hoping that at least on some values, D(n) could be guessed without computing all $d(i)$ $i\le n$.

What would prevent you to use a polynomial computation time $P(n)$ instead of $2^n$ in your proof ?