PDF de programación - Números y hoja de cálculo VII

Números y hoja de cálculo VII



Curso 2014-15



Colección Hojamat.es

© Antonio Roldán Martínez

http://www.hojamat.es







1








PRESENT ACIÓN




Llegamos al séptimo volumen de los resúmenes anuales del blog
“Números y hoja de cálculo” En esta temporada hemos publicado más
entradas relacionadas con ciertos temas concretos, que los que surgen
de forma ocasional. Debemos destacar el conjunto dedicado a Restos
cuadráticos, que prácticamente recorre toda la teoría sobre ellos, y la
parte dedicada a la comprobación de conjeturas o la que presenta
sucesiones recurrentes, que en esta temporada se ha dedicado a las
de tercer orden.

Intentaremos siempre que en cada tomo figuren algunos temas
desarrollados en varias entradas del blog junto a los que aparecen
sugeridos por la actualidad. Así no se pierde frescura, pero se van
recorriendo de forma más sistemática algunos temas importantes.

En el resumen actual, casualmente, sólo figura una entrada dedicada a
las hojas de cálculo, pero no abandonaremos su estudio, desarrolando
temas que surjan, pero sin planificación previa.







2






CONTENIDO




Presentación .................................................................................... 2

Contenido ......................................................................................... 3

Restos cuadráticos .......................................................................... 5

Introducción ................................................................................... 5

Criterio de Euler ............................................................................. 8

Propiedades de los restos cuadráticos ......................................... 13

No dejaremos la hoja ..................................................................... 16

Unión e intersección de conjuntos ............................................... 16

Comprobación de conjeturas ....................................................... 21

Goldbach. .................................................................................... 21

Conjetura n2+1 ............................................................................. 27

Conjetura de Polignac .................................................................. 33

Sucesiones recurrentes ................................................................ 41

Sucesión de Perrin....................................................................... 41

Sucesión de las vacas de Narayana ............................................ 47

Números “Tribonacci” .................................................................. 52

Sucesión de Padovan .................................................................. 58

Los divisores son los protagonistas ............................................ 66

Factores primos de la parte libre .................................................. 66

Antisigma de un número natural .................................................. 85

Relaciones entre un número y su sigma ...................................... 92



3














La función de Smarandache y los números de Kempner .......... 101

Cuestiones sobre primos ............................................................ 114

Suma con el próximo primo ....................................................... 114

Números especiales .................................................................... 123

Números especiales que son un producto especial ................... 123

Formas de ser un número equilibrado........................................ 140

Miscelánea ................................................................................... 158

Bienvenida al 2015 .................................................................... 158

Autonúmeros ............................................................................. 164



4


RESTOS CU ADR ÁT ICOS


I N T R O D U C C I Ó N


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

x2  a (mod p)

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
cuadrático”.

Para estudiar el tema con profundidad puedes acudir a

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



5

RestosRaízNo restos113235426Restos y no restos
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

x2  a (mod p)

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)



6


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.

2  a (mod p) también será
En efecto, si tiene una solución x1 con x1
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)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)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 alojada en esta
dirección:




7


http://www.hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm#restoscu
ad


Su 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)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 el siguiente apartado simplificaremos los cálculos necesarios para
sab