1. El algoritmo de la división
Dados dos números enteros \(a\) y \(b\), con \(a\) no nulo, la división euclídea asocia un cociente \(q\in\mathbb{Z}\) y un resto \(r\in\mathbb{Z}\), únicos, que verifican: \[b=q\,a+r,\quad 0\leq r<|a|\]
| (%i6) | b:2^(2^5)+1; a:2^(2^4)+1$ r:b−a$ i:1$ while(r>a) do ( r:r−a, i:i+1 )$ print(«cociente:»,i,«resto»,r,» -> «,b,«=»,i,«*»,a,«+»,r)$ |
\[4294967297\]\[\mbox{cociente}:65535\, \mbox{resto}:2\,\to\, 4294967297=65535\cdot 65537+2\]
Veamos almacenando
| (%i13) | b:126$ a:33$ r:[b−a]$ i:1$ while(r[i]>a) do ( r:append(r,[r[i]−a]), i:i+1 )$ print(r)$ print(«cociente:»,i,«resto»,r[i],» -> «,b,«=»,i,«*»,a,«+»,r[i])$ |
\[\left[ 93{,}60{,}27\right]\]\[\mbox{cociente}:3,\,\mbox{resto}:27\,\to\, 126=3\cdot 3+2\]
1.1 cociente
Por el algoritmo de la divisón, el cociente de b/a será el entero q tal que
a*q<=b<a*(q+1)
a*q<=b<a*(q+1)
1.1.1 algoritmo
| (%i15) | cociente(b,a):=block([q], q:1, while(a·q<=b) do ( q:q+1 ), q−1 )$ cociente(126,33); |
\[3\]
1.1.2 Función floor() de maxima
floor(x) nos da el cociente:
Sea \(\lfloor\cdot \rfloor:\mathbb{R}\to\mathbb{Z}\), definida por,
\[\forall x\in\mathbb{R},\ \lfloor x\rfloor=\{n\in\mathbb{Z}:n\leq x<n+1\}\]
Sea \(\lfloor\cdot \rfloor:\mathbb{R}\to\mathbb{Z}\), definida por,
\[\forall x\in\mathbb{R},\ \lfloor x\rfloor=\{n\in\mathbb{Z}:n\leq x<n+1\}\]
| (%i16) | floor(126/33); |
\[3\]
1.2 resto
| (%i18) | resto(b,a):=block([q], q:1, while(a·q<=b) do ( q:q+1 ), b−a·(q−1) )$ resto(126,33); |
\[27\]
1.2.1 Función mod() de maxima
la función mod() nos da el resto:
| (%i19) | mod(126,33); |
\[27\]
1.3 Ejercicio
¿Cuál es el resto de la división de \(F_5=2^{2^5}+1\) por 13?
| (%i21) | F5:2^(2^5)+1$ print(F5,«=»,floor(F5/13),«*»,13,«+»,mod(F5,13))$ |
\[\]\[4294967297=330382099{\cdot}13+10\]
1.4 Ejercicio
¿Cuántos números hay entre 123 y 235 divisibles por 7?
| (%i25) | a:[]$ for i:126 thru 235 do ( if(mod(i,7)=0) then a:append(a,[i]) )$ a; length(a); |
\[\left[ 126{,}133{,}140{,}147{,}154{,}161{,}168{,}175{,}182{,}189{,}196{,}203{,}210{,}217{,}224{,}231\right] \]
\[16\]
Este resultado lo podemos ver observando que hay floor(n/m) número divisibles por m menores que n
| (%i26) | floor(235/7)−floor(126/7); |
\[15\]
Observemos que no da el mismo resultado pues 126 es divisible por 7 y se resta dos veces. Para ser correcto sería:
| (%i30) | ini:126$ fin:235$ num:floor(fin/7)−floor(ini/7)$ if(mod(ini,7)=0) then print(num+1) else print(num)$ |
16
1.5 Cifras de un número en base 10
Veamos una curiosidad. Para conocer el número de cifras que tiene un entero positivo cualquiera basta con calcular :\[\# n=\text{Nº cifras de }n=\lfloor\log(n)\rfloor+1\] donde \(\log(n)\) es el logaritmo decimal.
Ejercicio: ¿Cuántas cifras tiene \(F_{7}\)?
| (%i32) | F7:2^(2^7)+1; print(«número de cifras: «,floor(log(F7)/log(10))+1)$ |
número de cifras: 39
2 Algoritmo de la numeracion
Aprenderemos a expresar un número en base decimal a cualquier otra base
| (%i34) | F4:2^(2^4)+1; q:[floor(F4/7),mod(F4,7)]; |
\[65537\]
\[\left[ 9362{,}3\right] \]
| (%i35) | q:[floor(q[1]/7),mod(q[1],7)]; |
\[\left[ 1337{,}3\right] \]
| (%i36) | q:[floor(q[1]/7),mod(q[1],7)]; |
\[\left[ 191{,}0\right] \]
| (%i37) | q:[floor(q[1]/7),mod(q[1],7)]; |
\[\left[ 27{,}2\right] \]
| (%i38) | q:[floor(q[1]/7),mod(q[1],7)]; |
\[\left[ 3{,}6\right] \]
| (%i39) | q:[floor(q[1]/7),mod(q[1],7)]; |
\[\left[ 0{,}3\right] \]
Terminamos porque hemos llegado a un cociente igual a 0, el numero que buscamos es (362033) en base 7
2.1 Algoritmo
El proceso unificado es:
| (%i44) | F4:2^(2^4)+1$ q:[floor(F4/7),mod(F4,7)]$ m:matrix([q[1]],[q[2]])$ for i:1 thru 5 do ( q:[floor(q[1]/7),mod(q[1],7)], m:addcol(m,transpose(q)) )$ m; |
\[\begin{pmatrix}9362 & 1337 & 191 & 27 & 3 & 0\\3 & 3 & 0 & 2 & 6 & 3\end{pmatrix}\]
Recordemos que vimos que los dígitos de un número se calculaban con floor(log(n)/log(10))+1, pues los dígitos en cualquier base b es floor(log(n)/log(b))+1, por tanto en el for anterior basta con hacer el thru hasta floor(log(F4)/log(7))
2.1.1 Ejercicio
¿Cuánto suman los dígitos de F4 en base 7?
| (%i45) | sum(m[2,i],i,1,6); |
\[17\]
2.1.2 Ejercicio
Expresar F5 en base 8
| (%i50) | F5:2^(2^5)+1$ q:floor(F5/8)$ d:[mod(F5,8)]$ while(q>0) do( d:append(d,[mod(q,8)]), q:floor(q/8) )$ concat(F5, es (,sum(d[i]·10^(i−1),i,1,length(d)),«)_»,8); |
\[4294967297 \mbox{ es } (40000000001)_8\]
2.2 Función algoritmo
Veamos una función que nos de la expresión de cualquier número en base 10 a base b.
| (%i52) | base(n,b):=block([q,d], q:floor(n/b), d:[mod(n,b)], while(q>0) do ( d:append(d,[mod(q,b)]), q:floor(q/b) ), d )$/* Esta función nos da los dígitos*/ num_base(n,b):=block([d,i,p], d:base(n,b), p:sum(d[i]·10^(i−1),i,1,length(d)), concat(«(«,p,«)_»,b) )$/*Con esta función lo expresamos en base b*/ |
| (%i53) | print(F4,«=»,num_base(F4,7))$ |
\[65537=(362033)_7\]
| (%i55) | F6:2^(2^6)+1$print(num_base(F6,8))$ |
\[(2000000000000000000001)_8\]
| (%i57) | F7:2^(2^7)+1$print(num_base(F7,8))$ |
\[(4000000000000000000000000000000000000000001)_8\]