(50g) Möbius function (MOB)
03-16-2018, 02:34 PM (This post was last modified: 03-16-2018 02:49 PM by Joe Horn.)
Post: #1
 Joe Horn Senior Member Posts: 1,687 Joined: Dec 2013
(50g) Möbius function (MOB)
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

<0|ɸ|0>
-Joe-
03-16-2018, 03:26 PM (This post was last modified: 03-16-2018 10:58 PM by Luigi Vampa.)
Post: #2
 Luigi Vampa Member Posts: 246 Joined: Dec 2015
RE: (50g) Möbius function (MOB)
Thanks for sharing. Your PDQ is more practical for good, but MOB certainly gives food for thought to avoid any prospect cognitive starvation! :O)

Saludos Saluti Cordialement Cumprimentos MfG BR + + + + +
Luigi Vampa +
Free42 HuaweiP10 '<3' I + + +
03-16-2018, 07:25 PM
Post: #3
 DavidM Senior Member Posts: 788 Joined: Dec 2013
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...

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?
03-17-2018, 05:58 AM
Post: #4
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (50g) Möbius function (MOB)
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   ; ;
03-17-2018, 02:06 PM (This post was last modified: 03-17-2018 02:08 PM by Joe Horn.)
Post: #5
 Joe Horn Senior Member Posts: 1,687 Joined: Dec 2013
RE: (50g) Möbius function (MOB)
(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.

<0|ɸ|0>
-Joe-
03-17-2018, 09:38 PM
Post: #6
 John Keith Senior Member Posts: 623 Joined: Dec 2013
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
03-17-2018, 11:12 PM
Post: #7
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: (50g) Möbius function (MOB)
(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.

Wikis are great, Contribute :)
03-18-2018, 06:08 AM (This post was last modified: 03-18-2018 06:35 AM by Joe Horn.)
Post: #8
 Joe Horn Senior Member Posts: 1,687 Joined: Dec 2013
RE: (50g) Möbius function (MOB)
(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.

<0|ɸ|0>
-Joe-
 « Next Oldest | Next Newest »

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