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, p^k, TAU(p^k)=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+a₁)(1+a₂)…(1+a_k)

a₁, a₂, …a_k son los exponentes de los factores primos de N.

Por ejemplo, TAU(24)=TAU(2³*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 Z_n 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

(p_i son sus factores primos)

Por ejemplo, el número 18=3²*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