Post Reply 
(50g) Möbius function (MOB)
03-17-2018, 09:38 PM
Post: #6
RE: (50g) Möbius function (MOB)
(03-16-2018 02:34 PM)Joe Horn Wrote:  The Möbius function, used in number theory, usually written as μ(n) but called MOB(n) here, is defined thus:
  • MOB(n) = 0 if n has a squared prime factor.
  • MOB(n) = 1 if n is a square-free positive integer with an even number of prime factors.
  • MOB(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
Examples:
  • MOB(32) = 0 because it has a squared prime factor (it can be divided by 2^2).
  • MOB(33) = 1 because it is square-free and has an even number of prime factors (3 and 11).
  • MOB(30) = -1 because it is square-free and has an odd number of prime factors (2, 3, and 5).
Here is an HP 50g program that returns MOB(n) for any positive integer n.

Code:
\<< 
  IF DUP 1 -
  THEN FACTORS AXL DUP SIZE 2. / 2. + RDM TRAN AXL EVAL 1. +
    IF \PILIST 1. SAME
    THEN SIZE 2. MOD -2. * 1. + R\->I
    ELSE DROP 0
    END
  END
\>>

BYTES: 132.5 #2EE7h

I wrote a similar program a few years ago for a similar reason (playing around with number theory). It is longer but also quite a bit faster:
Code:

\<<
  IF DUP 1 >
  THEN FACTOR
    IF DUP TYPE 9. SAME
    THEN DUP \->STR
      IF "^" POS
      THEN DROP 0
      ELSE SIZE 1. + 2. / 1 SWAP 2. MOD { NEG } IFT
      END
    ELSE DROP -1
    END
  END
\>>

I imagine that an even faster program could be made by combining aspects of both programs, and I may give it a shot when I have some spare time. However, I'm sure that Gerald's sysRPL version will put both of ours to shame!

John
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
(50g) Möbius function (MOB) - Joe Horn - 03-16-2018, 02:34 PM
RE: (50g) Möbius function (MOB) - DavidM - 03-16-2018, 07:25 PM
RE: (50g) Möbius function (MOB) - John Keith - 03-17-2018 09:38 PM
RE: (50g) Möbius function (MOB) - pier4r - 03-17-2018, 11:12 PM



User(s) browsing this thread: 1 Guest(s)