## 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}$$

1. Empty

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

2. anonymous

( I have no Idea what this is sorry haha )

3. nincompoop

that omega is a sample space? lol

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

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

6. 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})$$

7. anonymous

oops, supposed to divide both sides by $$p_1$$ at the bottom there

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

9. anonymous

er greater than that*

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

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

12. 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'

13. anonymous

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

14. anonymous

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

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

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

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

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

19. anonymous

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

20. 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, ...

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

22. Empty

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

23. 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?

24. anonymous

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

25. anonymous

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

26. Empty

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

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

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

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

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

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