Post Reply 
Moebius transforms
02-18-2019, 10:20 PM (This post was last modified: 02-18-2019 10:35 PM by John Keith.)
Post: #1
Moebius transforms
Here are three Moebius transform related programs. They are most useful for integer sequences related to the divisor function, the Moebius Mu function, and the Euler Phi function.

First, the Moebius transform. The program takes a list of integers and returns a list of integers of the same length. It requires ListExt and MOB, Gerald H's program for Mu(n) detailed in this thread.

Code:

\<< DUP SIZE R\->I \-> n
  \<< 1 n
    FOR k k DIVIS DUP2 LPICK SWAP REVLIST Mu * LSUM SWAP
    NEXT DROP n \->LIST
  \>>
\>>

Next, the inverse Moebius transform. Also requires ListExt.

Code:

\<< DUP SIZE R\->I \-> n
  \<< 1 n
    FOR k DUP k DIVIS LPICK LSUM SWAP
    NEXT DROP n \->LIST
  \>>
\>>

Finally, a program for Dirichlet convolution, a closely related operation. Note that this is not a convolution of two lists, but rather of two functions over a list of the natural numbers.

The program requires two programs for the desired functions on levels 2 and 3, and an integer representing the length of the list to be returned on level 1.

Code:

\<< \-> f g n
  \<< 1 n
    FOR k k DIVIS DUP f EVAL SWAP REVLIST g EVAL * 0 + \GSLIST
    NEXT n \->LIST
  \>>
\>>

For example, if level 3 contains \<< MOB \>> from the second link above
and level 2 contains \<< EULER \>> and level 1 has the number 20,
the program will return the first 20 terms of A007431.

For anyone interested in this area of number theory, I also highly recommend Gerald H's SUMDIVISORS, detailed in this thread.
Find all posts by this user
Quote this message in a reply
Post Reply 




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