Tuesday 8 September 2009

CURIOUS SERIES-002

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

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

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

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

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

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

If we sum over all divisors:

$latex \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)} $

$latex \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 $latex s$ is a squarefree number and if $latex d|s$ then $latex GCD(d,d/s)=1$ and, the number of divisors , $latex \displaystyle \tau_{2}(s)=2^{\omega(s)}$, then:

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

For every number $latex n>1$:

$latex \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) $

$latex \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:

$latex a(n)=A062799(n)$

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

$latex \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!