Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $s(n)$ an arithmetical function defined as $$s(n)=(p_1+1)^{e_1} (p_2+1)^{e_2} \cdots (p_m+1)^{e_m}$$ where prime factorization of $n$ is $n=p_1^ {e_1} p_2 ^{e_2} \cdots p_m^{e_m}$.
(For example, $s(49)=s(7^2)=8^2=64$, $s(60)=s(2^2 \times 3^1 \times 5^1)=3^2 \times 4^1 \times 6^1=216$)

Prove or disprove the following proposition;

$\phantom{a}\bullet$ There exists a positive integer $M$ such that $$\forall N>M(N\in\mathbb{N})\phantom{;}; \phantom{;}\sum_{n= 1}^{N}s(n)>N^2$$

share|cite|improve this question
I might be able to get a nice estimate on the summatory function for you, if you can give me some other way of representing your function, as it stands, I can give you a good estimate for $$\sum_{n=1}^N \ln(s(n))=\sum_{p\leq n}\ln(p+1)([\frac{n}{p}]+[\frac{n}{p^2}]+[\frac{n}{p^2}]...)\sim n\ln(n)$$ in addition if n is square free then we have the relation, $$s(n)=\sigma(n)$$ where $\sigma(n)$ is the divisor function. – Ethan Jan 27 '13 at 4:27
It may be helpful to realize that $s(n)$ is the sum of the divisors of $n$ counted according to their multiplicities. E.g., the divisors of $60$, so counted, are $$1,2,2,3,4,5,6,6,10,10,12,15,20,30,30,60\;,$$ whose sum is $216$. – Brian M. Scott Jan 27 '13 at 4:41
I get $\sum_{k\le n} s(k) \approx 1.337 n^2$, if I didn't flub my singular series constant. Experimentally, for $n=10000$ the sum is $1.3108 n^2$. – Erick Wong Jan 27 '13 at 5:28
up vote 3 down vote accepted

This is true. If $\nu_p(n)$ is maximal such that $p^{\nu_p(n)}\mid n$, then $$ s(n)\ge (\frac32)^{\nu_2(n)} (\frac43)^{\nu_3(n)}n. $$ Therefore, for all $i=1$, $\dots$, $2^5 3^3$, $$ s(2^5 3^3n+i)\ge (\frac32)^{\min(\nu_2(i),5)} (\frac43)^{\min(\nu_3(i),3)} (2^5 3^3 n+i). $$ Summing over $i=1$, $\dots$, $2^5 3^3$ gives \begin{eqnarray*} \sum_{1\le i\le 2^5 3^3} s(2^5 3^3n+i)&\ge&1555910n+ 785732\\ &\ge& 2.08 \sum_{1\le i\le 2^5 3^3}( 2^5 3^3n + i). \end{eqnarray*} This proves that $$ \sum_{1\le n\le N} s(n)\ge 2.08 \frac{N(N+1)}{2}>N^2 $$ whenever $N$ is a multiple of $2^5 3^3=864$. If $N$ is not a multiple of $864$, write $N=N'+N''$, where $N'$ is a multiple of $864$ and $1\le N''\le 863$. Then, since $s(n)\ge n$ for all $n$, $$ \sum_{1\le n\le N} s(n)\ge 2.08 \frac{N'(N'+1)}{2} + N' N'' + \frac{N''(N''+1)}{2} $$ which will be bigger than $$ N^2 = N'^2 + 2 N' N'' + N''^2 $$ whenever $N'\ge 22464$. Also, computation shows that $$ \sum_{1\le n\le N} s(n)> N^2 $$ whenever $24\le N\le 22463$. So, we can take $M=23$.

Asymptotically, $s(n)/n$ should behave similarly to the random variable $$ W:=\prod_p (1+\frac{1}{p})^{Z_p-1}, $$ where the $Z_p$'s are independent geometrically distributed random variables with success probability $1-\frac{1}{p}$, and $$ {\Bbb E}(W) = \prod_p \frac{p(p-1)}{p^2-p-1} \approx 2.67411. $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.