Mobius function “recursion”

Update 18.2.2017:

The recurrence for the Möbius function is:
\mu(1)=1
n>1:
\mu(n) = -\underset{\underset{d<n}{d|n}}{\sum} \Lambda(d)

The recurrence for the von Mangoldt function is:
\Lambda(n) = \log(n)-\underset{\underset{d<n}{d|n}}{\sum} \Lambda(d)

The recurrence for the Euler totient function is:
\phi(n) = n-\underset{\underset{d<n}{d|n}}{\sum}\phi(d)

The recurrence for the Dirichlet inverse of the totient function a(n)is:
\frac{a(n)}{n} = \frac{1}{n}-\underset{\underset{d<n}{d|n}}{\sum} a(d)

The recurrence for the Liouville lambda function is:
\lambda(n) = \text{sgn}\left(a-\underset{\underset{d<n}{d|n}}{\sum} \lambda(d)\right)

Where \text{sgn} is the sign function and 0<a<1

Link to math se answer:
http://math.stackexchange.com/a/853300/8530

—————————–
Someone searched the Internet for "mobius function recursion" and found this blog so this post will be about how to view the Mobius function in terms of recursion, although the mobius function “mu” doesn’t have a recurrence/recursion.  (I am not sure any more. I read in Wikipedia that it has a recursion.) Anyhow here follows examples of what the “recursion” looks like:

mu(1) = 1

mu(2)=-mu(1)=-1

mu(3)=-mu(1)=-1

mu(4)=-mu(1)-mu(2)=-1-(-1)=-1+1=0

mu(5)=-mu(1)=-1

mu(6)=-mu(1)-mu(2)-mu(3)=-1-(-1)-(-1)=-1+1+1=1

mu(7)=-mu(1)=-1

mu(8)=-mu(1)-mu(2)-mu(4)=-1-(-1)-0=-1+1-0=0

mu(9)=-mu(1)-mu(3)=-1-(-1)=-1+1=0

mu(10)=-mu(1)-mu(2)-mu(5)=-1-(-1)-(-1)=-1+1+1=1

mu(11)=-mu(1)=-1

mu(12)=-mu(1)-mu(2)-mu(3)-mu(4)-mu(6)=-1-(-1)-(-1)-0-(1)=-1+1+1-0-1=0

mu(13)=-mu(1)=-1

mu(14)=-mu(1)-mu(2)-mu(7)=-1-(-1)-(-1)=-1+1+1=1

mu(15)=-mu(1)-mu(3)-mu(5)=-1-(-1)-(-1)=-1+1+1=1

mu(16)=-mu(1)-mu(2)-mu(4)-mu(8)=-1-(-1)-0-0=-1+1-0-0=0

mu(17)=-mu(1)=-1

mu(18)=-mu(1)-mu(2)-mu(3)-mu(6)-mu(9)=-1-(-1)-(-1)-(1)-0=-1+1+1-1-0=0

mu(19)=-mu(1)=-1

mu(20)=-mu(1)-mu(2)-mu(5)-mu(10)=-1-(-1)-(-1)-(1)=-1+1+1-1=0

mu(21)=-mu(1)-mu(3)-mu(7)=-1-(-1)-(-1)=-1+1+1=1

mu(22)=-mu(1)-mu(2)-mu(11)=-1-(-1)-(-1)=-1+1+1=1

mu(23)=-mu(1)=-1

mu(24)=-mu(1)-mu(2)-mu(3)-mu(4)-mu(6)-mu(8)-mu(12)=-1-(-1)-(-1)-0-(1)-0-0=-1+1+1-0-1-0-0=0

mu(25)=-mu(1)-mu(5)=-1-(-1)=-1+1=0

mu(26)=-mu(1)-mu(2)-mu(13)=-1-(-1)-(-1)=-1+1+1=1

mu(27)=-mu(1)-mu(3)-mu(9)=-1-(-1)-0=-1+1-0=0

mu(28)=-mu(1)-mu(2)-mu(4)-mu(7)-mu(14)=-1-(-1)-0-(-1)-(1)=-1+1-0+1-1=0

mu(29)=-mu(1)=-1

mu(30)=-mu(1)-mu(2)-mu(3)-mu(5)-mu(6)-mu(10)-mu(15)=-1-(-1)-(-1)-(-1)-(1)-(1)-(1)=-1+1+1+1-1-1-1=-1

A European dot comma style Excel formula for the above:


=IF(COLUMN()=1;1;IF(ROW()=COLUMN();-SUM(INDIRECT(ADDRESS(ROW();1)&":"&ADDRESS(ROW();COLUMN()-1)));IF(ROW()>COLUMN();INDIRECT(ADDRESS(ROW()-COLUMN();COLUMN()));0)))

which is a recurrence for the Mobius function.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.