Essays/Totient Function
< Essays
Jump to navigation
Jump to search
Euler's totient function computes the sum +/1=n+.i.n , the number of numbers less than n co-prime to n . If the prime factorization of , then
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.