miércoles, 27 de febrero de 2013

Carnaval de triangulares

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)


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

* Curiosidades



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*T4 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*T2 = 5*T3 = 3*T4 = 2*T5

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.

miércoles, 20 de febrero de 2013

De los triangulares alojados a los primos de Sophie Germain


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.

miércoles, 13 de febrero de 2013

Convertir esquemas de cálculo en tablas


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.



domingo, 27 de enero de 2013

Pandigitales, cromos y un poco de Benford (2)

Esta es la segunda parte de nuestra participación en el  Carnaval de MatemáticasEdició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 2N sería interesante saber cómo se comporta en 2N+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.


lunes, 21 de enero de 2013

Pandigitales, cromos y un poco de Benford (1)


Esta es la primera parte de nuestra participación en el  Carnaval de MatemáticasEdició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 2N y las de 2N+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.

domingo, 13 de enero de 2013

Números altamente compuestos (3)


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.

martes, 8 de enero de 2013

Números altamente compuestos (2)



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.