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

x equals any whole number.

y equals the number of prime factors of x.

You plot those points, then find a line of best fit.

What would the equation for that line be?

Also; why?

$x = 48$

$y = 5$

Because $48 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3$

share|cite|improve this question
A vertical line at x = that whole number. More seriously, can you give some clarification as to what these "points" are and how you find them? – El'endia Starman Sep 6 '11 at 22:06
@El'endia I think the OP means plotting the points $(x,y)$ for all $x$, where $y$ is the number of prime divisors of $x$, and drawing a best fit line through all of them. – Srivatsan Sep 6 '11 at 22:09
Sure. Editing question now. – Peter Sep 6 '11 at 22:09
Since there are infinitely many points, and the true relation is manifestly not linear, what does a "best fit" even mean here? – Henning Makholm Sep 6 '11 at 22:25
@Peter: It should be pointed out that $48 = 2^4 \cdot 3$, not $2^5 \cdot 3$. – JavaMan Sep 6 '11 at 22:27
up vote 4 down vote accepted

It's easiest to think in terms of the partial sums of this function (number of prime factors of 1, plus number of prime factors of 2, plus ..., plus number of prime factors of n). Call this function $f(n)$. What does the best curve for $f(n)$ look like? Well, $f(n) \approx n/2 + n/3 + n/4 + n/5 + n/7 + n/8 + n/9 + \cdots + n/p^k$ for $p$ prime, $p^k < n$. Why? Because approximately $n/2$ of the numbers less than $n$ are divisible by 2 once, $n/3$ are divisible by 3 once, $n/4$ are divisible by 2 twice, etc.

So what does that sum look like? Well, $1/p + 1/p^2 +\cdots + 1/p^k = \frac{p^k - 1}{p^k (p-1)}$, which is approximately $1/(p-1)$. So

$f(n) \approx \sum_{p\leq n} \frac{1}{p-1}$

where the sum is over primes.

Your function is approximately the derivative of $f(n)$, which can be approximated by $1/(n-1)$ times the probability that $n$ is prime, or roughly $1/n \ln n$.

share|cite|improve this answer
Yeah, I realized that after I posted, and have modified my answer accordingly. – Craig Sep 6 '11 at 23:59
Your answer is puzzling. Surely the number of prime factors cannot be smaller than 1, right? (Also, the sum $\sum_{p < x} 1/p$ is like $\log \log x$.) – Srivatsan Sep 7 '11 at 0:01
Yes, it should be $f(n) \approx n \sum_{p\leq n} 1/(p-1) \approx x \ln \ln x$, which gives his function is $\ln \ln x + \frac{1}{\ln x}$ and we can drop the latter term asymptotically. I really shouldn't post when I'm this tired. – Craig Sep 7 '11 at 0:21
Ok. Nice. I'll vote it up. – Srivatsan Sep 7 '11 at 0:22

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.