Revisions to Computing the Mobius function

added 29 characters in body

Source Link

edited Jul 20, 2019 at 17:05

11
2

One of the recursive formulas relating values of mobious function is $$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ But inorder to find the $\mu(n)$ we need to know the mobious values for $m < n $. Hence $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Here we are dividing $n$ by the smaller positive integers $m<n$, we don't have to know if they are factors of $n$ when $m$ has a square factor! ( $\mu(m)=0$) ,But still we have to know the factors of $m$ to conclude this!! Hence we have: $$\mu(n)=1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor + \cdots $$\begin{align} \mu(n)=&1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \\ +&\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \\ -&\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor + \cdots \end{align} Refer to this paper: https://projecteuclid.org/euclid.mjms/1513306829 for the proof of the formula.

One of the recursive formulas relating values of mobious function is $$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ But inorder to find the $\mu(n)$ we need to know the mobious values for $m < n $. Hence $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Here we are dividing $n$ by the smaller positive integers $m<n$, we don't have to know if they are factors of $n$ when $m$ has a square factor! ( $\mu(m)=0$) ,But still we have to know the factors of $m$ to conclude this!! Hence we have: $$\mu(n)=1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor + \cdots $$ Refer to this paper: https://projecteuclid.org/euclid.mjms/1513306829 for the proof of the formula.

One of the recursive formulas relating values of mobious function is $$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ But inorder to find the $\mu(n)$ we need to know the mobious values for $m < n $. Hence $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Here we are dividing $n$ by the smaller positive integers $m<n$, we don't have to know if they are factors of $n$ when $m$ has a square factor! ( $\mu(m)=0$) ,But still we have to know the factors of $m$ to conclude this!! Hence we have: \begin{align} \mu(n)=&1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \\ +&\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \\ -&\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor + \cdots \end{align} Refer to this paper: https://projecteuclid.org/euclid.mjms/1513306829 for the proof of the formula.

deleted 2 characters in body

Source Link

edited Jul 20, 2019 at 16:56

Hunde Eba

11
2

One of the recursive formulas relating values of mobious function is $$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ But inorder to find the $\mu(n)$ we need to know the mobious values for $m < n $. Hence $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Here we are dividing $n$ by the smaller positive integers $m<n$, we don't have to know if they are factors of $n$ when $m$ has a square factor! ( $\mu(m)=0$) ,But still we have to know the factors of $m$ to conclude this!! Hence we have: $$\mu(n)=1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor\sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \ +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor\sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor \cdots \$$$$\mu(n)=1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor + \cdots $$ Refer to this paper: https://projecteuclid.org/euclid.mjms/1513306829 for the proof of the formula.

One of the recursive formulas relating values of mobious function is $$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ But inorder to find the $\mu(n)$ we need to know the mobious values for $m < n $. Hence $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Here we are dividing $n$ by the smaller positive integers $m<n$, we don't have to know if they are factors of $n$ when $m$ has a square factor! ( $\mu(m)=0$) ,But still we have to know the factors of $m$ to conclude this!! Hence we have: $$\mu(n)=1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor\sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \ +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor\sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor \cdots \$$ Refer to this paper: https://projecteuclid.org/euclid.mjms/1513306829 for the proof of the formula.

One of the recursive formulas relating values of mobious function is $$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ But inorder to find the $\mu(n)$ we need to know the mobious values for $m < n $. Hence $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Here we are dividing $n$ by the smaller positive integers $m<n$, we don't have to know if they are factors of $n$ when $m$ has a square factor! ( $\mu(m)=0$) ,But still we have to know the factors of $m$ to conclude this!! Hence we have: $$\mu(n)=1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor + \cdots $$ Refer to this paper: https://projecteuclid.org/euclid.mjms/1513306829 for the proof of the formula.

added 26 characters in body

Source Link

edited Jul 20, 2019 at 16:48

Hunde Eba

11
2

One of the recursive formulas relating values of mobious function is $$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ But inorder to find the $\mu(n)$ we need to know the mobious values for $m < n $. Hence $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Here we are dividing $n$ by the smaller positive integers $m<n$, we don't have to know if they are factors of $n$ when $m$ has a square factor! ( $\mu(m)=0$) ,But still we have to know the factors of $m$ to conclude this!! Hence we have: $$\mu(n)=1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor +\sum_{a_1 < n} \sum_{a_2<a_1}\left \lfloor \dfrac {n}{a_1}\right \rfloor\left \lfloor \dfrac {a_1}{a_2}\right \rfloor -\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor\sum_{a_1 < n} \sum_{a_2<a_1}\left \lfloor \dfrac {n}{a_1}\right \rfloor\left \lfloor \dfrac {a_2}{a_3}\right \rfloor$$$$\mu(n)=1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor\sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \ +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor\sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor \cdots \$$ Refer to this paper: https://projecteuclid.org/euclid.mjms/1513306829 for the proof of the formula.

One of the recursive formulas relating values of mobious function is $$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ But inorder to find the $\mu(n)$ we need to know the mobious values for $m < n $. Hence $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Here we are dividing $n$ by the smaller positive integers $m<n$, we don't have to know if they are factors of $n$ when $m$ has a square factor! ( $\mu(m)=0$) ,But still we have to know the factors of $m$ to conclude this!! Hence we have: $$\mu(n)=1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor +\sum_{a_1 < n} \sum_{a_2<a_1}\left \lfloor \dfrac {n}{a_1}\right \rfloor\left \lfloor \dfrac {a_1}{a_2}\right \rfloor -\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor\sum_{a_1 < n} \sum_{a_2<a_1}\left \lfloor \dfrac {n}{a_1}\right \rfloor\left \lfloor \dfrac {a_2}{a_3}\right \rfloor$$ Refer to this paper: https://projecteuclid.org/euclid.mjms/1513306829 for the proof of the formula.

One of the recursive formulas relating values of mobious function is $$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ But inorder to find the $\mu(n)$ we need to know the mobious values for $m < n $. Hence $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Here we are dividing $n$ by the smaller positive integers $m<n$, we don't have to know if they are factors of $n$ when $m$ has a square factor! ( $\mu(m)=0$) ,But still we have to know the factors of $m$ to conclude this!! Hence we have: $$\mu(n)=1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor\sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \ +\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor\sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor \cdots \$$ Refer to this paper: https://projecteuclid.org/euclid.mjms/1513306829 for the proof of the formula.