martes, 29 de noviembre de 2011

Pasito a pasito hacia la complejidad (ampliación)

Después de publicar las dos entradas anteriores referentes a “pasito a pasito hacia la complejidad” nuestro amigo Claudio Meller nos escribió destacando propiedades muy parecidas. En concreto:

47 primo
46 = 2 x 23
45 = 3 x 3 x 5

107 primo
106 = 2 x 53
105 = 3 x 5 x 7
104 = 2 x 2 x 2 x 13

71999 primo
71998 = 2 x 35999
71997 = 3 x 103 x 233
71996 = 2 x 2 x 41 x 439
71995 = 5 x 7 x 11 x 11 x 17

En este blog si nos dan un empujoncito salimos corriendo a descubrir cosas nuevas. Así que Claudio ha sido en este caso el motor de arranque de nuevas búsquedas.

Pasitos hacia atrás

En efecto, los pasos no tienen que ser necesariamente hacia un crecimiento. Pueden decrecer, como en los ejemplos propuestos por nuestro amigo. Investigando en OEIS y con nuestros buscadores podemos presentar lo siguiente:

Primos p con p-1 semiprimo

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467,…

https://oeis.org/A005385

Como en la entradas anteriores, p-1 ha de ser múltiplo de 2 y de otro primo q=(p-1)/2 Por tanto ese nuevo primo q sería del tipo de Sofie Germain.

