Números y hoja de cálculo

Retículos en el conjunto de divisores (1)

2013-05-20T15:23:00.000+02:00

Esta entrada y la siguiente participan en la Edición 4.1231 del Carnaval de Matemáticas cuyo anfitrión es Matemáticas Interactivas y Manipulativas.

El conjunto de divisores de un número natural N está ordenado parcialmente mediante la relación de orden a|b (“a divide a b”) que es reflexiva, simétrica y transitiva, pero en la que dos elementos pueden no ser comparables: ni 6 divide a 13 ni 13 a 6. Por ello decimos que se trata de un orden parcial. En cualquier texto o página específica puedes leer más detalles. Con un nivel elemental, en nuestro documento sobre Teoría de la Divisibilidad http://hojamat.es/sindecimales/divisibilidad/teoria/teordivi.pdf

Quizás sepas que el conjunto de los divisores de un número tiene estructura de retículo. Como este blog no va de Álgebra, sólo daremos una noción de este concepto en su variante de orden (existe otra definición algebraica y ambas son equivalentes)

Definimos

Se dice que un conjunto ordenado es filtrante superiormente si para cada par de elementos a y b del mismo existe al menos otro elemento del conjunto que es mayorante de ellos (en nuestra relación de divisibilidad se traduciría como “múltiplo común”). Lo será inferiormente si existe un minorante de ambos (aquí sería un “divisor común”).

El conjunto de los divisores de N está filtrado superior e inferiormente, y además, para cada par de elementos existe un supremo, que es el mayorante mínimo (el mínimo común múltiplo), que representaremos como aÚb y un ínfimo (el máximo común divisor), representado como aÙb.
Por estas dos propiedades recibe el nombre de retículo.

Sería semirretículo si sólo cumpliera una. Investiga en un tratado de Álgebra las propiedades de estas operaciones (conmutativa, asociativa, absorbente, idempotente…). Si sólo se garantiza la existencia de un supremo, el retículo se convertiría en un sup_semirretículo, y sub_semirretículo en el caso del ínfimo.

Un retículo puede ser acotado si existe un máximo E que es mayorante de todos los demás elementos, y un mínimo F que es minorante de todos ellos. Es claro que en nuestro ejemplo N es el máximo E y 1 es el mínimo F. Se cumple que NÙb=b y que 1Úb=b. A los elementos que sólo tienen como minorante F (y distintos de él) les llamaremos átomos, y en nuestro caso son los factores primos de N. Por el contrario, si su único mayorante es E, reciben el nombre de coátomos.

Estos dos elementos E y F nos valen para la siguiente definición: un retículo acotado es complementado si para todo elemento a existe otro a’, su complemento, tal que aÚa’=E y aÙa’=F. Aunque no nos extenderemos en esta dirección, el complemento no tiene que ser único.

Puedes investigar cuándo un retículo se convierte en un álgebra de Boole. No trataremos esto aquí.

Aquí hay que pararse:

El retículo de los divisores de N es complementado si y sólo si N es libre de cuadrados.

En efecto: Si N es libre de cuadrados, todos sus factores primos estarán elevados a la unidad, por lo que cada divisor a se caracterizará tan sólo por su colección de factores primos, y bastará tomar para a’ el número formado por el producto de los primos que no son divisores de a, que cumplirá trivialmente lo exigido. Por ejemplo, entre los divisores de 210 (libre de cuadrados porque 210=2*3*5*7), el complemento de 35 es 14.

Por el contrario, si no es libre de cuadrados, un divisor al menos p se presenta elevado a una potencia con exponente r mayor que 1. Busquemos el complemento q de p (sin elevar a r). En primer lugar deberá cumplir que pÙq=F o expresado mejor en este caso, p y q han de ser coprimos. Entonces q sólo podrá contener factores primos distintos de p. Pero al calcular pÚq el resultado no podrá coincidir con N, ya que el MCM(p, q) contendrá a p elevado a la unidad, mientras que N lo contiene elevado a r>1. Así que ningún candidato a complemento cumple las dos propiedades. Hemos encontrado un contraejemplo que invalida la propiedad.

Este carácter de retículo se suele expresar mediante un diagrama de Hasse, en el que cada dos elementos relacionados se unen mediante una línea, no teniendo en cuenta la propiedad reflexiva y aprovechando la transitiva para eliminar líneas. Aquí tienes el correspondiente a 150:

Se comprende que hay otras formas de ordenarlo y dibujarlo. Es un buen ejercicio identificar el carácter de un número según su diagrama de divisores (potencia de un primo, semiprimo, libre de cuadrados…)

Presentada esquemáticamente la teoría, nos dedicaremos a descubrir algunos retículos y semirretículos que se dan en el conjunto de divisores de N. Todo él completo hemos visto que es un retículo.

Pero eso queda para otro día

Particiones con sumandos restringidos

2013-05-13T15:00:00.000+02:00

En la anterior entrada hemos supuesto que el número de sumandos en una partición era libre, hasta el mayor posible. Puede ocurrir, sin embargo, que sólo deseemos usar un máximo de hasta tres sumandos, o exactamente cuatro o cualquier otra posibilidad. Por otra parte, los sumandos pueden estar restringidos en magnitud dentro de un rango. Esto complica un poco las cuestiones.

Veremos con algunos ejemplos la utilidad de las funciones generatrices y la posibilidad de comprobar resultados con la hoja Cartesius.

¿De cuántas formas se puede descomponer el número 8 en sumandos no mayores que 4?

Si has entendido de qué van las funciones generatrices comprobarás que la siguiente es la adecuada para este caso

Como en casos anteriores podemos expresarlo como sumas de sucesiones geométricas

Y en general

Para aplicarlo al caso de 8 bastará buscar su coeficiente en la F.G. aplicada al caso en el que k=4. Lo escribimos en PARI

print(taylor(1/(1-x)/(1-x^2)/(1-x^3)/(1-x^4),x,9))

Y obtenemos

F.G.=1+x+2x^2+3*x^3+5*x^4+6*x^5+9*x^6+11*x^7+15*x^8+O(x^9)

Luego la solución del problema es P(8/sumandos no mayores que 4)=15

Si lo planteamos con Cartesius obtenemos los 15

Particiones conjugadas

Ahora usaremos una técnica muy simple, pero que da buenos resultados. Como veíamos en otra entrada (http://hojaynumeros.blogspot.com.es/2011/02/particiones-de-un-numero.html) cada una de las particiones se puede representar mediante un diagrama de Ferrer, en el que se adosan tantas filas como sumandos entran en la partición, siendo la longitud de cada columna el valor del sumando. Así, la partición 8=4+2+1+1 se puede representar como

Cada fila representa un sumando: 4, 2, 1 y 1. Todos los diagramas que formemos con estas 15 particiones tendrán como máxima anchura cuatro cuadrados.

Lo bueno de estos diagramas, entre otras ventajas, es que si los giramos convirtiendo las filas en columnas y las columnas por filas seguirán siendo particiones, llamadas particiones conjugadas.
Así, la partición 3+2+1+1+1

Se puede convertir en 5+2+1

Esta correspondencia es biyectiva. Si en las 15 particiones consideradas ninguna podía sobrepasar la anchura de 4, sus conjugadas no podrán tener más de cuatro filas, es decir, más de cuatro sumandos.

Esto es muy interesante: Las particiones en sumandos no mayores que k coinciden en número con las particiones en no más de k sumandos.

En nuestro ejemplo: si existen 15 particiones de 8 en sumandos no mayores que 4, también serán 15 las que se obtengan con no más de cuatro sumandos libres.

Lo comprobamos, intercambiando en Cartesius el 4 con el 8, y vemos que resultan también 15:

Así que si alguna vez no puedes construir la F.G. de un tipo de particiones, puedes acudir a las conjugadas por si resulta más sencillo. El siguiente ejemplo lo aclara.

¿De cuántas formas distintas podemos descomponer el número 12 en exactamente cuatro sumandos?

Acudimos a la conjugada: Este problema es el mismo que descomponer 12 en sumas de las cuales el mayor sumando sea 4. De otra forma: debe figurar al menos un 4 y el resto ser 1,2 o 3.

De esa forma la F.G. es fácil de obtener:

(hemos suprimido el 1 en el mayor sumando)

Generalizando

Efectuamos las comprobaciones en nuestro ejemplo

Con la función generatriz y PARI

print(taylor(x^4/(1-x)/(1-x^2)/(1-x^3)/(1-x^4),x,9))

Desarrollo: x^4+x^5+2*x^6+3*x^7+5*x^8+6*x^9+9*x^10+11*x^11+15*x^12+O(x^13)

Solución: el coeficiente de 12, que es 15.

Con Cartesius

Tenemos que eliminar el cero de los sumandos, para que sean exactamente cuatro. Por eso el rango será 1..12

Resultado: 15

Problema conjugado

Ahora, en lugar de cuatro sumandos, el máximo ha de ser siempre 4, pero eso no es operativo, pues podemos eliminar siempre ese 4 y en lugar de formar una suma 12 pedimos que la suma sea 8. Este problema lo tenemos resuelto más arriba y nos resultó 15, como era de esperar.

Particiones y funciones generatrices

2013-05-06T15:30:00.000+02:00

Unimos hoy dos conceptos que ya hemos tratado en el blog

http://hojaynumeros.blogspot.com.es/2011/01/montones-de-piezas.html y siguientes
http://hojaynumeros.blogspot.com.es/2013/03/funciones-generatrices-en-combinatoria.html y siguiente.

y que al unirse dan resultados mucho más potentes. Recomendamos la lectura previa de ambas. Recorreremos ahora los principales tipos de particiones, ayudados también por nuestra hoja de cálculo Cartesius.

Particiones ordinarias P(n)

En la entrada ya referida las estudiamos desde un punto de vista general. Aplicaremos ahora el concepto de función generatriz.

Supongamos que deseamos encontrar todas las particiones ordinarias del número 6 (formas de representar 6 como suma con posible repetición de sumandos). Para ello no necesitamos ni funciones ni técnicas informáticas. Con un poco de atención llegaremos a que el 6 se descompone en suma de las siguientes formas:

6 = 5+1 = 4+2 = 4+1+1 = 3+3 = 3+2+1 = 3+1+1+1 = 2+2+2 = 2+2+1+1 = 2+1+1+1+1 = 1+1+1+1+1+1

Son once en total

Si queremos expresar este proceso mediante funciones generatrices hay que recordar que los sumandos provenían de exponentes en un polinomio. En efecto, en este caso del 6 podemos considerar la función

Si multiplicamos todo, el término de grado 6 se compondrá de todos los productos en los que el primer paréntesis aporta los sumandos iguales a 1, el segundo los que valen 2, el tercero, 3, y así hasta llegar al 6. Hemos tomado infinitas potencias en cada uno porque las mayores que 6 no van a influir, pero gracias a ello la expresión se simplifica como una progresión geométrica:

O expresado de forma sintética y generalizando hasta n:

Después volveremos a esta función generatriz para adaptarla a casos particulares. La comprobamos para n=6. Vimos en anteriores entradas que con PARI se pueden desarrollar fácilmente.

print(taylor(1/(1-x)/(1-x^2)/(1-x^3)/(1-x^4)/(1-x^5)/(1-x^6),x,7))

Resultado: 1+x+2x^2+3x^3+5x^4+7x^5+11x^6+O(x^7) con el coeficiente 11 para x^6, como era de esperar. Serían las once particiones esperadas. Como en ocasiones anteriores, este método nos da más, pues podemos leer otros coeficientes: con el 5 tendríamos 7 particiones, con el 4, 5, y así…A la inversa, si en lugar de pararnos en el 6 hubiéramos seguido escribiendo factores, obtendríamos más particiones, para 7, 8,… Así que recordemos la función generatriz (F.G.) para las particiones ordinarias del número n:

Podemos comprobar el resultado con nuestra hoja Cartesius. Basta programar esto:

Concreta un total de 6 conjuntos, formado cada uno por el rango 0..6, en el que sólo se seleccionan los arreglos crecientes (para evitar duplicidades) y con suma 6.
Obtendríamos once resultados

Intenta obtener otros resultados similares. Lo importante es que recuerdes la definición de partición de un número y su F.G.

Particiones en sumandos distintos Q(N)

Si al descomponer un número en sumandos no permitimos que figuren repetidos, obtendríamos resultados muy distintos, recogidos como la función de partición Q(n).

En este caso la función generatriz se simplifica mucho, pues en los paréntesis no han de figurar todas las potencias sino una sola por cada sumando. Así, para n=7 la F.G. sería

y generalizando para n

Para el caso de 7 podemos expandir la F.G. mediante wxMaxima

Obtendremos un desarrollo en forma de polinomio, pero sólo serán útiles los coeficientes menores o iguales a 7:

Ya tenemos la solución, el 7 se puede descomponer en 5 formas diferentes como suma de números naturales distintos:

7=6+1=5+2=4+3=4+2+1

Además, hemos obtenido que el 6 tiene 4 descomposiciones, el 5, 3 y así hasta el 1. Recuerda: estos son los únicos fiables en el desarrollo.

Con Cartesius:

5 soluciones

Particiones en partes impares P(N/Impar)

Aquí vemos rápidamente la utilidad de la función generatriz. Si en la fórmula general de las particiones eliminamos los pares de los paréntesis quedaría

que fácilmente se traduce, al igual que en las particiones ordinarias, a cocientes:

O bien

Por ejemplo, para n=7, usando PARI, nos resultaría

print(taylor(1/(1-x)/(1-x^3)/(1-x^5)/(1-x^7),x,8))

1+x+x^2+2*x^3+2*x^4+3*x^5+4*x^6+5*x^7+O(x^8)

Como el coeficiente de 7 es 5, ese será el número de particiones en impares. Como son tan pocas, las podemos escribir directamente: 7 = 5+1+1 = 3+3+1 = 3+1+1+1+1 = 1+1+1+1+1+1+1
Intenta comprobar, como en los casos anteriores, que con 6 resultarían 4, con 5, 3, y así con todos los coeficientes resultantes.

Comprobación con Cartesius

La instrucción CONCERO significa que a los impares les adjuntamos el cero para representar los sumandos que no entran en una suma determinada. Además, se impone la condición de ser impares.
5 soluciones:

Este resultado coincide con el de representar 7 con sumandos distintos. En realidad siempre es así, como demostró Euler usando funciones generatrices:

El número de particiones de un número en sumandos distintos coincide con el de particiones en sumandos impares

Con el uso de las F.G. todo se reduce a un artificio algebraico:

Demostración

Todo se basa en que

Así que partiendo de la F.G. de la partición en elementos distintos, representamos cada factor de esta forma, se simplificarán los factores de exponente par y sólo quedarán los impares en el denominador

En el caso de n=7 te proponemos una correspondencia biyectiva por el método de Sylvester. Para que pienses un poco más sólo daremos el proceso y tú sacas tus consecuencias:

7=6+1=5+2=4+3=4+2+1 = 2*3+1 = 5+2*1=4*1+3=4*1+2*1+1 y ahora sustituimos cada producto por la suma correspondiente: 7 = 3+3+1 = 5+1+1 = 1+1+1+1+3 = 1+1+1+1+1+1+1

¿Puedes generalizarlo?

Para el camino inverso deberíamos expresar cada suma de repetidos como suma respecto a potencias de 2 distintas que se sacan como factor común.

7 = 3+3+1 = 5+1+1 = 1+1+1+1+3 = 1+1+1+1+1+1+1 = 3*2+1=5+2*1=4*1+3=4*1+2*1+1

Serían siempre todos distintos, porque o se diferencian en el números sacado factor común o en las distintas potencias de 2

Medir el mundo con los dedos

2013-04-29T15:00:00.000+02:00

Hace poco volví a leer el procedimiento de calcular las horas de sol que quedan antes del ocaso mirando el cielo con el brazo extendido y contando una hora por cada vez que podamos insertar cuatro dedos de nuestra mano. Quizás sea un método poco exacto y criticable, pero me animó a jugar con las medidas a través de proporciones corporales, dejando a un lado la medida de ángulos, que no se contempla en los objetivos de este blog.

Esta técnica me recordó otras parecidas, que pude consultar en el libro de Geometría Recreativa de Yakov Perelman y las que yo mismo experimenté cuando era profesor en activo.

Mi propósito es reunir y comprobar algunas de estas técnicas añadiendo propuestas nuevas, estableciendo un orden lógico y con el uso de hojas de cálculo. En esta entrada trataremos de medidas que se pueden efectuar con los dedos de la mano sin considerar ángulos.

Parte 1 – Medidas y proporciones

Los dedos de la mano comparados con la longitud del brazo constituyen goniómetros bastante aceptables. Por ejemplo, se ha propuesto muchas veces intentar tapar la imagen de la Luna mediante el dedo índice o el pulgar con el brazo extendido. De esa forma se demuestra que su tamaño aparente es mucho menor del que se cree. Podemos organizar en el aula prácticas similares mediante el uso de los dedos de la mano. Comenzamos con este de un solo dedo.

Primer multiplicador corporal

Elegimos el pulgar porque se puede hacer formar un ángulo casi recto con el brazo, lo que aumenta su fiabilidad. El pulgar es un transportador de ángulos: lo usan los pintores para medir proporciones en un paisaje y con el mismo dedo trasladarlas al cuadro. Esto es lo que proponemos, usar la proporción entre dedo y brazo para comparar alturas y distancias. De esa forma, si conocemos uno de los dos datos, podemos calcular el otro. Daremos ejemplos más adelante.

Llamaremos primer multiplicador P1 al cociente entre la longitud de nuestro brazo y la del pulgar extendido en ángulo recto. En el caso del autor este cociente es de 10 con una cierta aproximación. Por tanto, la altura que tape nuestro pulgar tendrá una longitud diez veces más pequeña que la distancia que la separa de nosotros. Así, una casa de cinco pisos, que a unos 3 metros largos por piso tendrá una altura de unos 20 metros, si la tapa nuestro pulgar extendido verticalmente estará a unos 200 metros de nosotros. Esta proporción equivale a un ángulo de visión de unos 5,7º (Perelman sugiere 4º).

Además de esa proporción P1=10 podemos usar muchas más a partir de la mano y el brazo. Si proponemos estas medidas en el aula quizás bastaría con que se concreten sólo unas tres proporciones. Estas son las más destacadas (usando siempre el brazo extendido, salvo en el caso del índice que se inclina un poco):

P2 - Grueso del pulgar medido a la altura de la uña: cercano a 40, o bien unos 2 grados.
P3 – Dedo índice a nivel de uña y ligeramente inclinado hacia adelante: unos 50, que equivalen a un grado largo.
P4 – Anchura del puño cerrado medido en los nudillos: 8 o 7º (en algunos textos usan 10º)
P5 – Distancia entre pulgar e índice ambos extendidos: 3,7 o 15º

¿Qué podríamos organizar en el aula?

Daremos algunas ideas ordenadas de cómo vemos una serie de experimentos de este tipo.

1) Toma de medidas en nuestro cuerpo

