This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/EulerTotient

From OeisWiki

Jump to: navigation, search

Sequences related to
Euler's totient function

KEYWORDS: relatively prime, totient of n, generalized totient function, phi function, generalized phi function, reciprocity balance of n, square-free kernel of n, number of distinct primes dividing n, factorset, nilpotent elements.

Concerned with sequences:  A000010, A193805, A193804, A023900, A007947, A000027, A003557, A051953, A066781, A001221, A179179, A130212, A181538, A181549, A181550, A181552.

Contents

Euler's Totient Function

Euler's totient function φ(n) counts how many positive numbers ≤ n are coprime (or orthogonal) to n. Two integers a, b are coprime (written a 'perp' b) if the set of common positive divisors of a and b is {1}.
Thus the defining formula is, using the Iverson bracket

 \varphi(n) = \sum_{1 \leq k \leq n} \left[ k \perp n \right].

Since a and b have only one divisor in common this is also the greatest common divisor, (a,b) = gcd(a,b) = 1.

 \varphi(n) = \sum_{1 \leq k \leq n} \left[ \text{gcd}(k, n) = 1 \right] .

This representation of φ(n) is often taken as a definition of φ. This is bad practice as the term greatest common divisor suggests the notions of magnitude and order, which is not meant here. The mathematical domain under consideration is the algebraic structure of a principal ideal domain D and does not have an order. In the general definition of ''relatively prime'' in a principal ideal domain the set {1} is just replaced by the set of invertible of  D.

What is a divisor?

The style sheet of OEIS says: "Divisors - often a source of confusion!" and explains:

  • divisors: number d in the range 1 ≤ d ≤ n which divide n A000005
    1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2
  • aliquot divisors: numbers 1 ≤ d < n which divide n A032741
    0, 1, 1, 2, 1, 3, 1, 3, 2, 3, 1, 5, 1, 3, 3, 4, 1, 5, 1
  • proper divisors, nontrivial divisors: these terms refer to divisors d of n with 1 < d < n A070824.
    0,0, 0, 1, 0, 2, 0, 2, 1, 2, 0, 4, 0, 2, 2, 3, 0, 4, 0

Even this list misses an important further case.

  • strong divisors: number d in the range 1 < d ≤ n which divide n A032741.
    0, 1, 1, 2, 1, 3, 1, 3, 2, 3, 1, 5, 1, 3, 3, 4, 1, 5, 1

Arguably the notion of a strong divisor is the most natural one: it is the naive concept of a divisor of everyday usage; it excludes the case where no 'real' division takes place.

The introduction of strong divisors now makes the definition of ''relatively prime'' simpler and avoids the poor and misleading use of the gcd in this context: Two integers a, b are coprime (written a 'perp' b) if they share no strong divisors.

To illustrate this approach let us look at the triangle which displays the intersection of the strong divisors of k and the strong divisors of n for n ≥ 1 and 1 ≤ k ≤ n.

                       {}
                     {}, {2}
                   {}, {}, {3}
               {}, {2}, {}, {2, 4}
            {},   {},   {},   {},  {5}
         {}, {2}, {3}, {2}, {}, {2, 3, 6}
     {},   {},   {},   {},   {},   {},   {7}
   {}, {2}, {}, {2, 4}, {}, {2}, {}, {2, 4, 8}

This fundamental triangle deserves it's place in the OEIS (but it is not there yet).

                   0
                  0, 1
                0, 0, 1
               0, 1, 0, 2
             0, 0, 0, 0, 1
            0, 1, 1, 1, 0, 3
          0, 0, 0, 0, 0, 0, 1
         0, 1, 0, 2, 0, 1, 0, 3

A generalization of the totient function.

Let us start with two facts:

  • The coprimes of n (set)minus the strong divisors of 1 are the coprimes of n.
  • The coprimes of n (set)minus the strong divisors of n are the coprimes of n.
  • The coprimes of n (set)minus the strong divisors of k are what?

