1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number of unique prime factors of n is O(log n/(log log n))?

  1. Feb 10, 2015 #1
    1. The problem statement, all variables and given/known data

    Let [itex]f(n)[/itex] denote the number of unique prime factors of some positive integer [itex]n > 1[/itex]. Prove that [itex]f(n) \in \mathcal{O}\left(\dfrac{\log n}{\log \log n}\right)[/itex]

    2. Relevant equations

    3. The attempt at a solution

    Since every prime number except 2 is prime, an upper bound on the number of prime factors of any [itex]n[/itex] would be [itex]k[/itex] such that
    [tex]\ln n=\sum_{i=1}^{k}\ln\left(2i-1\right)[/tex]
    Using AM-GM inequality,
    [tex]\sum_{i=1}^{k}\ln\left(2i-1\right)\geq k\sqrt[k]{\prod_{i=1}^{k}\left(2i-1\right)}=k\sqrt[k]{n}[/tex]
    The best I can arrive at is:
    [tex]\ln\ln n\geq\ln k+\dfrac{1}{k}\ln n[/tex]
    which is ugly. I've also tried attacking this with
    instead, but this makes my inequality uglier.

    What should I do? Thanks!
  2. jcsd
  3. Feb 10, 2015 #2


    User Avatar
    2017 Award

    Staff: Mentor

    I don't understand your approach.
    I guess that last word should be "odd", otherwise the statement is odd (sorry ;)).
    What does the next equation say? That equation has no solution for most n, I would expect an inequality here.

    How do you get the equation below "Using AM-GM inequality,"?
  4. Feb 10, 2015 #3
    Haha, yes it should read "odd".

    The left hand side of the inequality is the arithmetic mean while the right hand side is the geometric mean:

    [tex]{\displaystyle \dfrac{\sum_{i=1}^{k}\ln\left(2i-1\right)}{k}\geq\sqrt[k]{\prod_{i=1}^{k}\left(2i-1\right)}}[/tex]

    I don't think this cuts through the problem though. :(
  5. Feb 10, 2015 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I would approach this another way entirely.
    For any prime p < n, what is the probability that p|n?
    Are these probabilities independent?
    Using that, what is the average number of different primes that divide n?
    To go further, need to use the usual formula for the density of primes. I assume you are allowed to use that.

    Interestingly, I don't get the given answer. Seems too high. Is the ∈ symbol denoting 'behaves like' or 'is bounded above by'?
  6. Feb 10, 2015 #5
    It means [itex]{\displaystyle \limsup_{x\rightarrow\infty}\left[p\left(n\right)/\left(\dfrac{\log n}{\log\log n}\right)\right]<\infty}[/itex].

    Alternatively, [itex]\exists c,n_{0} c\geq0[/itex] and for all [itex]n\geq n_{0}[/itex], such that [itex]\left|p\left(n\right)\right|\leq c\dfrac{\log n}{\log\log n}[/itex].

    I believe that means [itex]p\left(n\right)[/itex] is within some constant multiple of [itex]\dfrac{\log n}{\log\log n}[/itex] neglecting small [itex]n<n_0[/itex]. So we don't need a very strong bound.
  7. Feb 10, 2015 #6


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well, no, that would mean it is asymptotically like ##\dfrac{\log n}{\log\log n}##, whereas all your other statements say it is asymptotically bounded above by ##\dfrac{\log n}{\log\log n}##.
    I make the asymptotic behaviour ##\ln\ln n##. If so, the given expression is indeed an asymptotic upper bound, but a very loose one.

    Have you tried answering my other questions?
  8. Feb 10, 2015 #7
    I will think about your approach. It seems to me that my approach would suffice if I can show that [itex]
    Sorry I accidentally posted before answering your other questions. I'm still thinking about your approach. Our professor did emphasize that we didn't need to and shouldn't rely on the density of primes to prove this proposition. That seems to prevent your approach.

    Hm, I'm getting confused now. Doesn't it mean that [itex]p\left(n\right)[/itex] is bounded above by some constant multiple of [itex]\dfrac{\ln\ln n}{\ln n}[/itex] as well as below by the negative of the same constant multiple of [itex]\dfrac{\ln\ln n}{\ln n}[/itex]? Is this what you mean by "asymptotically behaves like" instead of "asymptotically bounded above by"?

    Since [itex]p\left(n\right)>0[/itex] for all [itex]n>0[/itex], doesn't this suffice for the lower bound condition of [itex]p\left(n\right)\in\mathcal{O}\left(...\right)[/itex] so this reduces to a problem of finding the upper bound?
  9. Feb 10, 2015 #8


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, 'asymptotically behaves like' would mean ##0 < {\displaystyle \lim_{x\rightarrow\infty}\left[p\left(n\right)/\left(\dfrac{\log n}{\log\log n}\right)\right]<\infty}##
    Fair enough.
  10. Feb 10, 2015 #9
    I see - thanks!

    Yeah. I've been staring at my approach and it seems to get me to [itex]\mathcal{O}\left(\dfrac{\ln n}{\sqrt[n]{n}}\right)[/itex], which is still too loose. I really admire the people who led all the way to the PNT.
  11. Feb 10, 2015 #10


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    How about Sterling's formula? I think that'll do it. But you don't need to go to the trouble of eliminating even factors, that makes little difference.
  12. Feb 10, 2015 #11
    I think Sterling's formula works and is cleaner than AM-GM on odd factors. I should've done that.

    I got the production function in the geometric part wrong, otherwise I realized that approach works too after a few simplifying assumptions (as you've pointed out, this bound is really weak).

    Thanks so much!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted