A community for students.
Here's the question you clicked on:
 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}$$
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

Empty
 one year ago
Best ResponseYou've already chosen the best response.0Even approximate bounds are good I'm just sorta playing around with something weird I found.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0( I have no Idea what this is sorry haha )

nincompoop
 one year ago
Best ResponseYou've already chosen the best response.0that omega is a sample space? lol

Empty
 one year ago
Best ResponseYou've already chosen the best response.0Nope 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

Empty
 one year ago
Best ResponseYou've already chosen the best response.0I 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.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0well, \(\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})$$

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0oops, supposed to divide both sides by \(p_1\) at the bottom there

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0the 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...

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0er greater than that*

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0now 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\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0hmm, 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\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0oops 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'

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0i may have made an error, so check my work and tell me if you concur

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0actually, I think I got the direction of bounds backwards, so now I'm not so sure...

Empty
 one year ago
Best ResponseYou've already chosen the best response.0Well 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.

Empty
 one year ago
Best ResponseYou've already chosen the best response.0If 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.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0yeah, 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\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0in 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\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I also wrote some code to test for the values under 65536: http://ideone.com/RVxsVk

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0if 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, ...

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0note 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

Empty
 one year ago
Best ResponseYou've already chosen the best response.0Interesting, this seems to be quite a bit more complicated than I was expecting which is kind of fun

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0so 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?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0indeed, 1001 = 7 * 11 * 13, and even repeated primes work sometimes: 11 * 13 * 13 = 1573, but 7 * 7 * 11 = 539 is absent

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0so it fails for primes bigger than five, and then certain products of these primes

Empty
 one year ago
Best ResponseYou've already chosen the best response.0Maybe 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.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0lol, reading too much /r/math?

Empty
 one year ago
Best ResponseYou've already chosen the best response.0Oh 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

Empty
 one year ago
Best ResponseYou've already chosen the best response.0I 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.

Empty
 one year ago
Best ResponseYou've already chosen the best response.0Right 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.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0well, 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

Empty
 one year ago
Best ResponseYou've already chosen the best response.0I 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.
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.