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!


Advertisements

Actions

Information




%d bloggers like this: