lunes, 30 de enero de 2017

Números 3-friables


Estudiaremos en esta entrada y la siguiente los números que sólo poseen como factores primos el 2 y el 3. De nuevo nos inspiramos en una sucesión de OEIS. Esta vez en la A003586 (http://oeis.org/A003586), que presenta los que llama “3-smooth numbers”, que se puede traducir como “liso o alisado (o regular) de grado 3”. En francés se les denomina 3-friables, y en nuestro idioma “friable” equivale a “fácilmente desmenuzable”. Si alguien conoce otra  denominación española puede comunicármelo. Mientras tanto, utilizaré una denominación similar a la francesa. Hendrik Lenstra les llama armónicos, en recuerdo de un texto de Phillipe de Vitry, obispo de Meaux, compositor del siglo XIV.

Me quedaré con la nomenclatura francesa: Un número es B-friable si todos sus factores primos son menores o iguales a B. En nuestro caso los números que estudiaremos son 3-friables. En este blog no nos son desconocidos, porque vimos en una entrada de hace unas semanas que los máximos productos de sumandos en las particiones de un número eran de este tipo (ver http://hojaynumeros.blogspot.com.es/2016/11/maximo-producto-en-la-particion-de-un_23.html)

Simplemente son números cuyos únicos factores primos son el 2 o el 3 (o ambos), es decir, que tienen la forma N=2^i*3^j con i,j³0.

Los primeros son estos:

1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486,…

Es fácil ver que desde el 1=2^0*3^0 hasta el final, todos tienen como únicos factores primos el 2 y/o el 3.

Existe una prueba muy sencilla para averiguar si un número es de este tipo. Consiste en dividir entre 2 y entre 3 mientras sea posible, es decir, mientras el número y los cocientes sucesivos sean múltiplos de uno de los dos. Si al final del proceso nos queda un 1, es que los únicos factores son 2 y 3, como se pide. Lo podemos concretar mediante la función solo23, que devuelve VERDADERO o FALSO. Adjuntamos la versión para el Basic de hojas de cálculo:

Public Function solo23(n) As Boolean
Dim m
m = n ‘m representa los cocientes sucesivos
While m Mod 2 = 0: m = m / 2: Wend ‘Divide entre 2 mientras se pueda
While m Mod 3 = 0: m = m / 3: Wend ‘Hace lo mismo con el 3
If m = 1 Then solo23 = True Else solo23 = False ‘Si al final queda un 1, es de ese tipo
End Function

La siguiente tabla aparece en la hoja con bastante rapidez:



La versión en PARI puede ser esta:

m23(n)={local(m,v);m=n;while(m/2==m\2,m=m/2);while(m/3==m\3,m=m/3);if(m==1,v=1,v=0);v}
for(i=1,300,a=m23(i);if(a,print1(i,", ")))

Es idéntica a la anterior, pero con otras reglas de sintaxis.

Esta misma idea puede servir para descomponer un número 3-friable en sus dos componentes 2^p y 3^q. Insertamos las funciones COMP2 Y COMP3 que no necesitan explicación:

Public Function comp2(n)
Dim m
m = n
While m Mod 3 = 0: m = m / 3: Wend 'Divide entre 3 mientras se pueda
comp2 = m
End Function

Public Function comp3(n)
Dim m
m = n
While m Mod 2 = 0: m = m / 2: Wend 'Divide entre 2 mientras se pueda
comp3 = m
End Function

En la siguiente tabla se han descompuesto los primeros números 3-friables:



Generación recursiva

Es tentador generar nuevos términos si se conocen los anteriores. Se puede lograr siguiendo algunas ideas sugeridas en la sucesión A003586 ( Hai He y Gilbert Traub, Dec 28 2004 ). El procedimiento se basa en que las potencias de 2 aparecen con más frecuencia que las de 3. Usamos estas potencias 3^q como indicadores del progreso de creación: mientras se pueda, se añaden factores 2 a los términos anteriores, y cuando ya sea imposible, se aumenta el exponente del 3 y se toma como nuevo término.

Dada una potencia de 3 cualquiera, 3^q, que sea término de la sucesión:

(1) Se prueba a multiplicar por 2 todos los términos anteriores que den lugar así a términos nuevos
(2) Si se agotan las multiplicaciones por 2 (al sobrepasar 3^q), se pasa a 3^(q+1) y se vuelve al paso 1.


 El problema de este procedimiento es que para multiplicar por 2 quizás debamos retroceder bastante en la sucesión, con lo que habría que definir variables locales que almacenaran los términos, con ocupación de memoria y la ignorancia previa de qué dimensión darles. Para resolverlo usaremos la primera columna de una hoja de cálculo. Definiremos como u(k) el valor de la celda k de la primera columna, y usaremos una subrutina es_u(k,v) para escribir el valor v en esa celda k. Lo escribimos para Excel:

Public Function u(i)
u = ActiveWorkbook.Sheets(1).Cells(i, 1).Value ‘la variable u(i) representa la celda i
End Function

Sub es_u(i, a)
ActiveWorkbook.Sheets(1).Cells(i, 1).Value = a ‘esta rutina lee el valor de la celda i
End Sub

Con la ayuda de estas dos rutinas, podemos ya presentar el algoritmo completo:

Sub engendram23()
Dim k, j, n

Call es_u(1, 1) ‘rellena con un 1 la primera celda de la columna 1
k = 1 ‘la variable k lleva la cuenta de los términos engendrados
j = 1 ‘la variable j lleva la cuenta de los exponentes del 3
For n = 1 To 100 ‘así se generan 100 términos. Lo podemos cambiar.
k = k + 1 ‘se busca un nuevo elemento
If 2 * u(k - j) < 3 ^ j Then ‘se retrocede para multiplicar por 2
Call es_u(k, 2 * u(k - j)) ‘si no se llega a la potencia 3^j, se almacena un nuevo término
Else
Call es_u(k, 3 ^ j): j = j + 1 ‘si ya no es posible multiplicar por 2, se almacena 3^j y se incrementa
End if
Next n
End Sub

Aquí tienes el resultado de los primeros, ordenado por filas:




¿Por qué no un producto cartesiano?

Los anteriores cálculos se han introducido para que los números 3-friables aparezcan ordenados, pero si renunciamos a ese detalle, se pueden generar sencillamente con un producto cartesiano entre el conjunto de las potencias de 2 y el de 3. Si trabajamos con hoja de cálculo podemos posteriormente ordenar la columna que los contiene.

Así hemos procedido acudiendo a nuestra hoja Cartesius, de pronta publicación. Hemos definido dos conjuntos de potencias (2 y 3) que hemos combinado formando un producto cartesiano, indicando a la hoja que nos presente el producto de cada par. Las instrucciones han sido estas:



Se adivina que se han definido dos conjuntos, uno de potencias de 2 a partir de 1 (de ahí el n-1) y otro de potencias de 3. A los pares que resultan se les ha convertido en producto, creando así una columna desordenada de números del tipo 2^p*3^q. Después sólo queda copiar esa columna en otra hoja y proceder a ordenarla. De esa forma dispondremos de (en este caso 1000) los números 3-friables hasta donde deseemos.

En esta captura de pantalla puedes ver algunos de ocho cifras:




jueves, 19 de enero de 2017

Número de descomposiciones en diferencia de cuadrados


Después de jugar bastante con los números naturales, he observado la disparidad existente entre ellos respecto al número de sus descomposiciones en diferencias de cuadrados. Nos referimos al número de soluciones de

N=a^2-b^2 con a y b enteros y a>0 y b>=0 para un N dado.

Hay números que no admiten ninguna descomposición de este tipo, como el 22, y otros que admiten muchas. Un ejemplo es el 1680, que admite doce:

1680=421^2-419^2=212^2-208^2=143^2-137^2=109^2-101^2=89^2-79^2=
=76^2-64^2=67^2-53^2=52^2-32^2=47^2-23^2=44^2-16^2=43^2-13^2=41^2-1^2

En la tabla lo puedes comprobar:



¿De qué depende esto? Lo iremos viendo más adelante.

Obtención del número de descomposiciones

Al igual que hemos procedido con otros temas, comenzaremos encontrando las soluciones sin apoyo de la teoría, para más adelante fundamentarlo y después extraer propiedades y curiosidades.

Cualquier algoritmo para resolver esta cuestión se puede basar en el hecho de que una descomposición de este tipo equivale a expresar N mediante un producto de factores con la misma paridad, ambos pares o ambos impares. En efecto, si N=b^2-a^2 resultaría N=(a+b)(a-b), y ambos factores tienen la misma paridad, como se comprueba estudiando los cuatro casos posibles para a y b: par-par, par-impar, impar-par e impar-impar. Es fácil. A la inversa: si N=m*n, ambos de la misma paridad resultaría que (m+n)/2 y (m-n)/2 serían enteros, cumpliéndose que N=((m+n)/2)^2-((m-n)/2)^2

El número de descomposiciones de N en diferencia de cuadrados coincide con el de productos con factores de la misma paridad y resultado N.

Para hacer más fáciles los trabajos, admitiremos que b pueda ser nulo, o de forma equivalente, que los dos factores sean iguales.

Establecida esta propiedad, la búsqueda se efectuaría encontrando divisores d de N tales que d y N/d tengan la misma paridad. Esto lo podemos lograr fácilmente, usando divisiones enteras y aritmética modular. En el siguiente ejemplo lo implementamos como función Basic para hojas de cálculo:

Public Function numdifcuad(n)
Dim i, m
m = 0 ‘Contador de casos
For i = 1 To Sqr(n) ‘Se llega a la raíz cuadrada para evitar repeticiones de divisores
If n / i = n \ i Then ‘Si el cociente es igual al cociente entero, es que es divisor
If Abs(i - n / i) Mod 2 = 0 Then m = m + 1 ‘el divisor i y el cociente n/i tienen la misma paridad, porque su diferencia da resto 0 módulo 2, luego incrementamos el contador.
End If
Next i
numdifcuad = m
End Function

Así de sencillo. Con esta función podemos contar las descomposiciones posibles para cada número. En la tabla puedes observar las correspondientes a los primeros números:



Verás que se dan muchos casos, desde el 22 o el 14, que no admiten descomposiciones, hasta el 16 o el 15, que admiten 2. Si siguiéramos leyendo hacia abajo descubriríamos que 45 es el primero que admite 3 casos: 45=23^2-22^2=9^2-6^2=7^2-2^2.que se corresponden con las descomposiciones en producto 45=45*1=15*3=9*5, todas con factores de igual paridad. El primero con cinco casos es el 96, y así podríamos seguir hasta 1680 que vimos presenta doce.



Estos resultados están ya publicados en https://oeis.org/A034178



Podemos comprobar que coinciden con nuestros resultados

Análisis teórico de la situación

Es importante distinguir en principio si N es par o impar.

Caso 1: N es impar

Si N es impar, todos los posibles pares de factores N=m*n tendrán la misma paridad, luego sólo tenemos que contarlos. Recordamos que la función TAU, que cuenta los divisores, viene dada por la fórmula


En ella a, b c,…representan los factores primos y p, q, r,…sus exponentes. Como los divisores han de formar pares, deberemos encontrar la mitad de la función (si esta es par), por tanto, si expresamos el número de descomposiciones mediante la función ND, tendremos:


Lo comprobamos. Según la tabla el 21 admite dos descomposiciones. Como 21=3*7, ?(21)=(1+1)(1+1)=4, y su mitad entera es dos, como indica la tabla.

Si TAU es impar, será porque todos los exponentes serán pares, con lo que N será un cuadrado, apareciendo entonces un par nuevo al multiplicar la raíz cuadrada por sí misma. Podemos unificar ambas situaciones:


El segundo paréntesis valdrá cero en el caso par y uno en el impar.

Es el caso del número 3969:



Los factores son todos impares, los exponentes, 4 y 2, pares. TAU valdrá en este caso (1+4)(1+2)=15. Su mitad entera es 7, y añadimos 1 por su raíz cuadrada. Coincide entonces con el valor 8 que nos da NUMDIFCUAD.

Caso 2: N es par

En este caso aparece el factor 2, lo que obliga a que los dos factores que buscamos sean ambos pares y deban contener el 2 como factor. Esto no es posible si el factor 2 es único, con exponente 1, y esa es la causa de que 6, 10, 14 o 22 no presenten descomposiciones.

No admiten descomposiciones en diferencias de cuadrados los múltiplos de 2 que no lo sean de 4, es decir, los del tipo 4k+2

N es potencia de 2

Siguiendo un razonamiento similar al caso impar, deberemos encontrar la función TAU. Como tratamos con un solo exponente, sea p, el número de divisores será 1+p, pero al ser el caso par, el divisor 1 no nos interesa, y nos quedarían tan solo p divisores. Así, para p=5 dispondríamos de 2, 4, 8, 16 y 32. La potencia completa, en este caso 32, no nos valdría, porque tendría que formar par con el 1, que es impar, luego sólo nos quedan p-1 divisores disponibles. Esto vuelve a confirmar que el caso p=1 no produce pares de la misma paridad.

Los pares engendrados por el 2 serán pues, (p-1)/2 si p es impar y Int((p-1)/2)+1 si es par, por el par que se gana por su raíz cuadrada. Unificando:

N no es potencia de 2

Si el número es potencia de 2, sin factores impares, esta expresión vale, pero, en caso contrario, estas posibilidades del factor 2 se deberán multiplicar por las correspondientes al factor impar. La complicación surge del hecho de cada par puede producir productos idénticos, que se contarían dos veces, y hay que tener en cuenta los pares de factores repetidos en el caso de que p sea par. Por ello, la única forma de encajar todo es:


Multiplicamos el número de pares con factores desiguales de la potencia de 2 contenida en N por todos los factores de la parte impar de N, y después, en otro producto, los factores con repetición se multiplican sólo por los pares que se forman en la parte impar. Algo complicado, pero funciona.

Hemos plasmado los tres casos en una única función, a la que llamaremos NUMDIFCUAD2:

Public Function numdifcuad2(n)
Dim p, q, r, s, t, m

m = n: p = 0
While m Mod 2 = 0: m = m / 2: p = p + 1: Wend ‘Extraemos la potencia de 2
If p = 1 Then numdifcuad2 = 0: Exit Function ‘Caso imposible
q = n / 2 ^ p ‘q es la parte impar
If q = 1 And p > 1 Then numdifcuad2 = Int((p - 1) / 2) + (p - 1) Mod 2
‘Es potencia de 2 pura
If p = 0 And q > 1 Then t = fsigma(q, 0): numdifcuad2 = Int(t / 2) + t Mod 2
‘Es un número impar
If p > 1 And q > 1 Then t = fsigma(q, 0): numdifcuad2 = t * Int((p - 1) / 2) + ((p - 1) Mod 2) * (Int(t / 2) + t Mod 2)
‘Tiene parte par y parte impar
End Function

La complejidad del cálculo nos ha aconsejado comprobar mediante tablas si las dos versiones de NUMDIFCUAD coinciden. Lo hemos probado desde 1 hasta 100000, sin que aparecieran discrepancias. Como ejemplo, adjuntamos los valores de algunos números de seis cifras entre los que hay impares, pares y una potencia de 2 pura:



Otra interpretación

Como todo cuadrado es suma de números impares consecutivos, como por ejemplo 16=1+3+5+7, al restar dos cuadrados se eliminarán sumandos impares, quedando tan sólo aquellos que no sean comunes. Es, por ejemplo, el caso de 44=12^2-10^2=21+23 o el de 72=9^2-3^2=7+9+11+13+15+17

Así que el número de descomposiciones que estamos estudiando coincide con el de formas de expresar el número como suma de impares.





lunes, 9 de enero de 2017

Sandwich de semiprimos


Unos comentarios de James Tanton (@jamestanton) en Twiter me han hecho interesarme por aquellos números tales que tanto su anterior como su posterior son semiprimos. No los recorreremos todos, porque son muchos, sino que los clasificaremos por tipos.

Todos los números que poseen esta propiedad han de ser pares, salvo el 5, porque si fueran impares, los semiprimos adyacentes deberían ser dobles de primos, que serían números consecutivos, lo que salvo el caso de 2 y 3 es imposible.

Consecuencia inmediata es que un número primo mayor que 5 no puede estar encerrado entre dos semiprimos.

Los comentarios citados arriba se referían a los cuadrados, y estos ya están publicados en http://oeis.org/A108278

Cuadrados “sandwicheados”

En realidad, en esa página figuran las bases, pero elevando al cuadrado nos resultarán los cuadrados pedidos:

144, 900, 1764, 3600, 10404, 11664, 39204, 97344, 213444, 272484, 360000, 656100, 685584, 1040400, 1102500, 1127844, 1633284, 2108304, 2214144,…

En todos ellos el anterior y el posterior son semiprimos. Tomemos el cuadrado 213444=462^2. Su anterior 213443=461*463  y el posterior 213445=5*42689, ambos semiprimos. El primero nos lleva a una situación interesante, y es que si el cuadrado central es n^2, el anterior será n^2-1=(n-1)(n+1), y al ser semiprimo el producto ambos factores serán primos y más aún, primos gemelos. Es lo que ha ocurrido con el 144.

Si un cuadrado está rodeado por dos semiprimos, el anterior es producto de dos primos gemelos.

Respecto a los factores de n^2+1, han de ser del tipo 4k+1, según estudiamos hace tiempo. Puedes seguir el razonamiento en el apartado dedicado a “Un cuadrado y una unidad” en el documento

http://www.hojamat.es/publicaciones/hojanum1.pdf

Al deber ser pares, estos cuadrados serán todos múltiplos de 4.

Si deseas reproducirlos con PARI, este puede ser el código:

for(i=2,2000,n=i*i;if(bigomega(n-1)==2&&bigomega(n+1)==2,print1(n,"; ")))

Triangulares entre semiprimos

También los triangulares pueden estar comprendidos entre dos semiprimos. Los primeros están publicados en http://oeis.org/A121898

120, 300, 528, 780, 2628, 3240, 3828, 5460, 13530, 18528, 19110, 22578, 25878, 31878, 32640, 37128, 49770, 56280, 64980, 72390, …

En PARI:

for(i=2,2000,n=i*(i+1)/2;if(bigomega(n-1)==2&&bigomega(n+1)==2,print1(n,"; ")))

Además de ser pares, son múltiplos de 3, y por tanto de 6. En efecto, si un triangular no es múltiplo de 3 sólo puede ser porque su orden sea del tipo 3k+1, ya que entonces el triangular tendría la expresión (3k+1)(3k+2)/2, que no contiene ningún factor 3 (en los otros casos sí). Pero en este caso, al restarle 1 no obtendríamos un semiprimo. Lo desarrollamos:


Al tener el factor 9 no puede ser semiprimo. Además hemos descubierto que es nueve veces el triangular de orden k.

Por ejemplo, el número triangular de orden 13, 91=13*14/2, no es múltiplo de 3, y su anterior, 90, no puede ser semiprimo, y es igual a 9*10=9*T(4)

El desarrollo anterior se puede invertir, es decir, que si multiplicamos por 9 un triangular y sumamos 1, obtenemos otro triangular no múltiplo de 3 o 6.
Sólo los números triangulares N múltiplos de 6 pueden tener semiprimos N-1 anteriores a ellos.

Oblongos entre semiprimos

¿Ocurrirá algo similar con los oblongos? La respuesta es negativa.

Recordemos que los números oblongos son los dobles de los triangulares, es decir, los que se pueden expresar como N=k(k+1). Así, 56=7*8 es oblongo, y su anterior 55=5*11 y el posterior 57=3*19 son semiprimos. Cumple la condición de estar entre semiprimos, pero no es múltiplo de 3 (par sí tiene que ser).

Los primeros oblongos con la propiedad requerida son:

56, 552, 870, 1056, 1190, 1640, 1892, 2652, 4032, 5256, 5402, 6806, 8372, 9120, 9506, 9702, 10920, 11772, 12656, 12882, 15006, 15252, 15500, 16256, 16770, 17556, 18632, 23256, 24492, 27722, 29070, 30800, 33306, 33672, 34410, 36290, 40200, 40602, 44310, 45582, 46872, 49506,…

Esta sucesión estaba inédita y la hemos publicado en https://oeis.org/A276565

Tomamos uno de ellos, por ejemplo 16256=127*128, y por tanto, oblongo. Su anterior es semiprimo, ya que 16255=5*3251, y 16257=3*5419, también lo es.

El posterior no puede ser múltiplo de 5, porque los oblongos terminan todos en 0, 2 o 6, y al sumar no obtendremos ni 5 ni 0 como última cifra.

El anterior no puede ser múltiplo de 3. Si lo es el oblongo, es claro que al restar 1 deja de serlo. Si no lo es, sería del tipo

(3k+1)(3k+2)-1 = 9k^2+9k+1 y tampoco.

Si deseas obtener más términos, puedes adaptar este código en PARI:

for(i=2,2000,n=i*(i+1);if(bigomega(n-1)==2&&bigomega(n+1)==2,print1(n,"; ")))

Números de Fibonacci

Están publicados los números de la sucesión de Fibonacci comprendidos entre semiprimos. Sólo hay cuatro con pocas cifras: 5, 34, 144, 46368.  Se conjetura que no hay infinitos.

Puedes estudiarlos en http://oeis.org/A167023

Cubos perfectos

Los cubos rodeados de semiprimos son muy escasos. El primero es 216=6^3, con 215=5*43 y 217=7*31.

Los siguientes llegan a ser casi inabordables: 216, 1302170688, 7211429568, 20346417000, 71887512312, 281268868608, 1394417360448, 17571944311992, 28350304855488, 170400029184000, 450335804625000, 504966851923968, 616121259098688, 1064394808685208, 3442267015299000, 3517494650695368, 3540860163178632, …

Es preferible tratar con sus bases. Las tienes publicadas en http://oeis.org/A268043

6, 1092, 1932, 2730, 4158, 6552, 11172, 25998, 30492, 55440, 76650, 79632, 85092, 102102, 150990, 152082, 152418, 166782, 211218,…

Estos números tienen una propiedad importante, y es que su anterior y posterior han de formar un par de primos gemelos. La idea es sencilla: si n^3-1 ha de ser semiprimo, al ser múltiplo de n-1, este ha de ser primo, pues en caso contrario el otro no sería semiprimo. Igual ocurre con n+1. Por ejemplo, 166782 está rodeado por los primos gemelos 166781 y 166783.

Los puedes encontrar con PARI:

for(i=2,2000,n=i^3;if(bigomega(n-1)==2&&bigomega(n+1)==2,print1(i,"; ")))

Potencias enteras

Hemos estudiado los cuadrados y cubos entre semiprimos, pero podríamos generalizar a todas las potencias de base y exponente enteros mayores que 1.
No es muy difícil encontrarlos si se dispone de una función ESPOTENCIA o similar. En nuestro equipo disponemos de ella, y hemos podido emprender la búsqueda, consiguiendo esta lista de los primeros:

144, 216, 900, 1764, 2048, 3600, 10404, 11664, 39204, 97344, 213444, 248832, 272484, 360000, 656100, 685584, 1040400, 1102500, 1127844, 1633284, 2108304, 2214144, 3504384, 3802500, 4112784, 4536900, 4588164, 5475600, 7784100, 7851204, 8388608, 8820900, 9000000, 9734400…

Los hemos publicado en https://oeis.org/A276564

Puedes reproducirla con PARI:

for(i=2,10^7,if(ispower(i)&&bigomega(i-)==2&&bigomega(i+1)==2,print1(i,", ")))

Con base prima hay muy pocos. Los primeros son 2048 y 8388608

Otros casos

Podríamos seguir el estudio con pentagonales (los primeros serían 5, 92, 590, 1080, 1820, 8400,…) o hexagonales (120, 780, 3828, 19110,…), pero por hoy ya está bien. Lo dejamos como propuesta.