Empty
  • Empty
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}$$
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
jamiebookeater
  • jamiebookeater
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
Empty
  • Empty
Even approximate bounds are good I'm just sorta playing around with something weird I found.
anonymous
  • anonymous
( I have no Idea what this is sorry haha )
nincompoop
  • nincompoop
that omega is a sample space? lol

Looking for something else?

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

More answers

Empty
  • Empty
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
Empty
  • Empty
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.
anonymous
  • anonymous
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})$$
anonymous
  • anonymous
oops, supposed to divide both sides by \(p_1\) at the bottom there
anonymous
  • anonymous
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...
anonymous
  • anonymous
er greater than that*
anonymous
  • anonymous
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\)
anonymous
  • anonymous
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\)
anonymous
  • anonymous
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'
anonymous
  • anonymous
i may have made an error, so check my work and tell me if you concur
anonymous
  • anonymous
actually, I think I got the direction of bounds backwards, so now I'm not so sure...
Empty
  • Empty
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.
Empty
  • Empty
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.
anonymous
  • anonymous
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\)
anonymous
  • anonymous
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\)
anonymous
  • anonymous
I also wrote some code to test for the values under 65536: http://ideone.com/RVxsVk
anonymous
  • anonymous
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, ...
anonymous
  • anonymous
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
Empty
  • Empty
Interesting, this seems to be quite a bit more complicated than I was expecting which is kind of fun
anonymous
  • anonymous
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?
anonymous
  • anonymous
indeed, 1001 = 7 * 11 * 13, and even repeated primes work sometimes: 11 * 13 * 13 = 1573, but 7 * 7 * 11 = 539 is absent
anonymous
  • anonymous
so it fails for primes bigger than five, and then certain products of these primes
Empty
  • Empty
Maybe I'll work through the case of \(n=p^aq^b\) with p and q primes and p
anonymous
  • anonymous
lol, reading too much /r/math?
Empty
  • Empty
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
Empty
  • Empty
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.
Empty
  • Empty
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.
anonymous
  • anonymous
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
Empty
  • Empty
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.

Looking for something else?

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