Sucesión de Perrin

En la pasada temporada dedicamos varias entradas a las sucesiones definidas mediante una recurrencia de segundo orden. Ahora comenzaremos una serie sobre las de tercer orden. Entre ellas son muy populares las de Perrin y Padovan. Como en las anteriores, nuestro planteamiento no será teórico, pues ya existe mucho publicado sobre ellas. El objetivo será crear esquemas y cálculos que faciliten  la comprensión de sus propiedades.

Sucesión de Perrin

La teoría fundamental sobre esta serie la puedes consultar en

http://mathworld.wolfram.com/PerrinSequence.html
http://en.wikipedia.org/wiki/Perrin_number

Aquí la describiremos con la ayuda de la herramienta que hemos ofrecido en entradas anteriores, alojada en

http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2

Definición

Esta sucesión es recursiva de tercer orden homogénea, por lo que necesita tres valores iniciales y que X(n) dependa de los tres valores anteriores X(n-1), X(n-2) y X(n-3) mediante la relación

X_n= A*X_n-1+B*X_n-2+C*X_n-3

En este caso particular sólo depende de los dos últimos, y no de X(n-1). Concretando:

Condiciones iniciales: X₀=3   X₁=0  X₂=2 Ecuación de recurrencia: X_n= X_n-2+X_n-3

Es como una sucesión del tipo Fibonacci pero “con retraso”, pues los que se suman no son los dos anteriores, sino los que están un paso más atrás.

En nuestra hoja de cálculo se define así (segunda hoja del libro):

El primer coeficiente es nulo, que es lo que produce el “retraso”, y debajo tienes los tres valores iniciales.

La sucesión resultante la vemos pulsando el botón correspondiente:

Esta popular sucesión la tienes disponible en http://oeis.org/A001608, donde les llaman números skiponacci, quizás por los saltos o retardos que presentan: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367, 486, 644, 853,…

Ecuación característica

La ecuación característica correspondiente será X³-x-1=0. Con el botón Resolver de esa hoja obtienes las tres soluciones de la ecuación, una real y dos complejas

Coinciden con las soluciones que da WxMaxima

La solución real 1,32471…(aquí sólo aproximada) es el número plástico y, cuyo nombre se eligió como afín al número de oro o el de plata. En estas páginas puedes estudiarlo más a fondo:

http://es.wikipedia.org/wiki/N%C3%BAmero_pl%C3%A1stico
http://revistasuma.es/IMG/pdf/57/055-064.pdf http://cscmates.blogspot.com.es/2010/11/el-numero-de-plastico.html

Recordemos que, como en sucesiones anteriores, todo número de Perrin es combinación lineal de las potencias de las tres soluciones de la ecuación característica, pero las dos complejas tienen módulo menor que la unidad, por lo que sus potencias tenderán a cero en valor absoluto. Por tanto, X(n) se acercará asintóticamente a yⁿ

Se puede construir una tabla doble en la que se observe este acercamiento:

A partir de un cierto orden basta redondear la potencia para obtener el número de Perrin  correspondiente. Lo puedes comprobar en las últimas filas de la tabla.

Función generatriz

Usando procedimientos similares a los que explicamos para las recurrentes de segundo orden, se puede demostrar que la función generatriz es

Puedes comprobar que esta es la F.G. adecuada efectuando este desarrollo en PARI

write("sucesion.txt",taylor((3-x^2)/(1-x^2-x^3),x,20))

Te escribirá en un archivo sucesión.txt su desarrollo, y aparecerán como coeficientes los términos de la sucesión de Perrin:

3 + 2*x^2 + 3*x^3 + 2*x^4 + 5*x^5 + 5*x^6 + 7*x^7 + 10*x^8 + 12*x^9 + 17*x^10 + 22*x^11 + 29*x^12 + 39*x^13 + 51*x^14 + 68*x^15 + 90*x^16 + 119*x^17 + 158*x^18 + 209*x^19 + O(x^20)

Sucesión de Perrin y números primos

La propiedad más conocida de estos números es que si p es primo, p divide a X(p). Por ejemplo, X(11)=22, que es múltiplo de 11. Podemos construir una tabla en la que dividamos X(n) entre n y los cocientes enteros se corresponderán con los números primos:

