División integral por minimalización

Question

Dados enteros no negativos $m,n$ con $m\geq n>0$ . Visite $q,r\geq 0$ con $m=q\cdot n + r$ donde $0\leq r<n$ . Utiliza el formalismo de las funciones recursivas primitivas y nada más.

Quiero utilizar la minimalización acotada: Dado $g:{\Bbb N}_0^2\rightarrow{\Bbb N}_0$ definir $f:{\Bbb N}_0\rightarrow{\Bbb N}_0$ con $$f(x) = \mu [y\leq z](g(x,y)=0)$$ que es el valor más pequeño $y$ tal que $g(x,y)=0$ y $0\leq y\leq z$ (es decir, la búsqueda está acotada). Si $y$ no existe, el valor $y+1$ se emite.

En el caso anterior, considere $$\mu[q\leq m](m-q\cdot n=0)$$ donde la resta $-$ nunca recibe un valor negativo. Aquí los casos $m=qn$ y $m\ne qn$ por lo que es difícil ofrecer una expresión única. Se puede utilizar la función de signo ${\rm sgn}(x)$ que es 1 si $x>0$ y 0 si $x=0$ .

Answer 1

Bueno, tengo una solución. Para ello, vamos a $m\geq n>0$ .

$f(n,m) = \chi_D(n,m) \cdot \mu[q\leq m](m-q\cdot n=0) + ({\rm csg}(\chi_D(n,m)) \cdot [\mu[q\leq m](m-q\cdot n=0) - 1],$

donde $\chi_D(n,m) = 1$ si $n$ divide $m$ y $0$ en caso contrario y la resta es ''condicional'', es decir, $x-y = 0$ si $x\leq y$ y la función de cofirmación es ${\rm csg}(x) = 0$ si $x>0$ y $1$ si $x=0$ .

Ejemplo:

$m=6$ y $n=2$ . Entonces el primer sumando da el resultado: $\chi_D(2,6) = 1$ y $\mu[q\leq m](m-q\cdot n=0)$ produce $q=3$ : $7=3\cdot 2$ .

$m=7$ y $n=2$ . A continuación, el segundo sumando proporciona el resultado: ${\rm csg}(\chi_D(2,7)) = 1$ y $\mu[q\leq m](m-q\cdot n=0)$ produce $q=4$ por lo que tenemos que restar 1: $7=3\cdot 2+1$ .

Dado que todas las funciones implicadas son recursivas primitivas, la función $f$ es recursivo primitivo. Hecho.