(50g) Möbius function (MOB)

[Joe Horn]

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

[Luigi Vampa]

Thanks for sharing. Your PDQ is more practical for good, but MOB certainly gives food for thought to avoid any prospect cognitive starvation! :O)

[DavidM]

(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...

Neat program, Joe, and well done!

I recognize a couple of the sequences from having worked on a certain library lately. But while I can understand your code, I'm afraid the wikipedia function description leaves my head spinning as to what you might intend to do with this now that you have it. Are you using it for something special? Or would that description leave my head spinning the opposite direction?

[Gerald H]

Here a Sys version of the important function:

Size: 102.

CkSum: # 22A4h

Code:

::
  CK1&Dispatch
  # FF
  ::
    {
      ROTDROPSWAP
      %1
      EQUALcase
      FPTR2 ^RNEGext
      FPTR2 ^DROPZ0
    }
    1LAMBIND
    ::
      FPTR2 ^ZAbs
      FPTR2 ^DupQIsZero?
      caseSIZEERR
      FPTR2 ^DupZIsOne?
      ?SEMI
      FPTR2 ^MZSQFF
      #2/
      ZINT 1
      SWAP
      ZERO_DO
      1GETLAM
      COMPEVAL
      LOOP
    ;
    ABND
  ;
;

[Joe Horn]

(03-16-2018 07:25 PM)DavidM Wrote:  

(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...

I'm afraid the wikipedia function description leaves my head spinning as to what you might intend to do with this now that you have it. Are you using it for something special? Or would that description leave my head spinning the opposite direction?

Short answer: I use it mostly when playing around with multiplicative functions, as explained here: https://brilliant.org/wiki/mobius-functi...s-function
Here's an interesting blog posting about it: https://rjlipton.wordpress.com/2011/02/2...-function/

Long answer: When playing with numbers, I always write tiny RPL routines to perform snippets of the task at hand. These are used at the time but soon abandoned and forgotten about. Such routines accumulate in RAM, and I hate to purge them because I know they were useful once upon a time, but I no longer remember what they are for. For example, the following routine is currently in my 50g, called 'PR.2' (on page 50 of my HOME directory):

\<< NPR \GSLIST OVER MODSTO EXPANDMOD OVER EULER MOB \>>

It calls MOB... but I have NO IDEA what it was intended for, nor what its name meant. Its first command is NPR, which is a global label, which no longer exists in my 50g! Many such ghosts haunt my 50g's RAM.

I also have a few other routines that call MOB, as well as routines that call THOSE routines, and so on... but I don't remember what any of them are for. They are playthings which were abandoned and forgotten as new playthings were discovered. Just goes to show that HP 50g memory is more tenacious than my own brain's memory. I suspect that many MoHPC members have similar experiences.

[John Keith]

(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

[pier4r]

(03-17-2018 02:06 PM)Joe Horn Wrote:  I suspect that many MoHPC members have similar experiences.

Guilty of the same. For this reason I normally have also a notebook as "log" of what I am doing. If possible then I write the reference to the log in a string or comment.

Like "this dir (playthings grouped) was used for the test on the 2018-03-18" . Then I check the log related to that date and I find some useful info, if I wrote them down properly.

Also with the 50g one can do tons of backups using the SD. With other systems I do not know.

[Joe Horn]

(03-17-2018 09:38 PM)John Keith Wrote:  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...

Yowza! I had thought that using FACTORS would be faster than using FACTOR because the former is faster... but that's not the only factor here (as it were). Good job!

EDIT:

(03-17-2018 09:38 PM)John Keith Wrote:  However, I'm sure that Gerald's sysRPL version will put both of ours to shame!

Yep. Timing for input of 12345678:
Joe: 0.247_s
John: 0.177_s
Gerald: 0.041_s

Gerald's shines even brighter on things like large factorials. Try 20! to see what I mean.