viernes, 27 de diciembre de 2013

Saludamos al 2014


Como en diciembres anteriores, saludamos al nuevo año con algunos cálculos. No tocamos sus propiedades como número porque ya aparecerán en otros blogs y en las redes sociales, así como en un documento de Rafael Parra

(http://hojamat.es/parra/PROPIEDADES2014.pdf).

Aquí nos limitaremos a generarlo de diversas formas:

Con una cifra

Unas más breves que otras, son posibles todas las generaciones con una sola cifra. Destacamos la del 5, que usaremos en la portada de http://hojamat.es/

2014=(1+1)^11-11×(1+1+1)-1
2014=2^(22/2)-2^(2+2+2/2)-2
2014=3!×333+3^3-33/3
2014=4^4×(4+4)-44+4!/4+4
2014=5^5-5555/5
2014=(6×6+(6+6)/6)×(66-6-6/6-6)
2014=(7×7+77/7-7)×(7×7-77/7)
2014=8!/(8+8)-8×8×8+8-8/8-8/8
2014=999+999+9+9-(9+9)/9

Como amigo de números trascendentes

Si usamos sus cifras, podremos engendrar el 2014, pero con cierta dificultad
Con p2014=(31+4+1)×59-(2+6)-5-3-5-89
Con e:  2014=(2+7+1)×8×(28+1)-(8+284+5+9)
Con j:  2014=16×180-(3+3+988-7-49-8×9)

A veces sube y otras baja

Cuesta abajo, ¡es la crisis!: 2014=98×76-5432-1-0!
Pero hay salida: 2014=0+1234+5×(67+89)
Con una montaña: 2014=1234+(5+6)×(7+89+8)-76-(5+4)×32×1
O con un valle: 2014=987+(6+5+4+3)×2×(1+0+1+2+3+4+5+6+7)-(8+9)

Con ritmillos de año joven

2014=53×(53-5×3)
2014=(3×8×3-(8+3+8))×38
2014=45×45-4×5+4+5
2014=3^7-(3×(7+3)×7-37)

Que se autogenera

2014=20×14×(2+0+1+4)+(20+14)×2-(0+14)
2014=(201+4)×2-0-1×4+201×4+201×4
2014=201×4-201×4/2×0!×1+4+201×4+201×4
Este en broma: 2014=2014×(-2-1-(42×0×1)+4)

Con todas las cifras

2014=(7+82+3+0+9)×4^1×5-6
2014=(56+0)×8×(4+1!)×9/(3+7)-2

Y por último, con potencias

2014=21^2+22^2+33^2
2014=2^11-2^5-2^1


Feliz año 2014


domingo, 22 de diciembre de 2013

Propiedades del 2014 (colaboración de Rafael Parra Machío)


Como en años anteriores, nuestro amigo Rafael Parra aprovecha la entrada del nuevo año 2014 para describir en un documento muchas de sus propiedades, así como recordar algunas otras de tipo general no vinculadas a ese número. También incluye algunas técnicas de cálculo mental.

Lo puedes descargar desde la dirección

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

Incluimos la reproducción parcial de una de sus páginas.



Le agradecemos esta aportación, que enriquece el blog y será de utilidad para nuestros lectores.

miércoles, 18 de diciembre de 2013

Resultados curiosos de la suma de divisores cuadrados

Engendramos cuadrados

La siguiente sucesión presenta varias propiedades respecto a la suma de los divisores cuadrados (ver entrada anterior) que merece la pena destacar

1764, 60516, 82369, 529984, 2056356, 2798929, 3534400, 18181696, 38900169, 96020401, 97121025, 335988900, 455907904, 457318225, 617820736, 1334513961, 1599200100, 2176689025, 3279852900, 4464244225, 8586616896…(publicada en https://oeis.org/A232554)

Todos ellos son cuadrados tales que la suma de sus divisores cuadrados, incluidos ellos mismos, también es un cuadrado. Sí, puedes volver a leerlo si no lo has captado. En la siguiente tabla puedes comprobar esta propiedad:



En la primera columna figuran los elementos de la sucesión. Hemos prescindido del 1, que también cumpliría la misma propiedad. En la siguiente su descomposición en factores primos, que ya analizaremos. Como en la entrada anterior sugeríamos sumar los divisores cuadrados mediante la función sigma_2 aplicada a la raíz interna, hemos calculado dicha suma en las siguientes columnas, comprobando mediante su raíz cuadrada que se trata de cuadrados perfectos. Finamente también se han calculado los factores de esas raíces.

Se pueden generar con este código en lenguaje PARI:

{for(n=1,10^5,m=n*n;k=sumdiv(m,d,d*issquare(d));if(issquare(k)&&k>>1,print(m)))}

Factorización

Podemos observar que ningún término de la sucesión es potencia de un solo primo.

Con dos factores primos distintos sólo se dan tres casos, que puedes buscar en la tabla, y los primos que intervienen son 7, 41 y 239, curiosamente pertenecientes a la sucesión de primos  p para los que p^2+1 no está libre de cuadrados (ver el documento de Rafael Parra http://hojamat.es/parra/NumerosLDC.pdf y la sucesión https://oeis.org/A224718). En el caso de los tres citados, 7^2+1=2*25^2, 41^2+1=2*29^2 y 239^2+1=2*13^4. Si ahora los multiplicamos dos a dos, obtendremos un factor 2*2=4 multiplicado por dos cuadrados, luego será cuadrado perfecto, como se pedía.

Otra curiosidad es que las sumas de cuadrados son todas pares y muchas de ellas múltiplos de 100. Sus raíces son pares hasta donde hemos buscado. Queda ahí abierta una cuestión para estudiarla con más ciencia que nosotros.

Sucesión derivada

Si multiplicamos los términos de esta sucesión por otro número libre de cuadrados resultará otra sucesión formada por números no cuadrados con suma de divisores cuadrados propios que resulta ser cuadrada:

3528, 5292, 8820, 10584, 12348, 17640, 19404, 22932, 24696, 26460, 29988, 33516, 37044, 38808, 40572, 45864, 51156, 52920, 54684, 58212, 59976, 61740, 65268, 67032, 68796, 72324, 74088, 75852, 81144, 82908, 89964, 93492, 97020……(publicada en https://oeis.org/A232555)

Podemos construir todos los múltiplos de ese tipo hasta una cota, por ejemplo un millón y después ordenarlos en sucesión. Así lo hemos hecho y casi todos los primeros son múltiplos de 1764.

En realidad esta sucesión es parte de otra más amplia en la que aparecen todos los casos, y no sólo estos múltiplos que hemos considerado. Son estos:

Números cuya suma de divisores cuadrados propios es otro cuadrado mayor que 1

900, 3528, 4900, 5292, 8820, 10404, 10584, 12348, 17640, 19404, 22932, 24696, 26460, 29988, 33516, 37044, 38808, 40572, 45864, 51156,  52920, 54684, 58212, 59976, 61740, 65268, 67032, 68796, 72324, 74088, 75852, 79524, 81144, 81796, 82908, 89964, 93492, 97020………(publicada en https://oeis.org/A232556)

En ellos la suma de divisores cuadrados propios es otro cuadrado. Por ejemplo, la suma en el caso de 5292 es  1764+441+196+49+36+9+4+1=2500=50^2, que también es un cuadrado.

Aunque los hemos buscado con funciones de hoja de cálculo, se puede intentar también con PARI. Prueba si quieres este código:

{for(n=1,10^5,k=sumdiv(n,d,d*issquare(d)*(d<n));if(issquare(k)&&k>>1,print(n)))}

Todos los encontrados son múltiplos de 4 y al menos poseen tres factores primos distintos. De ellos, algunos son también cuadrados:

900, 4900, 10404, 79524, 81796, 417316, 532900, 846400, 1542564, 2464900, 3232804, 3334276, 3496900, 12432676, 43850884, 50836900, 51811204, 71470116, 107453956, 236975236, 253892356, 432889636, 544102276, 864948100, 1192597156, 1450543396, 1554094084, 2024820004, 2165413156………(publicada en https://oeis.org/A232557)

No son cuadrados el resto: 3528, 5292, 8820, 10584, 12348,…que resultan ser los múltiplos de la primera sucesión que ya tratamos.

Resumimos:

Sucesiones de cuadrados

(1) Pueden formar un cuadrado sumándoles todos sus divisores cuadrados propios. Nos resultaría la primera sucesión: 1764, 60516, 82369, 529984,…(A232554)

(2) Forman un cuadrado sólo la suma de divisores propios, sin sumarles el número dado. Tendríamos la sucesión: 900, 4900, 10404, 79524, 81796,…(A232557)

Sucesiones de no cuadrados

(3) Números cuyos divisores cuadrados suman otro cuadrado. Son 3528, 5292, 8820, 10584,…(A232555) Son múltiplos de elementos de la sucesión (1)

Sin condicionamiento

(4) La unión de la sucesión (2) con la (3) (A232556)
   
Formamos palindrómicos

Con la suma de divisores cuadrados podemos formar números palindrómicos. Es una simple curiosidad, pero está inédita, que sepamos. Hay dos formas, con divisores cuadrados propios o con todos:

Con divisores propios

Estos son los números en los que la suma de divisores cuadrados propios es un número palindrómico de al menos dos cifras (para eliminar casos triviales):

144, 324, 1089, 1936, 5929, 13225, 30752, 46128, 58564, 76880, 92256, 107632, 125316, 138384, 149769, 153760, 154449, 169136, 199888, 215264, 230640, 261392, 292144, 322896, 338272, 342225, 353648, 378225, 399776, 405769, 445904, 461280, 476656, 507408, 522784, 538160, 568912, 584288, 599664
(Los hemos publicado en https://oeis.org/A232892)

Si expresamos el resultado en una tabla de dos columnas, vemos los resultados palindrómicos a la derecha:

Llama la atención la frecuencia con la que aparece el valor 20202, y prolongando la tabla veríamos muchos más. La razón de esto es que el primer caso, 30752=25*312,  tiene como divisores cuadrados  15376+3844+961+16+4+1=20202, que provienen de los factores 24*312 =15376 y entonces, si multiplicamos ese número por factores libres de cuadrados se volverá a dar el mismo caso. En efecto, según la tabla, los siguientes son: 46128=15376*3, 76880=15376*5, 92256=15376*6, 107632=15376*7,…

La pregunta es por qué no funciona este razonamiento en los primeros casos de la tabla. La respuesta es que esos números son cuadrados y si los multiplicamos por un libre de cuadrados, se convertirían ellos mismos en divisores cuadrados propios, y eso alteraría la suma.

Un código PARI para encontrarlos puede ser

reverse(n)=concat(Vecrev(Str(n)))
palind(n)=(Str(n)==reverse(n)&&n>10)
{for(n=1,10^5,k=sumdiv(n,d,d*issquare(d)*(d<n));if(palind(k),print(n)))}

Con todos los divisores cuadrados

Los primeros números con esta propiedad son

15376, 30752, 46128, 76880, 92256, 107632, 153760, 169136, 199888, 215264, 230640, 261392, 292144, 322896, 338272, 353648, 399776, 445904, 461280, 476656, 507408, 522784, 538160, 568912, 584288, 599664, 630416, 645792, 661168, 707296, 722672, 784176, 814928, 845680, 876432, 891808, 907184, 937936, 953312, 999440,…
(Los hemos publicado en https://oeis.org/A232893)

Todos producen la suma de cuadrados 20202, que ya vimos, y todos son múltiplos del primero 15376 con cociente libre de cuadrados. Esta situación llega hasta el número 2217121, que ya no es múltiplo de 15376 y la suma palindrómica que produce es 2217122, ya que sus únicos divisores cuadrados son él mismo y la unidad.

Código PARI:

reverse(n)=concat(Vecrev(Str(n)))
palind(n)=(Str(n)==reverse(n)&&n>10)
{for(n=1,10^5,k=sumdiv(n,d,d*issquare(d));if(palind(k),print(n)))}

Otras sumas

Podemos intentar lograr números de otros tipos, como triangulares u oblongos, pero los resultados son tan abundantes que pierden su interés. En el caso de los oblongos los primeros resultados son múltiplos de 144. Ahí tienes una exploración.

martes, 10 de diciembre de 2013

Divisores cuadrados


Consideremos el conjunto de divisores de un número natural N que son cuadrados perfectos. Sabemos que el mayor de ellos es la parte cuadrada del número

(ver http://hojaynumeros.blogspot.com.es/2011/05/parte-cuadrada-y-parte-libre.html),

a la que designaremos como PC(N). Si descomponemos N en factores primos


para encontrar la parte cuadrada basta elevar a cada factor primo al mayor número par contenido en cada uno de los exponentes, es decir
(2)

Así, por ejemplo, para encontrar la parte cuadrada de 26460=22*33*5*72 bastará truncar cada exponente a un número par, con lo que quedaría PC(26460)= 22*32*72=1764. A la raíz cuadrada de esa parte se le suele llamar Raíz Interna del número N (ver http://hojaynumeros.blogspot.com.es/2011/12/emparedado-de-cuadrados-2.html)

En este caso la raíz interna de 26460 sería 42=2*3*7.

Todo esto lo recordamos para poder estudiar mejor los divisores cuadrados de un número. Se pueden considerar las siguientes afirmaciones:

Los divisores cuadrados de N coinciden con los de su parte cuadrada.

Si k es divisor cuadrado de N, todos sus exponentes en (1) serán pares, pero ninguno sobrepasará al correspondiente en PC(N), luego será también divisor de esa parte cuadrada. Inversamente, todo divisor de PC(N) lo es también de N.

El número de divisores cuadrados de N coincide con el de los divisores de la raíz interna de N.

Esto es así porque si extraemos la raíz cuadrada a todos los divisores cuadrados de N, es claro que permanecerán los mismos factores primos, pero con sus exponentes reducidos a la mitad, que es la misma operación sufrida por la raíz interna.

En el ejemplo elegido, si esa raíz interna es 42, poseerá ocho divisores, por ser igual a 2*3*7 (aplicando la fórmula del número de divisores resultaría (1+1)(1+1)(1+1)=8). Efectivamente, si buscamos todos los divisores cuadrados de 26460 nos resultan estos ocho: 1764, 441, 196, 49, 36, 9, 4 y 1, que son los cuadrados de los divisores de 42: 42, 21, 14, 7, 6, 3, 2 y 1

Existe una correspondencia biyectiva entre los divisores cuadrados de N y los divisores de su raíz interna, de forma que cada uno de los primeros es el cuadrado de otro del segundo conjunto.

Por ejemplo, para N=1200, su parte cuadrada es 400, su raíz interna 20, y se da la correspondencia entre los divisores de 20 y los divisores cuadrados de 20.



Esto nos da, como hemos visto, un procedimiento para contar los divisores cuadrados de un número, pero también para sumarlos, si recordamos la fórmula de la función sigma_2, que suma los cuadrados de los divisores (ver http://hojaynumeros.blogspot.com.es/2011/03/la-familia-de-las-sigmas-2.html)


Aplicamos esa fórmula a la raíz interna. Esto es importante, porque esa raíz determina el número de divisores cuadrados. En nuestro ejemplo lo haríamos así:

SDC(26460)=(2^4-1)/(2^2-1)* (3^4-1)/(3^2-1)* (7^4-1)/(7^2-1)=5*10*50=2500

Comprueba: 1764+441+196+49+36+9+4+1=2500

Si deseas comprobar este resultado con otros números, con este codigo PARI puedes sumar todos los divisores cuadrados:

print(sumdiv(26460,d,d*issquare(d)))

Sustituyes el ejemplo 26460 por otro número cada vez que lo desees.

Con el Basic de las hojas de cálculo también lo puedes calcular mediante esta función:

public function sumdivcuad(n)
dim i,p,a,s

p=1
s=0
for i=1 to sqr(n)
a=i*i
if n/a=n\a then s=s+a
next i
sumadivcuad=s
end function

Comprueba de varias formas que el número 84000 posee sólo seis divisores cuadrados cuya suma es 546. Usa también la fórmula basada en sigma_2 ((2^6-1)/(2^2-1)*(5^4-1)/(5^2-1)=21*26=546)

Como otras variantes de la función sigma, esta suma de divisores cuadrados es una función multiplicativa, por lo que basta definirla para pr, siendo p un factor primo. Para ello, según (2) tomamos como exponente de su raíz interna (r – r MOD 2)/2, con lo que la suma de los divisores cuadrados será




Por ejemplo, la suma de divisores cuadrados de 2048=211 será igual a (2^12-1)/(2^2-1)=4095/3=1365. Comprobamos: 1024+256+64+16+4+1 = 1365.

En el caso particular de que r sea igual a 2 o a 3 la suma de divisores cuadrados será p2+1. Es muy fácil razonarlo.
Otro caso particular se da cuando la raíz interna está libre de cuadrados, tipo RI(N)=p*q*r*s…, la suma buscada será (1+p2)(1+q2)(1+r2)(1+s2)…Sería el caso, por ejemplo, del número 60500, cuya parte cuadrada es 12100 y la raíz interna 110=2*5*11, libre de cuadrados, por lo que la suma de divisores cuadrados de 60500 debería ser (1+22)(1+52)(1+112)=5*26*122=15860. En efecto, los divisores cuadrados de 60500 suman 12100+3025+484+121+100+25+4+1=15860

En la siguiente entrada encontraremos algunos resultados curiosos sobre esta suma.

martes, 3 de diciembre de 2013

Una curiosidad: permutaciones obtenidas por simulación


El estudio que emprendemos hoy se parece bastante al problema de completar una colección de cromos, que ya tratamos hace unos meses (http://hojaynumeros.blogspot.com.es/2012/05/este-cromo-lo-tengo-repe-1.html)

Pertenece al tipo de problemas de llenado aleatorio de un conjunto, como el de una línea o un cartón de bingo. Estos ejemplos se caracterizan porque la probabilidad de obtención de un nuevo elemento del conjunto depende del número de los ya obtenidos, en el sentido negativo, de ir disminuyendo la probabilidad conforme se llena el conjunto.

Hoy lo experimentaremos con permutaciones. Hace días, jugando con las cifras del número 19913 con el fin de obtener todos los números primos posibles, acudí a la herramienta Combimaq, de hojamat.es (http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#combimaq), que me proporcionó la solución exacta, elemental, de 30 permutaciones, 30=5!/(2!2!)=120/4



Me pregunté entonces por la posibilidad de obtener esos resultados mediante simulación. Elegí este procedimiento:

(1) Se fija un conjunto cualquiera de unos pocos elementos, por ejemplo el dado 1, 9, 9, 1, 3, con o sin repetición de elementos.

(2) Lo sometemos reiteradamente a transposiciones aleatorias de sus elementos. Como una permutación se puede  descomponer en dichas transposiciones, cada vez que efectuemos esta operación estaremos creando una permutación del conjunto primitivo. Como es de suponer, después de varios intentos las permutaciones comenzarán a repetirse.

(3) Cada permutación nueva la comparamos con las anteriores, y si es distinta a todas ellas, la incorporamos a la lista de las formadas y seguimos el proceso. Nada nos garantiza que esto agote el conjunto de todas las permutaciones posibles, al igual que una colección de cromos en la que no se intercambian ni se compran puede no llegar a completarse nunca.

(4) El proceso parará si le incluimos un tope, que podría ser el número total de permutaciones que conozcamos previamente. Por ejemplo, en el caso de 19913 serían 30 permutaciones. Si no se indica ningún tope, puede que el proceso llegue a completar el catálogo de permutaciones o bien, cosa improbable, que nunca lo haga, se inicie un ciclo sin fin y haya que interrumpir el proceso (en realidad, esto también puede ocurrir fijado un tope de resultados). Esta interrupción se logra con la pulsación de la tecla ESC (en Excel) o Ctrl+May+ Q en OpenOffice y LibreOffice.

Descripción de la herramienta

Hemos incluido este simulador en http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#simulpermu

Funcionamiento

La  hoja principal presenta esta estructura



Escribes los elementos del conjunto en la fila de color verde. En la imagen se  ha elegido aaabbb.

Fijas el número de elementos, porque en esa fila puede haber otros residuales más a la derecha.

Después concretas el tope, o número de permutaciones esperado. En el ejemplo hemos escrito un 0 para que sea el simulador el que llegue al número de permutaciones totales, en este caso 20.

En la parte izquierda verás aparecer los intentos y los resultados. Es normal que se necesiten muchos intentos, y en este caso sin tope, la tardanza nuestra en interrumpir el proceso añadirá más. Por eso, para recuentos o estadísticas es preferible fijar previamente el número esperado de permutaciones.

Junto a cada permutación figura el número de intentos que ha necesitado.

Podemos usar el simulador para reproducir un resultado que ya conocemos. Imaginemos que en un curso de Combinatoria al alumnado le cuesta entender el número de permutaciones que se pueden construir con las letras REDADA. Iniciamos la simulación y observamos que la creación de permutaciones se estabiliza en el número 180













Para entender mejor el proceso, ordenamos la tabla completa mediante las columnas D, E, F,… (no olvides desactivar la opción de “Mis datos tienen encabezados”). De esta forma se entenderá mejor cómo se crean las distintas permutaciones:



En un segundo paso se puede demostrar la fórmula 6!/(2!2!)=720/4=180

Por el contrario, si sabemos, por ejemplo, que el conjunto 17767 presenta 5!/3!=20 permutaciones, planteamos la generación aleatoria con tope 20, y posteriormente ordenamos la tabla:



Podemos observar que las permutaciones se han ordenado de forma creciente (como si fueran cifras de un número) y demuestran mediante formación ordenada que el número de permutaciones vale 20.

Estadísticas de la simulación

Lo anterior presenta un interés relativo, es un mero ejercicio de simulación. Le dotaremos de más potencia realizando algunas estadísticas mediante la inclusión de un generador de series, que repite el proceso cuantas veces deseemos y nos devuelve las estadísticas.

Recuerda que cada permutación viene acompañada de los intentos que se han necesitado para encontrarla. En la imagen figura el desarrollo para generar las permutaciones del conjunto 1234.



Se han necesitado 64 intentos, repartidos como se ve en la imagen, con bastantes oscilaciones aleatorias, aunque con tendencia a crecer. Si deseamos estudiarlos mejor deberemos acudir a series de simulaciones.

La primera permutación sólo ha necesitado un intento. Siempre es así si el conjunto básico no presenta repeticiones (¿por qué?). Aquí el segundo también ha salido a la primera, pero el tercero ya necesita a 2 intentos. Así van aumentando hasta llegar al último, que requirió 16 intentos. Estamos ante una sucesión creciente de incrementos también crecientes.

Para estudiarla mejor pasamos a la segunda hoja de cálculo, en la que disponemos del botón para crear series, y lanzamos una de 1000 repeticiones, para obtener unas medias que se puedan confrontar con una posible teoría o realizar el ajuste a una función. El resultado de esta serie ha sido el siguiente:



¿Se podrá confrontar esto con alguna teoría? En realidad sí, porque el caso de los intentos necesarios para obtener unos éxitos se estudia con la distribución binomial negativa o de Pascal (http://www.uv.es/ceaces/base/modelos%20de%20probabilidad/binegativa.htm).

En nuestro ejemplo sólo se pretende conseguir un éxito y no varios, por lo que la fórmula de los intentos medios es muy simple M=1/p, siendo p la probabilidad de obtener, en nuestro caso, una permutación nueva, y que será del tipo 3/24, 4/24, …

En la imagen se han añadido los resultados que se esperarían según la teoría. Parecen muy ajustados, pero en otros muchos experimentos que hemos realizado se advierte un sesgo, en el sentido de que el número de intentos medios es algo superior a lo esperado, lo que nos hace dudar de la absoluta aleatoriedad del proceso.

En esa misma segunda hoja aparecerán los valores máximos y mínimos del número de intentos. El mínimo, si no hay repeticiones, siempre será 1 y el máximo oscila tanto que no tiene interés una estadística sobre él.

Pues a ver si descubres algo más o amplías el modelo.

martes, 26 de noviembre de 2013

Primo, ¿qué tienes que ver con tu número de orden?

Esta entrada participa en la Edición 4.12310562 del Carnaval de Matemáticas cuyo blog anfitrión es ZTFNews.org.


En el mes de septiembre, en un diálogo a través de Twiter, Benjamin Vitale (http://benvitalenum3ers.wordpress.com/) me hizo notar que 3559 es el número primo de número de orden 499, y que ambos números tienen la misma suma de cifras, 22. Ya sabéis que en este blog respondemos, cuando es posible, a todas las ideas que nos llegan con una cuestión a resolver, y no es la primera vez que estas nos llegan de Ben Vitale. En este caso podría ser:

¿Qué detalles pueden tener en común un número primo y su número de orden en la lista de los mismos?

Coincidencia entre cifras

No sólo pueden coincidir en la suma de sus cifras. Será relativamente fácil que lo hagan en la última cifra. En efecto, los primos 17, 31, 83, 109, 157, 563, 587, 599, 661, 811, 823, 859, … Por ejemplo, el 17 es el primo número 7 y 31 el número 11. Puedes estudiarlos mejor en http://oeis.org/A085598

Es más difícil que ambos números coincidan en sus dos últimas cifras. Los primeros números que cumplen esto son (los presentamos por pares, número de orden y primo):

(243,1543), (519, 3719), (589, 4289), (703, 5303), (741, 5641), (823, 6323), (901, 7001), (959, 7559), (973, 7673), (1033, 8233), (1081, 8681), (1197, 9697), (1223, 9923), (1443, 12043), (1477, 12377), (1491, 12491),(1541, 12941), (1723, 14723) (1751, 14951)…

En todos ellos coinciden las dos últimas cifras del primo y de su número de orden. Para encontrarlos necesitamos dos funciones: CORTACIFRAS y PRIMONUM.

Cortar cifras

La primera no es difícil de programar en cualquier lenguaje. Su misión es seleccionar algunas cifras de la expresión decimal de un número. La versión más simple, sin control de errores, es esta
CORTACIFRAS(P,M,N)=(P MOD 10^N)\10^(M-1), en la que P es el número, M el inicio del corte y N el final, ambos incluidos (pueden ser iguales y entonces se corta una sola cifra). El significado de la fórmula es que calculas el módulo o residuo de P respecto a 10^N y el resultado lo divides de forma entera entre 10^(M-1)

Si del número 288762 deseas seleccionar las cifras que van de la segunda a la quinta deberás efectuar estos cálculos: 288763 MOD 10^5 = 88762 y ese número lo divides sin decimales entre 10^(2-1), es decir 8876.

En hoja de cálculo se expresaría así: =COCIENTE(RESIDUO(288762;10^5);10). Compruébalo.

En PARI es más sintético: (288762%10^5)\10

Encontrar el número primo dado su número de orden

Esta función PRIMONUM es más difícil de conseguir. En PARI está yá implementada: prime(k), pero no para números grandes. En el resto de la entrada usaremos esta notación prime(k) que resulta muy sintética. En hoja de cálculo no está disponible de entrada, aunque sí en algún complemento. Un código que resulta un poco lento podría ser este:

Public Function primonum(n)
Dim p, c, i

'encuentra el primo cuyo número de orden es n

c = 0: i = 2
While c < n
If esprimo(i) Then c = c + 1: p = i
i = i + 1
Wend
primonum = p
End Function

Para quienes siguen este blog no será muy difícil encontrar la función esprimo.

Con estas dos funciones y una estructura tipo FOR_NEXT puedes encontrar los primos deseados. Hemos usado también este programa en PARI:

cutdigit(a,p,q)=(a%10^q)\10^(p-1)
{for(n=5,5000,p=prime(n);if(cutdigit(p,1,2)==cutdigit(n,1,2),print(p)))}

En primer lugar hemos definido cutdigit para seleccionar cifras y después la hemos usado entre 1 y 2 para averiguar si coinciden las cifras en k y prime(k)

Hemos publicado la tabla para prime(k) en  https://oeis.org/A232102 y la de k ya estaba publicada en https://oeis.org/A067838

Modificando lo anterior podemos buscar la igualdad en las tres últimas cifras. Los resultados son estos:

(1491, 12491), (1723, 14723), (4119, 39119), (4437, 42437), (6347, 63347), (6931, 69931), (7817, 79817), (9551, 99551), (12083, 129083), (12637, 135637), (13647, 147647), (15103, 165103), (16637, 183637), (17181, 190181),…

Los números primos los hemos publicado en https://oeis.org/A232104 y sus números de orden los tienes en https://oeis.org/A067841. Intenta reproducirlos.

Con cuatro cifras tenemos que forzar la máquina, porque en Basic resulta lento y en PARI la función prime(k) sólo está definida hasta un tope, que en nuestro caso se supera después de obtener el primo número 24833. Hemos tenido que acudir a la función primenext (o nuestra primprox), pero no daremos detalles. El resultado es, para los números de orden:

9551, 15103, 18697, 23071, 24833, 48229, 53853, 58681, 83819, 91617, 93909, 107647, 115259, 120487, 126497, 156991, 160681, 162857, 177477, 181833, 189143, 194229, 208679, 213703, 221569,…

Y para los números primos:

99551, 165103, 208697, 263071, 284833, 588229, 663853, 728681, 1073819, 1181617,
1213909, 1407647, 1515259, 1590487, 1676497, 2116991, 2170681, 2202857, 2417477,
2481833, 2589143, 2664229, 2878679, 2953703, 3071569,…

Puedes compara uno a uno. Por ejemplo, el primo número 194229 es el 2664229.

Las hemos incorporado a https://oeis.org/A232189 y https://oeis.org/A232188 respectivamente.

No seguimos presentando sucesiones, por nuestro deseo de no cansar. Sólo destacaremos que los primos 1407647 y 1515259, de órdenes respectivos 107647 y 115259 son los primeros en presentar una coincidencia de cinco cifras, y prime(303027)=4303027, prime(440999)=6440999 son los primeros en coincidir en seis.

De los de coincidencia en siete cifras damos el primero: prime(5517973)=95517973, pero le siguen más. Hay que forzar el PARI y con las hojas de cálculo mejor lo olvidamos.

Coincidencia total

Existen primos cuyo número de orden constituye todo su final en cifras. Son los llamados primos automórficos, y están publicados en http://oeis.org/A046883. Por ejemplo, el primo número 9551 resulta ser 99551 y el 303027, 4303027, coincidencia en las últimas cifras.

Operaciones con cifras

Las coincidencias en la suma de cifras similares a las de 499 y 3559 están recogidas en http://oeis.org/A033548 y reciben el nombre de “primos de Honaker”. Puedes ver en la siguiente dirección un ejemplo notable de este tipo de primos:

http://primes.utm.edu/curios/page.php/37778931862957154241011.html

Hemos investigado las coincidencias en el producto de cifras, pero no presenta gran interés, ya que las cifras 0 aumentan las posibilidades de coincidencia. Te lo dejamos como propuesta. Los primeros son: 17, 181, 409, 443, 491, 601, 809, 1013, 1069,…

Concatenaciones

Están publicadas relaciones basadas en la concatenación de cifras:

Concatenar p y prime(p) y que resulte un primo:

http://oeis.org/A084667: La concatenaciones primeras son (separamos con un guión el número de orden y el primo) 2-3, 4-7, 6-13, 12-37, 17-59, 18-61, 23-83, 27-103, 30-113, 35-149, 36-151,…

Concatenación inversa

http://oeis.org/A084669: Si invertimos la concatenación también obtenemos ejemplos:

5-3, 23-9, 67-19, 73-21, 157-37, 307-63, 389-77, 419-81, 449-87, 587-107,…

Hemos investigado también las diferencias entre prime(k) y k, pero o están publicadas o carecen de interés. Ahí tienes un reto.




martes, 19 de noviembre de 2013

¿De dónde vengo? (3) – Sumamos y contamos factores primos


En la anterior entrada vimos todos los divisores de un número en la búsqueda de una función inversa tal como la definimos previamente. Vamos a fijarnos en los primos, en las funciones que cuentan y suman primos.

Función Omega

Esta función cuenta los factores primos distintos de un número natural. No se cuentan las repeticiones, sino el número de primos distintos. Así, w(6)= w(12)= w(18)= w(24)=2, porque todos comparten dos primos distintos, 2 y 3.

Para encontrar MF_OMEGA(N) de un número bastará encontrar el primorial
(http://hojaynumeros.blogspot.com.es/2012/02/el-primorial.html), que contiene tantos factores primos como indique N. Esto es así porque los primoriales tienen como expresión  2*3*5*…*k , y es fácil entender que son los números mínimos que tienen k factores primos distintos.

Como ya conocemos la solución, podemos plantear la estrategia 2 de búsqueda acotada y obtendremos las soluciones:2, 6, 30, 210, 2310…

Con bigomega

BigOmega cuenta los factores primos con repetición. Esto cambia totalmente el planteamiento, porque es fácil ver que MF_BIGOMEGA(N)=2^N

Se entiende que si con factores primos distintos el mínimo vendrá de productos tipo 2*3*5*7…, si se admite repetición, se convertirán en 2*2*2*2…como candidatos a MF_BIGOMEGA

Función SOPF

Esta función suma los factores primos de un número sin contar repeticiones. Por ejemplo, sopf(84)=3+2+7=12, porque aunque el factor 2 figura al cuadrado en la descomposición factorial, sólo se cuenta una vez.

Podemos definir MF_SOPF(N) como el mínimo número cuyo resultado en la función SOPF es N. En el ejemplo anterior no sería 84 el valor de MF_SOPF(12). Habría que profundizar más.

¿Cómo encontramos el valor de MF_SOPF(N)?

Si es un número relativamente pequeño bastará con descomponerlo en suma de números primos diferentes de todas las formas posibles y después elegir aquellos cuyo producto sea mínimo. Así, como todos estarán elevados a la unidad, nos garantizamos que el resultado es el MF_SOPF buscado.

Si el número N es primo, MF_SOPF(N)=N, porque N sería el mínimo valor de la suma de factores primos distintos que den N. Esto es trivial en el caso de 2, 3 y 5. Para primos mayores es así porque si descomponemos N primo en una suma de primos, el valor más pequeño posible, además de N, sería 2(N-2) (en el caso de que N y N-2 fueran primos gemelos y esto ocurre a partir de 7, luego N>=7, con lo que 2(N-2)=N+N-4>N. Lo mismo ocurriría con 3(N-3), 5(N-5), que cada vez producirían un resultado mayor. Esto es así porque la función x(N-x) presenta un máximo en x=N/2.

Si se descompone en más de dos sumandos, por un razonamiento similar vemos que el valor mínimo posible es N, luego

Si N es primo, MF_SOPF(N)=N

Si N es compuesto, lo descomponemos en sumandos primos diferentes, como se indicó en párrafos anteriores. En el caso de 12 lo podemos descomponer como 12=7+5=7+3+2. Los productos resultantes son 7*5=35 y 7*3*2=42, luego la solución es 35: MF_SOPF(12)=35

Según la conjetura de Golbach todo número par mayor o igual que 4 puede descomponerse en la suma de dos primos y según una variante débil, todo impar se puede descomponer en suma de tres primos. En ninguna de las dos se afirma que los sumandos sean distintos, por lo que no tenemos la absoluta certeza de que todos los números a partir de 7 posean un valor para la función. Existe una conjetura similar que afirma que todo número par mayor que 8 es suma de dos primos distintos. Podemos seguir con el tema con una cierta seguridad de que salvo 1, 4 y 6, todos los números naturales poseen un valor para MF_SOPF, salvo que se demuestre algún día que estas conjeturas son falsas.

Para números mayores tendríamos que automatizar el proceso: buscaríamos todas las descomposiciones de N en suma de primos distintos y evaluaríamos los productos para descubrir el mínimo.

Búsqueda acotada

Usaremos la Búsqueda acotada que explicamos en la primera entrada de esta serie. Es fácil encontrar una cota para un número con un valor de SOPF dado, sea, por ejemplo N. Todos los sumandos primos en los que pueda descomponerse N serán menores o iguales que N y como todos son mayores o iguales a 2, su número no sobrepasará N/2. Así que el número buscado tendrá como cota N^(N/2). Es muy amplia, y en la mayoría de los casos se encontrará la solución mucho antes, pero lo importante es que existe y nos permite acotar la búsqueda. Con esta idea podemos construir la función. Se supone que tenemos implementada la función SOPF, que no es difícil de programar.

Public Function sopf(n)
Dim f, a, s
Dim vale as boolean

If n=1 then sopf=0:exit function
If <4 then sopf=n:exit function
a = n
f = 2: s=0
While f * f <= a
vale=false
While a / f = Int(a / f)
Vale=true
a = a / f
Wend
If vale then s=s+f
If f = 2 Then f = 3 Else f = f + 2
Wend
sopf = s
End Function

Sobre esta función definimos MF_SOPF

Public Function mfsopf(n)
Dim vale As Boolean
Dim k, a, s, j

vale = True
k = 1
a = 0
While vale And k <= n ^ (n / 2)
If sopf(k) = n Then a = k: vale = False
k = k + 1
Wend
mfsop = a
End Function

Está diseñada para que en caso de que no se obtenga solución devuelva un 0. Esto sólo ocurre en 1, 4 y 6. Estudia la razón.

La cota es tan alta que, a partir de 255 aproximadamente, los registros de Excel se sobrepasan en muchos números. En estos casos se puede intentar la búsqueda con cotas más pequeñas, o bien usar un lenguaje más potente, como PARI

Código PARI

sopf(n)={local(f,s=0);f=factor(n);for(i=1,matsize(f)[1],s+=f[i,1]);return(s)}
mfsopf(n)={k=1;m=0;t=n^(n/2);while(m==0&&k<t,k=k+1;p=sopf(k);if(p==n,m=k));return(m)}
{for(i=7;200,print(mfsopf(i))

Con este código podemos reproducir las soluciones contenidas en http://oeis.org/A064502
Después de muchas búsquedas, parece que sí, que sólo 1, 4 y 6 carecen de función.

En esta tabla puedes ver los valores mayores que alcanza MF_SOPF para números menores que 1000:


Como se puede observar, muchos números requieren búsquedas que casi duplican su número de cifras, lo que obstaculiza el proceso.

Con SOPFR

La función logaritmo entero o sopfr es similar a la anterior, pero contando los primos con repetición. Casi todas las consideraciones estudiadas hasta ahora siguen siendo válidas salvo algún detalle:

Ahora el 4 y el 6 poseen valores para la función buscada: MF_SOPFR(4)=4=2*2 y MF_SOPFR(6)=8=2*2*2. El 1 sigue sin presentar solución.

La función sopfr se obtiene con un código similar, pero los divisores primos se suman cada vez que aparecen (línea con el añadido de ‘**)

Public Function sopfr(n)
Dim f, a, s


If n=1 then sopfr=0:exit function
If <4 then sopfr=n:exit function
a = n
f = 2: s=0
While f * f <= a
While a / f = Int(a / f)
a = a / f
s=s+f ‘**
Wend
If f = 2 Then f = 3 Else f = f + 2
Wend
sopfr = s
End Function

La función MF_SOPFR también se obtiene con un código similar al de MF_SOPF sustituyendo las referencias a sopf por sopfr

Con estos cambios puedes obtener fácilmente los valores de MF_SOPFR, que están contenidos en http://oeis.org/A056240


miércoles, 13 de noviembre de 2013

¿De dónde vengo? (2) – Sumamos divisores

Proseguimos nuestra búsqueda de esa especie de función inversa que hemos rotulado con MF en la anterior entrada. Ahora estudiaremos la suma de divisores.

Recuerda que la función SIGMA suma todos los divisores de un número. Generalizaciones de la misma son las funciones SIGMA_K, que suman los divisores elevados al exponente K (Ver http://hojaynumeros.blogspot.com.es/2011/02/la-familia-de-las-sigmas-1.html y la entrada siguiente). Cualquier valor elegido al azar no tiene por qué ser el resultado de este tipo de sumas. De hecho, se sabe ya qué valores puede tomar SIGMA(N) y cuáles no.

No tienen solución los incluidos en http://oeis.org/A007369: 2, 5, 9, 10, 11, 16, 17, 19, 21, 22, 23… La función SIGMA no puede tener nunca estos valores. No existe ningún número cuya suma de divisores sea 17, 19 o 21.

Sí la tienen estos otros (http://oeis.org/A002191): 1, 3, 4, 6, 7, 8, 12, 13, 14, 15, 18, 20…Por ejemplo, el valor 13 se corresponde con la suma de divisores de 9: 9+3+1=13.

Para reproducir esta situación podemos acudir a la siguiente consideración: Para un N dado, SIGMA(N)³1+N, porque ese sería el valor más desfavorable, que se da cuando N es primo. En cualquier otra situación, aparecerán otros divisores, superando así el valor 1+N. así que, N£SIGMA(N)-1. Por tanto, si nos dan un valor fijo K=SIGMA(N),  bastará buscar N en el rango 1…K-1. Esto nos lleva a que el mejor método entre los que propusimos en  la anterior entrada sea el de búsqueda acotada.

Así lo hemos intentado con hoja de cálculo, llegando a la misma conclusión que las dos sucesiones citadas de OEIS:

Tienen un valor determinado para MF_SIGMA(N) los números
1, 3, 4, 6, 7, 8, 12, 13, 14, 15, 18, 20…http://oeis.org/A002191

Puedes comprobarlo en esta tabla obtenida con hoja de cálculo:



Observa que cuando la diferencia entre N y MF_SIGMA(N) es 1, el número de la segunda columna es primo.

En la tabla se intuye que los dobles de los perfectos, como el 12, coinciden con la suma de divisores de su mitad, el 6.

Hemos usado la función SIGMA definida por nosotros. Si no tienes acceso a ella puedes usar el siguiente código para obtener los mismos resultados. Como advertimos a menudo, estos códigos se trasladan fácilmente a otros lenguajes de programación. Este que ofrecemos devuelve un cero si MF_SIGMA no está definida para ese número. No es muy eficiente, pero sí fácil de entender:

Public Function mfsigma(n)
Dim vale As Boolean
Dim k, a, s, j

vale = True
k = 1
a = 0
While vale And k <= n
s = 0
For j = 1 To k
If k / j = k \ j Then s = s + j ‘Este FOR-NEXT calcula la función sigma de k
Next j
If s = n Then a = k: vale = False ' comprueba si SIGMA coincide con el argumento n
k = k + 1
Wend
mfsigma = a
End Function

Con esta función puedes determinar si un número coincide con la función SIGMA de otro. Por ejemplo MF_SIGMA(2014)=0, luego no existe ningún otro número cuya suma de divisores sea 2014. Si embargo, MF_SIGMA(2012)=2011, porque este último es primo, y MF_SIGMA(2016)=660, porque

2016= 660+330+220+165+132+110+66+60+55+44+33+30+22+20+15+12+11+10+6+5+4+3+2+ 1

Puedes usar también la función definida en PARI

mfsigma1(n)={k=0;while(k<=n&&sumdiv(k, d, d)<>n, k=k+1);if(k>=n,k=0); return(k)}
{print(mfsigma1(20))}

Con él, cambiando el valor de 20 por otro cualquiera, puedes encontrar su MF_SIGMA

Las otras sigmas

Si sumamos los cuadrados de los divisores de un número nos resulta la función SIGMA_2, con los cubos SIGMA_3 y, en general, podemos definir toda la familia para exponentes mayores.

¿Qué números coinciden con la suma de los cuadrados de los divisores de otros?

Repetimos todo el trabajo. Basta sustituir la línea de código

If k / j = k \ j Then s = s + j

Por esta otra

If k / j = k \ j Then s = s + j^2

Obtenemos así la lista de números cuya MF_SIGMA_2 está definida:

1, 5, 10, 21, 26, 50, 85, 91, 122, 130, 170, 210, 250, 260, 290, 341, 362, 455, 500, 530, 546, 610, 651, 820, 842, 850, 962, 1050, 1220, 1300, 1365, 1370, 1450, 1682, 1700, 1810, 1850, 1911, 2210, 2366, 2451, 2500, 2562…

Entre ellos están los de la forma 1+p^2 con p primo.

Figuran en http://oeis.org/A001157, pero con algunos repetidos respecto a nuestra sucesión.

En PARI

mfsigma2(n)={k=0;while(k<=n&&sumdiv(k, d, d*d)<>n, k=k+1);if(k>=n,k=0); return(k)}

Como complemento de ella, podemos encontrar los números cuyo valor de sigma_2 coincide con los valores de la anterior sucesión.

1, 2, 3, 4, 5, 6, 8, 9, 11, 10, 13, 12, 14, 15, 17, 16, 19, 18, 21, 23, 20, 22, 25, 27, 29, 24, 31, 28, 33, 30, 32, 37, 34, 41, 39, 38, 43, 36, 40, 45, 49, 42, 44, 46, 53, 51, 55, 50, 48, 59, 52, 57, 61, 54, 58, 56, 65, 67, 63, 62, 71, 69, 73, 60, 64, 68, 66, 79, 70, 75, 74, 83, 81, 85, 76, 72, 89, 82, 87, 78, 80, 86, 97, 95, 93…

Están casi todos los números. Los que faltan no son los mínimos con cada valor de la función. Por ejemplo, el 7 no está porque sigma_2(7)=50 y sigma_2(6)=50, luego ha de figurar el 6 y no el 7.

Para SIGMA_3

Estos son los valores que puede tomar sigma_3. Como se ve, con frecuencia muy baja.

1, 9, 28, 73, 126, 252, 344, 585, 757, 1134, 1332, 2044, 2198, 3096, 3528, 4681, 4914, 6813, 6860,…
http://oeis.org/A001158

En PARI

Mfsigma3(n)={k=0;while(k<=n&&sumdiv(k, d, d^3)<>n, k=k+1);if(k>=n,k=0); return(k)}

Puedes encontrar casos similares en  http://oeis.org/A063972 para divisores unitarios y en  http://oeis.org/A070015 para las partes alícuotas.

jueves, 7 de noviembre de 2013

¿De dónde vengo? (1) Generalidades


Nota previa: la serie de entradas que iniciamos hoy no tiene pretensiones de tipo teórico ni de descubrimiento de hechos nuevos. Gran parte de lo que trataremos está ya estudiado, pero con los procesos que desarrollaremos quienes nos lean podrán repasar conceptos y ejercitarse en buscar soluciones y justificarlas.

Trataremos en esta entrada y en las siguientes un problema similar al de la función inversa:

Dado un número natural N cualquiera intentaremos encontrar otro número M natural tal que al aplicarle una cierta función aritmética, nos resulte el primero, es decir F(M)=N. 

Como en teoría de números suelen existir varias soluciones, elegiremos siempre la menor de ellas. La representaremos con el prefijo MF seguido del nombre de la función. Lo vemos con algún ejemplo:

Si tomamos el número 31, ¿qué otro número tendrá ese resultado al sumar sus divisores (función sigma)? Si calculamos un poco, veremos que el más pequeño que cumple esto es el 16, ya que 16+8+4+2+1=31. Lo expresaremos como 16=MF_SIGMA(31)

¿Cuál es el primer número que tiene exactamente 8 divisores (función tau)? Se trata del 24, que posee como divisores  24, 12, 8, 6, 4, 3, 2 y 1, luego MF_TAU(8)=24

No es fácil esta búsqueda, porque no siempre tenemos una acotación para encontrar aquellos números cuyo resultado en una función es el número dado. Por eso, tendremos que encontrar distintas estrategias. Avanzamos tres de ellas:

Reflexión teórica

Esta es la más valiosa, pero no siempre posible. Intentaremos en ella llegar al resultado por razonamiento. En el caso del ejemplo anterior MF_TAU(8)=24 era fácil. La función TAU viene dada por la fórmula

En ella a1, a2, … son los exponentes de los números primos en la descomposición factorial de N. Es claro que para que se tengan 8 divisores D(N) ha de tener como factores 2*2*2, 4*2 o 8, o lo que es igual, signatura prima (conjunto de los exponentes de los primos) igual a (1,1,1), (3,1) o (7). Para encontrar el mínimo N imagina qué primos se pueden corresponder con esos exponentes. Lo vemos:

2*2*2: la combinación de primos mínima en este caso sería 21*31*51 =30

2*4: Exponentes 1 y 3. El número mínimo sería 23*3= 24

8: El único exponente sería 7, y el mínimo posible N=27 = 128

De las tres posibilidades el resultado más pequeño es 24, luego es la solución.

Se comprende que no siempre será posible este tipo de razonamiento

Búsqueda acotada

Es muy difícil acotar la búsqueda del número mínimo que estamos intentando encontrar. Una estrategia sería la de fijar una cota, por ejemplo 1000, para números pequeños y tratar luego aparte las excepciones. Algo parecido hicimos en la entrada de este blog

http://hojaynumeros.blogspot.com.es/2011/01/alguien-sabe-algo-de-esto-1.html

En ella resolvíamos el problema propuesto, pero fracasando en números como 223 al intentar usar una hoja de cálculo.

Probemos con la indicatriz de Euler. Recuerda que esta función cuenta los números menores que N y coprimos con él, incluyendo el 1. Escribimos la lista de posibles resultados, 1, 2, 3, 4, … y buscamos hasta 10^4 qué números poseen como función de Euler ese valor. Podríamos usar un código parecido a este:

For i = j To l
k = i
vale = True
While vale And k < 10 ^ 4
If euler(k) = i Then vale = False: a = k
k = k + 1
Wend
If Not vale Then
Msgbox(i)
Msgbox(a)
Next  i


Si existe algún fallo se aumenta el tope o se estudia teóricamente.

Por ejemplo, en esta tabla figuran los resultados para la función de Euler en los primeros números. Cuando la imagen es 0 significa que se ha llegado a 10^4 sin encontrar resultados. Como son muchos, habría que aumentar el tope de 10^4 o bien cambiar de técnica.



Rellenado de resultados

Podemos plantear la búsqueda con el punto de vista contrario. Recorremos los números naturales y para cada uno de ellos evaluamos la función deseada. Preparamos unas memorias (pueden ser celdas de hojas de cálculo) y las vamos rellenando ordenadamente con los resultados. Las memorias que queden vacías necesitarán un estudio aparte.

Se puede intentar este método con la función TAU, o DIVISOR o SIGMA0, que estudiamos en anteriores párrafos. Este caso ya está publicado en OEIS http://oeis.org/A005179

1, 2, 4, 6, 16, 12, 64, 24, 36, 48, 1024, 60, 4096, 192, 144, 120, 65536, 180, 262144, 240, 576, 3072, 4194304, 360, 1296, 12288, 900, 960, 268435456...

Se ve que este método resultaría lento y necesitaría topes muy grandes, por la existencia del valor 268435456 que supera cualquier planteamiento.

En la imagen puedes ver un barrido efectuado entre 1 y 100



En ella falta el 1, porque todo número tiene al menos dos divisores, y el 11, que según http://oeis.org/A005179 su imagen sería 4096, fuera del rango de búsqueda.

Cuando ocurra que queden ceros en las memorias, se deberá ampliar la búsqueda, cambiar de método o demostrar la imposibilidad.

En las dos siguientes entradas estudiaremos algunos ejemplos concretos que presentan cierto interés. Puede que usemos los tres métodos de búsqueda, según la naturaleza de la función que tratemos.


miércoles, 30 de octubre de 2013

Piezas para cuadrados


En la entrada anterior formamos curiosos números triangulares concatenando un número con otros relacionados con él, como n//n, n+1//n, 2n//n y otros. Vamos hoy a intentarlo con cuadrados. Este tema está más estudiado, y ya hay más casos publicados en OEIS. Los recorremos:

n//n

Es difícil que un número concatenado consigo mismo produzca un cuadrado. Los pocos casos que aparecen ya están publicados:

1322314049613223140496, 2066115702520661157025, 2975206611629752066116, 4049586776940495867769, 5289256198452892561984,… http://oeis.org/A092118

La razón de que se descubran tan pocos es la siguiente: el número concatenado n//n es en realidad n*(10^c+1), siendo c el número de cifras de n, por lo que n<10^c. Por ejemplo, 7878=78*(10^2+1)=78*101. Si deseamos que n//n sea un cuadrado, 10^c+1 ha de contener algún cuadrado como factor, porque si es libre de cuadrados, es imposible que n aporte los factores que quedan para completar un cuadrado, puesto que es menor que 10^c.

Habrá que buscar números del tipo 10^k+1 que no sean libres de cuadrados.

Si factorizamos, por ejemplo, desde 11 hasta 10^50+1, descubrimos que sólo en cuatro casos  contiene un cuadrado (copiamos la tabla parcialmente)

100000000001=11^2*23*4093*8779
1000000000000000000001=7^2*11*13*127*2689*459691*909091
1000000000000000000000000000000001=7*11^2*13*23*4093*8779*599144041* 183411838171
1000000000000000000000000000000000000001=7*11*13^2*157*859*6397*216451*1058313049* 388847808493.

Para completar un cuadrado como el que se pide, n deberá contener los factores primos que no figuran al cuadrado (la parte libre) y además, si acaso, otros factores adicionales elevados al cuadrado. Ya vimos en su día que si multiplicamos N por la parte libre de N conseguiremos el mínimo múltiplo cuadrado de N

(http://hojaynumeros.blogspot.com.es/2011/12/emparedado-de-cuadrados-2.html).

Cumplido esto, deberá tener el número de cifras adecuado. Por ejemplo, en el primer caso
N=23*4093*8779*k^2 y si queremos que tenga 11 cifras, el valor mínimo de k es 4, con lo que nos da la primera solución: n=23*4093*8779*16=13223140496, que engendra el cuadrado

1322314049613223140496, primer término de http://oeis.org/A092118

Si tomamos k=5 obtenemos el segundo término: n=20661157025, que engendra el segundo cuadrado 2066115702520661157025

Para k=6 se engendra el tercer cuadrado: 2975206611629752066116 y para k=7, 8 o 9 se engendran los términos cuarto a sexto. A partir de este valor se sobrepasan las cifras.

Así que el caso 100000000001 engendra seis términos.

Pasamos al siguiente:

1000000000000000000001=7^2*11*13*127*2689*459691*909091

El valor adecuado de n será del tipo n=11*13*127*2689*459691*909091*k^2

Para k=1 y k=2 no se llega al número de cifras mínimo. Para k=3 nos resulta el séptimo término: 183673469387755102041183673469387755102041. No están publicados más términos. Para k=4, 5 y 6 nos resultan términos inéditos:

326530612244897959184326530612244897959184
510204081632653061225510204081632653061225
734693877551020408164734693877551020408164

No deseamos marear a nuestros lectores, por lo que no abordamos los siguientes casos. Sólo dejamos una muestra:

132231404958677685950413223140496132231404958677685950413223140496

2n//n

Se puede seguir el mismo razonamiento y descomponer en factores los números del tipo 2*10^c+1 que contienen cuadrados

20000000000000000001=3*7^2*83*1663*985694468327
2000000000000000000000000000000001=3*43^2*245169227*1470638299531951365929

Con el primero

32653061224489795921632653061224489796
73469387755102040823673469387755102041
130612244897959183686530612244897959184

Con el segundo

216333153055705786911844240129800108166576527852893455922120064900
261763115197404002163331530557058130881557598702001081665765278529
311519740400216333153055705786912155759870200108166576527852893456
365603028664142779881016765819362182801514332071389940508382909681
424012979989183342347214710654408212006489994591671173607355327204
486749594375338020551649540292050243374797187669010275824770146025
553812871822606814494321254732288276906435911303407247160627366144
625202812330989724175229853975122312601406165494862087614926987561
700919415900486749594375338020552350459707950243374797187669010276
780962682531097890751757706868578390481341265548945375878853434289
865332612222823147647376960519200432666306111411573823688480259600

Los primeros están publicados en http://oeis.org/A115529

n//2n

No explicamos ya el procedimiento. Los candidatos son:

12=2^2*3
100000000000000000000002=2*3*7^2*19961*17040030781111603
10000000000000000000000000000000000000000000000000000000002=2*3*89^2* 353891*184629530872289*3220312754723112768886882952137673

Con el primero obtenemos el 36=6^2

Con el segundo:

816326530612244897959216326530612244897959184
1836734693877551020408236734693877551020408164
3265306122448979591836865306122448979591836736

Y con el tercero, verdaderos gigantes:

5049867440979674283550056811008711021335689938139123848001009973488195934856710011362201742204267137987627824769600

Publicados en http://oeis.org/A115527

Concatenación con diferencias constantes

Casi todos los casos están estudiados. Aquí ya no disponemos del análisis de los factores de 2*10^c+1 o similares. Sólo podemos acudir a la búsqueda, porque al añadir un sumando al número todo el planteamiento anterior falla.

n//n+1

Los primeros ejemplos los buscaremos con hoja de cálculo (no mostraremos el código) y con PARI.



Hemos añadido la raíz cuadrada de la concatenación. Esta sucesión está publicada en
 http://oeis.org/A030465  y llama a los primeros números de Sastry.

El código PARI adecuado es

concatint(a,b)=eval(concat(Str(a),Str(b)))
{for(n=1,10^7,a=concatint(n,n+1);if(issquare(a),print(a)))}

 N+1//n

Los primeros ejemplos son



También publicado en  http://oeis.org/A054214

Adapta tú el código PARI para encontrar más.

n//n+2

El número par 7874 es el más pequeño que cumple que concatenado con el siguiente par 7876 produce un cuadrado: 78747876=8874^2. Este caso ya está publicado en http://oeis.org/A115426.

n+2//n

Es el problema simétrico del anterior y también está estudiado en http://oeis.org/A115431
Aquí paramos, porque otras concatenaciones resultan menos atractivas. No obstante, con lo que ya has leído puedes emprender búsquedas por tu cuenta.



miércoles, 23 de octubre de 2013

Triangulares con piezas concatenadas


Esta entrada participa en la edición 4.1231056 del Carnaval de Matemáticas, cuyo anfitrión es el blog Scientia.

Quien ha entrado en el mundo de la programación elemental sabe qué es la operación de concatenar cadenas (“strings”): situar sus caracteres uno detrás del otro. Si lo representamos por &, equivaldría a que “Pablo “&”Pérez”= “Pablo Pérez”.

En las hojas de cálculo disponemos de la función CONCATENAR, que une varios textos de celdas en uno =CONCATENAR(A12;B22;G1).

Más difícil es concatenar números naturales, de forma que el resultado sea otro verdadero número en el que cada cifra tenga su valor relativo. Una forma se basa en esta función CONCATENAR. Para ello debemos convertir los números en cadenas, con la función TEXTO, después, concatenarlos, y finalmente, usar la función VALOR para devolverles el carácter numérico. Tiene un inconveniente, y es que TEXTO ha de ir acompañado de un formato, y esto lo complica todo. En PARI no existe ese problema, por lo que puedes definir la concatenación entre números mediante

concatint(a,b)=eval(concat(Str(a),Str(b)))

Un método más matemático, y es el que adoptaremos para la hoja de cálculo es el de multiplicar el número de la izquierda por una potencia de 10 adecuada y sumar luego el de la derecha. Así, concatenar 255 con 182 equivaldría al número 255*10^3+182=255182

¿Qué exponente ha de tener esa potencia de 10? El número de cifras del que está a la derecha. Para encontrar ese número podemos usar el logaritmo decimal, de esta forma: =ENTERO(LOG(N;10))+1. Por tanto, una concatenación numérica vendría dada por la fórmula CONCAT(A;B)=A*10^((ENTERO(LOG(B;10))+1))+B

Esta fórmula fallaría para B=0, por lo que habría que retocarla con un condicional, pero no lo haremos. Basta que se sepa que existe esa función numérica, y en la práctica en este blog usaremos una rutina en Basic.

Se producen muchas curiosidades cuando concatenamos números naturales. Veamos algunas. Es evidente que nos movemos en cuestiones curiosas y no teóricas. Comenzamos generando números triangulares y dejaremos para otras entradas otros casos.

Producir triangulares

Intentaremos concatenar un número n consigo mismo o con otros relacionados con él a fin de conseguir un número triangular. Por ejemplo, 426 concatenado consigo mismo produce el triangular 426426. Para entender mejor lo que sigue, recuerda que todo número triangular se puede expresar como N(N+1)/2, es decir, la mitad de un oblongo N(N+1). En este caso, 426426=923*924/2

Estudiamos algunas concatenaciones concretas:

Triangular concatenando n//n

En primer lugar probaremos a concatenar un número consigo mismo para producir un triangular.

Ya están publicados en http://oeis.org/A068899

55, 66, 5050, 5151, 203203, 255255, 426426, 500500, 501501, 581581, 828828, 930930, 39653965, 50005000, 50015001, 61566156, 3347133471, 5000050000, 5000150001, 6983669836, 220028220028, 500000500000, 500001500001…

Si te llaman la atención los ejemplos del tipo 500…500 y 500…1500…1, piensa que no son nada extraordinarios: 500500=1000*1001/2, que es un triangular y 50015001=10001*10002/2 que es otro. Investiga casos similares.

Triangular concatenando 2n//n

De esta forma se generan los siguientes:

21, 105, 2211, 9045, 222111, 306153, 742371, 890445, 1050525, 22221111, 88904445, 107905395, 173808690, 2222211111, 8889044445, 12141260706, 15754278771, 222222111111, 888890444445, 22222221111111, 36734701836735, 65306123265306, 88888904444445, 163718828185941…

¿Es siempre triangular 2222…1111…? Sí, porque sus dobles se descomponen como 4444…2222=6666..6*6666…7, es decir, números oblongos formados por productos de números consecutivos. En lo que sigue acudiremos varias veces al hecho de que el doble de un triangular es un oblongo, k(k+1).
Se puede demostrar que cada vez que se añade la cifra a los factores aparecen 4444..2222. Lo razonamos con 666*667=444222 pero para más cifras se comprende igual: En efecto, si 666*667=444222, al añadir una cifra tenemos:

6666*6667=(6000+666)(6000+667)=36000000+6000*1333+666*667=43998000+444222=44442222.

Observa que si aumentamos las cifras, 1333 se convertiría en 133….33 y el sumando final 43998000 en 4399…8000… con lo que el efecto de reconstruir 44444 y 2222 sería el mismo.

Algo similar ocurre con la subsucesión 9045, 890445, 88904445,…engendrada por los oblongos 134*135, 1334*1335, 13334*13335,…Son casualidades que ocurren al dividir las potencias de 10 en tercios o en sextos.

Si deseas reproducir los resultados puedes usar este código en PARI

concatint(a,b)=eval(concat(Str(a),Str(b)))
istriang(x)=issquare(8*x+1)
{for(n=1,10^5,a=concatint(2*n,n);if(istriang(a),print(a)))}

Hemos publicado esta sucesión en https://oeis.org/A226742

Concatenación inversa n//2n

¿Y si concatenáramos en sentido contrario, primero el número y después su doble? Pues, aunque menos llamativo, también se construyen triangulares. Son estos:

36, 1326, 2346, 3570, 125250, 223446, 12502500, 22234446, 1250025000, 2066441328, 2222344446, 2383847676, 3673573470, 125000250000, 222223444446, 5794481158896, 12500002500000, 12857132571426, 22222234444446, 49293309858660...

Intenta razonar la aparición de estos números, con un método similar al usado en el anterior caso: 36, 2346, 223446, 22234446,… es porque sus dobles se descomponen como 666…68*666…69. Observa también esta otra subsucesión: 125250, 12502500, 12500025000, que provienen de los oblongos 500*501, 5000*5001,…¿Y el resto? Te lo dejamos por si encuentras una pauta.

Código PARI para este caso:

concatint(a,b)=eval(concat(Str(a),Str(b)))
istriang(x)=issquare(8*x+1)
{for(n=1,10^7,a=concatint(n,2*n);if(istriang(a),print(a)))}

Hemos publicado esta sucesión en https://oeis.org/A226772

Concatenación n//n+1

También se producen números triangulares:

45, 78, 4950, 5253, 295296, 369370, 415416, 499500, 502503, 594595, 652653, 760761, 22542255, 49995000, 50025003, 88278828, 1033010331, 1487714878, 4999950000, 5000250003, 490150490151, 499999500000, 500002500003, 509949509950, 33471093347110, 49999995000000, 50000025000003, 69834706983471…

Se destaca el subconjunto 45, 4950, 499500,….y es porque sus dobles son 9999…*10000… y también los 5253, 502503, 50035003,…¿En qué se parecen entre sí?

Puedes reproducirlos con este código PARI

concatint(a,b)=eval(concat(Str(a),Str(b)))
istriang(x)=issquare(8*x+1)
{for(n=1,10^7,a=concatint(n,n+1);if(istriang(a),print(a)))}

Hemos publicado esta sucesión en https://oeis.org/A226788

Con n+1//n resultan verdaderos monstruos

21, 26519722651971, 33388573338856, 69954026995401, 80863378086336,…

A partir de este último no se han podido encontrar más para n<10^10, o resultados menores que 10^20. Quizás con una herramienta o equipo más potentes se pueda encontrar alguno más fuera de esa acotación. Los lectores quedáis invitados a intentarlo. Podéis usar este código PARI

concatint(a,b)=eval(concat(Str(a),Str(b)))
istriang(x)=issquare(8*x+1)
{for(n=1,10^7,a=concatint(n,n+1);if(istriang(a),print(a)))}

Si disponéis de MATHEMATICA también bastará adaptar este otro, añadido por T.D. Noe a A226789:

TriangularQ[n_] := IntegerQ[Sqrt[1 + 8*n]]; t = {}; Do[s = FromDigits[Join[IntegerDigits[n+1], IntegerDigits[n]]]; If[TriangularQ[s], AppendTo[t, s]], {n, 100000}]; t (* T. D. Noe, Jun 18 2013 *)

No vamos seguir las concatenaciones de este tipo. Las dejamos para quien le apetezca encontrar más ejemplos curiosos. Sí podíamos seguir jugando con las cifras, pero con otras estructuras. Seguimos buscando triangulares.

Otras concatenaciones para triangulares

No hemos intentado todavía concatenar un número con su reverso. Por ejemplo, 59 con 95 forman el triangular 5995. Intentamos una búsqueda por ahí. Antes de presentar resultados hay que advertir que los terminados en 0, como 90, producen resultados ambiguos, en este caso 990. Por eso restringiremos la búsqueda a números no múltiplos de 10. En ese caso resultan estas soluciones:

55, 66, 5995, 8778, 617716, 828828, 35133153, 61477416, 1264114621,…, que forman una subsucesión de http://oeis.org/A003098

Un resultado curioso es si concatenamos un número n por la izquierda con 10*n, porque en ese caso resulta un número duplicado con un cero en el centro. Hemos encontrado estos, que resultan muy vistosos:

41041, 66066, 165301653, 56661056661, 3719010371901, 276816602768166, 13776656013776656, 28265441028265441, 41631576041631576, 47337278047337278, 55666611055666611, 82189446082189446, 91836735091836735, 1185252600118525260, 1960592100196059210…

Como es norma de este blog, evitamos seguir insistiendo en el tema. Con estos ejemplos nuestros lectores pueden abordar otras búsquedas.


jueves, 17 de octubre de 2013

Ciclos(3) Números de Stirling de primera especie

Vimos en la entrada anterior que toda permutación sobre el conjunto {1,2,3,…,n} se puede descomponer en k ciclos, y van desde la identidad, que comprende n ciclos, hasta las permutaciones cíclicas, que se reducen a un solo ciclo.

Si fijamos el número k, podremos plantearnos cuántas permutaciones se pueden descomponer exactamente en k ciclos. Por ejemplo, en el conjunto {1,2,3,4,5}, las permutaciones formadas por dos ciclos son (escribimos sólo los conjuntos invariantes en los ciclos):

(1,2,3,4)(5), (1,2,3,5)(4), (1,2,4,5)(3), (1,3,4,5)(2), (2,3,4,5)(1),
(1,2,3)(4,5), (1,2,4)(3,5), (1,3,4)(2,5), (2,3,4)(1,5), (1,2,5)(3,4), (1,3,5)(2,4), (2,3,5)(1,4),
(1,4,5)(2,3), (2,4,5)(1,3), (1,3,5)(1,2)

Resultan en total 15 configuraciones, pero cada conjunto de cuatro elementos equivale a seis ciclos (permutaciones circulares, factorial de n-1=3). Así, (1,2,3,4) contiene en realidad los ciclos (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3)(1,4,3,2) y cada conjunto de tres equivale a dos ciclos (y los de dos, a uno solo), luego tendremos:

S(5,2)=5*6+10*2=50

Al número de permutaciones de n elementos que están formadas por k ciclos le llamaremos número de Stirling de primera especie sin signo, y lo representaremos por S(n,k). Así, el cálculo anterior se puede expresar como S(5,2)=50

Es evidente que S(n,n)=1, pues sólo la identidad contiene n ciclos, y que S(n,1)=(n-1)!, pues representaría a las permutaciones circulares. Además, S(n,0)=0, valor adoptado por definición. Piensa también por qué S(n,n-1)=Cn,2 (número combinatorio).

El resto de números de Stirling se obtiene mediante la fórmula de recurrencia

S(n+1,k)=S(n,k-1)+nS(n,k)

En efecto, si añadimos un elemento nuevo a una configuración en ciclos, puede ocurrir que ese elemento sea un invariante, que forme ciclo consigo mismo. En ese caso puede estar acompañado de S(n,k-1) formas distintas de distribución en ciclos. Por el contrario, si el nuevo lo deseamos integrar en los ciclos ya existentes, lo podemos incluir ocupando n lugares distintos, luego formará nS(n,k) configuraciones diferentes.

Lo entenderás mejor con un ejemplo. Formemos todas las distribuciones de 4 elementos en 3 ciclos:

(1)(2,3)(4), (2)(1,3)(4), (3)(1,2)(4)
(1,4)(2)(3), (1)(2,4)(3), (1)(2)(3,4)

En total resultan 6. En la primera fila hemos añadido el 4 como elemento invariante, añadido a las tres configuraciones de 3 elementos en dos ciclos S(3,2) y en la segunda lo hemos integrado en los ciclos existentes, que sólo tienen una posibilidad, (1)(2)(3) (S(3,1)) y podemos insertarlo en 3 posiciones distintas, luego resultan 3S(3,3). En resumen:

S(4,3)=S(3,2)+3S(3,3)

Esto nos da una posibilidad de calcular estos números. Por convenio se les da valor cero cuando el número de ciclos es cero. En la imagen tienes la tabla conseguida en hoja de cálculo con stirling.xls y stirling.ods (los puedes descargar desde
http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#nume)



Comprueba en ella alguna generación por recurrencia. Por ejemplo, 274=50*5+24, 1624=225*6+274

También es elemental la propiedad de que la suma de números de Stirling para un n dado es n!, pues abarcan todas las posibilidades. Comprueba este hecho sumando todos los números de una misma fila en la tabla de la imagen.

Observa que cada fila posee un solo máximo, como ocurre, por ejemplo con los números combinatorios, sólo que aquí no está necesariamente en el punto medio.

Función generatriz

La función generatriz de estos números (con signo), para un n dado es

Fn(x)=x(x-1)(x-2)(x-3)…(x-n+1)=x(n

Con ella resultan los números con signo y prescindiendo de S(n,0). Observa que se trata de una potencia factorial, o factorial de grado n de x. Los números de Stirling con signo obedecen la misma fórmula de recurrencia, pero restando el segundo término. Esto es claro si consideras el desarrollo de

Fn+1(x)=x(x-1)(x-2)(x-3)…(x-n+1)(x-n)= Fn(x)(x-n)

Piensa en un grado cualquiera del desarrollo y lo comprenderás.

Lo podemos comprobar con PARI, por ejemplo en el caso n=6

{print(taylor(x*(x-1)*(x-2)*(x-3)*(x-4)*(x-5),x,7))}

Resultado: -120*x + 274*x^2 - 225*x^3 + 85*x^4 - 15*x^5 + x^6 + O(x^7)

En la imagen puedes estudiar la comprobación con wxMaxima:



Como ves, los ordena en sentido inverso.

Una interpretación sencilla de este desarrollo es el considerar los números de Stirling (salvo el caso de índice cero) como los coeficientes mediante los que una potencia factorial x(n se descompone como combinación lineal de potencias ordinarias xk de x.