miércoles, 22 de octubre de 2014

Unión e intersección de conjuntos con Excel


De cuando en cuando publicamos en este blog entradas sobre el funcionamiento de las hojas de cálculo, y en concreto sobre la programación en su Basic. La de hoy es una de ellas, así que si no te interesa el tema no sigas, que no vas a encontrar cuestiones sobre números.

Nos vamos a proponer la obtención de la unión y la intersección de dos conjuntos escritos en la hoja como dos columnas paralelas. Lo desarrollaremos en Excel sólo, para no duplicar las explicaciones, pero el contenido se puede adaptar a OpenOffice o LibreOffice. No se busca aquí la utilidad, sino la posibilidad de superar un reto. Lo que construyamos puede que aparentemente no sirva para nada.

Hemos preparado un esquema en el que a partir de la fila 7 se van escribiendo los conjuntos A y B con lo que deseamos operar. Después, con una simple pulsación de un botón, realizaremos las operaciones deseadas.



Intentamos en primer lugar resolver la cuestión sin el uso de macros, pero resultó un proceso tan complejo y artificioso que renunciamos a ello. Así, todo lo que sigue se basará en el lenguaje VBA de Excel. Como se observa en la imagen, se pueden usar números y también letras y palabras. Sólo hay que tener en cuenta que un espacio en blanco cuenta como un elemento, por lo que el borrado se debe realizar con el botón correspondiente o con la tecla Supr, sin escribir nada.

Otro detalle interesante es que en las operaciones se eliminan los elementos repetidos, logrando con ello una gran limpieza en la presentación. En un segundo paso puedes ordenar los resultados sin son más extensos.



Procedimientos necesarios

Recorrido por un conjunto 

Para obtener la unión e intersección de dos conjuntos se requiere, en primer lugar, el poder recorrer un conjunto del que no se sabe en principio cuántos elementos contiene. Para ello usaremos la idea de celda vacía. El recorrido se basará entonces en “avanzo mientras la celda no esté vacía”. Esta condición se puede verificar en VBA con la función IsEmpty, que nos devuelve True si la celda no contiene ningún dato. Con ella es fácil programar un recorrido:

fila = 7
While Not IsEmpty(Cells(fila, columna)) And … (cualquier otra condición)
‘ Aquí las operaciones que deseemos realizar con el elemento.
fila = fila + 1
Wend

Este sencillo esquema se repetirá cada vez que realicemos una operación elemento a elemento: ver si un dato pertenece o no al conjunto, buscar repetidos, incorporar elementos nuevos y otros. Comenzamos por la fila 7, que es donde comienzan nuestros conjuntos y después se va bajando de fila hasta que no queden elementos.

Por ejemplo, la siguiente función ESTA nos devuelve True si un valor n pertenece al conjunto situado en la cierta columna

Public Function esta(n, columna) As Boolean
Dim fila
Dim est As Boolean

est = False
fila = 7
While Not IsEmpty(Cells(fila, columna)) And Not est
If n = Cells(fila, columna).Value Then est = True
fila = fila + 1
Wend
esta = est
End Function

Es fácil identificar la estructura del recorrido por el conjunto. Esta función ESTA nos servirá para saber si podemos agregar un elemento nuevo a un conjunto mediante el procedimiento  AGREGA, que servirá para ir incorporando términos a la unión y a la intersección.

Sub agrega(n, columna)
Dim i

i = 7
While Not IsEmpty(Cells(i, columna))
i = i + 1
Wend
If Not esta(n, columna) Then Cells(i, columna).Value = n
End Sub

Recorre el conjunto, y si no encuentra el elemento dado, baja una fila y lo incorpora.
Con los procedimientos de recorrido y agregación y la función ESTA podemos ya planificar nuestra tarea:


  • Se elige el primer conjunto
  • Se recorre, y para cada elemento:
  • (A) Si no está en la unión, se agrega (así evitamos repetidos)
  • (B) Se compara con todos los elementos del segundo (mediante un recorrido por el mismo) y si está repetido, se incorpora a la intersección si todavía no está.
  • Se repite la tarea con el segundo conjunto, pero esta vez no se busca la intersección, que ya estará resuelta.

Para entender el listado que sigue recuerda que los conjuntos están escritos en las columnas  tercera y cuarta, que la unión se escribe en la quinta y la intersección en la sexta.

Así quedaría:

Option Explicit  ‘Evita el uso de variables no dimensionadas

Public Function esta(n, columna) As Boolean ‘ Ya explicada. Determina si un elemento pertenece a un conjunto
Dim fila
Dim est As Boolean

est = False
fila = 7

While Not IsEmpty(Cells(fila, columna)) And Not est
If n = Cells(fila, columna).Value Then est = True
fila = fila + 1
Wend
esta = est
End Function

Sub agrega(n, columna) ‘También explicada: añade un elemento si aún no está
Dim i

i = 7
While Not IsEmpty(Cells(i, columna))
i = i + 1
Wend
If Not esta(n, columna) Then Cells(i, columna).Value = n
End Sub


