Essays/Totient Function

Euler's totient function computes the sum +/1=n+.i.n , the number of numbers less than n which are relatively prime to n . If

$n = \prod_{p_i}^{} p_i ^ {k_i}$

is the prime factorization of n where the $$p_i$$ are distinct primes, then

$\phi(n) = \prod_{p_i}^{} (p_i-1) \cdot p_i ^ {k_i-1}$

The formula readily translates into J,

totient=: (- ~:)&.q:

noting that q:^:_1 is */ .

   totient 28
12
   +/ 1 = 28 +. i.28
12

   totient 1
1
   totient 7
6
   totient !40x
121343746763281707274905415180804423680000000000

   x=: 637 274
   +./ x
1
   */ totient x
68544
   totient */ x
68544

In J6.01, the totient function can also be computed by 5 p: y . Thus:

   5 p: !40x
121343746763281707274905415180804423680000000000

The totient function can also be computed as * -.@%@~.&.q: ; the present simpler definition is due to AndrewNikitin as posted to the J Forum on 2009-11-03.

Essays/Totient Function

See also