3

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$

Peter
  • 1,021
  • 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 06 '11 at 22:06
  • 1
    @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 06 '11 at 22:09
  • Sure. Editing question now. – Peter Sep 06 '11 at 22:09
  • $y = x$ would be mine – The Chaz 2.0 Sep 06 '11 at 22:22
  • It sounds like you are looking for an asymptotic value of $\Omega(n)$. Here is a place to start: http://en.wikipedia.org/wiki/Average_order_of_an_arithmetic_function – JavaMan Sep 06 '11 at 22:23
  • 2
    Since there are infinitely many points, and the true relation is manifestly not linear, what does a "best fit" even mean here? – hmakholm left over Monica Sep 06 '11 at 22:25
  • Do you really want a line? You'll always find a prime between n and 2n if n>1, so whatever line you pick doesn't fit infinitely many points all that well. A quadratic equation seems at least a little better here. Cross-post with Henning. – Doug Spoonwood Sep 06 '11 at 22:27
  • 1
    @Peter: It should be pointed out that $48 = 2^4 \cdot 3$, not $2^5 \cdot 3$. – JavaMan Sep 06 '11 at 22:27
  • @DJC Thanks for pointing that out – Peter Sep 06 '11 at 22:31
  • @Henning Makholm I do see the problem now with finding a line of best fit. It would have to be arbitrary. I guess this is more of a soft question. – Peter Sep 06 '11 at 22:37
  • If we do insist on a line, $y=0$ seems like the best candidate :) – Srivatsan Sep 07 '11 at 00:09

1 Answers1

4

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$.

Michael Hardy
  • 1
Craig
  • 3,536
  • Yeah, I realized that after I posted, and have modified my answer accordingly. – Craig Sep 06 '11 at 23:59
  • 1
    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 07 '11 at 00: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 07 '11 at 00:21
  • Ok. Nice. I'll vote it up. – Srivatsan Sep 07 '11 at 00:22