The answer is:

            {1}            
          {1}   {1}          
        {1,2}   {1}   {1,2}        
      {1,3}   {1,3}   {1}   {1,3}      
    {1,2,
3,4}
  {1,3,4}   {1,2,4}   {1,3}   {1,2,
3,4}
   
  {1,5}   {1,5}   {1,5}   {1,5}   {1}   {1,5}  
{1,2,3,
4,5,6}
  {1,3,4,
5,6}
  {1,2,4,
5,6}
  {1,3,
5,6}
  {1,2,3,
4,6}
  {1,4,5}   {1,2,3,
4,5,6}

Counting the members leads to:

            1            
          1   1          
        2   1   2        
      2   2   1   2      
    4   3   3   2   4    
  2   2   2   2   1   2  
6   5   5   4   5   3   6

This is the promised generalization of the φ function. More formally we set:

\scriptstyle \varphi(n,k)\ =\ \mid \{ j : j \text{ prime to } n \}\ \setminus \ \{ 
j: j \text{ strong divides } k \} \mid

Thus Euler's φ(n) = φ(n,1) = φ(n,n). The OEIS number of this function is A193805.

A generalization of the cototient function.

\scriptstyle \overline{\varphi}(n,k)\ =\ \mid \{ j: 1 \leq j \leq n \} \ \setminus \ \left( \{ 
j : j \text{ prime to } n \}\ \setminus \ \{ j: j \text{ strong divides } k \} \right) \mid

            { }            
          {2}   {2}          
        {3}   {2,3}   {3}        
      {2,4}   {2,4}   {2,3,4}   {2,4}      
    {5}   {2,5}   {3,5}   {2,4,5}   {5}    
  {2,3,
4,6}
  {2,3,
4,6}
  {2,3,
4,6}
  {2,3,
4,6}
  {2,3,4,
5,6}
  {2,3,
4,6}
 
{7}   {2,7}   {3,7}   {2,4,7}   {5,7}   {2,3,
6,7}
  {7}

Counting leads to:

            0            
          1   1          
        1   2   1        
      2   2   3   2      
    1   2   2   3   1    
  4   4   4   4   5   4  
1   2   2   3   2   4   1

Thus the cototient φ-(n) = φ-(n,1) = φ-(n,n). The OEIS number of this function is A193804.

The prime totient

We will now look closer at the connection A001221(A001783(n)) = A048865(n) observed by Enrique Pérez Herrero. We do so by looking at the prime totient and the prime cototient function. Prime totient will be our name for A048865 and prime cototient for A001221. These functions are nothing else but the totient and the cototient functions downstream processed by prime selection. We will look right from the start at the generalized versions.

\scriptstyle \varphi_{\mathbb{P}}(n,k)\ =\ \mid \mathbb{P} \cap \left( \{ 
j : j \text{ prime to } n \}\ \setminus \ \{ j: j \text{ strong divides } k \} \right) \mid

Let P denote the set of primes. Our usual low triangle view of the square array begins:

            {}            
          {}   {}          
        {2}   {}   {2}        
      {3}   {3}   {}   {3}      
    {2,3}   {3}   {2}   {3}   {2,3}    
  {5}   {5}   {5}   {5}   {}   {5}  
{2,3,5}   {3,5}   {2,5}   {3,5}   {2,3}   {5}   {2,3,5}

Looking at the cardinality of the sets leads to:

            0            
          0   0          
        1   0   1        
      1   1   0   1      
    2   1   1   1   2    
  1   1   1   1   0   1  
3   2   2   2   2   1   3

At the right and left hand side of the triangle the classical prime totient sequence A048865 emerges. The generalized prime totient function is A198066.

The prime cototient

\scriptstyle \overline{\varphi_{\mathbb{P}}}(n,k)\ =\ \mid \mathbb{P}\, \cap \, \left( \{ 
j: 1 \leq j \leq n \} \, \setminus \, \left( \{ j : j \text{ prime to } n \} \, \setminus \, \{ 
j: j \text{ strong divides } k \} \right)\right) \mid

            {}            
          {2}   {2}          
        {3}   {2,3}   {3}        
      {2}   {2}   {2,3}   {2}      
    {5}   {2,5}   {3,5}   {2,5}   {5}    
  {2,3}   {2,3}   {2,3}   {2,3}   {2,3,5}   {2,3}  
{7}   {2,7}   {3,7}   {2,7}   {5,7}   {2,3,7}   {7}

