Moebius transforms
02-18-2019, 10:20 PM (This post was last modified: 02-18-2019 10:35 PM by John Keith.)
Post: #1
 John Keith Senior Member Posts: 451 Joined: Dec 2013
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.
 « Next Oldest | Next Newest »

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