miércoles, 21 de diciembre de 2011

El algoritmo de Moessner

(Con esta entrada participamos en el Carnaval de Matemáticas 2.9, cuyo anfitrión es el blog "Que no te aburran las M@TES")



Presentamos hoy una curiosidad matemática a base de cribados: toma la lista de los primeros números naturales.
1    2    3    4    5    6    7    8    9    10   11    12    13     14

Tacha después uno de cada cuatro, comenzando con el mismo 4:
1    2    3    5    6    7    9    10    11    13   14

Después escribe la lista de sus sumas parciales.
1    3    6    11    17    24    33    43    54    67    81

Y ahora tachas de tres en tres, sumando después de nuevo.
1    3    11    17    33    43    67    81
1    4    15    32    65    108   175    256

Después tachas de dos en dos
1    15    65    175

Y sumas
1    16    81    256

El resultado es la serie de las potencias cuartas de los naturales. Recuerda que hemos comenzando tachando de cuatro en cuatro. ¿Funcionará con el tres?


Lo escribimos sin explicaciones:

1    2    4    5    7    8    10    11    13    14    16    17
1    3    7   12  19  27  37  48  61  75  91  108
1    7   19   37    61     91
1    8   27  64   125   216

Resultan los cubos. Prueba de dos en dos y obtendrás los cuadrados. ¿Funcionará esto siempre? Este algoritmo lo propuso Alfred Moessner y fue demostrada su validez para cualquier valor natural por Oskar Perron en 1951 usando la inducción matemática.

Nuestro objetivo hoy es reproducir este algoritmo con hoja de cálculo, que por cierto no es nada fácil. Contiene una verdadera trampa, que es la posible confusión entre valores y posiciones. Lo vemos:



En la celda A9 escribimos la amplitud de los saltos. En la imagen está preparado para que resulten las cuartas potencias. La hoja se encarga de ir restando una unidad hacia abajo y dejar de escribir cuando se llegue a 1. El modelo está preparado para llegar a 5, pero si lo descargas puedes ampliarlo a tu gusto.

La fila 7 contiene la serie de números naturales. Después se van repitiendo hacia abajo tres filas:

Primera: Es un artificio, pues la hoja debe buscar el elemento a tachar cada vez más lejos, y dependiendo del valor de A9. Esto lo hemos resuelto con la fórmula (usamos la contenida en C8)

=SI(ESNUMERO($A12);SI(RESIDUO(C$7-1;$A12)=0;B8+1;B8);"")

En primer lugar verifica si aún quedan saltos por dar con ESNUMERO($A12). Después encuentra el residuo del número de arriba respecto al salto y hace avanzar el contador (B8) si ese número es múltiplo del salto. Así medimos el alejamiento del elemento que debemos tachar. Observa que van aumentando los valores cada tres (representan los tres supervivientes después de tachar)

Segunda: Aquí se eligen los números entre los de arriba, saltando los que ocupan un lugar múltiplo de 3. Después, con la función DESREF se dirigen a la celda adecuada para copiar el número:

=SI(ESNUMERO($A12);DESREF(C9;-2;C8);"")

DESREF se dirige a dos filas más arriba (-2) y salta según indica el valor de arriba (C8). Como esta contiene los saltos adecuados, cada vez que cambie su valor se tacha un número. Es lo que queríamos. No es fácil de entender y cuesta encontrar el procedimiento.

Tercera: Se limita a acumular sumas, y al llegar al nivel 1 produce las potencias deseadas.
Aunque esto no pasa de una curiosidad, la construcción del algoritmo es apasionante. Este que ofrecemos no usa macros, y lo puedes descargar en dos versiones desde

hojamat.es/blog/moessner.zip

jueves, 15 de diciembre de 2011

Emparedado de cuadrados (4)

¡Que quedan flecos sueltos!

Después de tres entradas sabrás ya mucho sobre los cuadrados que rodean a un número natural. Demuéstralo:

(a)  Si A divide a B, ¿crees que la parte cuadrada de A dividirá a la de B?

(b) ¿Ocurrirá lo mismo con los menores múltiplos cuadrados?

(c) Si A divide a B y son distintos, ¿cuándo se dará que PC(A)=PC(B)?

(d) ¿Podemos relacionar de igual forma la parte libre de A con la de B?

(e) Considera el máximo común divisor de la parte cuadrada y la libre de un número natural N ¿qué podremos afirmar de él? ¿Se comportará como una función multiplicativa?

martes, 13 de diciembre de 2011

Emparedado de cuadrados (3)

