# When the Sum of digits exceed the Number of Divisors

Could somebody help me prove that there are a infinite number of natural numbers for which their sum of digits exceeds the number of divisors?

If $S(n)$ denoted the sum of digits, and $\sigma_k(n)$ was the divisor function, how can I prove that there are infinite such $n$ where $S(n) > \sigma_0(n)$.

Note that there are infinite such $n$ where $S(n) < \sigma_0(n)$, for example take $n=10^k$.

If $n=10^k$, then $S(n)=1$, while $\sigma_0(n)=(k+1)^2$.

But I did not know how to prove that there are infinite such $n$ where $S(n) > \sigma_0(n)$.

I thought that such a $n$ would be $10^k-1$, but was not able to prove it.

Any help would be appreciated.

Note: This is a problem I made myself.

Any prime number has (by definition) exactly $2$ divisors, but for most $p$, the sum of the digits of $p$ is $> 2$. The only exceptions are $2$ itself and the prime numbers of the form $100 \cdots 001$. Since for each positive integer $n$ there is a prime number $n \leq p \leq 2 n$, there are an infinite number of primes not of that form. (In fact, the only primes of that form $<10^{200}$ are $11$ and $101$.)
• Well, now I am embarrassed. Could you prove that if $n=10^k-1$ then $S(n)> \sigma_0(n)$? Commented Feb 8, 2016 at 13:06
• @Δαμον Perhaps that should posed as a separate question, but note that $n = \underbrace{1 \cdots 1}_k \cdot 3^2$. Can you bound the number of factors of $\underbrace{1 \cdots 1}_k$? Commented Feb 8, 2016 at 13:09
You can go even further and show that for a specific value of $\sigma_0(n)$ you can get infinitely many $n$ such that the sum of digits is greater than $\sigma_0(n)$.
Travis already demonstrated this for $\sigma_0(n) = 2$, which corresponds to the primes. For $\sigma_0(n) = 3$, which corresponds to the squares of primes, you just have to put in a tiny bit more effort. The last digit of an odd square is $1$, $5$ or $9$. There are infinitely many primes $p \equiv 3 \pmod{10}$, so then $p^2 \equiv 9 \pmod{10}$. Since $p^2$ only has three divisors and $p^2$ has a sum of digits of at least $9$, we're done.