(Ver http://es.wikipedia.org/wiki/N%C3%BAmero_primo_de_Sophie_Germain
y http://oeis.org/A005384)

Primos p con p-1 semiprimo y p-2 3-casiprimo

47, 107, 167, 263, 347, 359, 467, 479, 563, 863, 887, 983, 1019, 1187, 1283, 1907, 2039, 2063, 2099, 2447, 2819, 2879,…

En ellos p-1 es par, p-2 múltiplo de 3 y p es del tipo 12k-1

Esta sucesión estaba inédita en OEIS y la acabamos de publicar incluyendo a Claudio Meller como “sugeridor”. Está en http://oeis.org/A201147

Con tres pasos

107, 263, 347, 479, 863, 887, 1019, 2063, 2447, 3023, 3167, 3623, 5387, 5399, 5879, 6599, 6983, 7079, 8423, 8699, 9743, 9887,…

En ellos p-1 es par, p-2 múltiplo de 3, p-3 múltiplo de 4 y p es del tipo 12k-1

También la acabamos de publicar con la cita correspondiente a Claudio en http://oeis.org/A201220

Más pasos

Los primeros números naturales que inician sucesiones similares son

2, 5, 47, 107, 71999, 392279, 4533292679...

http://oeis.org/A093552

Por ejemplo, tenemos:

4533292679=4533292679
4533292678=2*2266646339
4533292677=3*251*6020309
4533292676=2*2*11*103029379
4533292675=5*5*17*1871*5701
4533292674=2*3*3*41*661*9293
4533292673=7*7*13*13*29*43*439

Si a alguien se le ocurre otro tipo de pasito a la complejidad no tiene más que avisarnos.

viernes, 25 de noviembre de 2011

Pasito a pasito hacia la complejidad (Soluciones)

(Con esta entrada y la anterior participamos en el 2.8 Carnaval de Matemáticas, organizado en esta ocasión por Ciencia Conjunta)


Soluciones a las cuestiones planteadas en la entrada anterior:

(a) Si N es primo y N+1 semiprimo, como N+1 es par, ha de ser múltiplo de 2, luego (N+1)/2 ha de ser primo para que se cumpla que N+1 sea semiprimo. Recíprocamente: si (N+1)/2 es primo, N+1 es semiprimo, pues N+1=2p con p primo.

(b) El directo es muy sencillo, pues sigma(N)=1+N por ser primo, luego sigma(N)/2 es primo. El recíproco hay que verlo con más cuidado: si sigma(N)/2 es primo, sigma(N)=2p con p primo. Pero la fórmula de sigma(N) se compone de varios factores del tipo 1+q+q2+q3+… con q factor primo de N. En este caso sólo puede haber un factor primo, ya que 1+q>2, luego el 2 se ha producido como factor de 1+q+q2+q3+…Para que 1+q+q2+q3+…=2p ha de reducirse a 1+q. En efecto, si la potencia mayor es impar, la suma de potencias 1+q+q2+…sería impar y no podría ser múltiplo de 2. Si la mayor es par, se puede descomponer en (1+q)+q(1+q)+q2(1+q)+…=(1+q)(1+q+q2+…) y ambos factores serían mayores que 2, lo que no es lo supuesto.

(c) Si N=4k+3 entonces N+1=4(k+1) con lo que no podría ser semiprimo.

(d) N es primo, luego no será múltiplo de 3. N+1 es del tipo 2p con p primo. Ese primo no puede ser 3, porque entonces N+1=6 y N=5 y hemos afirmado que es mayor. Si no es 3, no será tampoco múltiplo de 3, pues entonces N+1 no sería semiprimo. Por tanto, N+1 no es múltiplo de 3, Como los múltiplos de 3 aparecen de 3 en 3 números, N+2 sí tendrá que serlo.

(e) Si N es primo, su resto módulo 12 sólo puede ser 1, 5, 7 u 11. Por tanto los restos que producirá N+2 serán 2, 6, 8 o 0 y los de N+2 3, 7, 9 y 1. Hay que desechar estos:
11- Si el resto es 11, N+1 sería múltiplo de 12, y no podría ser semiprimo.
5- N+2 sería del tipo 12k+7, lo que impediría que fuera múltiplo de 3.
7- N+1 sería del tipo 12k+8=2*2*(3k+1) y no sería semiprimo
Luego sólo nos queda que el resto sea 1.

(f) Porque N+1 es múltiplo de 2, N+2 de 3, N+3 de 4, y así sucesivamente, luego N ha de tener resto 1 para 2, 3, 4, 5… y por tanto también para su MCM.

lunes, 21 de noviembre de 2011

Pasito a pasito hacia la complejidad

(Con esta entrada y la siguiente participamos en el 2.8 Carnaval de Matemáticas, organizado en esta ocasión por Ciencia Conjunta)


Toma el número 807905281, que es primo. Súmale una unidad y lo habrás convertido en un semiprimo múltiplo de 2:

807905282 = 2*403952641

Una unidad más y ahora será un 3-casiprimo (tres factores primos) múltiplo de 3:

807905283 = 3*15733*17117

Pero sigue de uno en uno. Descubrirás que cada vez tendremos un factor primo más y que será múltiplo de 4, 5, 6, 7, … Observa:

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


Pero hasta aquí llegamos, pues con una unidad más se disminuye el número de primos. En efecto, 807905288 = 2*2*2*53*1905437

¿Es frecuente este avanzar de unidad en unidad a estructuras más complejas?
Pues sí y no. Muy frecuente no es, pero si nos conformamos con menos pasos, existen muchos ejemplos, ya publicados, y que puedes reproducir fácilmente con un par de funciones. Aprovecharemos estos ejemplos para que razonemos un poco. Las soluciones aparecerán en una próxima entrada.

Un paso

Es el caso más simple, el de N primo y N+1 semiprimo. Lo cumplen estos primos: 3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541, 613, 661, 673, 733,… y está publicado en https://oeis.org/A005383

(a) Un razonamiento sencillo: Una condición equivalente para todos los primos N de la lista es que  (N+1)/2 sea también primo. ¿Descubres la causa?
(b) Otro más difícil: Estas condiciones también equivalen a que sigma(N)/2 sea un número primo. ¿Por qué?
(c) Salvo el 3, todos los demás son primos del tipo 4k+1. Piensa en resto que debería tener N+1 con módulo 4.

Dos pasos

Existen primos N en los que N+1 es semiprimo y N+2 tiene 3 factores primos. Son estos:
61, 73, 193, 277, 397, 421, 613, 661, 757, 1093, 1237, 1453, 1657, 2137, 2341, 2593,… https://oeis.org/A112998

Es evidente que forman un subconjunto de los anteriores, y esto nos va ocurrir en cada paso que demos.
Piensa un poco: (d) Si N>5 (y todos lo son) N+2 ha de ser múltiplo de 3

Y otro poco más: (e) Todos los primos de la sucesión presentan resto 1 al dividirlos entre 12: 61=5*12+1; 73=6*12+1,…Razónalo (lo tienes en inglés en A112998. Lo aclararemos en la próxima entrada)

Tres pasos

También los conocemos: 193, 421, 661, 1093, 1657, 2137, 2341, 2593, 6217, 7057, 8101, 9817, 12421, 12853,…https://oeis.org/A113000 Subconjunto de los anteriores y con las mismas propiedades.

En ellos N+1 es par, N+2 múltiplo de 3 y N+3 múltiplo de 4. Si has desarrollado las cuestiones anteriores, no te costará entenderlo.

Más pasos

Para seguir jugando a esto necesitas las funciones ESPRIMO y BIGOMEGA, que es la función que cuenta los factores primos con multiplicidad (Ver su código en http://hojaynumeros.blogspot.com/2011/01/redondez-de-un-numero.html)

Para crear un código de búsqueda puedes tener en cuenta que para el caso de k pasos, el número primo inicial ha de tener resto 1 tomando como módulo el MCM de los números 1,2,3…k 
 (f) Si has entendido todo lo anterior sabrás la razón.

En Basic puedes intentar algo así:

Input k Escribimos el número de pasos
Input mcm Para dar más velocidad, escribimos ya calculado el MCM
Input n Final de búsqueda. Generalmente un número grande.

For i = 1 To n Step mcm Los saltos de mcm en mcm ahorran muchos pasos de cálculo
a = 0
If esprimo(i)  Then
  For p = 1 To k
  If bigomega(i + p) = p + 1 Then a = a + 1
La línea fundamental
  Next p
  If a = k Then Msgbox(i)
End If
Next i
End Sub


Por ejemplo, para k=4, bastante tiempo y paciencia, llegarías a esta sucesión:

15121, 35521, 52321, 117841, 235441, 313561, 398821, 516421, 520021, 531121, 570601, 623641,… http://oeis.org/A113008

Para comprobar tu código y ahorrar tiempo, aquí tienes el primer número primo de cada caso:
2, 3, 61, 193, 15121, 838561, 807905281, 19896463921, 3059220303001, 3931520917431241,… https://oeis.org/A072875

Y para ampliar y asombrarte con el trabajo de algunos, estudia esta página:

http://www.primepuzzles.net/puzzles/puzz_425.htm

Las soluciones de las cuestiones (a) a (f) las tendrás en la próxima entrada de este blog

jueves, 10 de noviembre de 2011

Mi pequeño homenaje al 11/11/11

111111 se descompone en los factores primos 3, 7, 11, 13, 37. Si los concatenamos en ese orden resulta otro bonito número primo: 37111337 (Ver http://oeis.org/A046411) Si los sumamos, también: el 71

Y si expresamos 111111 en base 8: 331007(8, usa todas las cifras de la descomposición anterior.

6562-5652=111111 El curioso efecto de sustituir entre sí 6 y 5.

Como sólo quedan unas horas, no me da tiempo de buscar más.

martes, 8 de noviembre de 2011

El conjunto de los divisores

Aunque el conjunto de los divisores de un número aparece en muchas cuestiones y en este blog hemos hecho bastantes referencias a él, conviene, para entender algunas cuestiones sobre funciones multiplicativas, que le demos un repaso.

Consideremos, por ejemplo, el conjunto de los divisores de 240=24*3*5:

1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 40, 48, 60, 80, 120, 240

Lo primero que hay que considerar es que es un conjunto finito. Eso parece una trivialidad, pero nos evita preocuparnos por sumas o productos infinitos.

Orden

Los divisores presentan un orden total respecto a su valor absoluto, y además, cada divisor d está asociado a N/d mediante una correspondencia biunívoca que invierte ese orden. Si multiplicamos en la tabla siguiente dos divisores en columna siempre nos resulta 240:

240  120   80   60   48   40   30   24   20   16   15   12   10     8    6    5    4   3     2      1
  1     2       3     4     5     6    8   10   12    15   16   20   24   30  40  48  60  80 120  240

Por tanto, d y N/d recorren el mismo conjunto con órdenes opuestos.

Como todo tipo de divisores, los de N presentan también un orden parcial respecto a la relación divisor-múltiplo. En el siguiente esquema representamos el retículo correspondiente a los divisores de 240:



No se han representado todas las relaciones, para no complicar el esquema, pero cada dos divisores tiene un elemento minimal que es su MCD y otro maximal, su MCM. Obsérvese que al recorrer el esquema de arriba abajo va aumentando el número de divisores primos de las descomposiciones factoriales.

Número

Desde las enseñanzas secundarias sabemos que si un número N se descompone en factores primos como



El número de divisores, o función Tau, viene dado por

D(N)=(1+a1 )*(1+a2 )…(1+ak )

Y el conjunto de divisores coincide con los términos del producto


Esto ya es algo sabido. Sólo hay que destacar que el número de divisores depende de la signatura prima, que es el conjunto de exponentes, y no de los factores primos.

La fórmula anterior se traduce en un producto cartesiano formado eligiendo una potencia de un factor primo cada vez. Este producto cartesiano que forman los términos de la expresión (1) es fundamental para entender más tarde cómo se comportan las funciones multiplicativas sobre el conjunto de divisores.

El conjunto de divisores de un número es uno de los mejores ejemplos que existen de concurrencia entre cuestiones combinatorias y de divisibilidad.

Divisores libres de cuadrados

Si sólo consideramos los factores libres de cuadrados obtendremos un esquema similar al del Binomio de Newton. Esto nos será muy útil para algunas funciones multiplicativas.

Los divisores libres de cuadrados poseen factores primos distintos. De esta forma, para engendrar uno de estos divisores bastará elegir algunos de los factores primos, pero una sola vez cada uno. Así desembocamos en un problema de combinaciones. Lo vemos para el caso del 240, para el que el número de factores primos distintos es 3:
  • Divisores sin ningún factor primo: El 1. Hay en total C3,0
  • Divisores con un factor: 2, 3, 5. En total C3,1
  • Con dos factores distintos: 6, 10 y 15: C3,2
  • Con tres factores: 30, es decir C3,3
Así que en total hay 8. Si recuerdas el desarrollo del binomio, esto ocurre porque C3,0+ C3,1+ C3,2+ C3,3 = 23 = 8

Generalizando:


El número de divisores libres de cuadrados en un número que posee k factores primos distintos es 2k


Esta clasificación la usaremos en una próxima entrada. Hemos recorrido los ocho números libres de cuadrados 1, 2, 3, 5, 6, 10, 15 y 30.

Por tanto, el número de divisores no libres de cuadrados será:

D(N)=(1+a1 )*(1+a2 )…(1+ak )- 2k

En el caso de 240 sería: 5*2*2-8=12, que son estos: 4, 8, 12, 16, 20, 24, 40, 48, 60, 80, 120, 240

Divisores del producto

Si tomamos dos números A y B primos entre sí y los multiplicamos, sus conjuntos de divisores quedarán multiplicados término a término, todos los de A con cada uno de B.

Por ejemplo, si 240, con 20 divisores, lo multiplicamos por 119=7*17, que posee 4 divisores, 1, 7, 17 y 119, resultará 28540, con estos 80 divisores:


No sólo eso, sino que cada divisor de 28540 será el producto de uno de 240 por otro de 119, como puedes ver en esta otra forma de presentar los divisores:


Esto es así porque al ser primos entre sí A y B aportan factores primos distintos sin que se mezclen los de uno con los del otro.


Por tanto, los divisores de un producto AB en el que A y B son coprimos, están formados por todos los productos posibles dd’ en los que d divide a A y d’ a B

Y con esto llegamos a donde queríamos. Es fácil ya ver lo siguiente:

Si f es multiplicativa y se define F como




Entonces F es también multiplicativa

Ya que las multiplicativas actúan por separado sobre los factores primos y hemos visto que estos se combinan totalmente en el producto.

Este teorema hace que las funciones sigma y tau sumadas a lo largo de sus divisores sean multiplicativas, pero ya volveremos sobre ello. Por ahora lo comprobaremos para la tau mediante un ejemplo:

La suma de la función Tau para el número 77 recorriendo todos sus divisores es 9, la correspondiente a 12, coprimo con 77, es 18. Si los multiplicamos resulta 77*12=924, cuya suma de Tau es 162, producto de 9 con 18.