martes, 25 de septiembre de 2012

De SOPFR en SOPFR

(Con esta entrada participamos en la edición 3,141592 del  Carnaval de Matemáticas cuyo anfitrión será un blog de muchísima calidad: ZTF News)


¿Qué te parece esta igualdad? Quizás la hayas visto ya publicada.

2*2*2*3*3*3*5*5*5 = (2+2+2+3+3+3+5+5+5)3

Ambos miembros dan como resultado 27000.

No es la única de este tipo. Ahí va otra:

3*3*3*3*3*3*3*5*5*5*5*5*5*5*7*7*7*7*7*7*7= (3+3+3+3+3+3+3+5+5+5+5+5+5+5+7+7+7+7+7+7+7)7

Aquí el resultado común es 140710042265625, como puedes comprobar con alguna calculadora potente.

Estas dos igualdades no provienen de la casualidad, sino que se desprenden de unas propiedades que veremos a continuación. De hecho hay infinitas igualdades de este tipo, cada vez más complicadas.

La función SOPFR

Quienes acostumbráis a tratar estos temas habréis adivinado que se habrá usado alguna función aditiva, y así es. Todo esto se basa en el logaritmo entero o función SOPFR, que ya tratamos en otra entrada (http://hojaynumeros.blogspot.com.es/2009/11/logaritmo-entero-1.html). En ella definimos SOPFR(N) como la suma de todos los factores primos de N contando sus multiplicidades y explicamos que es una función aditiva (por eso recibe el nombre de logaritmo entero), porque se cumple que

sopfr(a*b)=sopfr(a)+sopfr(b).

Si volvemos a la primera igualdad nos daremos cuenta de que el primer miembro es la factorización prima de 27000=23*33*53 y el contenido del paréntesis del segundo miembro es la suma de sus factores primos, luego es sopfr(27000). Por tanto, lo que expresa la igualdad es que

27000=(sopfr(27000))3

Del mismo modo, la segunda se puede escribir así:

140710042265625=(sopfr(140710042265625))7

Nos las tenemos que ver con números muy grandes, pero afortunadamente una propiedad que vamos a demostrar nos facilitará la tarea de encontrar más igualdades de este tipo. La explicamos por partes:

(a) Si un número natural es potencia de otro, ambos comparten los mismos factores primos. No hay que pensar esto mucho. Imagina el caso contrario y sería imposible que uno fuera potencia del otro. Más aún, los exponentes de la potencia serán múltiplos de los correspondientes en la base. Elemental también.

(b) Como SOPFR es una función aditiva, se cumplirá que

SOPFR(AB) = B*SOPFR(A)

(c) Las igualdades presentadas son del tipo N=(SOPFR(N))K. Si aplicamos lo explicado en (b) obtendremos

SOPFR(N)=K*SOPFR(SOPFR(N))

(d) A la inversa, si M cumple que M=k*SOPFR(M) se tendrá que

SOPFR(MK)=K*SOPFR(M)= M

Hemos llegado a esto:

Si un número es potencia de su logaritmo entero, este a su vez será múltiplo de su respectivo logaritmo entero y a la inversa

No te dejes impresionar y léelo bien: en lugar de buscar números enormes que son grandes potencias de otros, podemos comenzar por buscar aquellos que son múltiplos de su logaritmo entero y el cociente entre ambos será el exponente de la potencia buscada.

Lo del principio sobrepasaba la capacidad de las hojas de cálculo, pero esta otra versión no. En lugar de buscar N buscaremos SOPFR(N) y después la elevaremos, si podemos, a la potencia k.

Nos dedicaremos sólo a potencias no triviales, porque si k=1 nos resultaría el 4 y todos los números primos (¿por qué?)


Búsqueda de números múltiplos de su logaritmo entero

La codificación de la función SOPFR no es difícil. Hemos publicado varias parecidas.

Public Function sopfr(n) ' logaritmo entero -  suma primos con repetición
Dim ene, f, c, s

ene = n
f = 1
s = 0
While ene > 1
f = f + 1
While ene / f = Int(ene / f)
ene = ene / f
s = s + f
Wend
Wend
sopfr = s
End Function

Recorre los posibles divisores de N y los va acumulando en un contador S que después se convertirá en SOPFR. Al ir dividiendo n entre los divisores que salen, se garantiza que todos son primos.

Con esta función es fácil ir encontrando aquellos números que son múltiplos no triviales de su función SOPFR (excluimos cuando son iguales, para librarnos de los primos). Estos son los primeros:




Número N
SOPFR(N)
Cociente K
16
8
2
27
9
3
30
10
3
60
12
5
70
14
5
72
12
6
84
14
6
105
15
7
150
15
10
180
15
12
220
20
11
231
21
11
240
16
15
256
16
16
286
26
11
288
16
18



(Están publicados en http://oeis.org/A046346)

Si has entendido la parte teórica (comprendemos que no es fácil), comprenderás que si elevamos los números de la primera columna a los de la tercera, resultarán todos los que cumplen

N=(SOPFR(N))K


Resultan estos:

256, 19683, 27000, 777600000, 1680700000, 139314069504, 351298031616, 140710042265625, 5766503906250000000000, 1156831381426176000000000000, 58431830141132800000000000, 99938258857146531850367031,…

La hemos publicado en http://oeis.org/A216397

Con cualquiera de ellos puedes construir igualdades tan llamativas como las que presentamos al principio.

viernes, 14 de septiembre de 2012

¿Qué hay detrás de los decimales periódicos? (2)



Con el apoyo de la teoría explicada en la anterior entrada describiremos a continuación una sencilla herramienta para hojas de cálculo que encuentra el anteperiodo y el periodo de un desarrollo decimal.

Necesitaremos las siguientes operaciones:

(1) Simplificar la fracción cuyo desarrollo decimal deseamos conocer. Esto se consigue en las hojas de cálculo dividiendo las celdas del numerador y del denominador por su MCD mediante la función M.C.D(A;B)

(2) Extraer del denominador los factores 2 y 5 tomando nota de sus exponentes (cero si no figuran) y quedándonos con el máximo, que será el número de cifras del anteperiodo

Un código posible para la extracción del 2 (igual se procede para el 5) puede ser este:

Public Function expo2(n)
Dim e, m
m = n
e = 0
While m / 2 = m \ 2
e = e + 1
m = m / 2
Wend
expo2 = e
End Function

Nos devuelve cero si el 2 no es divisor del denominador y el exponente en caso afirmativo. En la imagen puedes ver la disposición de cálculo que hemos elegido. El máximo se consigue con la función  MAX(A;B) aplicada a los dos exponentes (del 2 y del 5)










(3) Obtener la parte del denominador coprima con 10. Para ello basta dividir el denominador entre las dos potencias de 2 y 5 obtenidas.

(4) Obtener el gaussiano de 10 respecto a esa parte coprima. Podríamos usar exponenciación modular (ver http://hojaynumeros.blogspot.com.es/2012/03/de-la-multiplicacion-rusa-la.html), pero en este caso, como la generación de restos se realiza mediante mltiplicaciones por 10, hemos elegido el método directo, que no es demasiado lento en el rango de números que manejan las hojas.

(Añadimos comentarios al código)

Public Function gauss10(m)
Dim r, g, i

g = 1
r = 10 - m * (10 \ m) ‘Obtenemos el primer resto
While r <> 1 ‘Mientras no encontremos un resto igual a uno, seguimos
r = r * 10  ‘Cada resto es igual al anterior multiplicado por 10
r = r - m * (r \ m) ‘y convertido en resto módulo m
g = g + 1 ‘En cada ciclo aumenta el gaussiano
Wend
gauss10 = g
End Function








En el caso de la primera imagen el denominador era 30940, que contenía como factor 22*5. Eliminado este, quedó reducido a 1547, y aplicando el cálculo del gaussiano resulta nada menos que un periodo de 48 cifras, fuera del alcance ordinario de una hoja de cálculo.

(5) Expresión del anteperiodo y el periodo. Cuando ambos presentan muchas cifras, como en el caso del ejemplo, es mejor expresarlas en forma de texto, y no de número. El procedimiento consiste básicamente en el mismo usado para encontrar el gaussiano, multiplicar cada resto por 10 y reducirlo a resto módulo el denominador. Sirve igual para las cifras periódicas que para las no periódicas. La diferencia ahora es que los restos los convertimos en texto y los vamos incorporando a una cadena del mismo tipo.

El procedimiento completo puede resultar aburrido y dejamos su estudio a quien descargue la herramienta e inspeccione su código. Para el resto de lectores resultará una buena forma de comprobar los cálculos manuales.

Al necesitar calcular por separado la parte entera, el anteperiodo y el periodo, hemos preferido usar un botón y una macro para mayor comodidad:







Tienes esta herramienta en la dirección

http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#periodo

viernes, 7 de septiembre de 2012

¿Qué hay detrás de los decimales periódicos? (1)



Hace unos meses comentaba con un amigo el tratamiento que se podía hacer con hoja de cálculo de los decimales periódicos. Ya en una de las primeras entradas de este blog encontrábamos los decimales de este tipo

http://hojaynumeros.blogspot.com.es/2008/10/grandes-periodos.html

Lo que no nos planteamos en esa ocasión fue el cálculo del número de decimales del periodo, su longitud, mediante un cálculo directo, ni tampoco la del anteperiodo. Lo abordamos hoy mediante la ayuda de las congruencias y de los restos potenciales.

¿Qué es sacar decimales en una división o en una fracción?

Fundamentalmente se trata de multiplicar los distintos restos por 10 y hallar su nuevo resto respecto al cociente. Cuando este se repita, ya hay periodo.

Si tenemos una división entera de dividendo D, divisor d, cociente Q y resto R, sabemos que están relacionados por D=d*Q+R. Si multiplicamos R por 10 y volvemos a dividir entre Q (sacar el primer decimal) obtendremos R*10=d*q1+r1, donde q1 es el primer decimal y r1 el siguiente resto. Si unimos ambas relaciones se obtendrá

 D*10=(10*Q+q1)*d+r1

El paréntesis representa el nuevo cociente con un decimal, pero sin coma, es decir, multiplicado por 10. Ya hemos sacado un decimal.

Si damos otros pasos obtendremos

D*102=(102*Q+10*q1+q2)*d+r2
D*103=(103*Q+102*q1+10*q2+q3)*d+r3


Desarrollo decimal exacto o periódico

Sabemos desde la enseñanza secundaria que si el divisor sólo posee los factores primos 2 y 5 el proceso anterior nos lleva a un resto nulo y al fin del cálculo, lo que llamamos decimal exacto. Si existen otros factores aparecerá un anteperiodo si entre ellos figuran el 2 o el 5 y finalmente, el decimal se conviertirá en periódico con un periodo inferior o igual a d-1.

¿Qué hay detrás de estos hechos?: los restos potenciales del 10 respecto al divisor.

Los repasamos.

Restos potenciales

Imaginemos las congruencias definidas respecto a un módulo m

(http://hojamat.es/sindecimales/congruencias/teoria/teorcong.pdf)

y sea n un número natural. Llamaremos Restos potenciales de n respecto a m a los
restos producidos por las distintas potencias naturales de n respecto al módulo m.

Por ejemplo, los restos potenciales de 5 respecto al módulo 3 son:

De 50 el resto es 1, de 51 el resto es 2, de 52 el 1, de 53 el 2, etc. y así siguen de forma periódica.

Se puede ver muy fácilmente que si se tiene un resto potencial de n respecto a m, para conseguir el siguiente basta multiplicar el actual de nuevo por n y hallarle el resto respecto a m. No hay que hallar la potencia completa.

El conjunto de restos potenciales sigue unas pautas muy sencillas:

1. Si m sólo contiene los factores primos de n, se llegará a cierta potencia de n que será múltiplo de m y por tanto, a partir de ella, todos los restos potenciales serán nulos.

Sería el caso, por ejemplo, de los restos potenciales de 60 respecto al 18, cuyos factores primos 2 y 3 lo son también de 60. La potencia k que consiga que 60k sea múltiplo de 18 producirá un resto cero y al seguir multiplicando por 60 también serán nulos los restos que aparezcan.

600º1(mod 18

601º6 (mod 18

602º0 (mod 18

603º0 (mod 18

604º0 (mod 18

…..

Ya todos serían nulos. Hemos tenido que llegar a 602 para absorber el 32 que figura en el desarrollo de 18=2*32

(Este desarrollo y los siguientes los puedes comprobar con la herramienta “Restos potenciales” que puedes descargar desde

http://hojamat.es/sindecimales/congruencias/inicongruencias.htm)

En general, habrá que llegar a la potencia que viene determinada por el mayor de los cocientes (por exceso si no son enteros) entre los exponentes de los factores primos de m y sus homólogos en n.

En efecto, si n=paqbrc    y m=pa’qb’rc’ supongamos que elevamos n a un exponente k y que con eso conseguimos que nk sea múltiplo de m. Esto nos llevaría a que
nk=( paqbrc)k = pakqbkrck sea múltiplo de m= pa’qb’rc’, que a su vez implica que ak³a’, bk³b’ y ck³c’, lo que supone que k sea mayor o igual que los cocientes a/a’, b/b’ y c/c’, tal como hemos afirmado: el mínimo valor de k es el mayor cociente tomado por exceso entre los exponentes en n y sus homólogos en m.

2. Si m es primo con n, los restos son periódicos de periodo el índice o gaussiano de n respecto a m. El resto 1 se producirá en los múltiplos de ese gaussiano.

Si recorremos los restos potenciales de n respecto a m, si ambos son primos entre sí, por el teorema de Euler se cumplirá que

nj(m)º1 (mod m

Se representa mediante j(m) la indicatriz de Euler
(ver http://hojaynumeros.blogspot.com.es/2012/07/la-herencia-de-euclides-5-la-funcion.html)

Así que a partir de una de las potencias aparece el resto 1 y al seguir multiplicando por n irán apareciendo los demás de forma periódica.

Otra forma de verlo es que en este caso n es inversible en Zm, no divisor de cero, por lo que sus potencias producirán todas restos no nulos (ver http://hojaynumeros.blogspot.com.es/2012/06/la-herencia-de-euclides-3-el-anillo-zm.html) y esto nos llevará a que se repita alguno, porque su máximo número es m-1.

Sean dos potencias de n que producen el mismo resto: nrºnr+h (mod m. En ese caso se cumplirá que nr+h-nr=nr(nh-1) será múltiplo de m. Pero este es primo con n, luego no puede dividir a nr y lo hará a nh-1. Esto quiere decir que nhº1 (mod m y podemos afirmar que:

En general, no hay que llegar hasta el exponente j(m) para conseguir un resto igual a 1. Llamaremos gaussiano, orden o índice de n respecto a m al menor exponente k al que hay que elevar n para producir resto 1 respecto al módulo m.

Por tanto, cuando n y m son primos entre sí, los restos potenciales forman una sucesión periódica a partir del primero con periodo igual al gaussiano de n respecto a m.


3. Por último, si m posee los mismos factores primos de n y alguno más, la sucesión comenzará con unos restos no periódicos, tantos como el mayor cociente entre los factores comunes de uno y otro (ver primer caso),  a los que seguirán otros periódicos.

Si m contiene factores comunes con n y otros no comunes, lo podemos descomponer así: m=m1*m2, donde m1 contiene los comunes y m2 los no comunes. Si volvemos a repetir el análisis anterior sobre potencias cuyos restos se repiten, llegaremos a esto:
nr(nh-1) será múltiplo de m=m1*m2 con la suposición de que nr produce el primer resto que se repite.
Pero m2 es primo con nr, luego dividirá a nh-1. Con un razonamiento similar al del caso 1, llegaremos a que el menor valor de h es el gaussiano de n respecto a m2.

De igual forma, si m1 sólo contiene factores primos comunes con n, no podrá dividir a nh-1, luego lo hará a nr.   Hemos indicado que nr produce el primer resto que se repite, luego todos los anteriores no pertenecerán a la parte periódica, y formarán el anteperiodo, ya que la condición de que m1 divida a nr garantiza que r es mayor que 0. Para que nr sea múltiplo de m1 sólo tendremos que usar el criterio del mayor cociente de factores comunes, como en el primer caso.

Aplicación a los decimales periódicos

Todo lo que hemos aprendido se aplica a la generación de decimales. Aquí n=10, luego los factores comunes sólo serán el 2 y el 5. El divisor d equivale a la m que hemos usado en los razonamientos.

Antes de generarlos, la fracción D/d se habrá convertido en irreducible, luego D y d son primos entre sí. Esto es muy importante, porque según una conocida propiedad de la aritmética modular, si la sucesión 10, 102, 103, 104,…la multiplicamos por D, coprimo con el módulo d, la sucesión resultante D*10, D*102, D*103, D*104,…forma un sistema de restos con las mismas propiedades, salvo quizás los valores de los mismos.

Resumiendo:

Si d sólo contiene los factores 2 y 5, el proceso de generación de decimales  termina con un rk=0 (cuando la potencia de 10 del primer miembro contenga 2 y 5 con exponentes mayores o iguales a los de d) y se obtendrá un desarrollo decimal exacto.

Si el divisor d no contiene como factores ni el 2 ni el 5 se producirá un decimal periódico puro en la que todos los restos se repetirán a partir del primero, con periodo igual al gaussiano de 10 respecto al divisor d

Si d contiene además del 2 o 5 otros factores, el desarrollo comenzará con k decimales no periódicos (el anteperiodo), siendo k el mayor exponente tomado entre los del 2 y el 5 que figuran en la factorización prima de d, seguidos de un periodo con tantas cifras como indique el gaussiano de 10 respecto a la parte de d que no contiene 2 ni 5. Se formaría un decimal periódico mixto

En la siguiente entrada describiremos una sencilla herramienta para hojas de cálculo que encuentra el anteperiodo y el periodo de un desarrollo decimal.