martes, 18 de octubre de 2011

Funciones multiplicativas 1 - Definiciones

(Con esta entrada participamos en la edición 2.7 del Carnaval de Matemáticas, organizado en esta ocasión por el blog La aventura de la Ciencia)

Coincidiendo con la publicación en Hojamat.es del documento Funciones especiales y carácter de Dirichlet de Rafael Parra Machío, y como producto de una feliz casualidad, pues no ha habido acuerdo previo con dicho autor, iniciamos hoy una serie de entradas que de forma espaciada y algo periódica tratarán el tema de las funciones multiplicativas a lo largo de este curso.

Este tema está muy bien tratado en muchos manuales y páginas web, entre ellas la referida más arriba. Por eso, en estas entradas no nos limitaremos a repetir el tratamiento teórico, sino que abordaremos los temas mediante esquemas, cálculos, búsquedas o curiosidades. Los lectores no deben buscar en ellas los fundamentos teóricos, porque sólo aparecerán sintetizados. Así constituyen una invitación a la profundización teórica.

Comenzamos con unas definiciones:

Funciones aritméticas

Son funciones reales o complejas definidas sobre el conjunto de los números naturales.

Por tanto, toda función aritmética admite una representación como una sucesión de números (enteros, reales, complejos…)

Por ejemplo, la sucesión siguiente (representada como una correspondencia con los naturales) representa a la función “mayor divisor propio”. En efecto, repasa la tabla y observarás que los números de abajo son los máximos divisores propios de los de arriba.







Con frecuencia usaremos esta notación u otra similar para representar funciones aritméticas.

Funciones multiplicativas

Una función aritmética es multiplicativa cuando para todo par a y b de números naturales primos entre sí se cumple que

F(a*b)=F(a)*F(b) (si  (a,b)=1, siendo (a,b) el MCD de ambos números)

Si esto se cumple aunque los números no sean coprimos, llamaremos a la función completamente multiplicativa. Por ahora no las consideraremos.

Hoy lo explicaremos con un ejemplo sencillo: la función Tau, que es la que cuenta los divisores de un número, y que por comodidad tipográfica designaremos por D(n), ya que es parte de la familia de las funciones divisor o sigmas

