## CURIOUS SERIES-002

8 09 2009

This is the Dirichlet convolution of $\displaystyle \omega*1$:

$\displaystyle a(n)=\sum_{d|n}{\omega(d)}$

Where $\displaystyle \omega$ is the number of distinct prime factors function.

This function, $\displaystyle \omega(n)$ is an additive function:

$\displaystyle \omega(n)=\omega(d \cdot n/d ) \leq \omega(d)+\omega(n/d)$

Where the equal symbol holds iff $GCD(n/d,d)=1$

If we sum over all divisors:

$\displaystyle \sum_{d|n}{\omega(n)} \leq \sum_{d|n}{\bigg(\omega(d)+\omega(n/d)\bigg)}=\sum_{d|n}{\omega(d)}+\sum_{d|n}{\omega(n/d)}=2 \sum_{d|n}{\omega(d)}$

$\displaystyle \omega(n)\cdot \sum_{d|n}{1}=\omega(n)\cdot\tau_{2}(n) \leq 2 \sum_{d|n}{\omega(d)}=2\cdot a(n)$

If $s$ is a squarefree number and if $d|s$ then $GCD(d,d/s)=1$ and, the number of divisors , $\displaystyle \tau_{2}(s)=2^{\omega(s)}$, then:

$\displaystyle a(s)=\omega(s)\cdot 2^{\omega(s)-1}$

For every number $n>1$:

$\displaystyle a(n)=\sum_{d|n}{\omega(d)} \leq \sum_{d|n \; d\neq 1}{\omega(n)}= \omega(n) \cdot \sum_{d|n \; d\neq 1}{1}= \omega(n)\cdot(\tau_{2}(n)-1)$

$\displaystyle \omega(n)\cdot(\tau_{2}(n)-1) \geq a(n) \geq \bigg\lceil \frac{\omega(n)\cdot \tau_{2}(n)}{2} \bigg\rceil$

NOTE: Sequences in OEIS:

$a(n)=A062799(n)$

$\omega(n)=A001221(n)$

$\tau_{2}(n)=A000005(n)$

References:

[1]-A062799-Inverse Moebius transform of A001221, the number of distinct prime factors of n The On-Line Encyclopedia of Integer Sequences!
[2]-A001221-Number of distinct primes dividing n (also called omega(n)). The On-Line Encyclopedia of Integer Sequences!
[3]-A000005-d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n.. The On-Line Encyclopedia of Integer Sequences!