Essays/Mobius Function

From J Wiki
Jump to: navigation, 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.