A pesar de su carácter algo extraño, la propiedad ha sido demostrada para todos los números primos. La contraria no es cierta. X(n) puede ser múltiplo de n sin que este sea primo. A estos términos se les suele llamar pseudoprimos de Perrin (http://oeis.org/A013998):

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291,…

Otras propiedades

La paridad de X(n) recorre el ciclo {1, 0, 0, 1, 0, 1, 1} Es fácil de ver: las tres primeras vienen determinadas por la definición (en color rojo en la imagen). Las siguientes dependen de dos anteriores. Por tanto, existirá ciclo si se vuelve a repetir el par 1 0, y esto ocurre siete lugares más adelante (color verde):

Para ampliar el tema puedes visitar http://www.mathpages.com/home/kmath345/kmath345.htm en el que se incluye la espiral triangular creada con estos números.

Propiedades matriciales

Estas entradas sobre sucesiones recurrentes también se plantean el objetivo de un mayor conocimiento de las hojas de cálculo. Por eso vamos a aprovechar las propiedades matriciales de la sucesión de Perrin para  repasar este tipo de funciones.

La primera propiedad matricial se resume en la siguiente fórmula para n>2:

Recuerda que la traza es la suma de los elementos de la diagonal principal de una matriz cuadrada.
Para comprobarlo con una hoja de cálculo organizaremos este esquema:

Comenzamos escribiendo a la izquierda la matriz M dos veces, y a la derecha las multiplicamos.
Para ello usaremos la función matricial MMULT, pero como es de tipo matricial deberás seleccionar la matriz de la derecha (debajo del rótulo “Potencia n de M), después escribir una fórmula similar a esta: =MMULT(C3:E5;G3:I5), tomando como rangos los de las matrices de la izquierda. Cuando escribas la fórmula no termines con Intro, sino con la combinación Ctrl+Mayúsc+Intro, para indicar que la fórmula es de tipo matricial. Notarás que lo has escrito bien porque la fórmula se verá entre corchetes.

A la derecha de las matrices puedes incluir la traza de la tercera, que en la imagen te da 2. Después copia la tercera sobre la primera matriz con copia sólo de valores, y te resultará el siguiente número de Perrin, en este caso 3, porque esta propiedad genera la sucesión a partir del tercer término.
Seguirían 2, 5, 5, 7, 10,…

Variante de la anterior expresión

Si en lugar de usar la traza empleamos un producto por la matriz (en vertical) (3, 0, 2), obtenemos tres términos en lugar de uno. La expresión sería ahora:

Bastaría borrar la traza en el anterior esquema y sustituirla por otro nuevo producto matricial con la (3, 0, 2). Lo dejamos como ejercicio. Aquí tienes la generación de los términos 5, 7 y 10

Comprobar conjeturas con hoja de cálculo. Goldbach.

La formulación más simple de la Conjetura de Goldbach es:

Todo número par mayor que 2 es suma de dos primos

Fue propuesta por Goldbach el 7 de Junio de 1742, en una carta dirigida a Euler.  En realidad, su propuesta se refería a la conjetura ternaria: " Todo número impar es la suma de tres primos" y Euler le respondió con la propuesta binaria que todos conocemos.

Ha sido comprobada hasta números muy grandes, pero no se ha podido demostrar. No obstante, se han logrado resultados provisionales:

Cualquier número par es suma de 6 o menos números primos.(Ramaré 1995)

Todo número par suficientemente grande es suma de un primo y del producto de dos primos.(Chen 1966)

Todo número impar N mayor que 5 es suma de tres primos. (Demostración de la conjetura ternaria a cargo de Vinogradov en 1937).

En esta entrada sólo nos plantearemos, como en toda la serie que vamos desarrollando sobre conjeturas, la comprobación de algunos aspectos de la misma mediante el uso de la hoja de cálculo.

Primer nivel

Comprobaremos la conjetura en tres niveles distintos, según el uso que se haga del lenguaje de macros. En primer lugar lo efectuaremos con las técnicas usuales de las hojas de cálculo. Usaremos la hoja Conjeturas, alojada en la página

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#global

(Búscala en la relación de herramientas)

Organizaremos la comprobación según un esquema similar a este:

Escribimos un número par mayor que 2 en una celda. En la imagen es el 612. Después ordenamos los números primos en columna, hasta el límite que queramos. Para ello escribimos el 2, debajo primprox(2) (función implementada en esta hoja, y que encuentra el primo siguiente a uno dado).

Rellenamos hacia abajo y nos resultará la lista de primos.

En una segunda columna escribiremos una fórmula similar a a siguiente, que copiaremos de arriba a abajo:

=SI(Y(F15<=H$11/2;esprimo(H$11-F15));H$11-F15;"")

En ella H11 es la celda donde hemos escrito el 612. En tu caso podrá ser otra. La F15 en nuestro esquema apunta al número primo que tiene a su izquierda. De esa forma, la podemos interpretar así: “Si el primo no llega a la mitad del número par probado (aquí el 612) y su diferencia con él es otro primo, escribo esa diferencia, pero en caso contrario dejo la celda en blanco”.

Es sencillo de entender y funciona escribiendo los pares de primos en los que se descompone el 612. En la imagen 5+607, 11+601, 19+593,…hasta un total de 26 pares. Si no logras ese número, deberás rellenar hacia abajo las dos columnas hasta llegar a la mitad de 612

Este esquema puede aclarar, probando con varios pares, el sentido de la conjetura. También te da confianza en ella, pues no sólo existe un par de primos para cada número par, sino muchos. ¡Pero no se ha probado aún!

Nivel 2

Ya que con el esquema anterior nos han resultado varias descomposiciones en primos para cada número par, podíamos simplificar mucho si lo plasmáramos en una función. En la hoja de cálculo que estamos usando hemos implementado NUMGOLDBACH(N), que devuelve un cero si N no es par y el número de descomposiciones si es par. En el caso del 612 devuelve correctamente 26.

Aquí tienes los primeros resultados. Si la conjetura es cierta, deberán ser todos mayores que 0. Están recogidos en http://oeis.org/A045917

Merece la pena recorrer la codificación de esta función y así entenderás mejor las cuestiones.

Public Function numgoldbach(n)
Dim ng, i

If n <> 2 * Int(n / 2) Then  ‘si es impar devuelve un cero (valor de ng
ng = 0
Else
i = 2: ng = 0
While i <= n / 2  ‘si es par recorre todas las posibles sumas de primos
If esprimo(n - i) Then ng = ng + 1 ‘si el segundo sumando es primo, incrementa el contador ng
i = primprox(i) ‘esta línea asegura que el primer sumando sea primo
Wend
End If
numgoldbach = ng
End Function

Nivel 3

Podemos dejar que sea la hoja de cálculo la que recorra automáticamente los primeros números hasta un tope o hasta que numgoldbach dé un cero. Como lo segundo es imposible para números pequeños (ya está comprobada la conjetura), el resultado final será siempre un cero.

Podíamos usar un esquema similar al siguiente:

Escribimos un tope, pulsamos el botón e irán apareciendo valores de Numgoldbach, ninguno nulo, hasta finalizar la búsqueda. Si uno fuera cero, se interrumpiría el proceso con un solemne mensaje. La programación del botón podría ser similar a esta:

Sub buscagoldbach()
Dim i, g, p

p = ActiveWorkbook.Sheets(1).Cells(5, 3).Value ‘lee el tope
i = 4 ‘inicio búsqueda
g = 1’inicio valor de numgolbach
While g <> 0 And i <= p
i = i + 2 ‘busca de 2 en 2
g = numgoldbach(i)
ActiveWorkbook.Sheets(1).Cells(6, 3).Value = g ‘escribe el valor de g
If g = 0 Then MsgBox ("¡Contraejemplo!") ‘Esto no va a ocurrir
Wend
End Sub

Variantes

Variante ternaria

“Todo número impar mayor que 5 es la suma de tres primos"

No vamos a repetir con ella los tres niveles anteriores. El primer nivel necesitaría un estructura de datos tridimensional, poco intuitiva en una hoja de dos dimensiones. El tercero sería semejante al del primer caso. Así que sólo desarrollaremos un esquema con todas las posibles descomposiciones en tres sumandos primos:

Como en el caso anterior, no vamos a analizar si el número es impar o no. Simplemente hemos programado un botón que lo descompone en esos sumandos de todas las formas posibles (lo haremos con sumandos decrecientes)

Para quien le guste la programación, ahí tiene explicado el algoritmo que hemos usado:

Sub goldbach3()
Dim fila, a, b, c, n

fila = 7
n = ActiveWorkbook.Sheets(1).Cells(fila, 3).Value ‘lee el número, que se encuentra en C7
a = 2 ‘primer sumando primo
While a < n ‘ el primer sumando llega hasta n en lo posible
b = 2
While b < a ‘ el segundo es inferior al primero
c = n - a – b ‘tercer sumando
If esprimo(c) And c <= b Then ‘si el tercer sumando también es primo, se presenta el resultado
fila = fila + 1
ActiveWorkbook.Sheets(1).Cells(fila, 3).Value = a
ActiveWorkbook.Sheets(1).Cells(fila, 4).Value = b
ActiveWorkbook.Sheets(1).Cells(fila, 5).Value = c
End If
b = primprox(b) ‘se incrementa el segundo primo
Wend
a = primprox(a) 'se incrementa el primero
Wend
End Sub 

Como era de esperar, siempre aparecen los tres sumandos primos. Se deja a los lectores el definir una función que cuente las soluciones. Siempre existirá al menos una.

Expresión mediante equidistancia

Un comentario a la entrada http://culturacientifica.com/2013/06/26/la-conjetura-de-goldbach/ me ha dado la idea de organizar una comprobación distinta.

Si la conjetura es cierta, para todo número par 2N, si es la suma de dos primos p y q, con p>q, cumplirán que p+q=2N, o bien que p-N=N-q:

Todo número entero positivo mayor que 4 es equidistante de dos primos

Es fácil ver que es otra formulación distinta de la conjetura de Goldbach. En los párrafos anteriores hemos visto la consecuencia directa. A la inversa, si es cierto que todo N equidista de dos primos, dado un par 2N aplicamos p-N=N-q para cierto par de primos, con lo que 2N=p+q. El exigir que sea mayor que 4 es porque no habría primos inferiores para números menores.

Es muy fácil organizar la comprobación con esta variante. Lo efectuaremos en el Nivel 1, de cálculo manual:

Escribimos la lista de números consecutivos 1, 2, 3,…y los sumamos y restamos con el número dado. Después, en la tercera columna, escribimos una fórmula similar a

=SI(Y(ESPRIMO(D9);ESPRIMO(E9));"SI";"") 

que nos devuelve un “SI” si los equidistantes son primos.

En la imagen, 17=29-12 y 41=29+12.

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.

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 x² + 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.

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 x²ºa (mod p) entonces a^(p-1)/2ºx^p-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=14¹¹ Calculamos el resto de este último por potencias sucesivas: 14¹º14 (mod 23), 14²º12 (mod 23) 14⁴º12*12º6 (mod 23) 14⁸º6*6º13 (mod 23), luego 14¹¹º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: 70¹º-31 (mod 101), : 70²º31*31º-49 (mod 101), 70⁴º49*49º-23 (mod 101), 70⁸º23*23º24 (mod 101), 70¹⁶º24*24º-30 (mod 101), 70³²º30*30º-9 (mod 101), y ahora construimos el 50:

70⁵⁰º70³²70¹⁶70²º-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)

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: 1²=1, 3²=2 y 2²=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 x²ºa, o, con los cambios adecuados, la ecuación general de segundo grado. Lo vemos con un ejemplo:

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

Damos estos pasos:

x²-26x+10 º (x-13)²-159 º 7 (mod 11)
(x-13)²º166 (mod 11)
(x-13)²º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: 3²-26*3+10=-59 º-4 º 7 (mod 11) y 1²-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 1², 2², 3²,…,((p-1)/2)² y por tanto, este también es el número de no-restos.

Previamente estudia esta propiedad:

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

En efecto, si tiene una solución x1 con x1²º 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 1², 2², 3²,…,((p-1)/2)² no se repiten , ya que una igualdad entre ellos haría que la ecuación  x²º 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  1², 2², 3²,…,((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 .1², 2², 3²,…,((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.

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.