jueves, 14 de noviembre de 2019

Relaciones entre PHI(n) y TAU(n)



Función TAU

Las funciones PHI y TAU, aplicadas a un número entero positivo, tienen algo de complementarias. La segunda, TAU, cuenta los divisores de un número N. También es llamada función divisor, o D(x). En el caso de un número primo p, es claro que los divisores son 1 y p, luego la función TAU valdrá 2 en este caso. 

Igualmente, es fácil deducir que para potencias de un número primo, pk, TAU(pk)=1+k

Puedes acudir  a nuestra publicación Funciones multiplicativas (http://www.hojamat.es/publicaciones/multifun.pdf)
para consultar la fórmula general.

TAU(N)=(1+a1)(1+a2)…(1+ak)
a1, a2, …ak son los exponentes de los factores primos de N.

Por ejemplo, TAU(24)=TAU(23*3)=(1+3)(1+1)=8

Efectivamente, los divisores de 24 son ocho: 1, 2, 3, 4, 6, 8, 12 y 24.

Función PHI

La función j(n) (indicatriz o indicador de Euler) es el cardinal del conjunto de elementos inversibles en Zn o bien el conjunto de números coprimos con n y menores que él contando el 1. Esta segunda versión es más clara y adecuada al estudio que vamos a iniciar: cuenta los números primos con N y menores que N, con el añadido del 1.

La función indicatriz de Euler es multiplicativa, porque si m y n son coprimos, se cumple que

j(m). j(n) = j(m.n)

Su fórmula explícita es


(pi son sus factores primos)

Por ejemplo, el número 18=32*2 posee un valor de PHI igual a 18(1-1/2)(1-1/3)=6, Podemos comprobar que los números coprimos con 18 y menores que él son: 1, 5, 7, 11, 13 y 17. En total 6.

En los números primos p el valor de PHI(p)=p-1, como es fácil deducir.

En algunos lenguajes de programación recibe el nombre de función totient.

Relaciones entre TAU y PHI

Para cualquier número natural N, los números comprendidos entre 1 y N pertenecen a uno de estos tres conjuntos:

{A} Divisores de N: los cuenta la función TAU

{B} Coprimos con N incluido el 1: los cuenta la función PHI. En ambos conjuntos se encuentra el 1, lo que hace que no sean disjuntos.

{C} Resto de números: son aquellos números r que no son divisores de N ni coprimos con él: tienen un m.c.d con N que es mayor que 1 y menor que r.

Por ejemplo, en el número 30, los conjuntos serían:

{A} = {1, 2, 3, 5, 6, 10, 15, 30}, pues 30=2*3*5 y TAU(30)=(1+1)(1+1)(1+1)=8
{B} = {1, 7, 11, 13, 17, 19, 23, 29}, y PHI(30)=30(1-1/2)(1-1/3)(1-1/5)=1*2*4=8
{C} = {4, 8, 9, 12, 14, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28}, que son 15 elementos.

La suma de los cardinales de los tres conjuntos es 31, porque el 1 está repetido, y 8+8+15=31.

Con este planteamiento se adivina que pueden existir varias relaciones distintas entre los tres cardinales. El primero lo recoge TAU y el segundo PHI. El tercero lo dejamos como complemento de los otros dos.

PHI=TAU

Según lo publicado en http://oeis.org/A020488, solo existen estos casos: 1, 3, 8, 10, 18, 24, 30.

Por ejemplo, en N=10, TAU(10)=TAU(2*5)=(1+1)(1+1)=4 y PHI(10)=10(1-1/2)(1-1/5)=1*4=4.

No debemos conformarnos con lo publicado. Puedes comprobarlo con las dos versiones sencillas para el cálculo de ambas funciones que hemos preparado con el Basic de las hojas de cálculo. Para no interrumpir el estudio, las incluimos en un Anexo.

Jud McCranie da razones en esa página de por qué no hay más soluciones, y lo probó A. P. Minin  1894 . Lo comprobamos con nuestras funciones de hoja de cálculo:




El único número primo de la lista es 3, pues TAU(p)=2  para cualquier primo, y PHI(p)=p-1. Luego ha de ser 2=p-1 y p=3.

PHI doble de  TAU

También existen pocos casos (http://oeis.org/A062516):

5, 9, 15, 28, 40, 72, 84, 90 y 120.

Con nuestras funciones tenemos:




TAU doble de PHI

Sólo hay dos casos:



Otros casos

Con PHI=TAU+1 parece que no hay ninguno, y con PHI+1=TAU, solo dos casos:



PHI múltiplo de TAU

Si solo tenemos en cuenta múltiplos propios, cuyo cociente es mayor que 1, nos aparecen muchas soluciones. Las primeras son:



Si la relación de múltiplo es a la inversa, solo aparecen las soluciones ya vistas en las que TAU es el doble de PHI.

Por último, una curiosidad:

Pitagóricos

PHI y TAU son ambos catetos de una terna pitagórica. Solo se encuentran cinco soluciones:

20, 36, 60, 100, 300

Según el siguiente cuadro, en las ternas formadas sus elementos son múltiplos de las primitivas {3, 4, 5} o {9. 40, 41}.




Esta sucesión estaba inédita, y la hemos publicado en http://oeis.org/A308664. En esa página podrás leer un razonamiento de de Giovanni Resta con el que justifica que la sucesión sea finita.


  
ANEXO

Listado de la función PHI (Basic de Excel)

Public Function euler(n)
Dim f, a, e
Dim es As Boolean

'Calcula la indicatriz de Euler de un número

a = n ‘Copia el valor de n
f = 2 ‘Inicia el listado de primos
e = n ‘Inicia el valor de PHI
While f <= a ‘Recorre los primos posibles
es = False ‘Variable que indica si hemos llegado a un divisor primo o no
While a / f = a \ f ‘Si es un factor, se va eliminando del valor de n
a = a / f: es = True
Wend
If es Then e = e * (f - 1) / f ‘Si se ha encontrado un factor primo, se incorpora a PHI
If f = 2 Then f = 3 Else f = f + 2 ‘Busca el siguiente primo
Wend
euler = e
End Function


Listado de TAU
Es muy parecido al anterior


Public Function tau(n)
Dim f, a, e, exx


a = n ‘Copia el valor de n
f = 2 ‘Inicia el listado de primos
e = 1  ‘Inicia el valor de TAU
While f <= a ‘Recorre los primos posibles
exx = 0
While a / f = a \ f
a = a / f: exx = exx + 1 ‘Incrementa el exponente del factor primo encontrado
Wend
e = e * (1 + exx) ‘Construye TAU
If f = 2 Then f = 3 Else f = f + 2
Wend
tau = e
End Function



No hay comentarios: