(50g) Möbius function (MOB) - Printable Version

(50g) Möbius function (MOB) - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (50g) Möbius function (MOB) (/thread-10330.html)

(50g) Möbius function (MOB) - Joe Horn - 03-16-2018 02:34 PM

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

RE: (50g) Möbius function (MOB) - Luigi Vampa - 03-16-2018 03:26 PM

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

RE: (50g) Möbius function (MOB) - DavidM - 03-16-2018 07:25 PM

(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? Smile

RE: (50g) Möbius function (MOB) - Gerald H - 03-17-2018 05:58 AM

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

  ;

;

RE: (50g) Möbius function (MOB) - Joe Horn - 03-17-2018 02:06 PM

(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-function/#interesting-formulas-involving-the-mobius-function
Here's an interesting blog posting about it: https://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-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. Sad

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.

RE: (50g) Möbius function (MOB) - John Keith - 03-17-2018 09:38 PM

(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

RE: (50g) Möbius function (MOB) - pier4r - 03-17-2018 11:12 PM

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

RE: (50g) Möbius function (MOB) - Joe Horn - 03-18-2018 06:08 AM

(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! Smile

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.