Essays/Totient Function

Euler's totient function $\phi (n)$ computes the sum +/1=n+.i.n ,  the number of numbers less than n co-prime to n . If the prime factorization of $n=\prod _{i}^{}p_{i}^{e_{i}}$ , then $\phi (n)=\prod _{i}^{}(p_{i}-1)\cdot p_{i}^{e_{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 Andrew Nikitin as posted to the J Forum on 2009-11-03.

---

See also

• Sum of Divisors
• MathWorld
• On-line Encyclopedia of Integer Sequences A000010

---

Contributed by Roger Hui.