Es la fase divertida y caótica, pues se trata de que el alumnado proceda a encontrar tres proporciones entre mano y brazo en su propio cuerpo. Se puede realizar por equipos, con medidas reiteradas y cálculo de promedios, así como un pequeño comentario de qué proporción P1 a P5 (u otras) se ve más idónea.
Se puede terminar con una puesta en común en la que se explique el fundamento de la medición que se puede efectuar con esas proporciones (triángulos semejantes, teorema de Thales, razones trigonométricas si las conocen, ejemplos prácticos o históricos, etc.)

2) Calibrado

En la fase anterior, entre bromas y comentarios se han podido cometer errores. El siguiente paso podría ser el de calibrar nuestras proporciones, es decir, aprovechar medidas conocidas para ver si hemos trabajado bien. Damos algunas ideas:

2a) Una experiencia propia: El autor, en sus paseos veraniegos, suele tener a la vista la cruz del Valle de los Caídos (cosas de la vida), cuya altura es de 108 metros y puede taparla aproximadamente con el ancho de su dedo pulgar (P2). Según la página web de Cartografía de Madrid, la cruz se encuentra a 4500 de donde se ha medido, por lo que el factor multiplicador de su pulgar es de unos 42.

2b) Nos informamos de la altura de un monumento, como la torre de la iglesia de nuestro pueblo, y nos alejamos hasta que se tape con el pulgar extendido (P1), que podrán ser bastantes metros, por lo que podríamos usar una carretera que disponga de los postecillos que miden hectómetros.

2c) Colgamos una cuerda desde una ventana del centro escolar y medimos su altura. Nos separamos unos metros y contamos cuantos pulgares o índices necesitamos para llegar desde al suelo hasta la ventana (quien sabe de esto adivinará que no es un método exacto)

3) Realización de medidas

Una vez calibradas nuestras proporciones corporales nos pondremos en acción: o medimos distancias con anchuras o alturas conocidas, o bien medimos estas alejándonos lo suficiente. Es preferible que la propuesta de medida salga del alumnado, y que los profesores sólo sugieran cuando falten ideas. Ahí van algunas:

3a) En un paseo por el campo medimos con pasos la anchura de un camino. Después intentamos tapar con el ancho del pulgar esa misma anchura unos metros más adelante. La distancia a ese punto que abarca el pulgar será de unos 300 metros.

3b) Si tapamos un persona con el truco del pintor (pulgar hacia arriba P1), estaremos a unos 20 metros de ella.

3c) Vistos desde la calle, la distancia entre piso y piso en una casa es de 3 metros. Si lo tapamos con el índice (P3) estaremos a unos 150 metros, si es con la uña del pulgar (P2) a unos 100 y si es con el pulgar completo (P1), a unos 30.

3d) En una carretera recta es posible que situados en un punto kilométrico veamos el siguiente. En ese caso podemos contar los dedos índices (P3) que caben en la altura de un árbol. Por cada dedo sumaremos unos 20 metros al árbol.

3e) Situados a unos 10 km de una cordillera (lo puedes medir en una página web de mapas, o con el GPS), cada ancho de dedo índice (P3) que acumulemos hacia arriba representará 200 metros de altura. Si tú estás a un nivel de 1000 metros y necesitas tres dedos índices para tapar un pico, este tendrá unos 1600 metros de altitud. Si sabes este dato, con los dedos puedes saber a qué distancia estás, si sabes buscar bien la horizontal.

Uso de la hoja de cálculo

Nos puede servir para:

* Cotejar una misma longitud medida con procedimientos diferentes
* Hallar una longitud total mediante la suma de productos de medidas parciales obtenidas con distintos procedimientos.
* Crear una sencilla herramientas para resolver proporciones.
* Confección de informes de resultados.

Presentación

Quien siga este blog sabrá que en cada actividad que propongamos no falta nunca la expresión de resultados. Sólo se ha aprendido verdaderamente lo que somos capaces de explicar a otros. Como en otras ocasiones, proponemos la confección de documentos, presentaciones en PowerPoint, Impress o Prezi, colaboración en la web del centro y cualquier otra forma de conseguir que el alumnado le cuente a los demás lo que ha aprendido.

Proyectos

Sería muy rico que todo esto fuera parte de un proyecto global de medida en el que cada grupo aporte datos nuevos. Por ejemplo, crear un polígono de alturas de tu pueblo o barrio, es decir, crear una triangulación en la que en cada vértice se aporte la altura de un edificio notable o accidente geográfico.

También puede emprenderse un trabajo interdisciplinar. Si se dispone de algún pequeño barómetro de bolsillo, se puede emprender un cálculo de la altura relativa de las montañas que rodeen al pueblo y después usar el barómetro como altímetro, así como proponer una corrección de los barómetros según la altura y presentarlo en el Ayuntamiento. Un complemento muy rico sería el de relacionar las alturas con la fauna y flora.

Estadísticas de las alturas de los árboles más frecuentes en nuestro entorno, sean de ornato ciudadano o rurales. Si se completa con informaciones de los agricultores, se podría correlacionar la altura con la edad. Se puede aplicar, por ejemplo, a olivos, frutales y eucaliptos

Y ahora la suma de cubos de impares nos lleva a Pell

2013-04-17T16:30:00.000+02:00

