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.

tomo

Intentaremos siempre que en cada
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 .................................................... 10

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

No dejaremos la hoja ............................................. 20

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

Comprobación de conjeturas ................................ 28

Goldbach. .............................................................. 28
Conjetura n2+1 ...................................................... 37

Conjetura de Polignac ........................................... 45

Sucesiones recurrentes ......................................... 54

Sucesión de Perrin ................................................ 54

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

Números “Tribonacci” ............................................ 69

Sucesión de Padovan ........................................... 76



3





Los divisores son los protagonistas .................... 87

Factores primos de la parte libre ........................... 87

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

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

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

Cuestiones sobre primos .................................... 155

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

Números especiales ............................................ 167

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

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

Miscelánea ............................................................ 218

Bienvenida al 2015 .............................................. 218

Autonúmeros ....................................................... 226



4


RESTOS CUADRÁTICOS


INTRODUCCIÓ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
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:

restos, por ejemplo

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.



5

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

http://mate.dm.uba.ar/~pdenapo/teoria_analitica_de_nu
meros/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



6


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)



7


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)
En efecto, si tiene una solución x1 con x1
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
restos cuadráticos no
sobrepasará (p-1)/2. Es más, es igual que ese número,

tanto, el número de



8


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:

http://www.hojamat.es/sindecimales/congruencias/herra
mientas/herrcong.htm#restoscuad


Su primera prestación es la de encontrar
el conjunto de restos y no restos para un
módulo primo e impar.

el
En
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

implementado

ella

está

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.



9


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 saber si un resto es cuadrático o no
mediante un criterio debido a Euler.



CRITERIO DE EULER


En la una 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.