En esta entrada comprobaremos la potencia del concepto de función multiplicativa. Usaremos fundamentalmente dos propiedades:

(1) Según vimos en la entrada correspondiente a las funciones multiplicativas, si  g(x) es una función multiplicativa, entonces, la función f(n) definida por


en la que el sumatorio recorre todos los divisores de n, también es multiplicativa.

(2) Debemos recordar también que la definición de una función multiplicativa basta hacerla para los factores primarios pe de un número, siendo p un factor primo y e su exponente.

Estudiaremos esas sumas que recorren todos los divisores en las funciones multiplicativas estudiadas en la entrada anterior

Suma de las partes cuadradas de los divisores de N SPC(N)


Es una función multiplicativa

Si la parte cuadrada de un número es multiplicativa, su suma a lo largo de los divisores del número también lo será. Una forma rápida de encontrar esa suma se consigue con el Buscador de Naturales, usando estas condiciones y consultando después la suma en el evaluador.  Observa cómo lo hemos conseguido para el número 252= 2*2*3*3*7












Se ha definido una búsqueda entre 1 y 252, con las condiciones DIVISOR DE 252 y EVALUAR PARTECUAD(N) y nos da un resultado de 132.

Así que la suma de esas partes cuadradas (SPC(N)) para 252 es 132.

Esta función está publicada en http://oeis.org/A068976 y ahí se dan fórmulas y desarrollos para el cálculo de la misma. Es claro que es multiplicativa y por eso la fórmula de Vladeta Jovovic que se propone en esa página sólo define la función para un factor primario pe.

La escribimos de forma algebraica aplicada a pe:

Si e es par:



Si e es impar:



¿Cómo demostrarlo? Te damos una idea.

Considera todos los divisores del número pe:

1   p   p2   p3   p4   p5   p6 … pe-1   pe


Si les aplicamos la función “parte cuadrada” PC deberemos truncar los exponentes al máximo número par que contienen.

Si e es par quedaría:

1   1   p2   p2   p4   p4   p6 … pe-2   pe   que se puede descomponer en dos sumas:

SPC(pe)=( 1 +  p2 +   p4 +   p6 … pe  )+(   1 +  p2 +   p4 +   p6 … pe-2 ) que al final desembocan en la suma propuesta

Si es impar las dos sumas serían iguales, luego

SPC(pe)=2( 1 +  p2 +   p4 +   p6 … pe-1 ) que también nos lleva a la fórmula propuesta arriba.

Aplicamos estas fórmulas a 252= 22*32*7, en el que aplicaría el caso par para el 2 y el 3 y el impar para el 7:

SPC(252)=(15/3+3/3)(80/8+8/8)(2*48/48)=6*11*2=132, como era de esperar.

Si practicas estos cálculos con otros números, tanto manualmente como con el Buscador o las fórmulas aprenderás mucho.

Suma de partes libres SPL(N)

Es también multiplicativa

Con los mismos procedimientos y propiedades podemos intentar sumar las partes libres de los divisores de un número.

Con el Buscador podemos encontrar esa suma para 1102, por ejemplo:












Las condiciones usadas son DIVISOR DE 1102 y EVALUAR N/PARTECUAD(N), ya que esa es una definición de parte libre. Recorremos los números del 1 al 1102 y el evaluador nos da una solución de 180.

En la página http://oeis.org/A069088 puedes ver la lista de los primeros valores de esta función (1, 3, 4, 4, 6, 12, 8, 6, 5, 18, 12, 16, 14, 24…) y la definición ligeramente distinta a la nuestra. Lo que no ofrece es una fórmula para la evaluación directa. La ofrecemos nosotros para pe, como en los casos anteriores:

Si e es par:



Si e es impar



La demostración también se basa en el conjunto

1   p   p2   p3   p4   p5   p6 … pe-1   pe
 
Al aplicarle la función “parte libre” PL las potencias pares se convertirán en 1 y las impares en p, por lo que la suma de las partes libres será

1+p+1+p+1+p+1+p+…. Que terminará en 1 o en p según el exponente sea par o impar. El resto de la demostración es trivial, sacando factor común el factor (1+p) hasta donde se pueda.

Aplicamos la fórmula a 2200=23*52*11: SPL(2200)=(2+1)*4/2*((5+1)*2/2+1)(11+1)*2/2=3*2*7*12=504

Lo hemos comprobado con el Buscador y coincide.

Suma de los mínimos múltiplos cuadrados de los divisores de N SMMC(N)

Otra multiplicativa