(ver http://hojaynumeros.blogspot.com/2011/02/la-familia-de-las-sigmas-1.html)

Así, D(15)=4, porque admite los divisores 1, 3, 5 y 15. De igual forma, D(28)=6, ya que dividen a 28 los números 1, 2, 4, 7, 14 y 28

Pues bien, como 15 y 28 son coprimos, resulta que D(15*28)=24, como puedes comprobar. Más tarde lo razonaremos en general.

A partir de ahora podremos publicar tablas de doble entrada en las que puedas practicar y hacer comprobaciones con las funciones multiplicativas. Aquí tienes la primera, dedicada a la función Tau:








En la tabla sólo aparecen los valores de los productos cuando los dos factores son primos entre sí. Se ha elegido el rango de 20 a 30 porque en el mismo disponemos de gran variedad de números: primos, semiprimos, cuadrados…


Repasa algunos valores, calcúlalos si lo deseas y comprueba el carácter multiplicativo de Tau.

Propiedades de las funciones multiplicativas

(1) Si una función es multiplicativa se dará que F(a*1)=F(a)*F(1), luego deberá ser F(1)=1

A veces esta propiedad no está clara en alguna función, porque puede que no acabe de tener mucho sentido aplicarla a la unidad. En ese caso se suele definir directamente: F(1)=1.

En nuestro ejemplo D(1)=1 porque 1 sólo tiene un divisor.

(2) Si una multiplicativa está definida para cada potencia de un primo, lo estará para todo número natural, pues aplicando la función a la factorización

 Por su carácter multiplicativo se tendrá


Puedes seguir los detalles en los documentos teóricos. En ellos también se demuestra lo siguiente, que es fundamental para manejar funciones multiplicativas:

Si una función aplicada a N actúa de igual forma e independientemente para cada factor de N del tipo pr, siendo p un factor primo de N y r su exponente (factor primario de N), y después multiplica los resultados, esa función será multiplicativa

Si recuerdas la Teoría de la Divisibilidad, la función Tau tiene un desarrollo muy sencillo, que es el producto de los exponentes en la factorización aumentados en una unidad:


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

Sólo por este desarrollo ya se habría adivinado que es multiplicativa.

(3) El producto de dos multiplicativas también es también multiplicativo
Consúltalo, pero con un poquito de Álgebra comprenderás esta propiedad.

(4) En esta propiedad hay que detenerse un poco, aunque no la demostraremos (busca, busca…):

Si g(x) es una función multiplicativa, entonces, la función f(n) definida por


en la que el sumatorio recorre todos los divisores de n, también es multiplicativa.

Omitiendo detalles, la base de esta propiedad está en que los divisores de un producto de dos números coprimos M y N son productos de dos divisores, uno de M y otro de N, y al final la suma de productos coincidirá con el producto de sumas. ¿Es difícil de entender? Pues busca el desarrollo en cualquier manual o página que lo explique.

Nosotros lo comprobaremos en el caso de la tau para dos números concretos. Esto no demuestra nada, pero te ayudará a crearte una idea del proceso.














Ves que arriba hemos escrito los divisores de 105 y debajo de cada uno su número de divisores. Nos dan una suma de 27. Hemos efectuado la misma operación con 22 y nos suman 9. El producto de ambos (nótese que son coprimos) es 2310, que tiene 32 divisores (era de esperar ¿no?) y sus divisores suman 243, que es precisamente el producto de 27 por 9, luego en este caso el proceso ha sido multiplicativo. Pero no generalices. Hay que demostrar las cosas.

Lo dejamos por hoy. Otros días veremos algunos ejemplos de funciones multiplicativas interesantes.

miércoles, 12 de octubre de 2011

Distancia binaria entre primos


La historia se repite

En una entrada anterior “¿Alguien sabe algo de esto?” nos planteábamos si dado un primo p cualquiera, existe otro q tal que la suma de ambos sea una potencia de 2. Después de algo de reflexión y ayudas externas llegamos a la conclusión de que esta posibilidad fallaba, quizás en el número 1871.

Al revisar la entrada para integrarla en una publicación se me ocurrió usar la diferencia entre primos en lugar de la suma: dado un número primo p, ¿existe siempre un exponente k entero tal que p+2^k sea primo? Al mínimo valor posible de este exponente le llamaremos “distancia binaria entre ambos primos” o DISTBIN.

Podíamos interpretar ese número k como el lugar donde podríamos sumar 1 a la expresión binaria de p para que se convirtiera en otro número primo, el menor posible.

Por ejemplo, el número primo 61 tiene como expresión binaria 111101 y su función distbin vale 8. Esto quiere decir que en el orden 8 de su expresión binaria hay que añadir un 1 (tomamos como 0 la primera posición): 100111101, que equivale al número primo 317.

En los primeros números primos el cálculo de distbin es sencillo:

Primo P
Distancia binaria
Primo Q
2
0
3
3
1
5
5
1
7
7
2
11
11
1
13
13
2
17
17
1
19
19
2
23
23
3
31
29
1
31
31
4
47
37
2
41
41
1
43
43
2
47
47
5
79
53
3
61
59
1
61
61
8
317

Tienes los datos de q en http://oeis.org/A139758 y los de k en http://oeis.org/A094076

Como en el caso anterior de p+q=2^n, hay primos en los que el cálculo de esta distancia desborda la capacidad de una hoja de cálculo. Destacan los siguientes:

El 773

Se tiene que distbin(773)=955, con lo que el otro primo presenta 288 dígitos:

304541062856249971261043199621099634714882089299843985214622076787904646586450815702050470808812820600790778632231520880733099058287596688955562103009770419360352428123639782183462176734064176511024987296225574339802674935168589842054573862983405175400866837597008673346307143437247316741


Imagina que su expresión binaria estará formada por un 1, más de novecientos ceros y después la expresión del 773.

El 1627

Distbin: 127 q: 85070591730234615865843651857942054491

El 2131

Bloquea las herramientas que hemos usado. En  http://oeis.org/A094076. se afirma que se ha probado el 2131 para k<30000

Si deseas practicar con el tema, te ofrecemos los códigos de búsqueda que se han usado:

Basic

Definición de DISTBIN

Function distbin(a)
Dim c, p, p2, i

c = 0
If a > 2 And esprimo Then
p = 0
p2 = 1
i = 1
Do Until esprimo(p2)
i = i * 2
p2 = a + i
p = p + 1
If esprimo(p2)  Then c = p
Loop
End If
distbin = c
End Function


Wxmáxima

Imagen del cálculo de distbin(1627)




Calculadora Wiris

Imagen del cálculo de distbin(773). En ella no entra todo el resultado.



Con ellas puedes tener una idea de los algoritmos usados. Puedes usarlos para continuar las búsquedas.

lunes, 3 de octubre de 2011

Buscador de números naturales 2.1

Este blog, según consta en su cabecera, es complementario de la página web hojamat.es. Por eso se recoge en él de forma ocasional las novedades y actualizaciones de la misma. Hoy presentamos la nueva versión del Buscador de números naturales, que es una de las herramientas que figuran desde su creación.

Puedes descargar la versión para Excel en http://hojamat.es/sindecimales/divisibilidad/herramientas/hojas/buscador_2.xlsm y para Calc en http://hojamat.es/sindecimales/divisibilidad/herramientas/hojas/buscador_2.ods


Antecedentes

El Buscador fue creado a principios de los años noventa para su uso en las clases de Matemáticas, Informática y talleres. La idea del mismo era la obtención de una lista de números naturales que cumplieran determinadas condiciones, como ser primos, divisores de otros o capicúas. La primera versión se construyó en Pascal y como programa ejecutable, pasando posteriormente al Visual Basic. La especialización del autor en hojas de cálculo hizo natural el traspaso del mismo a Excel y Calc y su publicación en Hojamat.es.




Esta versión publicada heredó todos los botones y controles de la anterior, lo que hizo un poco complicado su uso. Lo que pretende la nueva versión que presentamos es la eliminación de tantas variantes y opciones, unificando el formato de las condiciones.

Estructura

En la nueva versión sólo hay que indicar el inicio y el final de la búsqueda, así como las condiciones, que se escribirán en un lenguaje cercano al natural mediante una palabra reservada y unos parámetros. Por ejemplo, para obtener los múltiplos de 18 y de 44 de cuatro cifras que terminen en 6 bastará concretar la búsqueda como se observa en la imagen





Se han escrito las condiciones MULTIPLO 18 44 y TERMINA EN 6, concretando los límites 1000 y 9999 para encontrar cuatro soluciones: 2376, 4356, 6336 y 8316.

Las búsquedas son así de simples: Inicio, final y condiciones escritas en un lenguaje muy directo.

Algunos ejemplos


Números de Ore

Son aquellos en los que la media armónica de sus divisores es entera
(Ver http://hojaynumeros.blogspot.com/2010/11/numeros-de-ore.html).
En el Buscador basta escribir esta condición algo compleja para obtenerlos:

ES ENTERO(N*NUMDIV(N)/SUMDIV(N))

En la imagen aparece el resultado, que coincide con http://oeis.org/A001599



Esta búsqueda se lentifica bastante en Calc al llegar a 1000. En Excel va más rápida.

Comprobación de un teorema

Se sabe desde Fermat que los números primos de la forma 4k+3 no se pueden descomponer en suma de cuadrados.

Si exigimos las condiciones PRIMO, LINEAL 4 3, SUMA C C (suma de dos cuadrados) observaremos que no aparece ninguna solución:



Números de Ruth-Aaron

En ellos la suma de divisores primos de un número coincide con la suma de los del siguiente
(Ver http://hojaynumeros.blogspot.com/2011/03/parientes-de-ruth-y-aaron.html)
Se buscan también con una sola condición: ES SUMDIVPRIM(N)=SUMDIVPRIM(N+1), resultando la secuencia http://oeis.org/A006145

Limitaciones

Este modelo de hoja de cálculo está dirigido a su uso por parte de profesores y alumnos de enseñanzas secundarias y de quienes se inicien en los estudios de la Teoría de Números. No tiene nivel universitario ni la potencia de otros programas especializados en cálculos matemáticos. En concreto, presenta limitaciones en el rango de los números considerados, que está marcado por las de Excel y Calc, y una excesiva lentitud al llegar a números grandes con ciertas condiciones. Está concebido para un entretenimiento matemático sin más pretensiones.

Tratamiento de errores

No se ha realizado un control exhaustivo de los errores. Es demasiado costoso para una herramienta de estas características (y para la edad del autor, que todo cansa). Cualquier persona con cierta habilidad matemática o informática lo pondrá en apuros. Si eso ocurre, se cierra y se comienza de nuevo. Aquí no hay nada trascendente.

Tampoco es total la validación de datos. Entre Excel y Calc existen pequeñas diferencias en los tipos de datos y donde uno da un mensaje de error el otro lo admite. Así que si comenzamos a escribir decimales o números negativos pueden producirse resultados engañosos.

Documentos

Esta versión viene acompañada de dos documentos:

Guía de uso

Describe una a una las condiciones admitidas por el Buscador, con la sintaxis correcta y un ejemplo, así como las funciones usadas en el módulo interno de cálculo. Se descaga en http://hojamat.es/sindecimales/divisibilidad/herramientas/Buscador de números naturales_2.pdf

Uso en la enseñanza

Recoge, ampliadas y corregidas, las propuestas que el autor usó en clase. Son las de nivel mínimo, aunque el Buscador permite propuestas más complejas. Su dirección es http://hojamat.es/sindecimales/divisibilidad/herramientas/Buscador_2.pdf

Si el tiempo disponible lo permite, se incluirá más adelante un documento con propuestas algo más complejas, que tenga más carga teórica. También en este blog a partir de hoy podrán aparecer búsquedas realizadas con la herramienta que presentamos.

Esperamos que la nueva versión del Buscador sea más útil que la anterior. Si no, ya pensaremos en la tercera.

jueves, 15 de septiembre de 2011

Obtención de la lista de divisores

Algoritmo con hoja de cálculo

(Si no te interesa la programación en Basic puedes dejar de leer)

Para encontrar los divisores de un número N la búsqueda más simple consiste (salvo alguna pequeña modificación que la acelere) en recorrer todos los números menores o iguales a N y tomar nota de los que son divisores suyos. Es muy sencilla de programar y sólo ocupa unas pocas líneas de código. Tiene el inconveniente de que para números de más de cuatro o cinco cifras decimales resulta muy lenta en hoja de cálculo, que es la herramienta que usamos en este blog.

Un algoritmo más rápido consiste en reproducir en la hoja el esquema que siempre se ha usado en las clases de Matemáticas, el que desarrolla las distintas potencias del primer divisor primo y después las combina con las de los demás en una tabla bidimensional como la siguiente, que se corresponde con los divisores del número 33075=33*52*72


3        1          3          9          27
5        5        15         45        135
        25        75       225        675
7        7        21         63        189
        35      105       315        945
       175     525     1575      4725
        49     147        441      1323
       245    735      2205      6615
     1225    3675   11025    33075


En ella se han situado en la primera columna los factores primos, en la primera fila las potencias del 3 y en las demás filas los distintos productos que se pueden formar entre las potencias, sumandos formados en la fórmula



de la obtención de sigma(N).

Para poder construir este esquema en la hoja necesitamos saber qué factores primos posee el número y con qué exponentes. La siguiente subrutina en Basic nos los proporciona:

Global p(50) as long  Se definen las variables p para los factores, e los exponentes y np el número total
Global e(50) as integer
Global np%



Sub sacaprimos(a)
Dim f,i
dim vale as boolean


f=2:i=1:e(i)=0:vale=false:np=0
while f<=a  El bucle while_wend divide el número entre el factor todas las veces posibles
if esprimo(f) then
while a/f=int(a/f)  Es divisor primo
vale=true
p(i)=f
e(i)=e(i)+1  aumenta el exponente
a=a/f
wend
if vale then
np=np+1  aumenta el número de factores
i=i+1:e(i)=0 se inicia un nuevo exponente
end if
vale=false
end if
f=f+1 buscamos otro factor primo
wend
End sub

Con este código obtenemos la lista de factores primos p(i), la de exponentes e(i) y el número total de factores primos np.

Al usar estos datos la búsqueda de divisores se simplifica mucho, pues todo el trabajo consistirá ahora en construir la tabla que estudiamos en nuestros años escolares:

(a) Formamos una fila con las potencias posibles del primer factor primo. Tomamos nota de que la altura de la tabla es de 1. También recogeremos el dato de la variable fila en la que se han escrito.

(b) Vamos multiplicando esas potencias de la primera fila por todas las de los otros primos, pero teniendo cuidado de:

* En cada nuevo primo la altura queda multiplicada por e(i)+1, que es el número de sus potencias posibles.

* En cada nuevo producto deberemos incrementar la variable fila en una unidad, para que se vaya formando la tabla hacia abajo.

* Deberemos usar muchos bucles anidados, porque intervienen as variables del número de potencias de la primera fila, el de las del resto de primos y las del número de primos diferentes.

Un posible código en OpenOffice sería:

sub todosdivisores


dim i,j,k,l, altura,fila
dim divi as long


Rellena la primera fila con las potencias del primer primo
if np>=1 then
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(2,11).value=p(1)
for k=0 to e(1)
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3+k,11).value=p(1)^k
next k
end if


Va multiplicando las potencias de los demás primos
if np>=2 then
altura=1:fila=12
for k=2 to np  Este bucle recorre los primos
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(2,fila).value=p(k)
for j=1 to e(k)  Recorre las potencias del primo actual
for i=1 to altura Recorre todos los divisores anteriores
for l=0 to e(1)  Ídem los elementos de cada fila
divi=StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3+l,10+i).value
divi=divi*p(k)^j  Efectúa el producto y lo escribe
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3+l,fila).value=divi
next l
fila=fila+1  Una vez escritos, aumenta la fila
next i
next j
altura=altura*(e(k)+1)  La altura se amplía
next k
end if
end sub

