MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 $\omega(n)$ be the number of distinct prime factors of a natural number $n$.

Note that $\omega(n)=0\iff n=1$, and that $\omega(24)=\omega(2^3\cdot 3^1)=2\ (\not = 4)$.

(For more details, you can see "Distinct Prime Factors" on wolfram math world)

Then, for $m\in\mathbb N$, let $S_m=\{n|n\in\mathbb N, \omega(n)=m\}$. Also, Let $N_m(x)$ be the counting function that gives the number of the elements of $S_m$ less than or equal to $x$, for any real number $x$. See the line graph below. This graph shows $N_m(x)\ (m=1,2,3,4)$ in $1\lt x\le 2309=2\cdot3\cdot5\cdot7\cdot11-1.$ Note that $N_m(2309)=0$ for $m\ge 5$, and that $\omega(2310)=\omega(2\cdot 3\cdot 5\cdot 7\cdot 11)=5$.

$\ \ \ \ \ \ \ \ \ \ $enter image description here

In addition to this, let $P_m(x)=\frac{N_m(x)}{x}\times 100$. See the line graph below. This graph shows $P_m(x)\ (m=1,2,3,4)$ in $1\lt x\le 2309=2\cdot3\cdot5\cdot7\cdot11-1.$

$\ \ \ \ \ \ \ \ \ \ $enter image description here

Then, here are my questions.

Question : Are the followings true?

$(1)$ For every $m\in\mathbb N$, $N_m(x)=O(x)\ (x\to\infty)$.

$(2)$ For every $m\in\mathbb N$, $\lim_{x\to\infty} P_m(x)=0$.

$(3)$ If $x\ge 50$, then $P_2(x)\gt P_m(x)$ for every $m\ge 3$.

The above graphs led me to the these conjectures, but I don't have any good ideas. I would like to know any relevant references. Can anyone help?

share|cite|improve this question
up vote 7 down vote accepted

I don't quite understand question (1). Isn't $N_m(x) \leq x$ trivially? You seem to be interested in fixed $m$. Then an affirmative answer to (2) and a negative answer to (3) follows from a classical extension of the prime number theorem due to Landau. See, for example,

In fact, the answer to (2) is "yes, uniformly in $m$." Indeed, a theorem of Hardy and Ramanujan implies that $N_m(x) \ll x/\sqrt{\log\log{x}}$ uniformly in $m$.

share|cite|improve this answer
Thank you very much for this answer! I think what I was trying to ask as $(1)$ is actually $(2)$. – mathlove Nov 24 '13 at 5:01

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.