A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Empty

  • one year ago

When is this true? $$\frac{\Omega(n)}{2} \le \frac{\log_2(n)}{LD(n)}$$ functions: $$\Omega(n) = \text{Total number of prime divisors of n}$$ $$LD(n) = \text{Least prime divisor of n}$$

  • This Question is Closed
  1. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Even approximate bounds are good I'm just sorta playing around with something weird I found.

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ( I have no Idea what this is sorry haha )

  3. nincompoop
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    that omega is a sample space? lol

  4. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Nope it's a function that counts the total prime divisors of a number, it's also fully additive which means: $$\Omega(ab)=\Omega(a)+\Omega(b)$$ So an easy way to test it is just try out an example, $$\Omega(20)=3$$ $$\Omega(5)=1$$ $$\Omega(2)=1$$ Yeah works out :P

  5. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I can explain it better I sorta just threw all this out there I don't know if I'm being vague or not cause I literally stayed up all night haha. I don't really know what I've explained well enough for someone new to seeing this, I've been looking at this the past 3 days or so off and on so it became second nature to me. I have to say, if the individual functions involved aren't stupid and simple then I have made a mistake in how I explained them haha.

  6. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    well, \(\log_2(p_1^{n_1} \cdots p_k^{n_k})=n_1\log_2(p_1)+\dots+n_k\log_2(p_k)\) so we we can bound it between \(N\log_2(p_1)\) and \(N\log_2(p_k)\) where \(N=n_1+\dots+n_k\) and \(p_1,\dots,p_k\) are in ascending order, so \(p_1\) is the least prime divisor here. this gives us: $$N\log_2(p_1)\le\log_2(p_1^{n_1}\cdots p_k^{n_k})\\\frac{N\log_2(p_1)}{p_1}\le\log_2(p_1^{n_1}\cdots p_k^{n_k})$$

  7. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oops, supposed to divide both sides by \(p_1\) at the bottom there

  8. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    the above proves it in the case that the least prime \(p_1=2\), since \(\Omega(p_1^{n_1}\cdots p_k^{n_k})=N\) and \(\log_2(2)=1\), but in the case the least prime is less than that...

  9. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    er greater than that*

  10. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    now consider the case where \(p_1\) is a bigger prime, so \ (p_1\ge 3\). now we want to show that $$\frac{N\log_2(p_1)}{p_1}\le\frac{N}2$$ which boils down to showing that \(\frac1x\log(x)\le\frac{\log2}2\) for \(x\ge 3\). so lets look for the maximum of \(f(x)=\frac1x\log(x)\) on \([3,\infty)\); since it's trivial to show that on this interval \(f\) is strictly decreasing on this interval as \(f'<0\) here (in fact, \(f\) has a global maximum at \(x=e\)), we can start with checking \(x=3\): $$\frac13\log3\le\frac12\log2\\3^{1/3}\le 2^{1/2}$$however this is not true, so our bound is insufficient to prove for \(p_1=3\). it is sufficient to prove for \(p_1=4\) since \(\log(4)/4=\log(2)/2\)

  11. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    hmm, if you test for \(p_1=3\), we see it is true:$$\Omega(3)=1\\\operatorname{LD}(3)=3\\\log_2(3)\approx 1.585>\frac32$$ so we see: $$\frac{\Omega(3)}2=\frac12\\\frac{\log_2(3)}{\operatorname{LD}(3)}>\frac12\\\implies \frac{\Omega(3)}2<\frac{\log_2(3)}{\operatorname{LD}(3)}$$ so it holds for all \(n\)

  12. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    oops earlier I meant that we showed that \(\frac1x\log(x)\le \frac12\log2\) holds for \(x\ge4\), which means it holds for primes \(p_1\ge5\) and thus our bound is sufficient to show that $$\frac{N\log(p_1)}{p_1}\le\frac{N}2\le\frac{\log_2(p_1^{n_1}\cdots p_k^{n_k})}{p_1}$$ since we showed it holds for \(p_1=2\) and now \(p_1\ge 5\) we only have to prove the edge case \(p_1=3\), which can be done 'by inspection'

  13. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i may have made an error, so check my work and tell me if you concur

  14. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    actually, I think I got the direction of bounds backwards, so now I'm not so sure...

  15. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Well one way I rearranged this was\[\frac{\Omega(n)}{2} \le \frac{\log_2(n)}{LD(n)}\] algebraically it's the same as this: $$2^{\Omega(n) LD(n)} \le n^2$$ However since our numbers will always be positive integers, then I can safely remove part of the inequality because $$2^{\Omega(n)} \le n$$ will always be true no matter what, with equality only holding when n is a power of 2. I don't really see how to use that to my advantage unfortunately, any ideas? Going along with what you said I found something, when n is a power of prime, \(n=p^k\) then it becomes: $$2^{\Omega(p^k) LD(p^k)} \le p^{k2}$$ $$2^{kp} \le p^{k2}$$ $$2^p \le p^2$$ So it turns out that for this special case at least that we can get a simple answer, since it only relies on the prime, if \(p=2\) or \(p=3\) it's true, but for all powers of 5 and higher is' clearly false since the only points of intersection for this graph are at p=2 and p=4. Maybe there is a way to build up other answers from this as well, but it's a pretty extreme case.

  16. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    If it helps at all, I these inequalities are both always true: \[2 \le LD(n)\]\[\Omega(n) \le \log_2(n)\] So the question I'm asking combines them both but in a backwards sense so that it's unclear when one scenario is true and the other isn't.

  17. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah, i went back and realized that I did show the following is true: $$\frac{\Omega(n)}{LD(n)}\le\frac{\log_2(n)}{LD(n)}$$ but this is too weak to show \(\Omega(n)/2\le\log_2(n)/LD(n)\) for prime \(n\ge 5\)

  18. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    in fact, if \(n\) is a prime, then we have: $$\frac12\le\frac{\log_2(n)}n$$so if \(\log_2(n)\ge n/2\), which is easy to show does not hold for primes \(n\ge5\)

  19. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I also wrote some code to test for the values under 65536: http://ideone.com/RVxsVk

  20. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    if you look at the output, the numbers that do not satisyf the inequality include primes from 5 on, up until the number 77, after which a large number of composites follow -- see: 77, 91, 119, 143, 187, 209, 221, 247, 253, 289, 299, 319, 323, 341, 361, 377, 391, 403, 407, 437, 451, 473, 481, 493, 517, 527, 529, 533, 551, 559, 583, 589, 611, 629, 649, 667, 671, 689, 697, 703, 713, 731, 737, 767, 779, 781, 793, 799, ...

  21. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    note that 77 = 7 * 11, 91 = 7 * 13, 119 = 7 * 17, and then 143 = 11 * 13, 187 = 11 * 17, 209 = 11 * 19, 253 = 11 * 23, 319 = 11*29 and so on

  22. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Interesting, this seems to be quite a bit more complicated than I was expecting which is kind of fun

  23. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so it appears that only certain (not too big, not too small) products of pairs of primes fail the inequality too, and i'll hazard a guess that this works for triples of primes too?

  24. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    indeed, 1001 = 7 * 11 * 13, and even repeated primes work sometimes: 11 * 13 * 13 = 1573, but 7 * 7 * 11 = 539 is absent

  25. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so it fails for primes bigger than five, and then certain products of these primes

  26. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Maybe I'll work through the case of \(n=p^aq^b\) with p and q primes and p<q, even though it's a special case it might have a simple solution to start discovering some pattern if there is one for the \(n=p^aq^br^c\) case although I feel like I am working too specifically and should try to adopt a more general method if possible. The main difference between the two is in its application. I may only know the least prime divisor or the total number of divisors so I'd like to know which of the two inequalities will give me a tighter upper bound, since both of these terms are really upper bounds on something called the arithmetic derivative.

  27. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    lol, reading too much /r/math?

  28. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Oh no, I haven't lately did they post something about the arithmetic derivative recently? I sorta just discovered this from the project euler question and every so often I'll play around with it. https://projecteuler.net/problem=484

  29. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I spent probably way too much time on that question with wio about a year ago but we kept getting side tracked because it sorta surprised me that it maintains a lot of nice calculus rules such as the power, chain, and quotient rules.

  30. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Right now I'm trying to look into "eigenvalues" of differentiation, so if there are a finite number of pairs of twin primes, we can multiply them all together to get some number \(b\), and \[b'=Bb\] where the "eigenvalue" \(B\) is Brun's constant. Really though the arithmetic derivative seems to be completely useless unfortunately oh well, still fun to wingspan around with lol.

  31. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    well, if you define it in terms of the Leibniz rule (i.e. declare it a derivation), there are only so many possible derivations we can choose from, and p' = 1 is a nice property

  32. Empty
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I see something, starting at this point: \[2^{\Omega(n)LD(n)} \le n^2\] I can write the left and right sides as products with \[n=\prod_{i=1}^{\Omega(n)}p_i\] Plugging in and rewriting \[\prod_{i=1}^{\Omega(n)}2^{LD(n)} \le \prod_{i=1}^{\Omega(n)}p_i^2\] Now I can divide them term for term since they contain the same amount. \[1 \le \prod_{i=1}^{\Omega(n)}\frac{p_i^2}{2^{LD(n)}}\] I think I can take this a little further: \[1 \le \prod_{i=1}^{\Omega(n)}\frac{p_i^2}{2^{p_1}}\] Basically \(\Omega(n)\) is not particularly important, I can sort of just see that unless the smallest prime is really large and the total number of factors is small then it's likely to be false. So better than nothing but this could probably stand to be improved.

  33. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.