Si ahora, en lugar de N/PARTECUAD(N) usamos N*N/PARTECUAD(N) en el Buscador (¿Por qué? Revisa la propiedades vistas en las entradas anteriores ) obtendremos la suma de MMC(N)

Esta función multiplicativa la hemos publicado en OEIS, pues en la fecha de su creación permanecía inédita (ver https://oeis.org/A198286). Sus primeros valores son

1, 5, 10, 9, 26, 50, 50, 25, 19, 130, 122, 90, 170, 250, 260…

Podemos usar una fórmula similar a las anteriores. No es difícil que la puedas justificar si entendiste las primeras.

Si e es par


Si e es impar


Lo vemos con un número compuesto, el 12=22*3

En primer lugar aplicamos la definición de SMMC y para cada primo sumamos el mínimo múltiplo cuadrado de cada una de sus potencias: SMMC(12)=(1+4+4)(1+9)=9*10=90, como puedes ver en la lista general.

Ahora aplicamos la fórmula:

SMMC(22) (caso par) = 1+2((16-4)/(4-1))=1+2*4=9, que era lo esperado

SMMC(3) (caso impar) = (1+9)((9-1)/(9-1))=10*1=10, que con el 9 anterior da 90.

Proponemos una cuestión:

(a) La suma de las partes cuadradas de los divisores de un número coincide con esta suma:


¿Sabrías demostrarlo? Se consigue como en las anteriores, comenzando a considerar el conjunto 1   p   p2   p3   p4   p5   p6 … pe-1   pe

jueves, 8 de diciembre de 2011

Emparedado de cuadrados (2)

Relaciones entre los cuadrados que rodean a un número

Según lo definido en la entrada anterior, para conseguir el mínimo múltiplo cuadrado de N sólo tendremos que multiplicar N por su parte libre. En efecto, esa parte libre contiene los factores primos de N elevados al residuo de cada exponente módulo 2. Más claramente: contiene los números primos elevados a 1 si su exponente era impar. Pero si los multiplicamos por N todos esos exponentes se harán pares, con lo que hemos conseguido el MMC(N).

Lo repasamos con un ejemplo:

Sea 11400=52*23*3*19. Su parte cuadrada contendrá los factores con exponente truncado a par: PC(1140)= 52*22 = 100. Su parte libre estará formada por el resto de factores, es decir, PL(1140)=2*3*19=114. Es evidente pues que:

PC(N)*PL(N)=N   (1)

Pero si ahora volvemos a multiplicar por PL(N), todos los exponentes se harán pares y el producto se habrá convertido en MMC(N):

1140*PL(1140)= 52*23*3*19*2*3*19=52*24*32*192=1299600=MMC(11400)

Hemos razonado que

N*PL(N)=MMC(N)   (2)

Uniendo (1) con (2) llegamos a una conclusión muy elegante: N es la media geométrica entre el mayor cuadrado que lo divide y su menor múltiplo cuadrado.

Es así porque N2=PC(N)*MMC(N), según (1) y (2)

 En nuestro ejemplo 114002=100*1299600.

Como los factores del segundo miembro son cuadrados, podemos considerar sus raíces cuadradas. Así definiremos:

(a) Raíz interna de N es la raíz cuadrada de su parte cuadrada. En el ejemplo sería 10. La representaremos como RI(N). En este caso RI(11400)=10

(b) Raíz externa de N es la raíz cuadrada de su menor múltiplo cuadrado. En el caso de 11400 podríamos escribir RE(11400)=1140, que es la raíz cuadrada de MMC(11400)

Un resumen también muy elegante:

Todo número natural equivale al producto de sus dos raíces enteras, interna y externa

En efecto: 11400=10*1140

Podemos representar todo lo anterior gráficamente. Observa esta imagen:

Representa los cuadrados correspondientes al número 180=22*32*5.

El cuadrado rojo de la esquina es su parte cuadrada PC(180)= 22*32=36, que son los cuadritos que contiene. Su raíz cuadrada es RI(180)=6, que se representa por el lado del cuadrado.

La parte libre de 180 es 5. Si copiamos el cuadrado rojo cinco veces a la derecha nos resultará un rectángulo (el separado por la línea gruesa roja) de 180 cuadros, o sea, el número considerado. Esto es así porque N=PC(N)*PL(N).

Si ese rectángulo que contiene 180 cuadros lo trasladamos cinco veces hacia arriba nos resultan 900 cuadros, que es precisamente el menor múltiplo cuadrado. Esto funciona porque N*PL(N) =MMC(N). El lado de ese cuadrado, 30, será la raíz cuadrada externa de 180.

¿Qué hemos visualizado?:

  • Todo número se puede representar por un rectángulo de base su raíz externa y de altura la interna.
  • Si el interior de ese rectángulo lo descomponemos en tantos trozos iguales como indique la parte libre obtendremos la parte cuadrada.
  • Si ese rectángulo lo adosamos consigo mismo por su base tantas veces como indique la parte libre, formaremos un cuadrado que será su menor múltiplo de ese tipo.
¡Se completó el emparedado!

Y lo mejor, como todas las funciones que hemos usado son multiplicativas, dados dos números coprimos, sus esquemas de este tipo se pueden fundir en uno solo multiplicando uno a uno los datos que han intervenido: PC, PL, RI,…

Todo esto no pasa de ser un divertimento, pero te ayuda a aprender conceptos.

sábado, 3 de diciembre de 2011

Funciones multiplicativas. Emparedado de cuadrados (1)

Comentábamos en una entrada anterior los conceptos de parte cuadrada y parte libre de un número. Ahora tomaremos estos conceptos para usarlos como ejemplo de funciones multiplicativas. Antes añadiremos otra definición. Repasamos:

Parte cuadrada PC(N): Es el mayor divisor cuadrado de N (Ver http://oeis.org/A008833)

Parte libre PL(N): Equivale al cociente entre N y su parte cuadrada (http://oeis.org/A007913)

Radical RAD(N): Es el mayor divisor de N que está libre de cuadrados (http://oeis.org/A007947)

Y añadimos otra

Menor múltiplo cuadrado MMC(N): Como indica su nombre, es el menor cuadrado divisible entre N
(http://oeis.org/A053143)

Así que el número N está emparedado entre dos cuadrados.

Uno es el mayor divisor cuadrado PC(N) y el otro es el menor múltiplo de esa clase MMC(N).

Lo aclaramos con un ejemplo

Si consideramos el número 126, sus factores primos son 2*3*3*7, luego
PC(126)=9 porque es el único cuadrado que podemos formar con 2,3,3,7. El exponente de 3 es par, como cabía esperar.
PL(126)=126/9=14, que equivale al producto de 2*7, ambos elevados a 1
RAD(126)=2*3*7=42 Está formado por todos los factores primos elevados a 1.
MMC(126)=22*32*72=1764. Se consigue este número completando los exponentes de sus factores primos a un número par.

Así que, como veremos, cualquier número está comprendido entre dos cuadrados de este tipo. A continuación estudiaremos su cálculo y carácter multiplicativo, dejando para la siguiente entrada sus relaciones.

Parte cuadrada PC

Es evidente que para calcularlo bastará sustituir cada exponente de los factores primos por el mayor número par contenido en cada uno de ellos. Por ejemplo, si N=23*72*11=4312, su parte cuadrada se obtendrá truncando cada exponente al máximo número par que contiene, es decir: PC(N)= 22*72*110=196

Vimos en la primera entrada de las funciones multiplicativas que estas quedaban caracterizadas por su acción sobre los factores primarios de N. De esta forma, la definición de parte cuadrada podía quedar como



Es decir, que a cada exponente se le resta su resto al dividirlo entre 2. Por este tipo de actuación sobre factores primarios de forma independiente, multiplicando después los resultados, ya sabemos que la parte cuadrada es multiplicativa.

Intenta reproducir esta comprobación:



En ella vemos que 1617 y 2000 son coprimos y que el producto de sus partes cuadradas 49 y 400 coincide con la parte cuadrada del producto 3234000=1617*2000. Tendrás que trabajar un poquito, pero aprenderás mucho.

Parte libre

Para no alargar el tema, tan sólo destacaremos que su definición para factores primarios puede ser:

Esto quiere decir que los factores pares desaparecerán en la parte libre y que los impares se convertirán en 1. Al actuar sobre los factores primarios de forma independiente, esta función es también multiplicativa.

Te proponemos una comprobación de su carácter multiplicativo:



Repasa los cálculos y recuerda que ahora se trata de la parte libre.

Mínimo múltiplo cuadrado

Con todo lo que ya llevamos, su definición te vendrá a la mente al momento. Es esta:



Era de esperar. El número N está “emparedado” entre dos cuadrados: el que resulta de restar un 1 o un 0 a los exponentes y el que se calcula sumando ese 1 a los impares y un 0 a los pares.

Por ejemplo:

PC(2400)= =24*52=400; 2400= =25*52*3;  MMC(2400)=14400= =26*52*32

Esta función es multiplicativa por la misma razón que las anteriores.

(Continuará)