Pues ya tienes una idea. El resto es cosa tuya. Seguro que la mejoras.

jueves, 14 de julio de 2011

Divisores unitarios 3 – Relaciones entre sigma y usigma

Terminamos esta serie con algunos resultados curiosos sobre las relaciones entre las funciones sigma(N) y usigma(N).

1) En los números libres de cuadrados coinciden sigma y usigma: todos los divisores son unitarios. En los que contienen cuadrados no se puede dar la igualdad, pues si el factor p figura como p2 o con una potencia mayor k, su correspondiente factor en usigma sería (1+pk) y en sigma (1+p+p2+…pk) ¿Recuerdas por qué?

2) En los números 108, 540, 756, 1188, 1404, 1836, 2052, 2484,…la función sigma es el doble que la usigma (ver http://oeis.org/A063880)

3) Se pueden establecer otras relaciones entre ambas funciones.

(a) Imagina un número N cuya parte cuadrada es 4. Su descomposición factorial será del tipo N=22*p1*p2*p3…con lo que las funciones tendrían como expresión:

Sigma(N)=(1+2+4)(1+ p1) (1+ p2) (1+ p3)…
Usigma(N)=(1+4)(1+ p1) (1+ p2) (1+ p3)…, luego

5*sigma=7*usigma

Si lo programas con una hoja de cálculo obtendrás la secuencia