En la entrada anterior, inspirados en propuestas de Benjamin Vitale
(http://benvitalenum3ers.wordpress.com/2013/02/21/sum-of-the-cubes-of-consecutive-odd-numbers-is-a-square/) desarrollamos cálculos de sumas de cubos consecutivos que equivalían a un cuadrado perfecto.

¿Y si sólo tomáramos impares?

Comenzamos con la unidad

¿A qué equivalen las sumas del tipo 1³+3³+5³+7³+…si han de coincidir con un cuadrado?

En la entrada aludida de Benjamín Vitale se propone la fórmula S(n)= n² (2n² – 1). La demostración no es complicada. Nos basamos en lo demostrado para sumas de cubos consecutivos

Si ahora suprimimos las sumas de cubos pares es fácil ver que (intenta justificarlo)

Simplificando llegamos a la expresión propuesta S(n)= n² (2n² – 1)

Para que se cumpla lo pedido, de que la suma sea un cuadrado, el paréntesis ha de ser otro cuadrado

Esto nos lleva a plantear: 2n²-1=m²
Pero esta es la ecuación de Pell con el segundo miembro igual a -1 y D=2

X²-2Y²=-1

La primera solución se ve que es X=1 Y=1 y nos daría la solución trivial del problema 1³=1²
Para encontrar las demás puedes a acudir a nuestra entrada http://hojaynumeros.blogspot.com.es/2010/02/ecuacion-de-pell.html

En ella tienes las fórmulas de recurrencia para encontrar más soluciones, pero es más cómodo acudir a nuestra herramienta http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#pell
A continuación te presentamos las primeras soluciones obtenidas con ella

Nos quedamos con las correspondientes a -1: 1, 5, 29, 169, 985, 5741, 33461, 195025,… http://oeis.org/A001653 que se corresponderán con el número de sumandos de cubos de impares que nos producen un cuadrado, el cual podemos calcularlo con la fórmula presentada arriba. Por ejemplo

Para n=5, el cuadrado será 5^2*(2*5^2-1) = 25*49 = 35^2 = 1225
En efecto: 1^3+3^3+5^3+7^3+9^3 = 1+27+125+343+729 = 1225

En realidad esa secuencia está definida en OEIS como la de números que verifican que 2n² – 1 es un cuadrado, pero como nosotros exigimos que lo sea n² (2n² – 1), es una condición equivalente. Si te apetece lee los comentarios contenidos en esa dirección, que pueden resultarte interesantes.

Aquí tienes la comprobación para 29 sumandos:

Comenzando en otro cubo

Para obtener un resultado similar, pero comenzando la suma en cualquier número impar, no necesariamente el 1, necesitaremos restar las expresiones de dos sumas completas diferentes y exigir que sean un cuadrado perfecto:

S(m)-S(n)= m^2 (2*m^2 – 1) - n^2 (2*n^2 – 1) = k^2

O bien

2*(m^4-n^4)-(m^2-n^2) =k^2

Con un algoritmo similar al empleado en casos anteriores, podemos encontrar los valores de m y n que cumplen esa igualdad:

For m=2 To 1000
For n = 1 To m - 2
c = sqr(2 * (m^ 4 - n ^ 4) - (m ^ 2 - n^ 2))
If c=Int(c) Then
Msgbox(m)
Msgbox(n+1)
End If
Next n
Next m

Hay que observar que el algoritmo devuelve n+1, porque debemos recordar que n es el valor anterior a la suma. Así hemos obtenido estos valores para el inicio y el final de las sumas de cubos de impares que produzcan un cuadrado:

La primera nos lleva a 5^3+7^3+9^3+11^3+13^3+15^3 = 90^2, es decir, desde el tercer impar hasta el octavo.

La segunda va desde el término 13º hasta el 37º:

25^3+27^3+29^3+…+73^3=1925^3

Puedes construirte un modelo para comprobar otras soluciones con hoja de cálculo. Sólo necesitas una columna con números de orden, otra con los impares, y otra con sus cubos. Después seleccionas una parte adecuada de estos (por ejemplo, desde el 46º hasta el 59º, los sumas con la función SUMA y le hallas la raíz cuadrada para ver si es entera:

Si no tienes suficiente con estas búsquedas, intenta analizar algebraicamente la condición

2(m⁴-n⁴)-(m²-n²) =k²

Ya nos contarás. Es que en este blog el Álgebra nos cansa mucho.

Las sumas de cubos nos llevan a los triangulares pitagóricos.

2013-04-09T16:30:00.000+02:00

No es la primera vez que en este blog se desarrollan ideas que han nacido a partir de las entradas de otros autores que seguimos habitualmente. En este caso partiremos de una serie de igualdades publicadas por Benjamin Vitale en el mes de de febrero.

http://benvitalenum3ers.wordpress.com/2013/02/21/sum-of-the-cubes-of-consecutive-odd-numbers-is-a-square/

En esa entrada y en otras anteriores y posteriores propone igualdades de estos tipos:

333^3 + 334^3 + 335^3 + 336^3 + 337^3 + 338^3 + 339^3 = 265559616 = 16296^2
1^3 + 2^3 + 3^3 + 4^3 + 5^3 = 225 = 15^2
1^3 + 3^3 + 5^3 + 7^3 + 9^3 = 1225 = 35^2

En todas ellas una suma de cubos equivale a un cuadrado. Unas comienzan en 1^3 y otras en números mayores, y una de ellas sólo se refiere a números impares. Como ya tocamos un tema parecido en nuestra entrada sobre “Cubos y gnomones” (ver http://hojaynumeros.blogspot.com.es/2009/10/cubos-y-gnomones-1.html y las tres siguientes) nos ha apetecido ampliar un poco el tema

Suma de cubos de los primeros números naturales

Es el caso más sencillo y que ya tratamos en nuestra entrada citada:

La suma de los cubos de los n primeros números naturales equivale al cuadrado del enésimo número triangular T_n

Puedes demostrarlo por inducción. Si no sabes cómo, aquí te darán una buena idea: http://diccio-mates.blogspot.com.es/2009/09/induccion-induccion-completa.html

Luego en estas circunstancias la propiedad de que una suma de cubos coincida con un cuadrado se cumple siempre

Suma general de cubos consecutivos

Si el comienzo de la suma no es la unidad, como en el ejemplo de Ben Vitale

333^3 + 334^3 + 335^3 + 336^3 + 337^3 + 338^3 + 339^3 = 265559616 = 16296^2

la fórmula anterior tiene una fácil adaptación:

Por tanto, si la diferencia entre esos dos números triangulares es un cuadrado, habremos obtenido un criterio para buscar todos los casos posibles.

El segundo miembro de la igualdad no invita a que intentemos igualarlo a un cuadrado y desarrollarlo algebraicamente (ahí tienes un reto), por lo que intentaremos búsquedas:

Encontrar todas las sumas de cubos consecutivos cuyo resultado sea un cuadrado, equivale a confeccionar la lista de todos los pares de números triangulares que formen parte de una misma terna pitagórica.

La razón es que su diferencia de cuadrados deberá dar otro cuadrado. Por eso forman una terna pitagórica. Con la anterior fórmula podemos programar búsquedas que nos devuelvan los casos deseados. Lo haremos en primer lugar para un número fijo de sumandos y después pasaremos al caso general. Excluimos del estudio los casos que comienzan por cero, que confundirían en el número de sumandos.

Número de sumandos prefijado

Si el número de sumandos está prefijado podemos usar un código similar al siguiente (lo expresamos en el Basic de Excel, que también vale para OOBasic, y se traduce fácilmente):

K=6 número de sumandos menos una unidad. Aquí estaríamos buscando siete sumandos
For i = inicio To final Extremos de la búsqueda
a = i * (i - 1) / 2 Triangular anterior a la suma
b = (i+k) * (i+k + 1) / 2 Triangular al final de la suma
c = Sqr(b ^ 2 - a ^ 2) Tercer lado
If c = Int(c) Then msgbox(a) Si es pitagórica se muestra el comienzo de la suma
Next i

En PARI tampoco es difícil. En cada pasada se puede cambiar el valor de k, que debe coincidir con el número de sumandos menos uno, que aquí hemos fijado en 4, así como los extremos en 1 y 1000

{for(i=1,1000,k=4;a=i*(i-1)/2;b=(i+k)*(i+k+1)/2;if(issquare(b*b-a*a),print(i)))}

Con este código obtenemos los valores iniciales para las sumas de cubos consecutivos que dan como resultado un cuadrado. En el caso del ejemplo, está preparado para cinco sumandos.

Con la hoja de cálculo o con PARI se obtienen los mismos resultados propuestos por Ben Vitale. Así que no vamos a repetir información y pasaremos al caso general.

Número de sumandos libre

Deberemos sustituir la asignación de un valor a K por un bucle. Buscaremos valores N de números triangulares que hagan de hipotenusa y para cada uno de ellos, recorreremos los valores de K menores que N para que sean catetos. Nos detendremos en N-2, porque hay que recordar que el segundo triangular es el previo a la suma.

En el Basic de las hojas de cálculo el código, fácilmente trasladable a otros lenguajes, puede ser:

For i = 5 To 400 No necesitamos más ejemplos por ahora
a = i *(i+ 1) / 2 Creamos el triangular que hará de hipotenusa
For k = 1 To i – 2 Buscamos el cateto triangular
b = k * (k + 1) / 2
c = Sqr(a ^ 2 - b ^ 2) Calculamos el otro cateto
If c = Int(c) Then Si es cuadrado perfecto, hemos encontrado una solución
Msgbox(k + 1) Número de sumandos
Msgbox(i - k ) Inicio de la suma
Msgbox(c) Base del cuadrado buscado
End If
Next k
Next i

Con un código similar, pero que crea una tabla, hemos confeccionado ésta:

Ahí aparecen los casos particulares con los que comenzamos la entrada. Por ejemplo, 23 de inicio, con 3 sumandos se ha de engendrar el cuadrado de 204.

23^3+24^3+25^3 =204^2 Compruébalo. Aquí hemos usado nuestra querida hoja de cálculo:

En la tabla se nos ofrecen casos de hasta 291 sumandos, que no comprobaremos, pero probemos con otra fila: 25, 15 y 720, es decir, 15 sumandos a partir del 25 deberán engendrar el cuadrado de 720. Aquí lo tienes:

Con esto hemos encontrado los primeros ejemplos del caso general. Podemos ordenar la tabla según el número de sumandos, o según el inicio, y así ver mejor la evolución de las soluciones.

Si prefieres probar con PARI, usa un código similar a este:

{for(i=1,10^3,for(k=1,i-2,a=i*(i+1)/2;b=k*(k+1)/2;if(issquare(a*a-b*b),write("final.txt",k+1," ",i-k))))}

Hipotenusas triangulares

Si cambiamos las salidas del código, podemos confeccionar una tabla con las ternas pitagóricas en las que una hipotenusa y un cateto son ambos triangulares:

Esta es la sucesión de hipotenusas de este tipo:

10, 45, 136, 325, 435, 595, 630, 666, 780, 1225, 2080, 2145, 3321, 5050, 5565, 5886, 6216, 7381, 7503, 9316, 10440, 11026, 11175, 12246, 13530, 14196, 14365, 14535, 15753, 16653, 18915, 19306, 24310, 25425, 32896, 33670, 39060,…

Puedes usar PARI

{for(i=1,10^3,k=1;v=1;a=i*(i+1)/2;while(k<i&&v,b=k*(k+1)/2;if(issquare(a*a-b*b),v=0;write1("final.txt",a,", "));k+=1))}

Esta sucesión la hemos publicado en http://oeis.org/A213188

De la misma forma, se pueden encontrar los catetos triangulares con hipotenusa también triangular:

6, 36, 91, 120, 210, 253, 300, 378, 528, 630, 1176, 2016, 2346, 3003, 3240, 3828, 4560, 4656, 4950, 5460, 6105, 6903, 7140, 7260, 8778, 10296, 11628, 13530, 14028, 14196, 15400, 17766, 19110, 23220, 23436, 24310, 25200, 26796, 32640, 34980, 41616…http://oeis.org/A213189

El código PARI adecuado es

{for(i=1,10^3,k=i+1;v=1;a=i*(i+1)/2;while(k<i*i&&v,b=k*(k+1)/2;if(issquare(b*b-a*a),v=0;write1("final.txt",a,", "));k+=1))}

En la siguiente entrada veremos las sumas de cubos de impares. Aquí ya no caben.

Función generatriz de combinaciones y variaciones

2013-04-02T17:49:00.000+02:00

Combinaciones sin repetición
Ya vimos en la entrada de presentación de la teoría de las funciones generatrices

(http://hojaynumeros.blogspot.com.es/2013/03/funciones-generatrices-en-combinatoria_14.html)

esta relación

Es el clásico Binomio de Newton y nos da de forma inmediata la función generatriz (F.G.) de las combinaciones de n elementos sin repetición.

Esta forma de expresar los números combinatorios da lugar a demostraciones muy sencillas de algunas de sus propiedades. Observa esta identidad:

Si la desarrollas da lugar a la identidad de Vandermonde

Basta imaginarse cómo sería el producto de las dos potencias

De igual forma, de esta otra identidad

Nos resultaría

Basta con igualar términos con el exponente k

Así se podría demostrar otras similares.

Combinaciones con repetición

La fórmula del binomio de Newton es válida también para exponente negativo, pero en ese caso los números combinatorios tendrían la forma

Pero la última expresión coincide con las combinaciones con repetición, luego

Sería, teniendo en cuenta los signos, la F.G. de las combinaciones con repetición.

Caso de elementos con repetición prefijada

Este es el caso con el que comenzamos a estudiar las F.G. en una entrada anterior. Si deseamos combinaciones con repetición, pero en las que algunos elementos tienen un máximo en su repetición (no se suele estudiar este caso en los niveles elementales), debemos usar otra técnica. Por ejemplo:

Disponemos de varias fichas en cada una de las cuales se ha dibujado una forma distinta. Por ejemplo esta distribución:

¿De cuántas formas distintas se puede tomar un conjunto de cinco símbolos? Al hablar de conjunto, no tendremos en cuenta el orden.

Basta usar, como ya vimos, un producto de polinomios en los que los exponentes representan las repeticiones posibles de cada símbolo:

F(x)=(1+x+x²)(1+x+x²+x³)(1+x+x²+x³+x⁴)

Buscamos con PARI su coeficiente de grado 5, que representa los elementos seleccionados:

print(polcoeff((x^2+x+1)*(x^3+x^2+x+1)*(x^4+x^3+x^2+x+1),5))

con un resultado de 11 posibilidades

Son estas (con la hoja Cartesius):

Podemos interpretarlas así:

Este método es general: para crear la F.G, en un caso de combinaciones con repeticiones prefijadas basta con formar polinomios de potencias para cada uno de los elementos y después multiplicarlos todos.

Funciones generatrices exponenciales

Hasta ahora hemos manejado combinaciones, no hemos tenido en cuenta el orden. Cuando éste interviene, para abordar las variaciones y permutaciones, necesitamos otro tipo de funciones generatrices, las exponenciales:

Dada una sucesión de números (en general complejos) {a0, a1, a2, a3,…an,….} llamaremos función generatriz exponencial de esa sucesión a la formada por

Es idéntica a la definición general, pero en cada término de la suma dividimos entre el factorial del exponente. La raíz de esta técnica está en el desarrollo del binomio de Newton, en el que podemos sustituir Cm,n por Vm,n/n!

De esta forma, si (1+x)^m era la F.G. de las combinaciones, también será ahora la F.G exponencial de las variaciones. Esta idea no es de mucha utilidad así en general, pero nos será muy útil en lo que sigue.

Variaciones con elementos repetidos

Un caso que no se suele estudiar en las enseñanzas medias es el las variaciones en las que se permite un máximo de repeticiones para cada elemento. Por ejemplo, tomar variaciones de 4 elementos en este conjunto de elementos con repetición: AAABBCDD.

Efectuamos previamente un acercamiento sin F.G.

En la imagen hemos obtenido con Cartesius todas las posibles combinaciones, escribiendo en cada columna el número de veces que se toman A,B,C y D, contando después las distintas ordenaciones de cada una. La suma obtenida fue de 162 variaciones.

Probamos ahora con una F.G. exponencial para cada elemento, hasta 3 para A, 2 para B y D y una para C. Observa que los términos de los polinomios están divididos entre factoriales.

FG=(1+x+x^2/2+x^3/6)(1+x+x^2/2)(1+x)(1+ x+x^2/2)

Desarrollamos esta función con wMaxima

Nos resulta para el exponente 4 un coeficiente de 27/4, pero recordemos que es una F.G. exponencial, luego hay que multiplicar por 4! para encontrar el verdadero coeficiente, el número de variaciones:

27/4*4!=27*6=162, que confirma el resultado previo.

Lo que hemos aprovechado en realidad es que al escribir estos paréntesis cada elemento está representado por los órdenes que puede presentar. Si usamos este factor (1+x+x^2/2+x^3/6) lo que estamos comunicando es que x^2 presenta dos posibles órdenes (que al repetir el símbolo se han perdido) y que x^3 proviene de 6 órdenes (permutaciones con tres elementos)

Quiere decir lo anterior que las contribuciones al coeficiente final de x^4, 27/4, ya vienen descontados los órdenes que se han perdido al repetir. Al final, al multiplicar por el factorial de 4, nos quedamos con los órdenes verdaderos. Es un poco complicado de entender, pero estúdialo, que funciona.

Lo comprobamos para el variaciones de 3 elementos: el coeficiente es 26/3 y si multiplicamos por 3! nos queda 26*2=52

Lo comprobamos con Cartesius

Lo generalizamos sin demostración:

Para encontrar el número de variaciones con repetición en el que conocemos el número máximo de repeticiones de un elemento, sean por ejemplo k, aportaremos a la F.G. un factor del tipo 1+x+x2/2!+x3/3!+…+xk/k! por cada elemento.

Permutaciones con repetición

La función generatriz que hemos empleado para variaciones coincide con la de permutaciones si el coeficiente que buscamos coincide con el total de las repeticiones de símbolos. En el ejemplo que estamos usando, AAABBCDD, el total de elementos es 8. Busca en el desarrollo mediante wMaxima de arriba el exponente 8 de la F.G. y verás que es 1/24. Como estamos usando funciones exponenciales, el verdadero valor será (1/24)*8! = 1680.

En este caso no es necesaria la F.G., pues ya sabemos que el número de permutaciones de AAABBCDD se calcula mediante 8!/(3!2!1!2!) =8!/24 = 1680, pero es conveniente comprobar que en este caso también funciona la técnica de las F.G.

Algoritmo de Euclides binario

2013-03-19T19:26:00.000+01:00

Esta entrada participa en la Edición 4.12 del Carnaval de Matemáticas cuyo anfitrión es el blog High Ability Dimension.

En este blog nos motiva mucho el construir un esquema en hoja de cálculo que explique de la mejor forma posible el funcionamiento de un proceso o un algoritmo. Lo haremos hoy con la variante binaria del Algoritmo de Euclides.

Restar en lugar de dividir

Ya se sabe que el algoritmo de Euclides por divisiones se puede sustituir por otro efectuado a base de restar los dos números. Parece más lento, pero al ahorrar divisiones puede resultar más eficiente. Hace sesenta años lo usábamos los alumnos de Bachillerato (con once añitos) para comprobar si dos segmentos eran inconmensurables o no. Llevábamos uno sobre otro y nos quedábamos con la diferencia. Si al reiterar llegábamos al segmento nulo, es que tenían una medida común. Aquello era Geometría de Euclides pura.

Si el algoritmo clásico se organizaba a partir de la división euclídea, en esta variante se usa la resta. Así, para encontrar MCD(96,36) por divisiones sería: 96=2*36+24; 36=1*24+12; 24=2*12+0, luego el MCD(96,36)=12. Por restas formaríamos estas parejas: (96,36), (60,36), (36,24), (24,12), (12,12), (12,0), llegando al mismo resultado.

Eliminar el factor 2 siempre que se pueda.

En computación con sistema de numeración binario la división y la multiplicación por 2 se reducen a trasladar un lugar a la derecha o izquierda del dígito que se multiplica. Por eso, es interesante dar protagonismo al número 2 en los cálculos. Una primera idea es que si expresamos los dos números A y B de la forma A=2^m*p, B=2ⁿ*q, con p y q los mayores divisores impares, el M.C.D se puede encontrar con dos cálculos por separado. Por una parte quedándonos con el menor exponente del 2 y por otra hallando MCD(p,q).

En el algoritmo que estamos presentando, se elimina en primer lugar la potencia de 2 común a ambos números, y se toma nota de ella. Una vez eliminada, el factor 2 no va a influir en el resultado, y cuando aparezca en alguno de los dos números se podrá igualmente suprimir. En términos binarios suprimir un 2 es trasladar los dígitos una posición hacia la derecha.

En Wikipedia y otras páginas que hemos consultado expresan lo anterior en forma de tres reglas. http://en.wikipedia.org/wiki/Binary_GCD_algorithm. No son difíciles de razonar.

(1) Si A y B son ambos pares se cumple MCD(A,B)=2*MCD(A/2,B/2)

Esto justifica que el primer paso que demos sea el de separar las potencias de 2.

(2) Si A es par y B impar se tiene MCD(A;B)=MCD(A/2,B)

Igualmente se aplicaría si B es par y A impar. En virtud de esta regla eliminaremos todos los factores 2 una vez que se ha separado la potencia común.

(3) Si ambos A y B son impares y A<B, MCD(A,B)=MCD(B-A,A). Si es B<A, MCD(A,B)=MCD(A-B,B)

Esta es la esencia del algoritmo de Euclides, restar ambos números.

Eliminar la potencia de 2 común (Regla 1)

Hemos creado una demo en hoja de cálculo para seguir visualmente los pasos del algoritmo binario. Lo puedes descargar desde la dirección

http://hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#euclibin

Como nuestro objetivo es visual, desarrollaremos ahora los pasos sugeridos pero en forma de esquema. En una hoja de cálculo se escribirán los dos números y con un botón iterativo se irán avanzando pasos hasta llegar al MCD. Esta primera fase de eliminar el factor común lo puedes ver en las imágenes siguientes:

En primer lugar hemos escrito los números 192 y 84. Al pulsar sobre el botón Aceptar números se han convertido ambos en binario y se han reconstruido a la derecha. La potencia de 2 común figura al principio con el valor 1.

Observamos que ambos números terminan en dos ceros (en binario), luego compartirán el factor 2²=4.
Según estamos explicando, el primer paso del algoritmo binario es eliminar el factor 2 común. Si ahora usamos el botón Paso a paso dos veces veremos que los dígitos de ambos números se mueven dos posiciones a la derecha y que la potencia de 2 se convierte en 4.

A la derecha figuran los números ya simplificados, 48 y 21, y la potencia de 2, que nos servirá al final.

Resto de pasos

Ahora la estrategia es triple:

(1) Si el primer número contiene aún potencias de 2, se eliminan (Regla 2)

Observa que en nuestro ejemplo el número 48 termina en cuatro ceros, luego al cabo de cuatro toques del botón Paso a paso desaparecerán.

(2) Se opera igual con el segundo: se le elimina el factor 2 (Regla 2)

En nuestro ejemplo ya no quedan factores 2 (por ahora)

(3) Si ambos son impares, se sustituye el mayor de ellos por la diferencia entre ambos.

Este es el núcleo del algoritmo de Euclides por diferencias. En la práctica quizás haya que intercambiar los valores de A y B, pero no entraremos en esos detalles.

Al restar dos impares se producirán nuevos factores 2, por lo que en la siguiente pasada del algoritmo los eliminará. Lo ves en las siguientes dos imágenes:

Reiteramos estas tres reglas hasta que lleguemos al valor 0. En ese momento el algoritmo construye el M.C.D. multiplicando el resultado por la potencia de 2 que tenía almacenada.
Aquí lo tienes:

Visto así, en hoja de cálculo, no parece ser nada del otro mundo, pero todas las operaciones que realiza son altamente eficientes en el sistema de numeración binario. Por algo lo introdujo el programador israelí Stein en 1967. Aquí sólo se nos queda como un tema de cultura matemática, pero es divertido implementarlo.

Versión recursiva

Lo que hemos desarrollado, con un botón que en cada paso reacciona según lo que se encuentra, nos permite sospechar que todo esto se resuelve también mediante una función recursiva. Es cierto, y está publicado. Lo que haremos aquí es adaptarlo al Basic de Excel y Calc:

Public Function mcdbin(m, n)
Dim mb

'Si son iguales, hemos llegado al MCD
If m = n Then
mb = m

'Si ambos son divisibles entre 2, se saca ese factor
ElseIf m / 2 = m \ 2 And n / 2 = n \ 2 Then
mb = 2 * mcdbin(m / 2, n / 2)

'El primero contiene un 2. Se elimina
ElseIf m / 2 = m \ 2 Then
mb = mcdbin(m / 2, n)

'Operamos de igual forma con el segundo
ElseIf n / 2 = n \ 2 Then
mb = mcdbin(m, n / 2)

'Ambos son impares. Se restan
Else
If m > n Then mb = mcdbin(m - n, n)
If n > m Then mb = mcdbin(m, n - m)
End If

'La función recoge el valor de mb
mcdbin = mb
End Function

Tiene toda la elegancia de las funciones recursivas
(ver http://hojaynumeros.blogspot.com.es/2012/03/funciones-recursivas-en-las-hojas-de.html)

En este caso resulta un poco complicada, pero funciona muy bien. Si te apetece, estudia la versión clásica y recursiva:

Public Function mcdeuclid(m, n)
Dim mb

'Si uno es múltiplo de otro, obtenemos el MCD
If m / n = m \ n Then
mb = n
ElseIf n / m = n \ m Then
mb = m
Else
'En caso contrario, se restan
If m > n Then mb = mcdeuclid(m - n, n)
If n > m Then mb = mcdeuclid(m, n - m)
End If
'La función recoge el valor de mb
mcdeuclid = mb
End Function

Ambas están implementadas en la herramienta que ofrecemos.

Funciones generatrices en Combinatoria– La teoría

2013-03-14T14:30:00.000+01:00

En la entrada anterior presentábamos como un artificio sustituir los elementos de un producto cartesiano condicionado de conjuntos numéricos por polinomios en una indeterminada con exponentes idénticos a los números a combinar.

Hoy lo convertiremos en un desarrollo teórico.

Función generatriz de un conjunto numérico

Dado un conjunto ordenado de números reales o complejos (aquí usaremos casi exclusivamente los enteros positivos) {a₀, a₁, a₂, a₃,…a_n} llamaremos función generatriz (ordinaria) o generadora del mismo al polinomio de la forma

Si el conjunto tiene infinitos términos sustituiremos el polinomio por una serie de potencias, pero en este caso la igualdad

sólo tendrá sentido si dicha serie posee un radio de convergencia no nulo y la función está definida dentro de ese radio. No obstante, aquí no trataremos la convergencia, sino las relaciones entre coeficientes. Si no converge, P(x) no será una función, pero las técnicas siguen valiendo.

Casos sencillos

El caso más sencillo de función generatriz es la que corresponde al conjunto {1,1,1,1,…1}
Si este es finito con n elementos, sabemos que su función generatriz se puede obtener mediante la fórmula de la suma de una progresión geométrica

Ya usamos esta fórmula en la entrada anterior

Si el conjunto es infinito {1,1,1,1,…}también es sencillo verificar que

Aquí nos encontramos con la potencia que tiene este método. Si derivamos miembro a miembro (omitimos detalles y también la cuestión de la convergencia) nos encontraremos con que

Por tanto esta es la función generatriz del conjunto {1,2,3,4,….}

La fórmula del binomio de Newton nos proporciona otro ejemplo de función generatriz. Los números combinatorios para un n dado tienen por función generatriz (1+x)ⁿ ya que

Podíamos seguir dando ejemplos hasta llenar páginas enteras, pero destacaremos especialmente dos técnicas

Manipulación algebraica

Con las técnicas algebraicas y sin plantearnos ahora el problema de la convergencia podemos encontrar la función generatriz de muchos conjuntos de coeficientes.

Por ejemplo, es fácil encontrarla para los números de Fibonacci F0, F1, F2, F3, F4…, de los que suponemos se conocen sus valores y propiedades. Observa estas manipulaciones:

F(x)=F₀+F₁x+F₂x²+ F₃x³+ F₄x⁴+…=
F₀+F₁x+(F₀+F₁)x²+(F₁+F₂)x³+(F₂+F₃)x⁴+… =
F₀+F₁x+(F₀ x²+ F₁ x³+ F₂ x⁴+…) + (F₁ x²+ F₂ x³+ F₃ x⁴+…)

Pero en los paréntesis se está reconstruyendo F(x) de alguna forma, por lo que podemos escribir (pon tú los detalles)

F(x)= F₀+F₁x+F(x) x²+(F(x)- F₀)x

Despejamos F(x), sustituimos F₀ por su valor 0 (a veces se toma 1) y F₁ por 1 y ya la tenemos:

Sólo hemos usado técnicas algebraicas sencillas. Más adelante comprobaremos este resultado.

Manipulación analítica

Si consideramos la derivación e integración formales podemos encontrar fácilmente funciones generatrices. Ya hemos considerado un ejemplo de derivación.

De la misma forma podemos usar la integración. Por ejemplo en la geométrica podemos integrar

Nos resultaría entonces

En cualquier manual puedes encontrar muchos ejemplos similares de este tipo de manipulación. No olvides que podemos mezclar las dos técnicas, analítica y algebraica, así como sumar, multiplicar y otras.

Problema inverso

Si la serie que define la función generatriz converge y conocemos esta, encontrar los coeficientes de la serie siempre es posible por la fórmula de McLaurin

Es un camino muy pesado, pero seguro. Sin embargo el problema contrario de dar los coeficientes y encontrar la expresión de P(x) quizás no lo puedas resolver. Es el clásico problema de la suma de series.

Con la ayuda de un ordenador se puede simplificar el proceso. Damos un ejemplo:

Antes vimos que los números de Fibonacci tenían como función generatriz (si se toma F0=0. A veces se toma F0=1 y entonces tiene una expresión ligeramente distinta)

Si tuviéramos posibilidad de desarrollar por McLaurin en algún lenguaje o programa, nos ahorraríamos mucho trabajo. Nosotros lo hemos hecho con el lenguaje PARI. Se entiende fácilmente aunque no se haya usado nunca:

{write("final.txt",taylor(x/(1-x-x^2), x,12))}

Ordenamos que escriba en el archivo “final.txt” 12 términos del desarrollo de Taylor (es en x=0) de la función dada. El resultado es:

0+x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 8*x^6 + 13*x^7 + 21*x^8 + 34*x^9 + 55*x^10 + 89*x^11 + O(x^12)

Como vemos, los coeficientes son los números de Fibonacci. Si quisiéramos hacer F0=1 nos daría otro resultado, pues la función generatriz seria 1/(1-x-x2) (intenta demostrarlo)

Programaríamos en PARI esta variante:

{write("final.txt",taylor(1/(1-x-x^2), x,12))}

Obtendríamos la sucesión comenzando en 1:

1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 8*x^5 + 13*x^6 + 21*x^7 + 34*x^8 + 55*x^9 + 89*x^10 + 144*x^11 + O(x^12)

Lo podemos intentar con el ejemplo de la entrada anterior, el de las bolas de colores, cuya función generatriz sin desarrollar era

Deberíamos escribir en PARI

{write("final.txt",taylor(x^5*(x^4-1)^2*(x^5-1)/(x-1)^3, x,20))}

Obtendríamos

x^5 + 3*x^6 + 6*x^7 + 10*x^8 + 13*x^9 + 14*x^10 + 13*x^11 + 10*x^12 + 6*x^13 + 3*x^14 + x^15 + O(x^20)

Identificamos los resultados de la entrada anterior: Con grado 9 el coeficiente es el esperado, 13. Para el grado 14 sólo 3 y para el grado 7 los 6 que ya se obtuvieron.

En otra entrada posterior veremos las funciones generatrices de combinaciones, variaciones y demás. Hoy seguiremos con ejemplos:

¿De cuántas formas se puede descomponer el número 28 como suma de primos distintos?

Los primos inferiores a 28 son 2, 3, 5, 7, 11, 13, 17, 19, 23. Cada uno de ellos o está en la suma una vez o no está. Entonces podemos usar términos del tipo (1+x^7) o (1+x^11) para combinarlos en la función generatriz:

F(x)= (1+x²) (1+x³) (1+x⁵) (1+x⁷) (1+x¹¹) (1+x¹³) (1+x¹⁷) (1+x¹⁹) (1+x²³)

Desarrollamos con wxMmaxima y nos da (hemos recortado la imagen):

Vemos que para el exponente 28 el coeficiente es 6, luego existen 6 formas distintas de expresar 28 como suma de primos distintos

Lo comprobamos con nuestra herramienta PARTLISTA (http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#reprenum)

Con ella vemos las seis sumas: 28=11+17=5+23=3+5+7+13=2+7+19=2+3+23=2+3+5+7+11

Con la función generatriz hemos conseguido también otros muchos coeficientes, pero cuidado con la lista de primos 2, 3, 5, 7, 11, 13, 17, 19, 23. Este desarrollo sólo valdría hasta el 28. Para números mayores deberíamos añadir (1+x^29)(1+x^31)…

Luego con la función generatriz podemos resolver varios problemas a la vez.

Estos desarrollos algebraicos son pesados incluso con ayuda de los CAS. Sería bueno elegir un solo coeficiente en ellos. El lenguaje PARI que estamos usando últimamente (es gratuito aunque de gestión poco amigable) posee la función POLCOEFF(P(x),E) en la que P(x) es un polinomio y E un exponente dado, y nos devuelve el coeficiente de ese polinomio correspondiente al grado E. Nuestro problema del 28 se calcularía así:

print(polcoeff((x^2+1)*(x^3+1)*(x^5+1)*(x^7+1)*(x^11+1)*(x^13+1)*(x^17+1)*(x^19+1)*(x^23+1),28))

Daría un resultado de 6. Si cambiamos 28 por un número inferior obtendremos más resultados. Para números superiores deberíamos incrementar los primos.

Funciones generatrices en Combinatoria

2013-03-07T15:00:00.000+01:00

Nota: Esta entrada es la primera de una serie que dedicaremos a las funciones generatrices y a los productos cartesianos condicionados. Aunque estarán enlazadas dentro de una secuencia lógica, para no convertir este blog en un tratado primaveral sobre Combinatoria, las iremos alternando con varias referentes a otros temas, en los que no abandonaremos nuestros queridos números ni a las hojas de cálculo.

Antes de iniciar cualquier planteamiento teórico sobre las funciones generadoras (o generatrices), muy usadas en Combinatoria y en el estudio de las sucesiones de números, las introduciremos mediante un ejemplo. Después, en sucesivas entradas, estudiaremos el concepto con más profundidad. Al principio no se ve bien la utilidad de estas funciones, pero si lees la serie entera que vamos a ir publicando descubrirás que constituyen un buen instrumento de cálculo. Paciencia, pues.

Problema

Deseamos elegir nueve cuentas de colores. Disponemos de cantidad suficiente de cuentas rojas, amarillas y verdes, pero queremos elegir entre 2 y 5 rojas, menos de 4 amarillas y al menos 3 verdes. ¿De cuántas formas podemos efectuar la elección?

Este problema nos plantea el desarrollo de particiones condicionadas de un número.

Ya hemos tocado este tema en el blog (http://hojaynumeros.blogspot.com.es/2011/02/particiones-de-un-numero.html y en
http://hojaynumeros.blogspot.com.es/2011/02/funciones-de-particion-de-un-numero.html)

Independientemente de que se trate de particiones, intentaremos resolver el problema con varias técnicas, y entre ellas la del uso de una función generatriz.

Con un producto cartesiano

Como de las rojas hemos de elegir entre 2 y 5, de las amarillas de 0 a 3 y de las verdes un mínimo de 3 y un máximo de 7 (¿por qué 7?), bastará formar el producto cartesiano {2,3,4,5}{0,1,2,3}{3,4,5,6,7} e ir eligiendo las ternas que sumen 9. Un problema totalmente elemental que se puede resolver en enseñanzas medias.

A poco que nos pongamos obtendremos: 9= 2+0+7 = 2+1+6 = 2+2+5 = 2+3+4 = 3+0+6 = 3+1+5 = 3+2+4 = 3+3+3 =4+0+5 = 4+1+4 = 4+2+3 = 5+0+4 = 5+1+3.

En total 13 particiones. Para este problema no se necesitarían más técnicas, pero lo estamos tomando como modelo sencillo de introducción.

Con la hoja de cálculo “Cartesius”, aún en fase beta y que presentaremos más adelante, se pueden construir productos cartesianos condicionados. En el problema que nos ocupa plantearíamos esto, que se comprende sin más explicación:

Y obtendríamos

Como era de esperar, son los mismos resultados. Veamos ahora el método que deseamos explicar hoy.

Función generatriz

La idea revolucionaria de la función generatriz consiste en sustituir los distintos elementos numéricos por potencias de una indeterminada, y los conjuntos convertirlos en polinomios. Así el producto cartesiano {2,3,4,5}{0,1,2,3}{3,4,5,6,7} se puede escribir en forma de producto de polinomios:

Es fácil darse cuenta de que si multiplicamos algebraicamente estos polinomios, el término de grado 9 tendrá como coeficiente el número de particiones pedido, en este caso 13.

Hemos sustituido una técnica de conteo por otra de tipo algebraico o analítico (esto último lo veremos más adelante)

En este caso tan sencillo parece que esto es una complicación, pero en casos generales veremos que puede resultar muy útil. Por dos motivos:

Las técnicas algebraicas y analíticas permiten simplificar estos productos y encontrar directamente el coeficiente deseado.
Al desarrollar estos polinomios no sólo resolvemos el problema para 9 cuentas, sino para cualquier otro total posible.

Disponemos en este caso de una ayuda, y es que sabemos sumar muy bien las progresiones geométricas. Así, el producto de polinomios dado se puede expresar como

Este a su vez se puede simplificar como

Con tres pasadas del algoritmo de Ruffini encontraremos todos los coeficientes (omitimos los que no influyen en el problema)

Hemos destacado el que nos interesa: con grado 9 aparece el coeficiente 13, que es la solución, pero este procedimiento nos devuelve mucho más. Por ejemplo, con suma 7 sólo son posibles estas elecciones: 7=2+0+5=2+1+4=2+2+3=3+0+4=3+1+3=4+0+3, seis en total, como marca el esquema, y con suma 14 sólo deberán aparecer 3. Son estas: 4+3+7 = 5+3+6 = 5+2+7

Hemos resuelto varios problemas en uno

Si dispones de un CAS puedes ahorrarte bastante trabajo. Aquí tienes el resultado con la calculadora Wiris (hemos recortado la imagen) Compara los coeficientes con los que resultan con Ruffini.

Es normal que pienses que es mucha complicación, pero se trataba de un problema elemental. En sucesivas entradas daremos un enfoque teórico a las funciones generatrices y nos complicaremos un poco, descubriendo así su utilidad.

Carnaval de triangulares

2013-02-27T16:00:00.000+01:00

Esta entrada se ha desbordado, como una serpentina que al arrojarla ya no puede volver a ser rollo. Comenzamos estudiando variantes de la entrada anterior

(http://hojaynumeros.blogspot.com.es/2013/02/de-los-triangulares-alojados-los-primos.html)

y a la multiplicidad de divisores triangulares le siguió su suma, las coincidencias en esa suma y la reconstrucción de otro triangular. Por ello, aunque sea infrecuente en un blog, comenzamos con un esquema:

* Número de divisores triangulares (http://oeis.org/A007862)

Cálculo general
Números con un solo divisor triangular propio (http://oeis.org/A203468)

* Suma de divisores triangulares (http://oeis.org/A185027)

* Curiosidades

Números con suma de triangulares también triangular (http://oeis.org/A209309)
Números triangulares con la misma propiedad (http://oeis.org/A209310)
Otras curiosidades menores
Caso en el que la suma de divisores triangulares es otro divisor (http://oeis.org/A209311)

Número de divisores triangulares

Vimos en la entrada anterior que el número 40 posee una parte triangular igual a 10, que le permite ser representado como un prisma triangular.

Esta representación 40=4*T₄ es única (en toda la entrada no consideramos el triangular 1, por lo que no volveremos a citarlo). Ningún otro número triangular menor o igual que 40 (3, 6, 10, 15, 21, 28 o 36) lo divide salvo el 10. Esto por lo que se refiere al 40, pero existen otros números que admiten varias representaciones. El 30 admite cuatro: 30=10*T₂ = 5*T₃ = 3*T₄ = 2*T₅

No es difícil contar los divisores triangulares que posee un número N (al menos, el 1). Basta cambiar el algoritmo que publicamos en la anterior entrada para que cuente en lugar de quedarse con el mayor

Public Function numdivtriang(n)
Dim p, i, t, tr

p = Int((Sqr(n * 8 + 1) - 1) / 2) ‘Calcula el máximo orden
t = 1
For i = 2 To p
tr = i * (i + 1) / 2 ‘forma todos los triangulares menores o iguales a n
If n / tr = n \ tr Then t = t+1 ‘si es divisor, incrementa el contador
Next i
numdivtriang = t ‘se queda con el mayor
End Function

Esta función cuenta el 1, por lo que para 30 dará 5 posibilidades y para 40 sólo 2. En la siguiente tabla parcial lograda con hoja de cálculo lo puedes comprobar

30 5
31 1
32 1
33 2
34 1
35 1
36 4
37 1
38 1
39 2
40 2

Este resultado lo tienes en http://oeis.org/A007862 y es interesante leer los comentarios que se incluyen.

Números con un solo divisor triangular propio mayor que 1

El caso del 40 no es único. Hay muchos números que sólo pueden representarse de una sola forma como un prisma triangular con base y altura mayores que uno (para evitar trivialidades). Son estos:

6, 9, 15, 20, 21, 27, 33, 39, 40, 50, 51, 56, 57, 69, 70, 80, 81, 87, 93, 99, 100, 111, 112, 117, 123, 129, 130, 141, 153, 159, 160, 170, 171, 177, 182, 183, 190, 196, 200, 201, 207, 213, 219, 224, 230, 237, 243…

Los hemos publicado en http://oeis.org/A203468

Prueba con cualquiera de ellos, el 182=2*7*13. Puedes usar la propiedad que vimos de que su doble ha de tener dos divisores consecutivos. 364=2*2*7*13 y su conjunto de divisores es {364, 182, 91, 52, 28, 26, 14, 13, 7, 4, 2, 1}. Los únicos divisores consecutivos son 13 y 14, que dan lugar a un único divisor triangular de 182, el 91.

Por cierto, su consecutivo 183 presenta la misma situación: su único divisor triangular es el 3. No es el único par de consecutivos contenido en la sucesión. Por ejemplo, tenemos 170 y 171.

Dentro de esta sucesión figuran números triangulares. Todos ellos presentarán tres divisores triangulares: ellos, un divisor propio y la unidad. Así, 351 tiene como únicos divisores triangulares 1, 3 y el propio 351.

Suma de divisores triangulares

Además de considerar la suma de todos los divisores de un número, puede resultar curioso sumar sólo los de un tipo. Por ejemplo, el número 720 tiene como suma de divisores 2418, pero si sólo consideramos los que son cuadrados, sumarían 210=144+36+ 16+9+4+1 y con los triangulares 236=120+45+36+15+10+6+3+1. Se pueden considerar otros tipos de divisores: los pares, los oblongos…

Un algoritmo un poco burdo, pero que funciona, es el de recorrer todos los posibles divisores y someter a cada uno a una condición antes de incorporarlo a la suma. Aquí tienes el que hemos usado para cuadrados y triangulares:

Public Function sumadiv(nume, tipo)
'tipos
'0 da todos los divisores
'1 los cuadrados
'2 los triangulares

Dim i, s

s = 0
For i = 1 To nume
If esmultiplo(nume, i) Then
If tipo = 0 Then s = s + i
If tipo = 1 And escuad(i) Then s = s + i
If tipo = 2 And estriangular(i) Then s = s + i
End If
Next i
sumadiv = s
End Function

Con un algoritmo similar hemos publicado en OEIS la función que recoge la suma de los divisores triangulares de los primeros números naturales:

1, 1, 4, 1, 1, 10, 1, 1, 4, 11, 1, 10, 1, 1, 19, 1, 1, 10, 1, 11, 25, 1, 1, 10, 1, 1, 4, 29, 1, 35, 1, 1, 4, 1, 1, 46, 1, 1, 4, 11, 1, 31, 1, 1, 64, 1, 1, 10, 1, 11, 4, 1, 1, 10, 56, 29, 4, 1, 1, 35, 1, 1, 25, 1, 1, 76…
(http://oeis.org/A185027)

Curiosidades

Esta sucesión da lugar a varias curiosidades:

La suma de triangulares puede ser triangular.

Excluimos el caso en que sea igual a 1 por trivial. Estos son los números que lo cumplen:

6, 12, 18, 24, 48, 54, 96, 102, 110, 114, 138, 162, 174, 186, 192, 204, 220, 222, 228, 246, 258, 282, 315, 318, 348, 354, 364, 366, 372, 384, 402, 414, 426, 438, 440, 444, 456, 474, 486, 492, 498, 516, 522, 534, 550…
También la acabamos de publicar (http://oeis.org/A209309)

Por ejemplo, 444 tiene como divisores triangulares 6, 3 y 1, y su suma es 10 que es triangular. Más complejo sería el caso de 1320, cuyos divisores triangulares, 120, 66, 55, 15, 10, 6, 3 y 1 suman 276, que es triangular igual a 23*24/2.

Similares a esta, pero menos exigentes, son estas condiciones:

(1) La suma de los divisores ordinarios es triangular
1, 2, 5, 8, 12, 22, 36, 45, 54, 56, 87, 95, 98, 104, 116, 152, 160, 200,… (A045746)

(2) La que es triangular es la suma de las partes alícuotas, y mayor que 1
2,4,6,14,16,18,24,25,28,33,36,51,54,66,91,112,...(no publicada)

(3) Números triangulares en los que la suma de sus divisores propios es también triangular
1, 3, 6, 28, 36, 66, 91, 231, 496, 8128, 14196, 15225, 129795, 491536,… (A083675)

(4) Números triangulares cuya suma de divisores es también triangular
1, 36, 45, 23220, 105111, 135460, 2492028, 5286126, 6604795, 14308575, 45025305, 50516326, 54742416, 99017628, 108125865, 152486916,... (A083674)

Ahora viene la nuestra, la más exigente:

Números triangulares cuya suma de divisores triangulares es mayor que 1 y triangular

Esto es ya mucho exigir, por lo que las soluciones crecen rápidamente:

6, 4186, 32131, 52975, 78210, 111628, 237016, 247456, 584821, 750925, 1464616, 3649051, 5791906, 11297881, 16082956, 24650731, 27243271, 38618866, 46585378, 51546781, 56026405, 76923406, 89880528, 96070591…(http://oeis.org/A209310)

El estudio del código PARI de esta sucesión te enseñará técnicas útiles:

istriangular(n)=issquare(8*n+1)
{t=0; for(n=1, 10^8, if(istriangular(n), k=sumdiv(n, d, istriangular(d)*d) ; if(istriangular(k)&&k>>1, t+=1; write("b209310.txt", t, " ", n))))}

Y por último, para no cansar (si es que has llegado hasta aquí), la última curiosidad

Números en los que la suma de divisores triangulares es mayor que 1 y divisor del número

285, 1302, 1425, 1820, 2508, 3640, 3720, 4845, 4956, 5016, 5415, 7125, 7280, 9100, 9114, 9912, 11685, 12255, 12740, 14508, 15105, 16815, 17385, 18200, 19095, 19824, 20235, 20805, 22134, 22515, 23655, 23660, 24021, 24738…http://oeis.org/A209311

Aquí tienes dos ejemplos:

285.-Divisores triangulares:1, 3 y 15 y su suma, 19, es divisor de 285

1302.- Divisores triangulares: 21 + 6 + 3 + 1 = 31 que es divisor de 1302.

Código PARI

istriangular(n)=issquare(8*n+1)
{t=0; for(n=1, 10^7, k=sumdiv(n, d, istriangular(d)*d); if(n/k==n\k&&k>>1, t+=1; write("b209311.txt", t, " ", n)))}

Nos queda algo en el tintero, porque en esta última el cociente puede ser también triangular, pero esto queda para otro día.

De los triangulares alojados a los primos de Sophie Germain

2013-02-20T16:00:00.000+01:00

Esta entrada participa en la Edición 4.1 del Carnaval de Matemáticas cuyo anfitrión es Tito Eliatron Dixit.

Si tomamos 40 cubos, los podemos apilar en forma de prisma con base un triángulo isósceles y rectángulo, o en términos aritméticos, un número triangular mayor que 1. Excluimos la unidad porque en ese caso se pierde la forma triangular.

Este ejemplo es válido porque 40=4*10, y 10 es el cuarto número triangular.

No todos los números enteros se pueden representar así, pues han de ser múltiplos de un número triangular y eso no siempre ocurre. Por ejemplo, el 14, ya que entre sus divisores no figuran 3, 6 ó 10, que son los triangulares menores que él (recuerda que excluimos el 1). Esto ya nos divide el conjunto de los números naturales entre los que tienen divisores triangulares mayores que 1 y los que no.

Los segundos, que no admiten la representación propuesta, son 1, 2, 4, 5, 7, 8, 11, 13, 14, 16, 17, 19, 22, 23, 25, 26, 29, 31, 32, 34, 35, 37, 38… (http://oeis.org/A112886) y les llamaremos libres de triangulares. Verás que están los primos, algunos semiprimos, potencias de primos y otros a los que volveremos más adelante.

Parte triangular y parte libre de triángulos

Sabemos que los primeros admiten un divisor triangular pero, como pueden ser varios, nos quedaremos con el mayor: llamaremos parte triangular (PTR) de un número al mayor divisor triangular que posea. Si has leído sobre estos temas, te recordará esto a la parte cuadrada y la parte libre de un número (http://hojaynumeros.blogspot.com.es/2011/05/parte-cuadrada-y-parte-libre.html)

El mayor divisor triangular puede ser 1 o el mismo número, como se comprueba en la lista de todos ellos (http://oeis.org/A115017):

N 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22…
PTR 1, 1, 3, 1, 1, 6, 1, 1, 3, 10, 1, 6, 1, 1, 15, 1, 1, 6, 1, 10, 21, 1…

En ella están los libres de triangulares, que son los que se corresponden con un 1, como el 4 y el 5, los triangulares, cuya PTR son ellos mismos, como 6 y 10, y el resto, en el que se tiene una parte triangular y otra libre ambas mayores que la unidad. Es el caso de 12 o 40. La parte libre de estos últimos está recogida en http://oeis.org/A121289

Una idea: dos números con la misma parte libre y partes triangulares consecutivas formarán un prisma cuadrado. Imagina el prisma de la primera imagen y su complementario.

Búsqueda de la parte triangular

Un algoritmo simple es el de ir recorriendo los números naturales k, formar con ellos los triangulares mediante k(k+1)/2 e ir verificando si el número dado N es múltiplo de alguno. El mayor de todos ellos será la PTR(N).

Previamente es bueno calcular el orden del máximo triangular que es menor o igual que N, para acortar el ciclo de búsqueda. Se deja a los lectores la demostración de que ese orden k se calcula mediante

En hoja de cálculo sería =ENTERO((RAIZ(8*N+1)-1)/2)

Por ejemplo, para N=14534, k=169 y el mayor triangular menor que N, 169*170/2 = 14365. A nosotros nos interesaría el 169, porque entre 2 y 169 estaría el orden del triangular buscado. Todo esto se puede plasmar en una función:

Public Function partetriang(n)
Dim p, i, t, tr

p = Int((Sqr(n * 8 + 1) - 1) / 2) ‘Calcula el máximo orden
t = 1
For i = 2 To p
tr = i * (i + 1) / 2 ‘forma todos los triangulares menores o iguales a n
If n / tr = n \ tr Then t = tr ‘si es divisor, toma nota
Next i
partetriang = t ‘se queda con el mayor
End Function

El algoritmo busca los triangulares entre el menor 3 y el mayor k(k+1)/2 y se va quedando con los divisores. El último encontrado será PTR(A).

Si en lugar de recoger el valor de i*(i+1)/2 hubiéramos ido recogiendo i, nos hubiera resultado el orden de PTR. Los tienes en http://oeis.org/A083312

¿Qué números dan alojamiento a un triangular?

Para que N tenga un divisor triangular mayor que 1 se ha de poder escribir de la forma N=k(k+1)*M/2 con k>1. Esto da lugar a varias interpretaciones:

(a) N tiene un divisor triangular mayor que 1, si y sólo si 2N posee dos divisores consecutivos mayores que 1.

Es condición necesaria, pues la expresión de 2N sería 2N=k(k+1)*M con k>1, con lo que k y k+1 son los divisores pedidos.

Por ejemplo, el triangular 21 divide a N=8883, con lo que el doble 17766=6*7*423 contiene a los consecutivos 6 y 7.

La condición es suficiente: Si 2N posee dos divisores consecutivos h y h+1 con h>1, estos serán primos entre sí, luego su MCM(h,h+1) será su producto h(h+1). Como 2N es múltiplo de h y h+1, lo será de su MCM, es decir de su producto. Por tanto 2N=h(h+1)P y será múltiplo del triangular h(h+1)/2, ya que uno de los dos h o h+1 es par.

Los números 2N de este tipo los tienes en http://oeis.org/A132895. Son el doble de un número libre de triángulos.

Sería interesante que pensaras en un algoritmo que descubriera esos números.

(c) Los semiprimos N=p*q son números libres de triángulos salvo que uno de sus factores sea 3, o bien q=2p±1

En efecto, si N=p*q con p y q primos, 2N=2pq ha de contener dos divisores consecutivos. Si p o q fueran iguales a 3, ya se cumpliría, porque 2N=2*3*k, pero entonces N sería múltiplo de 3.

Si ni p ni q son iguales a 3, lo serán a 2 o a un primo mayor que 3. Si por ejemplo p=2 entonces 2N=2*2*q y q se ve obligado a ser 3, con lo que pasamos al primer caso. Seria múltiplo de 3.

Así que sólo nos queda que N=p*q con p y q primos mayores que 3 y no son números consecutivos (porque son impares). En ese caso es claro que 2N=2pq no podría tener divisores consecutivos salvo que q=2p+1 o bien q=2p-1 (o simétricamente, p=2q+1 o 2q-1). En el primer caso p sería un primo de Sophie Germain.

Recuerda que los primos de Sophie Germain son aquellos en los que 2*p+1 también es primo: 2, 3, 5, 11,…

(d) Los números primarios (potencias de primos) están libres de triángulos salvo el caso N=3k

Esta es trivial: Si N=pk con k>1, entonces 2N=2pppp…sólo contendría divisores consecutivos en el caso 2N=2*3*3*3...

¿Se te ocurren más propiedades? A nosotros por ahora no.

Convertir esquemas de cálculo en tablas

2013-02-13T15:00:00.000+01:00

Desde este blog y nuestra página hojamat.es hemos promovido siempre el uso de esquemas de cálculo y apuntes interactivos (http://hojamat.es/contenidos/apuntes.htm)

La limitación que presentan es que al provenir de cálculos de cierta complejidad es difícil recogerlos en forma de función o tabla. En esta entrada presentaremos una herramienta sencilla para recoger resultados de esquemas en forma de tabla.

La herramienta

Al principio intentamos recogerlos como funciones, pero ni Excel ni OpenOffice ni LibreOffice lo permiten. Hay algo en la programación de funciones que hace que si se altera el valor de una celda cualquiera dentro del proceso de cálculo de la función, esta no recoja el valor que ha de devolver. Continuamente da mensajes de error.

Lo que sí podemos es construir una tabla que altere los parámetros del esquema y recoja el valor final del cálculo. Como estamos abusando de generalidades, lo explicaremos mejor con un ejemplo.
Partiremos del cálculo del fósil de un número (http://hojaynumeros.blogspot.com.es/2008/10/dndole-vueltas-2.html)

Este valor se halla multiplicando las cifras de un número, volviendo a realizar esta operación en el resultado y en los siguientes hasta llegar a un número de una cifra al que llamamos fósil.

Por ejemplo, partimos de 876, multiplicamos 8*7*6=336. Volvemos a multiplicar y reiteramos. 3*3*6=54, 5*4=20, 2*0=0, luego el fósil de 876 es 0.

Este cálculo lo podemos tener implementado en una hoja mediante un esquema (en este momento no nos va a interesar qué fórmulas se han usado)

Lo que deseamos es poder extraer de este esquema una tabla de valores y un gráfico si vamos cambiando el 876 por ejemplo en el intervalo 860…880. Esta tarea la realiza la hoja de cálculo esquefun, que está alojada en http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#esquefun

Tabla simple

Si la abres verás que la primera hoja estará en blanco o contendrá un esquema de cálculo cualquiera. En el segundo caso puedes borrarlo todo y construir tu propio proceso. No sobrepases el tamaño de una pantalla o algo más (unas treinta filas por treinta columnas).

En la segunda hoja se te ofrece la posibilidad de construir la tabla

¿Cómo se consigue esto? Lo explicaremos paso a paso para una tabla simple X,FX:

(1) En la primera hoja, en la celda que está a la izquierda del valor de la variable independiente escribes una X. Debes procurar tener esa celda siempre libre. También es conveniente que uses las primeras filas y columnas.

(2) También a la izquierda del resultado que te interese como valor de la función (en nuestro caso el fósil) escribes una F.

Si tu resultado no está en ellas siempre puedes copiarlas dinámicamente. Por ejemplo, si tienes el resultado en la celda AH44, basta que en una celda más arriba y a la izquierda escribas la fórmula =AH44 y así todos los resultados se copiarán a esa celda.

Con eso ya has terminado la preparación de la hoja 1: Escribir “X” a la izquierda de la variable independiente y una “F” al lado de la variable dependiente.

(3) En la segunda hoja define el mínimo, máximo y salto de la tabla que deseas para concretar los valores de X en la misma (puedes hacerlo de forma manual, pero sería cosa tuya borrar en la columna de la X todos los datos sobrantes)

(4) Pulsa el botón FX y obtendrás tabla y gráfico de los resultados. En el volcado de pantalla de más arriba puedes observar que la tabla va de 860 a 880 y que el comportamiento del fósil es totalmente irregular.

Ya está. No hay que trabajar más. Después tabla y gráfico los puedes exportar a cualquier otro documento.

Tabla simple con dos funciones

Lo explicamos también con un ejemplo:

Deseamos hacer entender a nuestro alumnado que la raíz de una suma no da el mismo resultado que la suma de raíces. Para ello hemos pensado en usar

Preparamos un esquema de cálculo en el que se manifiesten las diferencias. Podía ser este:

Si ahora deseamos ver en un gráfico cómo evolucionan las diferencias necesitaremos definir dos funciones. Así que rotulamos con X el número, con F el primer cálculo y con G el segundo (estos nombres son obligatorios)

A partir de este esquema ya rotulado podemos crear tabla y gráfico

Hemos construido una tabla del 10 al 2000 con saltos de 10, con la ¿sorpresa? de que las diferencias tienden a estabilizarse a valores cercanos al 2

En la imagen aparece una tercera columna de diferencias que se han creado manualmente. El objetivo de construir la tabla a partir del esquema se ha conseguido.

En cursos algo más avanzados puedes intentar demostrar que efectivamente el límite de la diferencia entre ambos resultados es 2.

Tabla doble

Sería también útil estudiar una función que dependiera de dos variables. Para eso dispones de la tercera hoja de esta herramienta. No se ha incluido el gráfico para no tener que insertar otra cuarta hoja, pero nuestros lectores sabrán cómo construirlo.

En este caso deberemos rotular con X e Y las dos variable independientes y con F la función. Lo explicaremos con un ejemplo que no tiene más interés que la mera curiosidad:

Sabemos que los pasos necesarios en el algoritmo de Euclides para obtener el MCD de dos números varía mucho según los datos usados. Intentemos formar una tabla de doble entrada con ellos.
Imagina que hemos trasladado a la primera hoja el algoritmo de nuestra herramienta Euclides (http://hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm):

Debemos ahora, después de comprobar que funciona bien, borrar los rótulos “Primer número” y “Segundo número” y sustituirlos por X e Y respectivamente. Abajo también sustituiremos “Número de cocientes” por F, para recoger su valor como una función. En este ejemplo tenemos un problema, y es que esas celdas están combinadas. Debes primero anular la combinación y después escribir X,Y,F de forma contigua a su valor.

Pasamos a la tercera hoja y definimos intervalos y saltos para X e Y, por ejemplo, de 20 a 30 con saltos de 1 (el carácter optativo se incluye porque se puede efectuar un relleno manual, aunque no es muy aconsejable).

Pulsamos el botón Fxy y se formará la tabla de doble entrada:

Llama la atención que no es simétrica para intercambios entre X e Y, pero es que si el primer número es menor que el segundo nos cuesta un paso más en el algoritmo.

Con los procedimientos habituales podemos traducirla a un gráfico 3D:

Estas son las tres modalidades de creación de tablas que hemos incluido en esquefun. Con ellas basta para encontrar usos en la enseñanza y como herramienta de búsqueda. Que os sea útil.

La hoja de cálculo gana cifras

2013-02-04T14:30:00.000+01:00

Calculadora STCALCU

Las estadísticas contenidas en la entrada anterior no hubieran sido posibles usando una hoja de cálculo normal. Ya es sabido que en ella cuando las cifras significativas de un número llegan a unas 15, se tratan automáticamente en coma flotante y notación científica. La única forma de mantener la expresión con todas las cifras es aumentando las prestaciones mediante un complemento o, como presentaremos aquí, mediante una colección de nuevas funciones.

Como mero divertimento emprendimos hace tiempo la tarea de dotar a las hojas de cálculo de la posibilidad de manejar números enteros con todas sus cifras, sin las limitaciones a las que nos hemos referido. Después de intentarlo con registros múltiples desembocamos en la decisión de usar variables de texto (string), como hemos visto en un trabajo similar al nuestro. Del hecho de manejar strings viene el prefijo ST que incorpora tanto la calculadora (STCALCU) como las funciones: stsuma, stresta,…La llamamos calculadora, aunque en realidad es una colección de funciones, pero para quien no se anime a manejarlas hemos incluido un esquema de cálculo con botones en la última hoja.

Representar un número mediante un string tiene una limitación, y es que las hojas de cálculo manejan en general cadenas de 255 caracteres. En la herramienta que presentamos se ha puesto un tope de 250, útil para la mayoría de los trabajos con números enteros.

Operaciones como funciones

Lo que presentamos ahora ha tenido un desarrollo totalmente personal (y por tanto sin la garantía de un producto profesional) y realiza los cálculos en forma de funciones. Así se pueden crear tablas o enlazar unos cálculos con otros con toda libertad. También así se podrán mezclar, con cuidado, nuestras funciones con las propias de Excel, OpenOffice o LibreOffice.

Con la implementación de las operaciones como funciones se consiguen varias ventajas:

Puedes escribir la función en cualquier celda, con lo que es fácil construir tablas y esquemas de cálculo.
Son independientes del resto de funciones de las hojas y se pueden mezclar con ellas (con cuidado)
No hay que preocuparse en exceso por la sintaxis de las expresiones algebraicas, que aquí se reducen a la aplicación reiterada de funciones. Así, A*B+C*D se escribiría como Stsuma(stmulti(A;B),stmulti(C;D)). Parece más complejo, pero todo es cuestión de costumbre.

La hoja que contiene la calculadora la tienes alojada en

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

En STCALCU dispones de las funciones más usuales. Si sabes programar podrás enriquecerlas con otras nuevas. Son estas:

Operaciones básicas

Son las clásicas (la raíz cuadrada resultaba costosa y poco útil), más el residuo

Operación Formato

SUMA =stsuma(A;B)
RESTA =sresta(A;B)
PRODUCTO =stmulti(A;B)
COCIENTE =stdivi(A;B)
POTENCIA =stpotencia(A;B)
RESTO =stresto(A;B)

Damos algunos ejemplos por si deseas reproducir alguno:

=stsuma(771662374885756;12636645869121) = 784299020754877
=stmulti(777654556988;299818) = 233154833967028184
=stpotencia(7;51) = 12589255298531885026341962383987545444758743
=stresto("27677841276031200";301)= 163

A y B son, en general, referencias a celdas, pero como ves en los anteriores ejemplos, se pueden usar números enteros directamente.

Hay que tener en cuenta estas consideraciones:

(a) Las funciones actúan sobre datos de tipo texto, pero frecuentemente la hoja los interpreta bien aunque no se escriban comillas. Observa el ejemplo anterior del resto, en el que sin comillas nos hubiera dado error. Para evitar esto es preferible usar las funciones sobre celdas, como en =stpotencia(Z12;W12), procurando que tengan formato de texto, también para ver mejor los datos, que, de otra forma aparecerían en formato de coma flotante.

(b) Las operaciones se pueden combinar como si fueran funciones. Esta fórmula te daría el séptimo número de Fermat

=stsuma(stpotencia(2;stpotencia(2;7));1) = 340282366920938463463374607431768211457

(c) Sobre ellas puedes definir otras funciones. Por ejemplo, el STCUBO

Public function stcubo$(x$)
Stcubo$=stpotencia(x$,”3”)
End function

Observa que prudentemente definimos todo como string

Otras funciones

Están orientadas a la divisibilidad, por lo que pueden ralentizarse en exceso si hay que factorizar

Función Formato

FACTORIZAR =stfactores(A)
ES MÚLTIPLO =stmultiplo(A;B)
ES PRIMO =stprimo(A)

STFACTORES

Te devuelve el conjunto de factores primos de un número con el formato usual de [primo1,exponente1] [primo2,exponente2] [primo3,exponente3]…

Ya se ha advertido que puede resultar muy lenta. Si tu paciencia se agota, pulsa ESC en Excel o CTRL+Mayúscula+Q en las otras.

Ejemplo:

stfactores(277311825)= [3,2],[5,2],[7,2],[25153,1]

Es decir, que 277311825=3^2*5^2*7^2*25153

STMULTIPLO

Devuelve VERDADERO si un número es múltiplo de otro

Ejemplo

Stmultiplo(36672753876570989401657263524087877113152819293759126100418746384384; 182273662712) = VERDADERO

STPRIMO

Devuelve VERDADERO si su argumento es primo. También puede resultar lenta.

Ejemplo

stprimo(7726631) = FALSO porque 7726631 = [11,1],[239,1],[2939,1]

Calculadora

Para quienes no se sientan muy a gusto manejando funciones se ha implementado en la tercera hoja de Stcalcu una calculadora simple en la que realizar los cálculos. Consultando el código de los botones implementados se pueden insertar otros nuevos. No es difícil.

Se ha habilitado una línea para el resto de la división, que aquí siempre es euclídea.

En la parte inferior figuran los botones de divisibilidad y aún más abajo unas memorias para almacenar datos intermedios. Todo el esquema es fácilmente revisable.

Con estas funciones y las estructuras del Basic de las hojas de cálculo puedes enriquecer el catálogo. Debes tener cuidado en declarar como string las variables que uses. Suerte.

Y de nuevo la advertencia: estás ante un trabajo no profesional. Si luego falla algo, ten paciencia.

Pandigitales, cromos y un poco de Benford (2)

2013-01-27T04:00:00.000+01:00

Esta es la segunda parte de nuestra participación en el Carnaval de Matemáticas, Edición 3.1415926535, cuyo anfitrión es La Aventura de la Ciencia.

Estudiamos en la anterior entrada cuándo unos resultados de potencias se convierten todos en pandigitales en sentido amplio (con repetición) Llegamos a la conclusión de que esto ocurre aproximadamente cuando la potencia alcanza unas 50 cifras. A partir de este resultado sospechamos que la distribución de cifras no presentan uniformidad.

Estadísticas de cifras

Según lo anterior, hemos de tener cuidado en considerar como casi uniforme la aparición de cifras en las potencias de un número. Si así aparecieran, deberíamos encontrar más similitud entre lo que se espera de un fenómeno aleatorio y este que nos ocupa.

La uniformidad

Para estudiar de forma empírica la distribución de cifras en las potencias hemos elegido las bases entre 2 y 9, a cada una la hemos elevado a todos los exponentes comprendidos entre 1 y 50, pues son los cálculos antecedentes de la región en la que desaparecen los resultados que no son pandigitales. Para ello nos ha sido útil nuestra calculadora STCALCU para hoja de cálculo (que presentaremos próximamente). Hemos obtenido este resultado:

(1) Las desviaciones típicas mayores se corresponden con los divisores del 10, 2 y 5. Después baja algo en los números no coprimos con 10: 4, 6 y 8. Por último, son más homogéneas en los coprimos, 3, 7 y 9. Esto tiene cierto sentido, pero no seguiremos por ahí.

(2) La distribución por cifras presentan un máximo en la cifra 1 (como en la Ley de Benford) de 11,2%, muy alejado del 8,7% de la cifra 0. Además, las cifras impares aparecen más que las pares. Esto lo afirmamos descriptivamente, pues una prueba chi-cuadrado no da significación.

(3) Casi todas las cifras presentan un máximo en la base igual a ellas. Las hemos destacado en rojo. Llama la atención el 14% del 5 y del 6. A eso no es ajeno el que en esas cifras coincidan las terminaciones de sus potencias sucesivas: 5, 25, 125, 625, … y 6, 36, 216,…Te puedes divertir intentando analizar otros casos.

Resumiendo, no aparece una uniformidad clara en los resultados, que más bien parecen sesgados hacia el 1 y los impares. ¿Se mantendrá esta tendencia para potencias mayores?

Hemos acumulado los resultados desde exponente 1 al 200, para ver cómo evoluciona la distribución de cifras, llegando a esto:

Aquí el panorama cambia algo: se percibe más uniformidad, aunque el 1 es la cifra que presenta mayor frecuencia. Por tanto debemos pensar que en las primeras potencias las cifras aparecen con frecuencias más alejadas del 10% y que eso es lo que produce que se tenga que llegar a unas 50 cifras para llegar a completar el carácter pandigital

La herencia

Otra pregunta sería pertinente: estas desviaciones de la uniformidad ¿se mantienen de cierta forma entre unas potencias y las posteriores dentro de una misma base? Si una cifra presenta una frecuencia en 2^N sería interesante saber cómo se comporta en 2^N+1. Pues bien, aquí tampoco se ve relación clara y significativa entre las frecuencias de un exponente con el siguiente. Tomamos como ejemplo la base 5 haciendo trampa, porque podía esperase que la cifra 5 y la 0 se mantuvieran en sus frecuencias al crecer N.

Basta ver los máximos y mínimos para darnos cuenta de lo alejada de la uniformidad que está la distribución de cifras. Respecto a la herencia, si recorres los porcentajes correspondientes a cada cifra sí se percibe una cierta constancia en la tendencia. No es importante. Le hemos aplicado la prueba Chi-cuadrado y no nos da una diferencia significativa respecto a la homogeneidad máxima.

Así que, por si acaso, no uses potencias para extraer números psudoaleatorios, que te puedes llevar sorpresas.

Nuestra Ley de Benford

Y ya puestos, ¿cómo se comportan las primeras cifras de cada potencia? Recuerda que según la Ley de Benford (en la Red tienes muchas referencias a ella, por ejemplo en http://www.estadisticaparatodos.es/taller/benford/benford.html),

se podría esperar un 30% para el 1, un 17% para el 2, 12% para el 3 y así disminuyendo para el resto, como se ve en la gráfica incluida en la página recomendada.

Lo intentamos: elevaremos las distintas bases de 2 a 9 (podían ser otras) a todos los exponentes comprendidos entre 1 y 250 y recogeremos las estadísticas de la primera cifra.
Son estas:

Esto quiere decir que respecto a la Ley de Benford las potencias se comportan admirablemente. Hemos comparado nuestras frecuencias con la fórmula de Benford LOG((d+1)/d) y nos ha resultado:

No necesita comentario. El comportamiento de las estadísticas globales viene dado más por las cifras intermedias que por la primera, que sigue la distribución esperada. A partir de aquí puedes emprender un estudio del que sólo hemos esbozado el principio.

Pandigitales, cromos y un poco de Benford (1)

2013-01-21T17:53:00.000+01:00

Esta es la primera parte de nuestra participación en el Carnaval de Matemáticas, Edición 3.1415926535, cuyo anfitrión es La Aventura de la Ciencia. El proximo día 27 publicaremos la segunda parte.

Hace unas semanas conocí esta conjetura:

El número 168 es el mayor N que cumple que la potencia 2^N no contiene todas las cifras del 0 al 9

http://www.johndcook.com/blog/2012/11/23/digits-in-powers-of-2/comment-page-1/#comment-316640

Es decir, a partir de 2^169 todas las potencias de 2 son pandigitales en sentido amplio, pues contienen todas las cifras, pero repetidas (usualmente se exige que los pandigitales presenten cada cifra una sola vez).

2^168 = 374144419156711147060143317175368453031918731001856
(le falta la cifra 2)

2^169 = 748288838313422294120286634350736906063837462003712
2^170 = 1496577676626844588240573268701473812127674924007424
2^171 = 2993155353253689176481146537402947624255349848014848
2^172 = 5986310706507378352962293074805895248510699696029696
2^173 = 11972621413014756705924586149611790497021399392059392
(todos contienen las cifras 0 al 9)

Esta conjetura también está publicada en http://oeis.org/A130696

Comienzo de los pandigitales

Nos podíamos preguntar qué ocurre con las demás bases y sus potencias. Hemos trabajado un poco con la hoja de cálculo y llegado a esta tabla, en la que figuran las siguientes bases (no múltiplos de 10, que serían casi triviales) y los exponentes hasta donde llega la carencia de alguna de las cifras en sus potencias

Esta tabla “huele” a inverso de un logaritmo. En efecto, si en lugar del tope en el que se acaban las potencias no pandigitales (con repetición) nos fijamos en las cifras de esas potencias llegamos a una cierta uniformidad, especialmente en las primeras:

Para que una potencia alcance un número de cifras se deberá cumplir de forma aproximada esta igualdad:

B es la base dada, T el tope no pandigital y C el número de cifras a partir del cual están representadas todas las posibles. Si tomamos este número de cifras en un promedio de 50, por ejemplo, nos daría una aproximación del tope:

El logaritmo es decimal, evidentemente. Si aplicáramos esta fórmula obtendríamos:

Resulta coherente con los cálculos, luego lo importante es el número de cifras. El tope es una consecuencia de ellas.

Esto no funciona como algo aleatorio

Este problema, si tuviera una base aleatoria se parecería al de completar una colección de cromos. Aquí la colección completa sería el conjunto {0,1,2,3,4,5,6,7,8,9} y los “cromos” se incorporarían uno a uno a la colección. Cuando aparezcan todos la colección estará completa, pero se habrán producido repeticiones.

En este blog estudiamos dichas colecciones de sobre en sobre, lo que no es este caso.

http://hojaynumeros.blogspot.com.es/2012/05/este-cromo-lo-tengo-repe-1.html
http://hojaynumeros.blogspot.com.es/2012/05/este-cromo-lo-tengo-repe-2.html

En otras direcciones puedes consultar una fórmula sencilla para cuando se incorporan a la colección los cromos de uno en uno, caso más parecido al que nos ocupa.

http://www.cienciaonline.com/2012/07/25/%C2%BFpor-que-nunca-complete-mi-coleccion-de-cromos/
http://www-eio.upc.es/~delicado/docencia/Daniel_Alcaide/Documento/PFC.pdf

En ellas puedes estudiar una fórmula que te da el total de cromos T que has de comprar para completar una colección de N

En el caso de diez cifras T=29,29

En nuestro ejemplo hemos necesitado más, unos 50. Es claro. Estamos comparando como mera diversión dos conceptos diferentes:

Los cromos aparecen de forma aleatoria y las cifras de las potencias constituyen un cálculo exacto, determinista.
En los cromos cada vez que sale uno ya lo tenemos definitivo y aquí en cada potencia hay que volver a empezar. Esto, en parte, justifica la discrepancia entre 29 y 50.
Aquí existe una relación clara de causalidad entre las cifras de 2^N y las de 2^N+1

Acabamos de afirmar que estudiamos un fenómeno determinista, pero si la distribución de cifras fuera muy uniforme, sus resultados se acercarían a los aleatorios. Cuidado: no confundas aleatorio con uniforme. Sólo afirmamos que los resultados serían más parecidos.

¿Cómo se comportan las potencias respecto a la frecuencia de las distintas cifras? ¿Qué grado de uniformidad presentan? Lo vemos en la siguiente entrada.

Números altamente compuestos (3)

2013-01-13T14:38:00.000+01:00

Encontrar sin ver

La hoja de cálculo tiene una precisión limitada en el cálculo con enteros, pero para encontrar números altamente compuestos no es necesario ver su desarrollo en el sistema de numeración decimal, pues basta poder dar los exponentes correspondientes de 2, 3, 5, 7, 11, 13,…(ver entradas anteriores) Así podemos estar seguros de haber encontrado un NAC aunque no lo veamos escrito, sólo leyendo los exponentes.

Hemos preparado una herramienta siguiendo las ideas contenidas en el documento http://wwwhomes.uni-bielefeld.de/achim/julianmanuscript3.pdf de D. B. Siano and J. D. Siano - Oct. 7, 1994

La idea consiste en manejar tan sólo las potencias del tipo

Para cada juego de exponentes tendremos en cuenta los siguientes hechos:

(a) El número 2N tiene más divisores que N, luego si tenemos un N altamente compuesto, para encontrar el siguiente partiremos de ese valor 2N hacia abajo, números cada vez más pequeños hasta llegar a N. Uno de ellos será el mínimo que cumpla el tener más divisores que N.

(b) Ramanujan descubrió una desigualdad doble para los exponentes de 2, 3, 5, 7,…en un NAC, que nos da el mínimo y máximo valor que han de tener estos en el desarrollo. Si llamamos aq al exponente con el que figura el número primo q en ese desarrollo, se cumple que

En la desigualdad p representa el último número primo del desarrollo y p+ el siguiente primo después de él.

Podemos recorrer todas las combinaciones posibles entre estas cotas para descubrir el próximo NAC a partir de un juego de exponentes dado. Necesitaremos efectuar cuatro comparaciones:

Con 2N y exigir que el número encontrado sea menor o igual
Con N y exigir que sea mayor
Con el anterior candidato para ver si es menor
Sus divisores han de compararse con los de N y presentar mayor número

No daremos excesivos detalles, pero la idea es la de comparar los exponentes de cada candidato con los de N y llamar exceso al número formado por aquellas potencias en las que el primero sobrepasa al segundo y defecto a aquellos en los que ocurre lo contrario. Es la única forma de comparar si tener que escribir los números en el sistema decimal.

Si el exceso es mayor que el doble del defecto, se desecha el candidato, porque sobrepasaría a 2N. Si el defecto es mayor que el exceso también, porque sería menor que N. Entre los que quedan analizaremos sus divisores calculados mediante. Además, deberán presentar más divisores que N

(c) Lo anterior presenta un problema, y es que dado un juego de exponentes para N, el siguiente puede tener el mismo número de ellos, uno más e incluso uno menos. Puedes verlo en estos ejemplos de la lista de NAC:

Los mismos primos:

20160 2* 2* 2* 2* 2* 2* 3* 3* 5* 7
25200 2* 2* 2* 2* 3* 3* 5* 5* 7

Un primo más

50400 2* 2* 2* 2* 2* 3* 3* 5* 5* 7
55440 2* 2* 2* 2* 3* 3* 5* 7* 11

Un primo menos

27720 2* 2* 2* 3* 3* 5* 7* 11
45360 2* 2* 2* 2* 3* 3* 3* 3* 5* 7

Así que el algoritmo que intentemos deberá ser triple, uno para cada caso. Como dijimos, no damos más detalles, que podrían ser largos y pesados.

Herramienta

Hemos preparado una herramienta que sacrifica la velocidad para que se vean bien los cambios de exponentes, el exceso y defecto y el resultado final

En la fila 6 escribimos los exponentes de un NAC conocido, en este caso 21621600, cuyo juego es 5, 3, 2, 1, 1 y 1 (en el resto, para que estén en blanco, usa la tecla Supr). En la 9 se irán formado todas las combinaciones posibles dentro de las cotas de Ramanujan (algo ampliadas) y en las 12 y 13 se calculan los excesos y defectos, para garantizar que se mueven entre 2N y N.

También se calcula el número de divisores del inicial y el candidato, así como sus valores, aunque estos no son representativos y pueden presentar desbordamiento.

Si usas el botón “Buscar el próximo NAC” verás que van cambiando los valores de las filas 9 a 19, pero que en esta última se puede ir estabilizando el mejor candidato, hasta que termina el proceso y se convierte en el definitivo. En nuestro ejemplo se obtiene el siguiente 32432400.

A la derecha tienes la posibilidad de obtener varios NAC consecutivos a partir del escrito en la fila 6. No abuses de números grandes, que lo que obtendrás será un gran bloqueo en los cálculos. Si te metes en ese terreno, intenta salir con la tecla ESC.

En este caso aparecen los valores, pero si avanzáramos más llegaría un momento en el que sólo podríamos leer los exponentes. Por eso usábamos la expresión “encontrar sin ver”

En la anterior entrada ya dimos la dirección para que descargues la herramienta. Sólo la hemos implementado en Excel, pues su complejidad nos ha llevado bastante tiempo.

http://hojamat.es/blog/nac.xlsm

Puedes intentar exprimirla y comparar con la lista publicada en http://wwwhomes.uni-bielefeld.de/achim/highly.txt. Y también puedes mejorar el algoritmo…con paciencia.

Números altamente compuestos (2)

2013-01-08T14:37:00.000+01:00

Generación ordenada de los NAC (ver entrada anterior)

Ya hemos visto una forma de generar los NAC a base de columnas en una hoja de cálculo, pero este procedimiento tiene el inconveniente de que para números grandes los intervalos de aparición son tan amplios que no se pueden presentar en una columna. Lo ideal sería poderlos tener en filas consecutivas, como vemos en la imagen:

Pero esto no es fácil, porque el orden natural de los números no coincide con el del número de divisores, por lo que deberemos avanzar uno a uno y quedarnos con el máximo.

Veamos qué necesitamos:

Una función POTE(a;p) que nos indique el exponente con el que figura un número p en la descomposición en factores primos de a. Si no figura, el valor de la función será cero.

Otra función ESPRENAC(n) que indique si un número puede ser altamente compuesto o no, dependiendo de si presenta el esquema exigido con exponentes decrecientes.

Deberemos usar la función POTE y con ella verificar que los exponentes son los adecuados.

Un truco muy útil es el siguiente:

Si el número no obedece el esquema previo, la función ESPRENAC devuelve un cero, pero si lo obedece, la salida será el número de divisores. De esta forma podremos comparar este número con los de los anteriores y descubrir cuándo se ha llegado a un NAC.

Función POTE

Dado un número natural a y un primo p (en el algoritmo no se necesita que sea primo), para calcular el exponente con el que figura p en la descomposición de a bastará ir dividiendo a entre p todas las veces posibles siempre que p siga siendo divisor de a. Algo así:

Pongo un contador a cero
MIENTRAS p sea divisor de a
Divido a entre p y vuelvo a probar
Aumento el contador por cada división exacta
FIN del MIENTRAS

El contador será el exponente

Su funcionamiento se entiende bien: al principio no sabemos si p es divisor de a, por lo que le asignamos exponente cero (el contador). Después intentamos una división exacta de a entre p. Cada vez que lo logremos aumenta el contador del exponente.

Código en Basic de hoja de cálculo

Public Function pote(a, b)
Dim p, c, d

p = 0: c = a
d = c / b (división con decimales)
While d = c \ b (división entera)
p = p + 1
c = c / b
d = c / b
Wend
pote = p
End Function

Dejamos a nuestros lectores la interpretación de este código.

Función ESPRENAC

Su objetivo es descubrir si un número tiene la estructura adecuada para ser NAC, es decir, que en su descomposición en factores primos sólo figuren los primeros con exponentes no crecientes.

Esta función recorre los primeros números primos 2, 3, 5, 7, … (representados en el código por la variable pr(i)) y va calculando la función POTE para cada uno de ellos. Analiza si ninguno es cero y si forman una sucesión no creciente. De paso, almacena (1+POTE) para al final calcular el número de divisores.

El esquena sería:

Inicio una variable SIGUE a uno
MIENTRAS el número N sea mayor que 1 y SIGUE>0
Recorro los primeros números primos
Para cada uno de ellos evalúo la función POTE, con lo N disminuirá
Si POTE es nula o mayor que la anterior, hago SIGUE=0
En caso contrario multiplico SIGUE por (1+POTE), con lo que preparo el cálculo del número de divisores
FIN del mientras

Por último, ESPRENAC toma el valor de SIGUE. Si es cero, es que el número no puede ser altamente compuesto y si no lo es, devolverá el número de divisores.

Su código puede ser:

Public Function esprenac(n)
Dim p(20)
Dim c, i
Dim sigue

c = n
i = 0
sigue = 1
While c > 1 And sigue > 0
If i < 20 Then
i = i + 1
p(i) = pote(c, pr(i))
If p(i) = 0 Then sigue = 0
c = c / pr(i) ^ p(i)
sigue = sigue * (p(i) + 1)
If i > 1 Then
If p(i) > p(i - 1) Then sigue = 0
End If
Else
sigue = 0
End If
Wend
esprenac = sigue
End Function

Búsqueda ordenada

Con estas dos funciones podemos generar fácilmente la lista de NAC. Es un algoritmo “ingenuo” porque recorre todos los números entre cada dos posibles NAC, con el consiguiente gasto de trabajo y tiempo, pero para números no muy grandes va bastante bien.

Consistiría en

Iniciamos la lista con el 1. Llamamos ANTERIOR al mismo y DANTERIOR a su número de divisores (también 1)
DESDE el valor 2 hasta el tope que marquemos
Analizamos cada número consecutivo para ver si puede ser NAC. Le calculamos su número de divisores y lo comparamos con DANTERIOR.
Si el resultado de la comparación es que es mayor, ya hemos encontrado el siguiente NAC. Lo almacenamos en ANTERIOR y su número de divisores en DANTERIOR
FIN del DESDE
De esta forma iremos comparando los divisores de los candidatos y cuando encontremos un NAC lo consideramos como ANTERIOR y vuelta a empezar.

El código de esta búsqueda contiene elementos propios cada hoja de cálculo concreta, por lo que es preferible que los descargues desde

http://hojamat.es/blog/nac.xlsm

¿Y qué ocurre si llegamos a números tan grandes que las hojas de cálculo no pueden ya representar sus cifras? Pues o bien nos pasamos a programas más potentes o intentamos buscar NAC sin verlos. Eso es lo que haremos en la siguiente entrada.

Números altamente compuestos (1)

2013-01-03T13:39:00.000+01:00

Estos números fueron estudiados por Ramanujan, que ya tenía ideas sobre ellos antes de su colaboración con Hardy. Su definición es muy sencilla:

Un número altamente compuesto es un entero positivo con más divisores que cualquier número entero positivo menor que él mismo.

Así, el 12 tiene 6 divisores, mientras que todos los números menores que él tienen (del 1 al 11) 1, 2, 2, 3, 2, 4, 2, 4, 3, 4 y 2 respectivamente, luego 12 es altamente compuesto (lo expresaremos como NAC)

Los primeros son:

1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, ...

(http://oeis.org/A002182)

La sucesión contiene infinitos términos, porque si N es NAC, el número 2N tiene los mismos factores que N y uno más, luego al menos existe un número con más divisores que N y recorriendo N+1, N+2, N+3,…N+N=2N bastará quedarse con el primer número que presente un máximo de divisores respecto a los anteriores (puede ser el mismo 2N).

Podemos expresarlo mediante la función divisor o sigma0, que cuenta los divisores de un número. En los NAC esta función presenta un valor superior al de cualquier otro número entero menor que él.
Pero si recordamos que la expresión de la función divisor es

siendo a_i los exponentes en su descomposición en factores primos

comprenderemos que lo que debemos estudiar son los máximos de esta expresión, que sólo dependen de la signatura prima de N (esto es, el conjunto de los exponentes en la factorización. Esto es importante: si sustituimos uno de los números primos de la factorización por otro, el valor de la función divisor no se altera. Esta idea tan simple nos lleva a la primera propiedad de los NAC:

Todo número altamente compuesto tiene como factores primos los primeros de la lista, de forma consecutiva: 2, 3, 5, 7, 11, …

Es sencillo demostrarlo. Imagina que en su desarrollo no figuraran todos los primeros números primos. Por ejemplo, que figurara el 11 y no el 7. Entonces, si sustituyéramos el 11 por un 7, el valor de N disminuiría, pero el de su función divisor, tal como vimos en el párrafo anterior, se mantendría igual, lo que contradice lo afirmado de que N presenta más divisores que cualquier otro número menor.

Esto recuerda a los primoriales. Puedes repasarlos, que los usaremos más adelante. Los tienes en http://hojaynumeros.blogspot.com.es/2012/02/el-primorial.html

No sólo han de figurar los primeros primos, sino que sus exponentes deberán ser no crecientes si ordenamos las potencias mediante bases crecientes: e1 ³ e2 ³ e3 ³ e4 ³ e5 ³…

También es fácil demostrarlo: si un par de exponentes se presentaran en orden inverso, intercambiando sus bases obtendríamos un número menor que N con sus mismos divisores, luego N no es NAC.

Por último, salvo en los casos de N=4=22 y N=36=22*32, el último de los exponentes debe ser 1. No he encontrado demostración de este hecho.

Obtención con hoja de cálculo

Debes disponer de la función divisor. Puedes definirla con esta versión muy simple

Public Function divisor(n)
Dim i, s

s = 1
For i = 1 To n / 2
If n / i = n \ i Then s = s + 1
Next i
divisor = s
End Function

Para implementarla en la hoja de cálculo puedes seguir las instrucciones contenidas en http://hojamat.es/guias/descubrir/htm/macros.htm

Comprueba que funciona bien y escribe en columna los primeros números naturales y junto a ellos el valor de divisor(n)

Una tercera columna la rellenaremos con los máximos consecutivos que se produzcan en la segunda. En la siguiente imagen te damos una idea del método para conseguirlo. Lee la fórmula en la línea de entrada.

Por último, en los saltos que se produzcan en ese máximo, allí estarán los NAC. Te dejamos en la imagen la fórmula usada

Con estas cuatro columnas te irán apareciendo los números altamente compuestos, para lo que basta que rellenes las fórmulas hacia abajo hasta donde quieras.

Más adelante volveremos a la generación ordenada de los NAC.

Relación con los primoriales

Si has visitado http://hojaynumeros.blogspot.com.es/2012/02/el-primorial.html sabrás ya que un número primorial el que equivale al producto de los primeros números primos sin saltar ninguno, es decir, son primoriales 1, 2, 6, 30, 210, 2310, 30030, 510510

Pues bien, es fácil demostrar que todo número altamente compuesto es un producto de primoriales.
La clave está en que los exponentes son no crecientes. De esa forma extraemos del NAC un primer primorial con todos los factores primos usados. Al cociente que nos resulte le hacemos lo mismo, dividirlo entre los primos que hayan quedado, y así sucesivamente. Al ser los exponentes no crecientes, siempre quedarán primos consecutivos que comenzarán en 2. Es mejor verlo con un ejemplo:

2520 es un NAC y se descompone como 2520=2⁵*3³*5*7= (2*3*5*7)*(2*3)*(2*3)*2*2 = P(5)*P(3)*P(3)*P(2)*P(2), si representamos por P(k) el k-ésimo primorial.

Se ve que se pueden repetir primoriales y que no tienen que estar todos lo posibles. El recíproco no es cierto: no todo producto de primoriales es un NAC. Por ejemplo, en el caso de P(2)*P(2)*P(2)*P(3)*P(4)=2*2*2*6*30=1440 no resulta un NAC.

Otra propiedad: A partir del 6, todos los elementos de la sucesión son múltiplo de 6 y abundantes.

En la siguiente entrada generaremos todos los NAC de forma ordenada en filas consecutivas de una hoja de cálculo.

¿Cómo veo el 2013?

2012-12-27T01:30:00.000+01:00

Comprobado ya que el mundo no se ha acabado el día 21 y que el calendario sigue cambiando cifras por ahora, saludamos a las siguientes que van a caer:

Veo al 2013…

Desde cifras panorámicas

2013=9*8-(2+1+0)+6+57*34
2013=(5+106)*(8+7+3)+9+4+2
2013=7*8*(0+2+4+6+19+5)-3
2013=4*(1+2)+(50+37)*(9+6+8)

Con ideas trascendentes

2013=(3+1)*(4+1+5)*9/2*(6+5)+(3+5+8+9+8) (p)
2013=2+7+1+8+(2+8+1+8+2+84)*(5+9+0+5) (e)
2013= =1*(6+1+8+0+3+39+8+8)*(7+4+9+8)-(9+4+8+4+8)+2+0 (j)

Y aspiraciones mesiánicas

2013==(7+7+7)*(7+77+7+7)-(7+7*7)+77/7

Pero amistades satánicas

2013==6+6+6+6+(66+6*6)*6*(6+66+6)/(6+6+6+6)

Lo dejan autoreferente

2013=((2+0)^(1+3+2+0)-1*3)*(20+13)
2013=20*(1+3+2+0+1+3)^(2+0)+13

A veces escala montes

2013=12*(2+3+3+4+4+5+5+6+6+7+7+8+8+99)+9

Para llegar a la cima

2013=(9+9+9+9+9)*(9+9+9+9+9)-(9+99)/9

Y hasta una humilde colina

2013=11+(11+11)*(1+1+11)*(1+1+1+1+1+1+1)

Se lo llevan los desmontes

2013=(9+9+8+8)+(77+6+6+5+5)*(4+4+3+3+2+2+1+1)-1

Acepta humilde el fracaso

2013=(3+3)*(3+333)-3

Y aunque un poco más lo intente

2013=11+(1+1+22)*33/(4+4)*(5+5+6+6)-(7+7+8)*8
2013=-1+(1+1+2+23)*(34+4+5+5+6+6+7+7)+(8+8)

Le deja el turno al siguiente

2013=(2+0+1+4)*(2+0)*(1+4+2+0+1+4)^2+(0+1)-4

Y se va marcando el paso

2013=(6+1+6+1+6+1+6+1+6)*(1+6+1+6+1+6+1+6+1+6+16+1+6+1)+6+1
2013=(61+6+1+6+1+6+1+6+1)*(6+16+1)-(6+1+6+1+6+1)-(6+1)-6
2013=(6+1+61)*(6+16+1+6+1)-(6+1+6+1+6+1+6+1+6)+1+6
2013=(6+1+6+1+6+1+6)^1*(61+6+1+6)+1+6+1+6+1
2013=(61+6+1)*(6+1+6+16+1)-(6+1+6)-1-6-6-1
2013=(6+1+6)*161-6-1-6-1-61-6+1
2013=(6+16+16+1-6/1)*61
…

Bueno, a veces lo cambia

2013=(16+16+1)*61/6/1*6

O se hace capicúa

2013=(16+16+1)*61

¡Feliz año nuevo!

Volvemos a visitar al mayor divisor impar

2012-12-19T16:08:00.000+01:00

Participamos con esta entrada en el Carnaval de Matemáticas 3.131592653 cuyo anfitrión es el blog Que no te aburran las M@tes.

En una entrada ya algo antigua

(http://hojaynumeros.blogspot.com.es/2009/03/la-hoja-de-calculo-ayuda-razonar.html)

resolvimos una cuestión muy elegante sobre el mayor divisor impar de un número (le llamaremos MDI).

Al revisar ahora esta cuestión nos hemos encontrado con que desde entonces se han desarrollado en este blog muchos estudios que nos podrían ayudar a estudiar con más profundidad esta función. Algunos de los temas que trataremos los hemos encontrado en http://oeis.org/A000265, pero sin desarrollar.

Definición y cálculo

Llamaremos mayor divisor impar (MDI) de un número natural N al mayor número impar (eventualmente igual a 1) que es divisor de N

Es evidente que si N es impar, MDI(N)=N y que si es potencia de 2, MDI(N)=1

Esto nos da una idea muy simple para calcularlo en un caso concreto: dividimos entre 2 todas las veces posibles y al final llegaremos al MDI:

144/2=72; 72/2=36; 36/2=18; 18/2=9, que será el MDI(144)

Visto de otra forma, hemos eliminado la mayor potencia de 2 posible. El exponente correspondiente, en este caso 4, recibe el nombre de valuación de N respecto a 2, V₂(N) (definición tomada de los números p-ádicos).

Podemos descomponer N como N=MDI(N)* V₂(N)

Esto nos lleva a códigos muy sintéticos para calcularlo:

En el Basic de las hojas:

Public Function mdi(n) 'mayor divisor impar
Dim s
s = n
While s/2=int(s/2): s = s / 2: Wend ‘ Divide entre 2 mientras se pueda.
mdi = s
End Function

No requiere explicación. Basta leerlo.

En PARI, como ya tiene implementada la función VALUATION, el código es aún más simple:

mdi(n)= {m=n / 2^valuation(n, 2);return(m)}

Existen otras formas elegantes de cálculo, pero más lentas:

Aquí hay un exceso: no es necesario llegar a 2^N. Es claro que el denominador es la valuación de N respecto a 2.Intenta razonarlo.

La sucesión de los mayores divisores impares la tienes en http://oeis.org/A000265:

1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9, 19, 5,21, 11, 23, 3, 25, 13, 27, 7, 29, 15, 31, 1, 33, 17, 35, 9, 37, 19, 39,…

Razona una propiedad muy sencilla y compruébala en la lista:

MDI(N)=MDI(2N)

Basándonos en esta propiedad podemos calcular MDI mediante recursividad, pues definiremos MDI(N) como el mismo N si es impar y MDI(N/2) si es par.

Es una solución muy elegante. Podemos usar la recursividad en las hojas de cálculo, ya explicada en http://hojaynumeros.blogspot.com.es/2012/03/funciones-recursivas-en-las-hojas-de.html:

Public Function mdirecu(n)
Dim d
If n = 2 * Int(n / 2) Then d = mdirecu(n / 2) Else d = n
mdirecu = d
End Function

Propiedades

(1) Es multiplicativa

En efecto, si m y n son coprimos, se cumple que MDI(m*n)=MDI(m)*MDI(n)

Casi podríamos dejarlo como ejercicio: Si m y n son coprimos tendrán diferentes factores primos. Es más, si m es par, n será impar. Hallarles el MDI equivale a eliminarle todas las potencias de 2 al que sea par, pero los demás factores no cambiarán y serán distintos en ambos números, luego al multiplicarlos se multiplicarán también sus MDI.

Como todas las multiplicativas (ver http://hojamat.es/publicaciones/multifun.pdf) para definir MDI basta hacerlo en el caso N=p^k, siendo p un factor primo de N. En este caso es trivial: si p=2, MDI(2^k)=1 y en caso contrario, MDI(p^k)= p^k

(2) El MDI representa la pauta de unos en su representación binaria

Ya nos referimos a esta propiedad en la anterior entrada: si N=MDI(N)* V₂(N), el paso de MDI(N) a N consistirá en añadir ceros a la derecha, luego la pauta de unos se conserva. Lo vemos con un ejemplo:

N=2664=101001101000(2 y MDI(2664)=333=101001101(2

Coinciden las pautas de unos

(3) Los conjuntos {MDI(N+1), MDI(N+2),…MDI(2N)} y {1,3, 5, 7…(n elementos)…} son idénticos.

También nos referimos a ella en su momento.

1.- Los elementos del primer conjunto son todos distintos, pues si dos fueran iguales, MDI(K)=MDI(J), uno de los números, por ejemplo K debería cumplir K=J*2^r y entonces, si J pertenece al rango N+1,…2N, K sería mayor que 2N y no pertenecería a ese rango.

2.- Todos los N primeros números impares deben pertenecer al segundo conjunto. Lo que es seguro es que pertenecen al intervalo 1..2N. Si pertenecen al intervalo N+1..2N ya está demostrado. Si no, M£N, y entonces existe un múltiplo suyo del tipo M*2^h que pertenece al rango N+1..2N. Supongamos que no, que existen dos exponentes consecutivos tales que M*2^h£ N < 2N < M*2^h+1 (h eventualmente igual a la unidad). Dividiendo resultaría M*2^h+1/ M*2^h > 2N/N, es decir 2>2, luego esta situación es imposible. Debe existir un exponente tal que M*2^r pertenezca a N+1..2N y por tanto su MDI estará en el segundo conjunto.

(3.1) Consecuencia: MDI(N+1)+MDI(N+2)+,…+MDI(2N) = N², por ser suma de los primeros impares.

(3.2) Otra consecuencia: Si llamamos U(n) a la suma de los MDI de los n primeros números naturales, se obtendrá que

U(2n) = n²+U(n)

(lo tienes en http://arxiv.org/pdf/1103.2295v1.pdf)

(4) La suma de los 2^N primeros términos de la sucesión de MDI equivale a (4^N+2)/3

Es consecuencia de la propiedad anterior. Lo vemos por inducción (recorre la sucesión presentada más arriba) 1+1=(4¹+2)/3=2; 1+1+3+1 = (4²+2)/3 = 6, 1+1+3+1+5+3+7+1 = (4³+2)/3=22,… luego podemos suponer cierta la igualdad para N. Sea

MDI(1)+MDI(2)+…+MDI(2^N) = (4^N+2)/3

Para 2^N+1, según la propiedad anterior, la suma sería: MDI(1)+MDI(2)+…+MDI(2^N+1) = (4^N+2)/3)+4^N = (4*4^N+2)/3 = (4^N+1+2)/3 y queda demostrado.

Y dejamos para el final la propiedad más elegante:

(5) Si sumamos los valores que toma la función j(N) (indicatriz de Euler) para todos los divisores impares de N, el resultado es el mayor divisor impar.

Es sabido que esa suma extendida a todos los divisores de N da como resultado N
(ver http://es.wikipedia.org/wiki/Funci%C3%B3n_%CF%86_de_Euler)

Por ejemplo, para el número 576, en la siguiente tabla tienes la comprobación de esta propiedad, los valores de la indicatriz también suman 576.

Como la función j es multiplicativa, la suma de la parte derecha se puede dividir en dos factores, uno para todos los divisores que son potencia de 2 y otro con los impares. Así, los 21 sumandos se pueden expresar así:
S = (j(1)+ j(3)+ j(9))*(j(1)+ j(2)+ j(4)+ j(8)+ j(16)+ j(32)+ j(64)) = 9*64 = 576

Vemos que la suma de la primera parte es 9, el MDI(576), como habíamos afirmado.

Esta descomposición se puede efectuar en cualquier número: por una parte incluimos las potencias de 2 y por la otra los coprimos con dos. La segunda suma dará la máxima potencia de 2 que divide a N y la primera tendrá como resultado MDI(N).

Extensión

Al igual que hemos definido el mayor divisor impar podíamos haberlo hecho con el mayor divisor no múltiplo de 5 (lo podemos representar como MD_5) que está estudiado en http://oeis.org/A132739, o no múltiplo de 10 (http://oeis.org/A132740) Puedes trasladar todo lo que se ha expuesto al caso en el que en lugar de 2 se use otro número.

También puedes pensar si siempre se cumplirá que MD_K(MD_L(N)) = MD_L(MD_K(N))

Propiedades del 2013 (y mucho más)

2012-12-12T19:51:00.000+01:00

Como viene siendo habitual desde 2010, nuestro colaborador y amigo Rafael Parra Machío saluda al nuevo año con otro de sus interesantes documentos. En esta ocasión, además de un recorrido exhaustivo por las propiedades del número 2013, nos documenta sobre

* Historia de la Cronología
* Los diversos calendarios
* La medida del tiempo
* Conversión entre calendarios

Lo podéis descargar desde

http://hojamat.es/parra/prop2013.pdf

Descubriréis muchos hechos y datos sobre la medida del tiempo a lo largo de la Historia.

Y si queréis repasar los años anteriores:

http://hojamat.es/parra/prop2012.pdf

http://hojamat.es/parra/prop2011.pdf

http://hojamat.es/parra/p2010.pdf

Mayor divisor propio con la misma suma de cifras

2012-12-12T04:00:00.000+01:00

A partir de una cuestión simple (que no sencilla) desarrollaremos varias técnicas y conceptos, ejercicio que nos agrada mucho en este blog.

¿Qué números poseen la misma suma de cifras que su mayor divisor propio?

Uno de ellos es el 12673 que se descompone como 12673=19*23*29, luego su mayor divisor propio es 23*29=667 y, en efecto la suma de las cifras de 12673 es 19 y la de 667 también es 19.

No hay que irse tan lejos: el mayor divisor de 18 es 9 y también se cumple esta propiedad. Puede que hayas pensado que la cumplen todos los múltiplos de 9 y no es así, porque 45 tiene como mayor divisor 15 y ahí no coinciden las sumas, y tampoco en 63. Sin embargo sí se cumple en 18, 27, 36, 54,…

Esto se complica, porque tienen la propiedad números no múltiplos de 9 y entre los que sí lo son, unos la cumplen y otros no. Reflexionemos:

Relación entre un número y su mayor divisor propio

Si B es el mayor divisor propio de A se tendrá que A/B será el menor divisor de A (mayor que 1 pues si no B no sería propio), pero por uno de los más elegantes teoremas sobre divisores, ese cociente A/B ha de ser primo. Por tanto

Si B es el mayor divisor propio de A se cumple A=Bp siendo p primo (igual o menor que B)

Condición de igualdad de sumas

Si dos números presentan la misma suma de cifras es que son congruentes módulo 9, como bien se sabe en Aritmética Modular (recuerda el criterio de divisibilidad por 9).

Por tanto tendremos, con la notación anterior, que AºB (mod 9, es decir BºBp (mod 9 y por tanto Bp-B=B(p-1) deberá ser múltiplo de 9. Ten cuidado, que esta condición es necesaria pero no suficiente.

Esto nos lleva a tres posibilidades: (a) B es múltiplo de 9 (b) B es múltiplo de 3 pero no de 9 (c) B no es múltiplo de 3

(a) Si B es múltiplo de 9, el número primo p sólo puede ser 2 o 3. Si fuera mayor no se cumpliría, porque entonces B no sería el mayor divisor, ya que el menor sería 3 y por tanto el mayor sería A/3. Esto divide a los múltiplos de 9 en dos clases:

(a1) Los números en los que un múltiplo de 9 está multiplicado por 2 o 3 (y por otros), sí pueden cumplir la igualdad de sumas. De hecho son estos:

18, 27, 36, 54, 72, 81, 90, 108, 126, 135, 144, 162, 180, 198, 216, 234, 243,…

No sé si echas de menos alguno. No estará el 288, a pesar de cumplir el contener el factor 2, pero es que sus cifras suman 18 y las de su mayor divisor 144 sólo 9.

Aquí tienes la trampa: dijimos que la condición era necesaria pero no suficiente. Por eso hemos usado la palabra “pueden ser”. Lo que sí ocurrirá es que las sumas sean congruentes módulo 9 (razónalo)

(a2) Aquellos que tienen la forma 9p con p producto de primos mayores que 3. Estos no tienen que cumplir la igualdad de sumas. Por ejemplo 873=9*97. Sus cifras suman 18. Su mayor divisor es 873/3=291 y sus cifras suman 12.

(b) Para que B(p-1) sea múltiplo de 9 también puede ocurrir que B sea múltiplo de 3 pero no de 9, luego el otro factor 3 debe pertenecer a p-1, de donde se deduce que p tiene la forma de 3k+1 con k>0, luego p será un primo mayor que 3 y entonces B no será el mayor divisor de A sino A/3. No se puede dar este caso.

(c) Si B no es múltiplo de 9, lo será p-1. Así que si A no es múltiplo de 9, tampoco lo será B y si se cumple la igualdad de suma de cifras, ha de ser divisible entre un número primo del tipo 9k+1 con k>0. Más exigente aún: como p-1 es par, p será del tipo 18k+1

Efectivamente, a continuación presentamos los números que cumplen la propiedad que estamos exigiendo y que no son múltiplos de 9. En todos ellos figura un factor primo del tipo 18k+1. En la factorización el primer número de cada corchete es el factor primo y el segundo su exponente.

361 [19,2]
551 [19,1][29,1]
703 [19,1][37,1]
1007 [19,1][53,1]
1273 [19,1][67,1]
1691 [19,1][89,1]
1843 [19,1][97,1]
2033 [19,1][107,1]
2071 [19,1][109,1]
2183 [37,1][59,1]
2413 [19,1][127,1]
2603 [19,1][137,1]
2641 [19,1][139,1]
2701 [37,1][73,1]
2831 [19,1][149,1]
2923 [37,1][79,1]
3071 [37,1][83,1]
3173 [19,1][167,1]
3293 [37,1][89,1]
3743 [19,1][197,1]
3781 [19,1][199,1]

No creas que todos son semiprimos. Hay otros que no lo son: 18791 está en la lista y se descompone como 19*23*43.

Recuerda también que la condición no es suficiente aquí tampoco.

Hemos publicado esta lista en OEIS con la referencia https://oeis.org/A219340

El código PARI que engendra esta secuencia lo tienes a continuación, aunque en este blog la primera búsqueda se efectúa con hoja de cálculo y después se comprueba con PARI, Wmaxima o Wiris cuando es posible.

digsum(n)={local (d,p); d=0; p=n; while(p,d+=p%10;p=floor(p/10)); return(d)}

largdiv(n)=if(n==1, 1, n/factor(n)[1, 1]) \\ Charles R Greathouse IV, Jun 15 2011

{ k=0; for (n=2, 10^5, if(digsum(n)==digsum(largdiv(n))&&n%9>0, k=k+1;write("B219340.txt",k,", ",n))); }

Sí, esta era una cuestión menor, pero nos ha divertido estudiarla. Se puede aprender mucho con este tipo de planteamientos.

Más pasos hacia la complejidad (2)

2012-12-05T04:00:00.000+01:00

Función DISTSEMI

Igual que hemos hecho para semiprimos inferiores en la anterior entrada lo podemos intentar para los superiores. Definiremos DISTSEMI(P) para P primo como la diferencia con el menor semiprimo superior a él

Esta función también está definida para todo número primo, incluidos el 2 y el 3, porque todo primo P es inferior al semiprimo 2P, luego el conjunto de semiprimos mayores que P no está vacío y poseerá un mínimo, que será el buscado.

Sus primeros valores son

2	3	5	7	11	13	17	19	23	29	31	37
2	1	1	2	3	1	4	2	2	4	2	1

Una lista más completa es 2, 1, 1, 2, 3, 1, 4, 2, 2, 4, 2, 1, 5, 3, 2, 2, 3, 1, 2, 3, 1, 3, 2, 2, 9, 5…

Esta sucesión no estaba publicada en OEIS, por lo que la hemos incorporado con el número A217612

http://oeis.org/A217612

Sí figuran en el catálogo los valores de los semiprimos en los que se convierte P al sumarle DISTSEMI(P) (ver http://oeis.org/A102414).

Sus valores también crecen muy lentamente. Su máximo para primos menores que 10000 es de 23, que se alcanza en P=8819. Estos son los primeros máximos:

2 2
11 3
17 4
41 5
97 9
599 12
1423 14
2683 18
6563 20
8819 23
32779 28
35983 36

También podemos conjeturar que DISTSEMI(P)/P tiende a cero al crecer P indefnidamente.

Otras cuestiones

Puede ocurrir que DISTSEMI(N)=DISTSEMI2(N), con lo que N sería la media aritmética de dos semiprimos (ver http://oeis.org/A103654)

También que DISTSEMI(N)=1 con lo que N y (N+1)/2 son ambos primos (ver http://oeis.org/A005383) (¿por qué?)

Para DISTSEMI(N)=2 resultan estos números

2, 7, 19, 23, 31, 47, 53, 67, 83, 89, 109, 113, 127, 131, 139, 167, 181, 199, 211, 233, 251, 257, 263, 293, 307, 317, 337, 353, 359, 379, 389, 401, 409, 443, 449, 467, 479, 487, 491, 499, 503, 509, 557, 563, 571, 577, …

Esta sucesión es una subsucesión de http://oeis.org/A063637

En ella están aquellos en los N y N+2 son semiprimos, pero N+1 no. Así, el 13 está en http://oeis.org/A063637 pero DISTSEMI(13)=1 y por eso no está en nuestra sucesión.

NOTA: Existen pares y tríos de semiprimos consecutivos, pero no conjuntos de 4, porque uno de ellos sería múltiplo de 4.

Podríamos seguir buscando más valores, pero hay que respetar el cansancio de los lectores.

Más pasos hacia la complejidad (1)

2012-11-29T04:00:00.000+01:00

En estas entradas de nuestro blog

http://hojaynumeros.blogspot.com.es/2011/11/pasito-pasito-hacia-la-complejidad.html
http://hojaynumeros.blogspot.com.es/2011/11/pasito-pasito-hacia-la-complejidad_25.html
http://hojaynumeros.blogspot.com.es/2011/11/pasito-pasito-hacia-la-complejidad_29.html

estudiamos los casos en los que partiendo de un número simple, como es un primo, al avanzar o retroceder unidad a unidad iban apareciendo números con cada vez más factores primos: semiprimos, 3-casiprimos, 4-casiprimos,…hasta que se rompía esa tendencia. Dábamos el ejemplo de 807905281, que es primo y cumple que

807905282 = 2*403952641
807905283 = 3*15733*17117
807905284 = 2*2*1871*107951
807905285 = 5*11*43*211*1619
807905286 = 2*3*3*3*37*404357
807905287 = 7*7*7*7*29*41*283

Si recordamos que la función BIGOMEGA cuenta los factores primos de un número teniendo en cuenta los repetidos, la situación anterior se podría representar así:

Revisando esta entrada para su inclusión en el resumen anual, nos hemos dado cuenta de que el tema de alcanzar complejidades mayores moviendo un número hacia adelante y hacia atrás daba para más estudios, por lo que os los presentamos en esta entrada.

¿POR QUÉ AVANZAR DE UNO EN UNO?

Se dan casos en los que N es primo y N+2 semiprimo:

2, 7, 13, 19, 23, 31, 37, 47, 53, 67, 83, 89,...

Están publicados en http://oeis.org/A063637

Toma un número de la sucesión. Por ejemplo, el 53. Le sumas 2 y se convierte en 55=5*11, que es el semiprimo más cercano (esto no lo exigimos y ya lo veremos más adelante), porque 54=2*3*3*3.

Estos números son de la forma p*q-2, con p y q primos.

También puede ser N primo y N-2 semiprimo

11, 17, 23, 37, 41, 53, 59, 67, 71, 79, 89, 97, 113,...

http://oeis.org/A063638

Estos números son de la forma p*q+2, con p y q primos.

Saltos de tres unidades

Existen números p primos con p+3 semiprimo

3, 7, 11, 19, 23, 31, 43, 59, 71, 79, 83, 103,…

http://oeis.org/A092109

Son del tipo p=4k+3 (¿por qué?) y cumplen que (p+3)/2 es primo (piensa que p+3 es par y semiprimo)

Existen números p primos con p-3 semiprimo

7, 13, 17, 29, 37, 41, 61, 89, 97, 109, 137,...

http://oeis.org/A089531

Sus propiedades son simétricas de las de los anteriores

Función DISTSEMI

En lugar de seguir buscando saltos mayores podemos definir dos funciones: DISTSEMI, que medirá la distancia mínima k tal que P sea primo y P+k sea semiprimo y DISTSEMI2, que hará lo mismo por la izquierda, ver el valor mínimo k para el que P sea primo y P-k semiprimo.

El código de la primera podría ser

Function distsemi(p)
Dim d, k
Dim noess

d = 0
If esprimo(p) Then
k = 0
noess = True
While noess
k = k + 1
If essemiprimo(p + k) Then d = k: noess = False
Wend
End If
distsemi = d
End Function

Se entiende fácilmente, e igual, con dos pequeñas variaciones podemos definir DISTSEMI2.

FUNCIÓN DISTSEMI2

Los valores de esta segunda función están publicados en http://oeis.org/A121885
No se puede definir para P=2 ni para P=3. Para los siguientes a partir del 5 tenemos los valores

5	7	11	13	17	19	23	29	31	37
1	1	1	3	2	4	1	3	5	2

Salvo para 2 y 3 esta función está definida para todo número natural, porque el conjunto de los semiprimos inferiores al mismo no está vacío, ya que al menos contiene al 4, y al ser un conjunto acotado de naturales tendrá un máximo Q (ver http://oeis.org/A102415) y la diferencia entre P y Q será el valor de DISTSEMI2 buscado.

Su gráfica para los primeros primos tiene este aspecto

Si vas leyendo los valores de X que se corresponden con valores concretos de Y te resultarán sucesiones similares a las que hemos presentado al principio. Así, los mínimos se corresponden con los primos P en los que P-1 es semiprimo, contenidos en https://oeis.org/A005385 y ya tratados en este blog.

En el nivel 2 están estos números primos

17, 37, 41, 53, 67, 71, 79, 89, 97, 113, 131, 157, 163, 211, 223, 239, 251, 269, 293, 307, 311, 331, 337, 367, 373, 379, 397, 409, 419, 439, 449, 487, 491, 499,…,

en los que p-2 es el semiprimo más cercano por la izquierda Los hemos publicado en https://oeis.org/A217195 con el siguiente código:

(PARI) forprime(p=3, 9999, bigomega(p-2)==2 && bigomega(p-1)!=2 & print1(p", "))

Y en el 3

13, 29, 61, 109, 137, 149, 181, 197, 229, 257, 277, 281, 317, 349, 389, 401, 457, 461, 541, 557, 569, 617, 677, 761, 797, 821, 929, 937, 977,…

(Los publicamos en https://oeis.org/A217197)

con el código

(PARI) forprime(p=5, 9999, bigomega(p-3)==2 && bigomega(p-1)!=2 && bigomega(p-2)!=2 & print1(p", "))

Entre los máximos destacan el 103 (ver gráfico), que necesita 8 pasos hacia atrás para encontrar el primer semiprimo. Entre los primos menores que 1000 el máximo se da en el 647, que está a 12 unidades de su máximo semiprimo inferior y entre los menores de 10000 se da en el 6381, con DISTSEMI2(6581)=22
Aquí tienes una lista de los números que presentan máximos respecto a sus anteriores:

13   3
19   4
31   5
101   6
103   8
607   10
647   12
1433   15
2699   18
6581   22
17989   24
32803   26
36011   30
36013   32
36017   36

No crecen mucho los valores máximos, porque al ir aumentando el valor de P van siendo posibles cada vez más combinaciones de dos primos que podrán estar bastante cerca de P. Esto es una observación nada más, sin fundamento riguroso.

Se impone una conjetura: ¿Tenderá a cero el cociente DISTSEMI2(P)/P con P primo al tender P a infinito? Lo dejamos ahí para quien tenga más preparación en estos temas.