examples of primitive recursive encoding
In this entry, we present three examples of primitive recursive encodings. In all the examples, the following notations are used: $\mathbb{N}$ is the set of all natural numbers^{} (including $0$), ${\mathbb{N}}^{*}$ is the set of all finite sequences^{} over $\mathbb{N}$, and $E:{\mathbb{N}}^{*}\to \mathbb{N}$ is the encoding in question. For any sequence ${a}_{1},\mathrm{\dots},{a}_{k}$, its image under $E$ is denoted by $\u27e8{a}_{1},\mathrm{\dots},{a}_{k}\u27e9$, and is called the sequence number corresponding to ${a}_{1},\mathrm{\dots},{a}_{k}$. Furthermore, $()$ denotes the empty sequence, and its sequence number is denoted by $\u27e8\u27e9$. The fact that the $E$ in each of the examples below is in fact encoding is proved in this entry (http://planetmath.org/EncodingWords).
Example 1. (Multiplicative encoding) $E$ is defined as follows:
$\u27e8\u27e9$  $:=$  $1,$  
$\u27e8{a}_{1},\mathrm{\dots},{a}_{k}\u27e9$  $:=$  ${p}_{1}^{s({a}_{1})}\mathrm{\cdots}{p}_{k}^{s({a}_{k})},$ 
where $s$ is the successor function, and ${p}_{1},\mathrm{\dots},{p}_{k}$ are the first $k$ prime numbers^{}.
To see that $E$ is primitive recursive, we verify the following:

•
the predicate^{} “$x$ is a sequence number” is primitive recursive: a number $x\in \mathbb{N}$ is a sequence number iff $x=1$ or, if $px$ for some prime $p$, then $qx$ for any prime $q\le p$. The predicates
$${\mathrm{\Phi}}_{1}:=\mathrm{`}\mathrm{`}px\text{for some prime}p\text{\u201d}\equiv \mathrm{`}\mathrm{`}\exists p\le x(P(p)\wedge (px))\text{\u201d},$$ $${\mathrm{\Phi}}_{2}:=\mathrm{`}\mathrm{`}p\text{is prime and}qx\text{for all primes}q\le p\text{\u201d}\equiv \mathrm{`}\mathrm{`}\forall q\le p(P(p)\wedge P(q)\wedge (qx))\text{\u201d}$$ where $P(r):=$ “$r$ is prime”, are primitive recursive by bounded quantification. Thus “$x$ is a sequence number” iff “$x=1$ or ${\mathrm{\Phi}}_{1}\to {\mathrm{\Phi}}_{2}$” iff “$(x=1)\vee (\mathrm{\neg}{\mathrm{\Phi}}_{1}\vee {\mathrm{\Phi}}_{2})$”, is primitive recursive as a result.

•
${E}_{k}({a}_{1},\mathrm{\dots},{a}_{k}):={p}_{1}^{s({a}_{1})}\mathrm{\cdots}{p}_{k}^{s({a}_{k})}$ is clearly primitive recursive.

•
$\mathrm{lh}(x)$ can be defined as the number of primes dividing $x$, which is primitive recursive.

•
${(x)}_{y}$ can be defined as the exponent of the $y$th prime in $x$ (the largest power of ${p}_{y}$ dividing $x$), which is again primitive recursive.
Example 2. (Encoding via a pairing function^{}) First, let $J:{\mathbb{N}}^{2}\to \mathbb{N}$ be a (primitive recursive) pairing function. For any $n\ge 2$, define
${J}_{2}({x}_{1},{x}_{2})$  $:=$  $J({x}_{1},{x}_{2})$  
${J}_{n+1}({x}_{1},\mathrm{\dots},{x}_{n},{x}_{n+1})$  $:=$  $J({x}_{1},{J}_{n}({x}_{2},\mathrm{\dots},{x}_{n+1})).$ 
Then define $E$ by
$\u27e8\u27e9$  $:=$  $0,$  
$\u27e8{a}_{1},\mathrm{\dots},{a}_{k}\u27e9$  $:=$  $J(k,{J}_{k}({a}_{1},\mathrm{\dots},{a}_{k})).$ 
$E$ is primitive recursive because

•
$E$ is a bijection, so the predicate “$x$ is a sequence number” is the same as “$x\in \mathbb{N}$”, which is clearly primitive recursive,

•
${E}_{k}({a}_{1},\mathrm{\dots},{a}_{k}):=J(k,{J}_{k}({a}_{1},\mathrm{\dots},{a}_{k}))$ is primitive recursive since both $J$ and ${J}_{k}$ are, the latter of which can be shown to be primitive recursive by induction^{},

•
The two functions $R,L:\mathbb{N}\to \mathbb{N}$ such that $J(L(m),R(m))=m$ are primitive recursive. So $\mathrm{lh}(x)=L(x)$ in particular is primitive recursive.

•
If ${J}_{k}({a}_{1},\mathrm{\dots},{a}_{k})=b$, then ${a}_{1}=L(b),{a}_{2}=LRL(b),\mathrm{\dots},{a}_{k1}={(LR)}^{k2}L(b)$, and ${a}_{k}=R{(LR)}^{k2}L(b)$. Thus,
$$ is primitive recursive, since each case is primitive recursive.
Example 3. (Digital Representation) Pick a positive integers $p>1$. Define $E$ by
$\u27e8\u27e9$  $:=$  $1$  
$\u27e8a\u27e9$  $:=$  ${p}^{s(a)}$  
$\u27e8{a}_{1},\mathrm{\dots},{a}_{k},{a}_{k+1}\u27e9$  $:=$  $\u27e8{a}_{1}\u27e9(\u27e8{a}_{2},\mathrm{\dots},{a}_{k+1}\u27e9+1).$ 
In other words,
$$\u27e8{a}_{1},\mathrm{\dots},{a}_{k}\u27e9={p}^{s({a}_{1})}+{p}^{s({a}_{1})+s({a}_{2})}+\mathrm{\cdots}{p}^{s({a}_{1})+\mathrm{\cdots}+s({a}_{k})}.$$  (1) 
To see that $E$ is primitive recursive, we first define three functions $f:\mathbb{N}\to \mathbb{N}$ given by $f(x):=\mathrm{lo}(p,x)$, the exponent of $p$ in $x$, $g:\mathbb{N}\to \mathbb{N}$ given by $g(x):=\mathrm{quo}(x,{p}^{f(x)})\dot{}1$, and $h:{\mathbb{N}}^{2}\to \mathbb{N}$ given by
$h(x,0)$  $:=$  $x$  
$h(x,n+1)$  $:=$  $g(h(x,n)).$ 
Clearly, $f,g,h$ are all primitive recursive. Furthermore, $h$ has the property that if $h(x,n)>0$, then $$, and therefore $h(x,n)=0$ for large enough $n$. Using $h$, we may proceed to show that $E$ is primitive recursive:

•
the predicate “$x$ is a sequence number” is equivalent^{} to the predicate
“$(x=1)\vee ((x>0)\wedge (\forall nph(x,n)))$”
which is equivalent to the predicate
“$(x=1)\vee ((x>0)\wedge (\forall n\le xph(x,n)))$”
since $p>1$. As the quantification is bounded, the predicate is primitive recursive.

•
${E}_{k}({a}_{1},\mathrm{\dots},{a}_{k})=\u27e8{a}_{1},\mathrm{\dots},{a}_{k}\u27e9$ is primitive recursive by equation (1) above.

•
$\mathrm{lh}(x)$ can be defined as the number of $n$ such that $h(x,n)\ne 0$, or
$$\sum _{i=0}^{x}\mathrm{sgn}(h(x,i)),$$ which is primitive recursive, because it is a bounded sum.

•
If $\u27e8{a}_{1},\mathrm{\dots},{a}_{k}\u27e9=x$, then $f(h(x,0))=s({a}_{1}),\mathrm{\dots},f(h(x,k1))=s({a}_{k})$. Therefore, ${(x)}_{y}$ is just $f(h(x,y\dot{}1))\dot{}1$, which is primitive recursive.
Remark. In the third example, $E$ can be more generally defined so that
$$\u27e8{a}_{1},\mathrm{\dots},{a}_{k},{a}_{k+1}\u27e9:=\u27e8{a}_{1}\u27e9(r\u27e8{a}_{2},\mathrm{\dots},{a}_{k+1}\u27e9+q),$$ 
provided that $p,q$ are coprime^{}. It is fairly straightforward to show that $E$ is again primitive recursive.
Title  examples of primitive recursive encoding 

Canonical name  ExamplesOfPrimitiveRecursiveEncoding 
Date of creation  20130322 19:06:23 
Last modified on  20130322 19:06:23 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  8 
Author  CWoo (3771) 
Entry type  Example 
Classification  msc 94A60 
Classification  msc 68Q45 
Classification  msc 68Q05 
Classification  msc 03D20 