4, 12, 20, 28, 44, 52, 60, 68, 76, 84, 92,… (http://oeis.org/A081770) formada por los números cuya parte cuadrada es 4.

(b) Esta relación de 5 a 7 se convierte en la de 10 a 13 en el caso de tener parte cuadrada igual a 9. ¿Cuál sería la relación si la parte cuadrada fuera pk con p primo?

(4) Recuerda las dos definiciones de sigma y usigma:



Nos vamos a plantear ahora cuál será el MCD de los valores de ambas para un mismo N

(a) Si N no es cuadrado perfecto, sigma y usigma tendrán algún factor común y su máximo común divisor será mayor que 1.


En efecto, entre la multiplicidades ei de los factores primos existirá una al menos que sea impar (¿por qué?). Supongamos que sea k impar y exponente de un factor primo p de N.

Entonces, por razones algebraicas tenemos:

1+pk = (1+p)(1-p+p2-p3….), luego 1+p divide a 1+pk y por tanto divide a usigma(N)

1+p+p2+p3+…pk = (1+p)p+(1+p)p3+(1+p)p5… = (1+p)(p+p3+p5+…pk-1)

Esto sólo es posible porque k es impar. Por tanto, (1+p) también divide a sigma(N)

Así que hemos demostrado que los números no cuadrados presentan un MCD(sigma(N),usigma(N))>1, que era nuestra afirmación. Ese máximo común divisor es múltiplo de p+1 para algún factor primo p de N.

Lo puedes comprobar en esta tabla


N
Sigma
Usigma
MCD
2
3
3
3
3
4
4
4
4
7
5
1
5
6
6
6
6
12
12
12
7
8
8
8
8
15
9
3
9
13
10
1
10
18
18
18
11
12
12
12
12
28
20
4
13
14
14
14
14
24
24
24
15
24
24
24
16
31
17
1
17
18
18
18


En ella vemos que los números que no son cuadrados el MCD es mayor que 1. Incluso en los libres de cuadrados coinciden las tres funciones, sigma, usigma y MCD. Sin embargo, en los cuadrados el resultado es 1, pero no debemos confiarnos.

(b) Los números cuadrados presentan en general MCD(sigma(N),usigma(N))=1, salvo algunos en los que se dan los valores 5, 13, 37, 61, 65, 73, 793,…

En este caso las multiplicidades ei de los factores primos serán todas pares, y no se podrá aplicar el razonamiento del apartado anterior.

Si emparejamos los factores que un mismo número primo p con multiplicidad k par produce en ambas funciones, tendremos (llamamos S al factor en sigma y U a su homologo en usigma):

S: 1+p+p2+p3+p4+….+pk   (factor de p en sigma)
U: 1+pk (factor de p en usigma)

Pues bien, U y S son primos entre sí y no aportan ningún factor al MCD.

En efecto, si un factor m divide a U y a S

-          No será m igual al número primo p, pues en ese caso no dividiría a U
-          No dividirá m a p+1, pues 1+pk = (1+p)M(p)+2 por el Teorema del Resto (k es par), lo que nos deja la única posibilidad de que m=2, pero entonces m no dividiría a S, que es impar (¿por qué?).

-          Dividirá m a la diferencia S-U: p+p2+p3+p4+….+pk   = p(1+p+p2+p3+p4+….+pk-1) y como no divide a p, será divisor de 1+p+p2+p3+p4+….+pk-1=(1+p)(1+p+p2+….+pk-2). Como tampoco divide a 1+p, lo hará a 1+p+p2+….+pk-2 y a su diferencia con S: pk+pk-1=(1+p)pk-1, y esto es definitivamente imposible. Razónalo.

Así que si entre sigma y usigma en los números cuadrados existen factores comunes, estos provendrán de la expresión U para un número primo y la S para otro primo distinto.

Los factores primos impares de U han de ser de la forma 4k+1, que son los únicos que presentan un resto cuadrático igual a -1 (ver http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm#restcuad y

Esto nos reduce el catálogo de valores de p a 2, 5 13 17 29 37 41 53 61 73 89 97 101 109 113…
Si estos dividen a expresiones del tipo S construidas sobre otro primo, serán los que formen el MCD buscado. No lo haremos, pero ahora, para cada factor primo de los anteriores, buscaríamos qué par de primos distintos producen múltiplos de ellos en U o en S.

Por ejemplo, el factor 61 lo producen U=1+11^2 = 122 = 2*61  y S= 1+13+13^2 = 183 = 3*61
Si encargamos a la hoja de cálculo que nos devuelva los números cuadrados N en los que MCD(sigma(N),usigma(N))>1, obtenemos estos primeros resultados:

N
Sigma
Usigma
MCD
225
403
260
13
576
1651
650
13
900
2821
1300
13
3600
12493
4420
13
8649
12909
9620
13
11025
22971
13000
13
14400
51181
16900
13
19881
29341
22100
13
20449
24339
20740
61
21025
27001
21892
13
27225
53599
31720
13
28224
94107
32500
13
34596
90363
48100
13
38025
73749
44200
13
44100
160797
65000
13
47961
70239
53300
13
53824
110617
54730
13
57600
205933
66820
13
58564
112735
73210
5
62001
90649
68900
13
65025
123721
75400
13
69696
219583
79300
13

Actualización: Publicamos esta secuencia en OEIS: https://oeis.org/A193003