Essays/Mobius Function
< Essays
Jump to navigation
Jump to search
The Möbius function on positive integer n is defined as follows:
- 1 if n has an even number of distinct prime factors
- _1 if n has an odd number of distinct prime factors
- 0 if n is not square-free
The Möbius function can be computed as follows:
mobius0=: (*./@(1&=) * _1 ^ #) @ {: @ (__&q:)
mobius1=: (-@(*./)@(1&=) ^ #) @ {: @ (__&q:)
mobius2=: (*./@~: * _1 ^ #)@q:
mobius =: */ @: - @: ~: @: q:
The Möbius function is non-zero only if the prime exponents are all 1s, 1 if there is an even number of them and _1 if odd (mobius0 and mobius1). The Möbius function is non-zero only if n has distinct prime factors, 1 if there is an even number of them and _1 if odd (mobius2 and mobius).
For example:
mobius"0 >:i.5 10 1 _1 _1 0 _1 1 _1 0 0 1 _1 0 _1 1 1 0 _1 0 _1 0 1 1 _1 0 0 1 0 0 _1 _1 _1 0 1 1 1 0 _1 1 1 0 _1 _1 _1 0 0 1 _1 0 0 0
See also
Contributed by Roger Hui. The J functions previously appeared in the J Programming Forum on 2007-09-17.