Question

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

Answer 1

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

Answer 2

( I have no Idea what this is sorry haha )

Answer 3

that omega is a sample space? lol

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

er greater than that*

Answer 10

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\)

Answer 11

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\)

Answer 12

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'

Answer 13

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

Answer 14

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

Answer 15

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.

Answer 16

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.

Answer 17

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\)

Answer 18

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\)

Answer 19

I also wrote some code to test for the values under 65536:

http://ideone.com/RVxsVk

Answer 20

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

Answer 21

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

Answer 22

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

Answer 23

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?

Answer 24

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

Answer 25

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

Answer 26

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.

Answer 27

lol, reading too much /r/math?

Answer 28

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

Answer 29

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.

Answer 30

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.

Answer 31

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

Answer 32

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.