Counting the members gives:

            0            
          1   1          
        1   2   1        
      1   1   2   1      
    1   2   2   2   1    
  2   2   2   2   3   2  
1   2   2   2   2   3   1

At the right and left hand side of the triangle the classical omega sequence emerges, A001221. The generalized prime cototient function is A198068.

The reduced residue system of n

The next sequence gives the number of nonprime numbers which are prime to n and are not strong divisors of k, A198067.

\scriptstyle \overline{\varphi_{\mathbb{P}}}(n,k)\ =\ \mid (\mathbb{N}\, \setminus \mathbb{P})\, \cap \, \left( \{ j : j \text{ prime to } n \} \, \setminus \, \{ 
j: j \text{ strong divides } k \} \right) \mid

            {1            
          {1}   {1}          
        {1}   {1}   {1}        
      {1}   {1}   {1}   {1}      
    {1,4}   {1,4}   {1,4}   {1}   {1,4}    
  {1}   {1}   {1}   {1}   {1}   {1}  
{1,4,6}   {1,4,6}   {1,4,6}   {1,6}   {1,4,6}   {1,4}   {1,4,6}

Counting gives:

            1            
          1   1          
        1   1   1        
      1   1   1   1      
    2   2   2   1   2    
  1   1   1   1   1   1  
3   3   3   2   3   2   3

At the right and left hand side of the triangle are the numbers of nonprime numbers in the reduced residue system of n, A048864.

Summary with Maple script

T(n, k) =
card {j | ...}
n = k n, k j prime
to n
j prime j strong
divides k
totient A000010 A193805 true irrelevant false
cototient A051953 A193804 false irrelevant false
prime totient A048865 A198066 true true false
prime cototient A001221 A198068 false true false
nonprimes in
res. classes
A048864 A198067 true false false
primes    := n -> select(isprime, {$1..n}): 
coprimes  := n -> select(j->igcd(j, n)=1, {$1..n}):
strongdivisors := n -> numtheory[divisors](n) minus {1}:
complement := (n,S) -> {$1..n} minus S:

GeneralTotient := proc(type) local T, n, j;
  if type = 'totient' then T := (n,k) -> 
coprimes(n) minus strongdivisors(k);
elif type = 'cototient' then T := (n,k) ->
complement(n,coprimes(n) minus strongdivisors(k)):
elif type = 'primetotient' then T := (n,k) ->
primes(n) intersect (coprimes(n) minus strongdivisors(k)):
elif type = 'primecototient' then T := (n,k) ->
primes(n) intersect complement(n,coprimes(n) minus
          strongdivisors(k)):
elif type = 'nonprimeresidue' then T := (n,k) ->
coprimes(n) minus (primes(n) union strongdivisors(k)):
else T := (n,k) -> 0; fi;

seq(print(seq(nops(T(n,k)), k=1..n)), n=1..7); 
print(seq(nops(T(j, j)),j=1..26));
print(seq(nops(T(j, 1)),j=1..26));
NULL end:
GeneralTotient('totient');
GeneralTotient('cototient');
GeneralTotient('primetotient');
GeneralTotient('primecototient');
GeneralTotient('nonprimeresidue');

The Möbius representation

With Knuth's proposal to write kn for `k relatively prime to n' we can write by the Möbius inversion formula

 \sum_{1 \leq k \leq n} \left[ k \perp n \right] = \sum_{1 \leq k \leq n} \left[ k \mid n \right] \mu\left(\frac{n}{k}\right) k.

Note that by the conventions of the Iverson bracket (`the strong 0 convention´) when the Iverson-bracketed statement is false, it `annihilates anything it is multiplied by - even if that other factor is undefined´. This formula is a strong reason to adopt Knuth's notational proposal.

To give an example for this formula consider the case n = 62. The left hand side says that {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61} has 30 members. The right hand side computes 1 - 2 - 31 + 62 = 30.

A130212 A μ-based generalization of the φ(n) function.

The formula can be generalized in a way which connects 1, 2, 3,... with φ(n) in a triangle, the rows of which sum to the triangular numbers.

 T(n,k) = \sum_{0 < j < k} \left[j \mid k\right] \left\lfloor \frac nk \right\rfloor \mu \left( \frac kj \right) j.

Clearly in the case n = k we recover the previous formula.

n\k 0 1 2 3 4 5 6 7 8
0 0
1 0 1
2 0 2 1
3 0 3 1 2
4 0 4 2 2 2
5 0 5 2 2 2 4
6 0 6 3 4 2 4 2
7 0 7 3 4 2 4 2 6
8 0 8 4 4 4 4 2 6 4

Thus we conclude for n > 0

 \sum_{1 < k < n} \left\lfloor \frac nk \right\rfloor \varphi(k) = \sum_{0 < k < n}T(n,k) = \binom{n+1}{2}.

A181538 A generalization of the φ(n2) function.

In a similar way we can define a triangle which generalizes the φ(n2) function

 T(n,k) = \sum_{0 \le j \le k} \left[j \mid k\right] \text{gcd}(n,k) \mu \left( \frac kj \right) j.


n\k 0 1 2 3 4 5 6 7 8
0 0
1 0 1
2 0 1 2
3 0 1 1 6
4 0 1 2 2 8
5 0 1 1 2 2 20
6 0 1 2 6 4 4 12
7 0 1 1 2 2 4 2 42
8 0 1 2 2 8 4 4 6 32

Let A181540 = 0, 1, 3, 8, 13, 26, 29, 54, 59, 84, 93, ...

 \sum_{1 \le k \le n} \text{gcd}(n,k) \varphi(k) = \sum_{0 \le k \le n}T(n,k) = A181540(n).


Möbius and totient function of order 2


Jutta Gut's theorem

We say an integer n is not a prime power if at least two different primes divide n (see A024619). A not so well known theorem of Jutta Gut is:

Theorem: Let n be a positive integer which is not a prime power then

 \prod_{ k \in S_{n} } 2 \sin \left( k \frac{\pi}{n} \right) = 1

where Sn = { 1 ≤ k ≤ ⌊ n/2 ⌋  : kn }.


Corollary: For an integer n > 1 which is not a prime power

 2^{\varphi(n)}= \left( \prod_{k \in S_{n}} \sin \left( k \frac {\pi}{n} \right) \right)^{-2}.

A curious formula! Let us check this with Maple!

isA024619 := n -> `if`(1 < nops(numtheory[factorset](n)),1,0):

JuttaGut := proc(n)
local k;
    if isA024619(n) = 0 then 0
    else
        select(k -> igcd(n, k) = 1, [`$`(1 .. iquo(n, 2))]);
        mul(sin(Pi*k/n), k = %);
        1/%^2
    fi
end:

seq(round(evalf(JuttaGut(i))),i=1..32);
seq(isA024619(i)*2^numtheory[phi](i),i=1..32);

The corollary has a nice extension which is: 2φ(n) times the least common multiple of the proper divisors of n equals n times the sine product given above.

Corollary: For an integer n > 1

  2^{\varphi(n)} \ \text{lcm}(\text{T}_{n})  = n \left( \prod_{k \in S_{n}} \sin \left( k \frac {\pi}{n} \right) \right)^{-2}.

where Tn = { 1 < k < n  : k | n }.

Euler's totient and the multiplication theorem of Gauß

The multiplication theorem of Gauß states

 \prod_{0 \leq k \leq m-1}\Gamma \left( z+\frac km\right) = (2\pi )^{\frac 12 \left( m-1\right)} m^{\left( 1/2-mz \right) }\Gamma \left( z\right) \ .


The substitution m ← φ(n) + 1, z ← 1 / (φ(n) + 1) leads to

 \sqrt{\varphi(n)+1}\prod_{0 < k \leq \varphi(n)+1}\Gamma \left(\frac{k}{\varphi(n)+1}\right)=(2\pi )^{\frac 12\varphi(n)}.


From this we see that if n is not a prime power, then also

 \prod_{\stackrel{0 < k < n}{k \perp n}} \Gamma \left(\frac{k}{n}\right) = (2\pi)^{\frac 12\varphi (n)} .


Thus — if n is divided by at least two different primes — then

 \sqrt{\varphi (n)+1} \prod_{1 \leq k \leq \varphi (n)}\Gamma \left(\frac{k}{\varphi (n)+1}\right) =\prod\limits_{\stackrel{0 < k < n}{k\perp n}} \Gamma \left(\frac kn\right) .


For an illustration consider n = 30 = 2 * 3 * 5. Then
P := { k : k ⊥ 30 } = { 1, 7, 11, 13, 17, 19, 23, 29 },
φ(n) + 1 = card(P) + 1 = 9 and

 \prod\limits_{p\in P}\Gamma\left(\frac {p}{30}\right)=(2\pi )^4 = \sqrt{9} \prod_{0 < k < 9}\Gamma \left(\frac{k}{9}\right).

To compute the left hand side all the values of P have to be known. To compute the right hand side it is sufficent to know the cardinality of P.

  • Note that φ(n) + 1 is A039649(n).

Perfect totient number

Note that 15 = φ(15) + φ(φ(15)) + φ(φ(φ(15))) + φ(φ(φ(φ(15)))).
Therefore 15 is a perfect totient number. More precise:

Let φ(1)(n) = φ(n) and φ(i)(n) = φ(φ(i-1)(n)). Let ρ(n) denote the smallest integer k such that φ(k)(n) = 1. Then define

 \Phi(n) = \sum_{1 \le i \le \rho(n)} \varphi^{(i)}(n).

n is called a perfect totient number if Φ(n) = n.

The ρ(n) of the perfect totient numbers start 2, 3, 4, 4, 5, 5, 6, 7, 6, 8, 7,...

with(numtheory):
A082897_list := proc(N)
local k, p, n, L;
    L := NULL;
    for n from 3 by 2 to N do
        k := 1;
        p := phi(n);
        while 1 < p do k := k + p; p := phi(p) od;
        if k = n then L := L,n fi
    od;
    L
end:

A multiplicative representation of the totient function

Let p denote a prime number.

\varphi(n) = n \cdot \frac{ \prod_{p \mid n} (p - 1)} {\prod_{p \mid n} p} = n \cdot {\prod_{p \mid n} \bigg(1 - \frac{1}{p}\bigg)}.\,

The range of the product are the primes p dividing n. This formula connects four integer sequences:

Changing the point of view this is a representation of the natural numbers.

 n = \frac{A000010(n) A007947(n)} {\mid A023900(n) \mid }

This relation introduces yet another sequence,

  • A003557 the number of nilpotent elements in the ring Z/nZ,
as remarked by Laszlo Toth.

 \frac{n}{A007947(n)} = \frac {A000010(n)}{\mid A023900(n) \mid }  = A003557(n)

Now it is also natural to ask how many positive numbers in the range [1,n] are not coprime to n, i.e. to consider n − φ(n). This gives

Clearly the totient function is closely related to the prime factors of an integer.
  • A001221 is number of distinct primes dividing n, ω(n)

Exercise: Is it true that there are never more distinct primes dividing n than positive integers which are coprime to n? In other words, is φ(n) ≥ ω(n) for all n ≥ 1?

 1, 0, 1, 1, 3, 0, 5, 3, 5, 2, 9, 2, 11, 4, 6, 7, 15, 
 4, 17, 6, 10, 8, 21, 6, 19, 10, 17, 10, 27, 5, 29, 
 15, 18, 14, 22, 10, 35, 16, 22, 14, 39, 9, 41, 18, 
 22, 20, 45, 14, 41, 18, 30, 22, 51, 16, 38, 22, 34 

The coprimorial

The coprimorial of n (the product of totatives of n) is

 \varphi_{_{_{!}}}(n) = \prod_{1 < k < n} k^{\left[ k \perp n \right]}.

The corresponding sequence is A001783.

The factorset of \scriptstyle \varphi_{_{_{!}}}(n) is a reduced residue system mod n. By a reduced residue system modulo m we mean any set of φ(m) integers, incongruent modulo m, each of which is relatively prime to m. (T. Apostol, Analytic Number Theory, p.113)

In terms of cardinality this means A001221(A001783(n)) = A048865(n) as was observed by Enrique Pérez Herrero.

Since

\varphi(n) = \sum_{d\mid n} d  \  \mu\left(\frac{n}{d} \right)

where µ is again the Möbius function we also have

\varphi_{_{_{!}}}(n) = {n^{\varphi(n)}}\prod_{d|n} \bigg(\frac{d!}{d^d}\bigg)^{\mu\big(\tfrac{n}{d}\big)} .

The trivial fact

 \prod_{1 \leq k \leq n} k = \prod_{1 \leq k \leq n} k^{\left[ k \perp n \right ]} \prod_{1 \leq k \leq n} k^{\left[ k \not \perp n \right ]}

can also be written as \scriptstyle n! \ = \ \varphi_{_{_{!}}}(n) ~ \overline{\varphi}_{_{_{!}}}(n) \, where \scriptstyle \overline{\varphi}_{_{_{!}}}(n) is the noncoprimorial of n, A066570.

The multiplicative equivalent to φ(n)

The multiplicative equivalent to Euler's totient function

 \varphi(n) = \sum_{ d | n } d \ \mu(n/d)

is

 T(n) = \prod_{ d | n } d \ \mu(n/d)

Some easy facts:

  • T(n) = 0 iff n is not square-free (A013929).
  • T(n) < 0 iff n is prime.
  • T(n) = -n iff n has 1 prime factor.
  • T(n) = n^(2^(k-1)) iff n has k prime factors (k>1).

Example: T(14) = 1*(1)*2*(-1)*7*(-1)*14*(1) = 14^2 = 196.

See A190902.

Implementations with Maple

Note that some of the implementations given here are much simpler than the ones published on OEIS. For better readability they are given in a Maple-like pseudo-code (for instance 'card' replaces 'nops').

with(numtheory):

  • A000010 the totient of n, φ(n);
       n -> phi(n)
  • A023900 the (unsigned) reciprocity balance of n;
       n -> mul(i-1,i=factorset(n))
  • A007947 the square-free kernel of n;
       n -> mul(i,i=factorset(n))
  • A003557 the number of nilpotent elements in the ring Z/nZ,
       n -> n / mul(i,i=factorset(n))
  • A051953 the cototient of n.
       n -> n - phi(n) 
  • A001221 number of distinct primes, ω(n)
       n -> card(factorset(n))
  • A179179 φ(n) − ω(n)
      n -> phi(n) - card(factorset(n)) 

Bounds

PhiBounds := proc(lo, hi)
local lowBound,highBound,U,P,L,H,M;
lowBound := proc(n) local l; 
l := ln(ln(n)); n/(exp(gamma)*l+3/l) end;
highBound := proc(n) n-sqrt(n) end;
phiValue := proc(n) numtheory[phi](n) end;
U := select(k -> 1 < nops(numtheory[factorset](k)),[`$`(lo..hi)]);
P := plots[listplot]([seq([i, phiValue(i)], i=U)],color=red);
L := plot(lowBound(x), x=lo..hi, color=blue);
H := plot(highBound(x),x=lo..hi, color=blue);
M := plot((lowBound(x)+highBound(x))/2, x=lo..hi, color=green);
plots[display](P,L,H,M) end;

An application of the bounds is the computation of the even nontotients, i. e. even n such that phi(m) = n has no solution (A005277).

A005277_list := proc(n) local L,P,p,i;
P := {seq(2*i,i=7..iquo(n,2))};
L := ceil(n^2/(exp(gamma)*ln(ln(n))+3)):
for i from 14 to L do
   p := numtheory[phi](i);
   if p <= n then P := P minus {p} fi;
od: 
sort(convert(P, list)) end:

A recreational problem

Assume n an integer which is divisible by at least two primes. Show that

 \sum_{1 \le k \le n} \cos(2 \pi k /n) \gcd(k,n) = \sum_{1 \le k \le \lfloor n/2 \rfloor} - \log_{\sqrt{2}}\left(\sin(\pi k / n )\right)[k \perp n].

RHS := proc(n) local k; 
add(-log[sqrt(2)](sin(Pi*k/n)),
k=select(k->igcd(n,k)=1,[$1..iquo(n,2)])) end;
LHS := proc(n) local k; add(cos(2*Pi*k/n)*igcd(k,n),k=1..n) end;
IsNotPrimePower := n->1<nops(numtheory[factorset](n)):
R := select(k->IsNotPrimePower(k),[$1..60]);
seq(round(LHS(n)),n=R); seq(round(RHS(n)),n=R);

See also

Personal tools