Essays/Totient Function

From J Wiki
Jump to: navigation, search

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



Contributed by Roger Hui.