Sub union() ‘Esquema general de trabajo. Se inicia al pulsar el botón “Operación”
Dim i, j, n1, n2
Dim esinter As Boolean

i = 7
Call borrar ‘Macro grabada aparte
While Not IsEmpty(Cells(i, 3)) ‘Recorre el primer conjunto


'Se recorre la primera columna
n1 = Cells(i, 3).Value
Call agrega(n1, 5) ‘Agrega el elemento a la unión

'se busca la intersección
j = 7
esinter = False
While Not IsEmpty(Cells(j, 4)) And Not esinter ‘Se recorre el segundo conjunto
n2 = Cells(j, 4).Value
If n1 = n2 Then esinter = True
j = j + 1
Wend
If esinter Then Call agrega(n1, 6) ‘Si está repetido se agrega a la intersección
i = i + 1
Wend
i = 7
While Not IsEmpty(Cells(i, 4))
'Se recorre la segunda columna y se repite el agregar a la unión.
n1 = Cells(i, 4).Value
Call agrega(n1, 5)
i = i + 1
Wend
End Sub

Si lo has entendido, intenta programar la diferencia entre dos conjuntos, los elementos que pertenecen a uno pero no al otro. Puedes repasar la hoja alojada en (http://www.hojamat.es/blog/union de conjuntos.xlsm) y modificarla libremente.

lunes, 13 de octubre de 2014

Propiedades de los restos cuadráticos


Usaremos en los desarrollos el símbolo de Legendre ya explicado en la entrada anterior, Recuerda que la actual entrada es parte de un ciclo de tres.

El criterio de Euler da lugar a propiedades interesantes de los restos cuadráticos respecto a ciertos tipos de primos. Los vemos:

 -1 es un resto para todos los primos del tipo 4N+1 y no resto para los del tipo 4n+3

Es una consecuencia del criterio de Euler, pues (p-1)/2 sería par en el primer caso, e impar en el segundo, luego al elevar -1 a esa cantidad producirá un 1 (ser resto) para p=4N+1 y -1 (no resto) en el otro caso.

Esto quiere decir que la ecuación x2 + 1 º 0 (mod p) tiene solución para p=4N+1 y no la tiene en el segundo caso. Podemos expresarlo también como que 1 posee una raíz cuadrada entre las clases de restos módulo p

Podemos diseñar un pequeño esquema con la hoja de cálculo que usamos en esta serie:


 En la celda del 11 hemos escrito =RESTOCUAD(-1;61). Como este módulo es del tipo 4N+1, obtenemos la solución 11, ya que 11*11 módulo 61 es igual a 60, es decir, la clase de restos -1
Si hubiéramos usado módulo 11, que es del tipo 4N+3. Obtendríamos un cero, que es la señal de que -1 no es resto cuadrático:


Esta propiedad se puede expresar así:

2 es resto cuadrático para todos los primos del tipo 8N+1 y 8N+7, y no resto para los demás

También podemos, en nuestra hoja de cálculo, crear un esquema para comprobar esta propiedad siguiendo la estructura que usamos en la anterior.


Vemos que 11 no pertenece al tipo 8N+1 ni al 8N+7, y para el 2 no devuelve raíz cuadrada (el cero es una señal)

Sin embargo, al usar el módulo 31, que es del tipo 8N+7, el 2 presenta raíz cuadrada 8, y es resto cuadrático.


No es sencilla la demostración. Tienes una en Fundamentos de la Teoría de los números de Vinogradov.

Encontrarás propiedades similares para el -3 y el 5 en el documento de Rafael Parra “Restos cuadráticos y Ley de reciprocidad cuadrática”(http://www.hojamat.es/parra/restocuad.pdf). Las puedes comprobar con el esquema propuesto, sustituyendo el 2 por otros valores.

Ley de reciprocidad cuadrática

La propiedad más importante de estos restos es la ley de reciprocidad cuadrática, enunciada y demostrada por Gauss en 1801 en su libro Disquisitones Arithmeticae. Con palabras la podemos expresar así:

Dados dos primos impares p y q, si ambos pertenecen al tipo 4k+3, entonces p es resto cuadrático módulo q si y sólo si q no lo es de p. Si alguno de los primos pertenece al tipo 4k+1 entonces o bien ambos son restos uno del otro, o bien ninguno lo es.

Expresada así o de forma similar la propiedad resulta oscura. Sin embargo su significado queda claro con el uso de los símbolos de Legendre. En ese caso la propiedad se reduce a esta identidad:

Así se explica mejor: Si uno de los dos, p o q, es del tipo 4k+1, el exponente del -1 será par y el segundo miembro valdrá 1, con los que los símbolos del primero serán ambos iguales a 1 (restos recíprocos) o bien -1 (ninguno es resto).

Si ambos son del tipo 4k+3 el exponente será impar, el segundo miembro -1 y los símbolos tendrán signo opuesto: Si uno de los primos es resto del otro, no se dará la reciprocidad.

En textos y documentos varios dispones de ejercicios sencillos que muestran la utilidad de esta propiedad. Nosotros la hemos incluido en nuestra hoja de cálculo (http://www.hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm#restocuad)

Al escribir los dos primos la hoja analiza si son del tipo 4N+3 o 4N+1, calcula después los restos y comprueba la propiedad.



Como se trabaja con valores 1 y -1, algunos manuales expresan esta propiedad mediante esta otra identidad equivalente:



Así se ve mejor cómo calcular un valor de (p/q) si se conoce el de (q/p). Como hemos afirmado más arriba, no entra dentro de los objetivos de esta entrada pasar a ese tipo de cálculos.


lunes, 29 de septiembre de 2014

Restos cuadráticos - Criterio de Euler


En la entrada anterior iniciamos el estudio de los restos cuadráticos respecto a un módulo. Descubrimos un procedimiento algo lento para encontrar los restos y los no restos. En esta otra entrada simplificaremos algo el proceso y aprenderemos nuevos conceptos. Se aconseja leer previamente dicha entrada.

El recorrer todos los restos desde 1 hasta (p-1)/2 puede hacerse muy pesado en el caso de valores muy grandes. Euler descubrió un criterio que nos ayuda a distinguir los restos de los no restos con un solo cálculo. Es este:

Si a es un resto cuadrático respecto a p (primo e impar) se cumple
Y si no lo es
Es una consecuencia del Teorema de Fermat:



Luego, como p-1 es par, podemos escribir


De esta congruencia deducimos que uno de los paréntesis es congruente con cero, pero ambos no pueden serlo, porque entonces su diferencia, 2, cumpliría 2º0 y eso es imposible para p primo impar.

De hecho, si a es resto cuadrático, el que se cumple es el segundo, ya que si existe un x tal que x2ºa (mod p) entonces a(p-1)/2ºxp-1º1 (mod p) de nuevo por el Teorema de Fermat.

Como sólo se puede cumplir una congruencia, si a  es no resto cuadrático, cumplirá la otra, con el -1.

Este criterio es bastante directo, para saber si un valor es resto cuadrático. Por ejemplo, ¿Es el 14 resto cuadrático respecto al 23?

14(23-1)/2=1411 Calculamos el resto de este último por potencias sucesivas: 141º14 (mod 23), 142º12 (mod 23) 144º12*12º6 (mod 23) 148º6*6º13 (mod 23), luego 1411º13*12*14º-1 (mod 23), luego no es resto cuadrático.

La herramienta de hoja de cálculo que proponemos, en su tercera hoja, te realiza los cálculos la aplicación de este criterio:



Es conveniente que lo intentes sin hoja de cálculo para practicar. Puedes usar la exponenciación modular (http://hojaynumeros.blogspot.com.es/2012/03/de-la-multiplicacion-rusa-la.html). La usaremos en el siguiente ejemplo:

¿Es resto cuadrático el número 70 respecto al módulo 101?

El módulo 101 es primo e impar, luego podemos usar el criterio de Euler. Bastará elevar 70 a (101-1)/2=50.

Sabemos que 50=32+16+2, luego vamos calculando: 701º-31 (mod 101), : 702º31*31º-49 (mod 101), 704º49*49º-23 (mod 101), 708º23*23º24 (mod 101), 7016º24*24º-30 (mod 101), 7032º30*30º-9 (mod 101), y ahora construimos el 50:

7050º70327016702º-9*30*49º1 (mod 101), luego según el criterio, 70 sí es resto cuadrático. Si lo compruebas con la herramienta que proponemos descubrirás que su raíz cuadrada es 26.

La aplicación de este criterio nos lleva a propiedades muy interesantes.

La primera es tan elemental que no tenemos que justificarla:

El producto de dos restos o de dos no-restos siempre da un resto, y el de resto con no resto produce un no-resto. Es decir, poseen estructura alternada, por lo que es fácil representar los restos mediante el signo + y los no restos con el -, y así poder usar la regla de los signos. Se razona fácilmente a partir del criterio de Euler.

Consecuencia inmediata:

El conjunto de restos cuadráticos forma un grupo multiplicativo en Zp

Por ejemplo, si m=11, los restos son 1, 3, 4, 5 y 9 y los no restos 2, 6,7, 8 y 10 (o bien -1, -3, -4, -5 y -9). Los restos forman un grupo, como se puede verificar fácilmente.

En la segunda hoja de la herramienta que ofrecemos dispones de una calculadora para comprobar las afirmaciones anteriores.



En particular puedes estudiar que si llamamos C al grupo de los restos cuadráticos, las clases laterales tipo a*C tienen cardinal (p-1)/2 y que por tanto el índice de C respecto a Zp es 2. Vemos una de esas clases. Multiplica el elemento 6 de Z11, por todos los elementos de C, en este caso 1, 3, 4, 5, 9: 6*1º6 (mod 11), 6*3º7 (mod 11), 6*4º2 (mod 11), 6*5º8 (mod 11), 6*9º10 (mod 11). Han resultado valores distintos, luego el cardinal de 6*C es (11-1)/2=5

Símbolo de Legendre

Esta estructura como grupo multiplicativo se expresa muy bien mediante el símbolo de Legendre (por comodidad tipográfica lo escribiremos como (m/p), con los dos números en línea, como hace Apostol).

Llamamos Símbolo de Legendre a una función que asigna a cada par de valores m y p, este último primo e impar, los siguientes valores:

(m/p)=1 si m es resto cuadrático respecto a p
(m/p)=-1 si m es no-resto cuadrático respecto a p
(m/p)=0 en el caso particular en el que m sea múltiplo de p.

En realidad, si recordamos el criterio de Euler, podemos usar una fórmula directa para encontrar el valor de un símbolo de Legendre:
Según lo explicado anteriormente, es fácil ver que esta función es multiplicativa:


Esto tiene una consecuencia práctica, y es que se pueden eliminar cuadrados al calcular el símbolo de un número compuesto.

Nótese que el valor del símbolo de Legendre es una propiedad de las clases de restos y no de los números concretos, por lo que es fácil entender que si aºb (mod p). entonces (a/p)=(b(p)

martes, 16 de septiembre de 2014

Restos cuadráticos

En esta entrada y otras posteriores trataremos el tema de las congruencias de segundo grado. Usaremos como siempre las hojas de cálculo, y, en especial una herramienta que hemos creado para este fin. Todo el tema gira alrededor de la ecuación

 

Imagina una clase de restos, por ejemplo la correspondiente a módulo 7, {0, 1, 2, 3, 4, 5, 6} Elige un resto, sea el 5. ¿Existirá otro resto que multiplicado por sí mismo dé como resultado 5, módulo 7? Probemos: 1*1º1, 2*2º4, 3*3º2, 4*4º2, 5*5º4, 6*6º1. Así que no es posible, los únicos resultados  son 1, 4 y 2. Nunca resulta un 5, ni tampoco 3 ni 6.

Podemos resumir esta situación calificando 1, 2 y 4 como “restos cuadráticos” y 3, 5 y 6 como “no restos cuadráticos”. También podemos hablar de la “raíz cuadrada” de los primeros: 12=1, 32=2 y 22=4. Es fácil ver que si k es raíz de n, también lo es m-k. Eleva esta última al cuadrado y lo comprobarás.

Esta situación la tendrás siempre. Unos elementos podrán ser restos cuadráticos y otros no. El primer intento que hemos hecho para averiguarlo ha sido el probar los elementos uno a uno hasta conseguir que el cuadrado de uno de ellos coincida con el resto dado, o bien comprobar que esto es imposible y que se trata de un “no resto cuadrado”.

Para estudiar el tema con profundidad puedes acudir a

http://hojamat.es/parra/restocuad.pdf
http://mate.dm.uba.ar/~pdenapo/teoria_analitica_de_numeros/clase11.pdf
http://en.wikipedia.org/wiki/Quadratic_residue

Diremos que a es resto cuadrático módulo p, coprimo con él, cuando exista una solución a la ecuación



Con hoja de cálculo (o con ligeras variaciones, en cualquier lenguaje de programación) podemos automatizar este procedimiento. Definiremos una función, que dependa de un resto dado y del módulo correspondiente, que nos devuelva la raíz cuadrada, con lo que sabremos que es resto cuadrático, o bien un cero si no lo es.

Public Function restocuad(n,modu) ‘los parámetros son el resto y el módulo
Dim k, r,s
Dim es As Boolean

es = False ‘ nos indica que aún no se ha encontrado una raíz
k = 1 ‘contador que busca la raíz
r = 0 ‘raíz encontrada
While k <= modu / 2 And Not es ‘va buscando las posibles raíces
s=(n-k*k)/modu
If s=int(s) Then es = True: r = k ‘se ha encontrado la raíz
k = k + 1 ’seguimos buscando
Wend
If es Then restocuad = r Else restocuad = 0 ‘devuelve un cero si no se ha encontrado
End Function

Con esta función implementada, puedes analizar qué restos son cuadráticos, formar tablas de restos y no restos y resolver la ecuación x2ºa, o, con los cambios adecuados, la ecuación general de segundo grado. Lo vemos con un ejemplo:

Resolver x2-26x+10º7 (mod 11)

Damos estos pasos:

x2-26x+10 º (x-13)2-159 º 7 (mod 11)
(x-13)2º166 (mod 11)
(x-13)2º1 (mod 11)

Buscamos la raíz cuadrada de 1 y resulta ser 1 o -1 (o 10) es decir:

(x-13)º1 o 10 (mod 11)

Despejando: x=3 y x=1

Comprobamos: 32-26*3+10=-59 º-4 º 7 (mod 11) y 12-26*1+10=-15 º-4 ?º7 (mod 11)

Hemos elegido un ejemplo que tenía solución, pero si llega a aparecer un no resto en lugar de 1, no podríamos seguir. Por eso es tan importante saber previamente si un resto es cuadrático o no.

Caso de módulo primo e impar

En este caso, si consultas la teoría descubrirás que si p es el módulo primo e impar resulta que el número de restos cuadráticos es (p-1)/2, que son congruentes con 12, 22, 32,…,((p-1)/2)2 y por tanto, este también es el número de no-restos.

Previamente estudia esta propiedad:

La ecuación x2º a (mod p) para un a dado, o no tiene solución, o tiene dos.

En efecto, si tiene una solución x1 con x12º a (mod p)  también será solución –x1 y sólo tenemos que demostrar que ambas son distintas. Es fácil: si fueran iguales tendríamos que 2x1=0, pero ni 2 ni x1 son divisores del cero, por ser p primo impar. La segunda solución la puedes expresar como p-x1

Por tanto, el número de restos cuadráticos no sobrepasará (p-1)/2. Es más, es igual que ese número, porque los restos de 12, 22, 32,…,((p-1)/2)no se repiten , ya que una igualdad entre ellos haría que la ecuación  x2º a (mod p) tuviera cuatro soluciones en lugar de dos.

Esta propiedad te ofrece un procedimiento para encontrar todos los restos cuadráticos en este caso, y es calcular los valores de  12, 22, 32,…,((p-1)/2)y los resultados serán los restos cuadráticos, y los demás será no restos.

Hemos preparado una herramienta en  hoja de cálculo

 (ver http://www.hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm#restoscuad),

cuya primera prestación es la de encontrar el conjunto de restos y no restos para un módulo primo e impar. En ella está implementado el procedimiento de ir calculando los valores de .12, 22, 32,…,((p-1)/2) La novedad de este esquema es que va situando los restos en una columna y los no restos en otra.



En la imagen figuran los 15 restos módulo 31, sus raíces, y los 15 no restos. Para ver cómo lo logra tendrías que acceder al Basic, pero no lo analizaremos en este momento.

Su funcionamiento en esta parte es muy simple: escribes el nuevo módulo,  y después pulsas el botón de Restos y no restos  para que aparezcan.

Puedes alternar tus cálculos manuales con los de la hoja para entenderlo todo mejor y comprobar resultados.

En la siguiente entrada simplificaremos los cálculos necesarios para saber si un resto es cuadrático o no mediante un criterio debido a Euler.

martes, 2 de septiembre de 2014

Nueva temporada 2014-15


Iniciamos hoy nuestra séptima temporada (o curso) con el anuncio de un nuevo resumen anual de este blog. Lo hemos alojado en 


En la anterior temporada iniciamos dos temas que continuaremos en la presente: comprobaciones de conjeturas y estudio de sucesiones recurrentes. También se publicó un capítulo sobre permutaciones y ciclos, que por ahora consideramos terminado.

Nuestro propósito para la nueva temporada, además de la continuación de los temas citados y de la atención a cuestiones ocasionales y de actualidad, es el de publicar entradas sobre el tema de los restos cuadráticos, con lo que, poco a poco, iremos completando temas teóricos.

En los dos primeros meses, por tener que atender a otras cuestiones personales, nuestras entradas aparecerán con intervalos de unos quince días, en lugar de los diez habituales. Quizás para diciembre recuperaremos la periodicidad acostumbrada, aunque ese mes el autor cumple 73 años y su ritmo de creación va disminuyendo forzosamente.

lunes, 7 de julio de 2014

Distancia de Hamming entre números de igual tipo

(Con esta entrada despedimos el curso 2013-14. En septiembre volovemos)

Hamming definió su distancia para palabra binarias como el número total de bit en los que ambas se diferencian, comparando, como es de esperar cada uno con el que ocupa el mismo lugar en la otra palabra. Así, la distancia de Hamming entre 11001011 y 11100011 es de 2, porque son diferentes entre sí los dígitos resaltados en negrita.

Es fácil extender esta definición a cadenas de caracteres o a las cifras de un número. Así, la distancia entre estos números de móvil 656232110 y 636182170 es de 4, que son las cifras en las que difieren. Con esta definición nos podíamos preguntar cómo se relacionan entre sí números del mismo tipo: primos con primos o cuadrados con cuadrados. La idea viene a cuento porque esperamos que en los primos abunden las cifras impares, o que en los cuadrados aparezcan 1, 4, 9, 6 o 5, o que en los triangulares o de Fibonacci se distribuyan uniformemente. Como siempre advertimos, hay que decir que esto sólo es una curiosidad sin valor matemático.

Para ello hemos construido la función hamming(a,b) (para el Basic de las hojas de cálculo), que cuenta las cifras diferentes existentes entre dos números. Hemos previsto el valor -1 como valor de error. Para aquellos que no tengan el mismo número de cifras, las de uno que no están en el otro se cuentan como diferencias. Su listado es el siguiente, aunque no lo explicaremos, ya que contiene varias funciones predefinidas:

Public Function hamming(a, b) 'devuelve -1 si algo va mal. Cuenta las diferencias entre cifras. Si uno es más largo que el otro cuenta los huecos también

Dim h, i, n, m

h = -1
If esentero(a) And esentero(b) Then
n = numcifras(a)
m = numcifras(b)
h = 0
If n > m Then h = n - m: n = m
For i = 1 To m
If cifra(a, i) <> cifra(b, i) Then h = h + 1
Next i
End If
hamming = h
End Function

Con esta función analizaremos qué números presentan más o menos diferencias con sus compañeros de tipo. Para no complicar la tarea, que al fin y al cabo es lúdica, nos limitaremos a comparar aquellos que tengan el mismo número de cifras. Comenzamos:

Distancias entre primos

Comenzamos con los de dos cifras. El valor de la función sólo podrá ser 1 o 2, porque el 0 indicaría igualdad. Comparamos cada primo de dos cifras con todos los demás, tomando nota de la distancia existente entre ellos. Nos ha resultado esta tabla:


En ella hemos reflejado las distancias de cada uno de los 21 primos de 2 cifras respecto a sus compañeros. En la segunda columna contamos las distancias de Hamming que valen 1 y en la siguiente las de 2. En la última columna se ha calculado la media ponderada de las distancias. Viendo las columnas se destaca que son mucho más abundantes las diferencias h=2.

Es fácil ver que el 97 es el primo que más diferencias presenta, el que está más alejado en cifras de los demás. En total 36 diferencias (4+2*16). Por el contrario, para el 13 hay 32, (8+2*12). Para comparar este colectivo con otros, hemos sumado todas las diferencias, con un resultado de 716 y una media de 34,095.

Primos de tres cifras

Como aquí aparecerán más resultados, usaremos un filtro para presentarlos. Los primeros valores de los 143 totales son:



Mediante ordenaciones y filtros en la hoja de cálculo descubrimos lo siguiente:

El primo más cercano a sus compañeros es el 157. Ha sido una sorpresa, pues no pensamos en él. Es curioso que los seis siguientes en la lista terminen en 7. Estos son los que tienen las cifras menos destacadas.




En el extremo opuesto, de los que presentan más diferencias han resultado números terminados en 9. A ver quién aclara esto (¿pura casualidad o hay algo detrás?)



Hay un triple empate entre 719, 919 y 929. Los tres se encuentran a una distancia media de los demás igual a 61,5, o una suma de diferencias de 369.

La suma de todas las diferencias es 51842, con un promedio de 362,5

Primos de cuatro cifras

Los más afines en cifras son



Y los más alejados



Con esta idea nos quedamos. El total de diferencias es de 3870022 con una media de 3647,5

Resumiendo, el resultado global es



En la última columna dividimos de nuevo ente los elementos, ya que su número influye en las distancias medias (hay más con los que comparar)

Estas medidas nos servirán para comparar la homogeneidad de las cifras ordenadas respecto a otros colectivos. Veremos ahora los cuadrados, triangulares y cualquier otro colectivo que nos llame la atención.

Distancias entre cuadrados

Los cuadrados son menos abundantes. En concreto, para dos cifras solo existen 6. Llama la atención en la tabla resumen que sólo un par (16 y 36) presenta una distancia de 1, mientras el resto se diferencia totalmente de los demás.



Las diferencias son muy uniformes. Los más afines son los ya destacados 16 y 36

Cuadrados de tres cifras

Aparecen 22 cuadrados. Los que tienen cifras más parecidas a sus compañeros son estos:



También es una sorpresa que el 121 comparta más dígitos que ningún otro. La clave está en los 13 con los que se diferencia en dos cifras.

Los que más se alejan:



Se ve que el 6 no es una terminación tan popular como creíamos.

Con cuatro cifras

Resultan 68 cuadrados. Los ordenamos como en los casos anteriores. Vemos los que presentan menos diferencias con los demás tienen todos una cifra 0


También es sorprendente que el mínimo caiga precisamente en 1024, el elemento más pequeño del conjunto.

Los que más se alejan terminan todos en 6. Otra casualidad.



Resumen




Distancias entre triangulares

Sólo damos los resultados más llamativos

Triangulares más afines: De dos cifras, el 15, de tres el 120 y de cuatro hay dos, el 1275 y el 1770
Triangulares más diferentes: Hay cinco de dos cifras: 10, 36, 66, 78 y 91. De tres cifras 378 y 528. De cuatro el 6903

No seguimos. No parece que el tipo de número influya mucho en los resultados si corregimos los totales según el número de elementos. Puede más la falsa aleatoriedad que produce la repetición que las diferencias del tipo de cifras.

domingo, 29 de junio de 2014

Suma de dos números primos consecutivos (2)


En la anterior entrada vimos algunos hechos que ocurren al sumar dos números primos consecutivos. Hoy terminamos con un catálogo de resultados que puede presentar esa suma.

La suma es cuadrado

En http://oeis.org/A061275 se recogen los casos en los que la suma de dos primos consecutivos da un cuadrado:

17, 47, 71, 283, 881, 1151, 1913, 2591,… (primer primo del par)

Por ejemplo, 17+19=36=62. Igualmente 47+53=100=102, 71+73=144=122

El cuadrado será par, y por tanto un múltiplo de 4. Si un elemento del par de primos es del tipo 4n+1, el otro deberá ser de la clase 4n+3, para que no resulte un múltiplo de 2 que no lo sea de 4, y así impida que resulte un cuadrado. Como los primeros se pueden descomponer en sumas de cuadrados, un elemento del par tendrá siempre la forma A2-B2-C2. Por ejemplo, en el par (103049, 103067), 103067=4542-1572-2802.

Suma triangular

Están contenidos en https://oeis.org/A225077:

17, 37, 59, 103, 137, 149, 313, 467, 491, 883, 911, 1277, 1423, 1619, 1783, 2137, 2473, 2729, 4127, 4933, 5437, 5507, 6043, 6359, 10039, 10453, 11717,…

Así, el par de primos gemelos (2087,2089) tiene como suma 41616=288*289/2, que es el triangular número 288.

Suma doble de un cuadrado

Este caso es interesante porque en ellos la media aritmética de los dos primos consecutivos sería un cuadrado. Así ocurre con 1087 y 1091, cuyo promedio es 1089, el cuadrado de 33.
En ese caso un primo es n2-k y el otro n2+k. Si k=1 tendríamos un par de primos gemelos. Sólo hemos encontrado el par (3,5), cuya media es el cuadrado de 2. No puede haber más, porque para que n2-1 sea primo, ha de ser n-1=1 y eso sólo ocurre en n=2 y el par (3,5).

Los términos de esta sucesión son

 3, 7, 61, 79, 139, 223, 317, 439, 619, 1087, 1669, 2593, 3593, 4093, 5179, 6079, 8461, 12541, 13687, 16633, 19037, 19597, 25261, 27211, 28219, 29581, 36857, 38011, 39199, 45361, 46649, 47521, 51977, 56167… https://oeis.org/A225195

Forman una subsucesión de http://oeis.org/A053001, que contiene los números primos mayores que son anteriores a un cuadrado. Los que estudiamos aquí cumplen esa condición, porque al ser el cuadrado la media entre dos primos consecutivos, el menor de ellos tendrá la propiedad pedida en A053001.

Otros casos

La suma puede ser una potencia perfecta:

3, 17, 47, 61, 71, 107, 283, 881, 1151, 1913, 2591, 3527, 4049, 4093, 6047, 7193, 7433…

https://oeis.org/A091624

Como casos particulares están publicados los cuadrados (http://oeis.org/A061275) y los cubos(https://oeis.org/A061308)

O el doble de una potencia perfecta:

3, 7, 61, 79, 139, 223, 317, 439, 619, 1087, 1669, 1723, 2593, 3593, 4093, 5179, 6079, 8461, 12541, 13687, 16633, 17573, 19037, 19597,…

En este caso la media de los dos primos será una potencia perfecta, y ambos se pueden representar por km-h y km+h, con k y h coprimos y no siendo h una potencia de exponente m (¿por qué?)

No es difícil encontrarlos. Con esta línea de PARI lo consigues.

{forprime(i=3,10^6,k=(i+nextprime(i+1))/2;if(ispower(k),print(i,", ")))}

(La hemos publicado en https://oeis.org/A242380)

Un caso particular interesante es cuando la media es un cubo. Los primos consecutivos serían del tipo k3-h y k3+h, con k y h coprimos y no siendo h un cubo. De esto también se deduce que un elemento de la sucesión es el mayor primo anterior a un cubo, y que por tanto pertenece también a la secuencia http://oeis.org/A077037

Son estos:

61, 1723, 4093, 17573, 21943, 46649, 110587, 195103, 287491, 314423, 405221, 474547, 1061189, 1191013, 1404919, 1601609, 1906621, 2000371, 2146687, 2196979, 3241783, 3511799, 4912991, 5268017, 6229501, 6751267, 6858997, 7077883, 11239421, 20346407, 21951997, 26198063,…

Los puedes reproducir con PARI

{for(i=3,3*10^7,if(isprime(i),k=(i+nextprime(i+1))/2;if(ispower(k,3),print(i,", "))))}

(publicados desde este blog en https://oeis.org/A242382)

En realidad se pueden probar otros casos por puro entretenimiento, y después incorporarlos a OEIS para que queden en esa extensa base de datos. Pueden ser estos:

Media oblonga

Se conocen ya los primos consecutivos cuya suma es un número oblongo (del tipo n(n+1) o bien doble de un triangular). Están contenidos en http://oeis.org/A154634. Los que aportamos desde este blog son aquellos cuya media es oblonga:

5, 11, 29, 41, 53, 71, 239, 337, 419, 461, 503, 547, 599, 647, 863, 1051, 1187, 1481, 1721, 1801, 2549, 2647, 2969, 3539, 4421, 6317, 7129, 8009, 10301, 12653, 13567, 14033, 17291, 18353, 19181, 19457, 20021, 22943, 23561, 24179, 27059, 29063, 29753, 31151, 33301…
(https://oeis.org/A242383)

Una propiedad curiosa es que están contenidos en http://oeis.org/A161550. La razón es que si un número primo pertenece a la sucesión que presentamos, en la que su media con el próximo primo es un oblongo del tipo n(n+1)=n2+n, es claro que será el máximo primo inferior a n2+n, que es la definición de A161550. Por el contrario, un término de esta sucesión no tiene que cumplir nuestra condición. Así, el 19 es el máximo primo inferior a 42+4=20, pero su media con el siguiente primo no es 20: (19+23)/2=21.

Los puedes encontrar con PARI:

{for(i=3,10^5,if(isprime(i),k=(i+nextprime(i+1))/4;if(issquare(8*k+1),print1(i,", "))))}

En el código se buscan pares de primos cuya suma dividida entre 4 produzca un triangular. Es otra forma de definirlos.

Suma del tipo n(n+2)

Estos números del tipo n(n+2) se pueden expresar también como (n+1)2-1. Salvo el caso n=1 ninguno puede ser primo. No es muy frecuente el que dos primos consecutivos produzcan este tipo de número. Los primeros son estos:

3, 11, 59, 139, 179, 311, 419, 541, 919, 1399, 1621, 2111, 3119, 5099, 6379, 8059, 8839, 9377, 15661, 16007, 16741, 17107, 21011, 21839, 23539, 24419, 28081, 30011, 31489, 33533, 35617, 37811, 39461, 41759, 44699, 45293, 60899, 68819, 71059, 78007, 83639, 84457, 86111, 87767, 92867, 99901,…(https://oeis.org/A242384)

Según el párrafo anterior se pueden ir sumando los pares de números primos consecutivos, sean p y q, y exigir que p+q+1 sea un cuadrado. Así los hemos encontrado con hoja de cálculo y con PARI:

{k=2;while(k<10^5,l=nextprime(k+1);if(issquare(k+l+1),print1(k,", "));k=l)}

Si efectuamos las sumas entre los pares de números consecutivos encontrados, es evidente que n(n+2) será par, luego n también lo será. Si elegimos un número primo de la sucesión, por ejemplo el 2111, su próximo primo será 2113, y su suma 4224 es igual a 64(64+2), con n=64, par.

Media del tipo n(n+2)

Es un caso similar al anterior, pero con cambios importantes. Los primeros primos que cumplen esto son:

13, 97, 113, 193, 283, 397, 479, 673, 953, 1439, 1597, 2297, 2699, 3469, 4219, 4483, 5323, 7219, 8273, 9209, 9403, 10799, 12097, 13219, 14879, 15373, 15619, 21313, 23399, 26237, 27883, 32029, 32749, 34217, 37243, 39989, 41203, 42433, 43669, 46219, 55219, 60509, 62497, 72353, 75619, 93001,…(https://oeis.org/A242385)

El código para encontrarlos es

PARI: {k=2;while(k<10^5,l=nextprime(k+1);if(issquare((k+l)/2+1),print1(k,", "));k=l)}

En ellos la media de los dos consecutivos incrementada en una unidad se convierte en un cuadrado. Por ejemplo, el primo consecutivo a 9209 es 9221. Su media 9215 y si le sumamos una unidad resulta 9216=962

Por último, capicúas

Terminamos con dos ejemplos más. El primero recoge los pares de primos cuya suma es capicúa (incluidos los de una cifra):


2, 3, 109, 211, 347, 409, 1051, 1493, 2111, 2273, 3167, 4219, 4441, 10099, 10853, 10903, 11353, 11909, 12823, 12973, 13421, 13831, 14543, 14639, 20551, 21011, 21347, 21661, 21863, 22271, 23581, 23981, 30047, 30557, 31259, 31307, 31963, 32069, 32213, 32467, 32869, …

Encontrarlos con PARI es algo más complicado: la función palind devuelve VERDADERO si el número es igual a su simétrico en cifras. El resto es fácil de entender:


palind(n)=Str(n)==concat(Vecrev(Str(n)))
{p=2;while(k<10^5,q=nextprime(p+q);if(palind(p+q),print1(p,", "));p=q)}

Los tienes en (https://oeis.org/A242386)


Con media capicúa

Con una codificación similar se pueden encontrar aquellos primos consecutivos cuya media es capicúa:

3, 5, 7. 97, 109, 281, 359, 389, 409, 509, 631, 653, 691, 743, 827, 857, 907, 937, 967, 1549, 2111, 2767, 4219, 4441, 7001, 9007, 9337, 9661, 10099, 11503, 12919, 13421, 16759, 17569, 21011, 21611, 23831, 26261, 26861, 28181, 29287, 29483, 30497, 31307, 32213, 33029, 33629

palind(n)=Str(n)==concat(Vecrev(Str(n)))
{k=2;while(k<10^5,l=nextprime(k+1);if(palind(k+l),print1(k,", "));k=l)}

(https://oeis.org/A242387)