Question

Came up with a simple little problem for dan to play with just now lol

Answer 1

For what numbers is this true:

\[\Omega(n)=\pi(n)\]

Answer 2

@dan815

Answer 3

@dan815

Answer 4

Big omega?

Answer 5

\(\Omega(n)\) is the number of prime factors of \(n\) with multiplicity
http://oeis.org/wiki/Omega(n),_number_of_prime_factors_of_n_(with_multiplicity)

Answer 6

Since dan died I guess anyone else is free to try to answer this, it shouldn't be too difficult knowing that and that the other function is the prime counting function.

Answer 7

well omega function is always increasing, so it seems it will be greater for nearly all numbers.

Only possible cases where they are equal would be n = 1,2,4

Answer 8

Yeah, that's it. :D

Answer 9

oh ok i was kinda hoping there would be an exception but just couldn't think of it

Answer 10

Yeah I was hoping so too, unfortunately not. Maybe there's some way to alter this slightly so that it's a more interesting statement though.

Answer 11

\[\pi(n) = \Omega(n)^2\]

Answer 12

Ok I just made some of these functions so I could quickly find them without thinking, here are all the n that satisfy that new equation for less than 10,000:

1
2
9
10
27
28
54
56

Answer 13

I'm pretty willing to bet that these are all solutions too, come to think of it maybe we could/should look at the general set of sequences generated by:

\[\pi(n) = \Omega(n)^k\]

maybe? I dunno haha.

Answer 14

I ran some quick program on it testing for values less than 10,000 still for each k, I dunno if anyones into this or not haha, but here it is anyways:

So for the formula \(\pi(n)=\Omega(n)^k\) I have listed:

k: values of n that satisfy it.

1: 1 2 4
2: 1 2 9 10 27 28 54 56
3: 1 2 21 22 105 696 700
4: 1 2 55 57 58
5: 1 2 133 134 1545 1547 8162 8164
6: 1 2
7: 1 2 721 723

I'm pretty sure the lists go higher for 6, I just didn't check high enough.

Answer 15

interesting. i guess the sequences will all be finite, as the pi function will outpace omega for any k eventually?

Answer 16

How about \[\Omega(n) = \Omega(\pi(n)) \] ?

Answer 17

is the solution set infinite?

Answer 18

hmm interesting, I'll throw it into my program and see if it suggests that it's never ending real fast

Answer 19

what program are you using?

Answer 20

There are 2009 less than 10000 numbers that satisfy that equation \(\Omega(n) = \Omega(\pi(n))\)

I'm using some methods I made up with Java, I could paste it if you want to play with it, give me a sec.

Answer 21

i see and you store pi and Omega values pre-computed in a table?

Answer 22

yeah my guess is the set will be infinite, just purely from probabilistic POV

Answer 23

Nah, I just have a sieve that calculates them when I need them although I probably should do that.

Answer 24

thanks for sharing the interesting problem!

Answer 25

Haha thanks for joining me in playing around. I like that last suggestion, even though this is never true:
\[n = \pi(n)\]
It's kinda interesting to think that this might be true for infinitely many values?
\[\Omega(n) = \Omega(\pi(n))\]

I wouldn't mind trying to prove this somehow.

Answer 26

Ok in my attempt to probe the situation, I tried letting n be a prime, call it p. Then

\[\Omega(p)=\Omega(\pi(p))\]
since I know that \(\Omega(p)=1\) that means:
\[1= \Omega(\pi(p))\]
or in other words,

\(\pi(p)\) is a prime number.

So I conjecture that there are infinitely many cases where \(\pi(p)\) is a prime when \(p\) is prime.

Answer 27

(If that is true, then that formula also has infinitely many solutions.)

I think it might be, since the function \(\pi(n)\) takes on the value of every prime at some point. It seems like it would be strange for at some point every time you evaluate \(\pi(n)\) for n being a prime that you get only composite numbers.

Hmmm

Answer 28

Does anyone have a proof for the first problem ?

Answer 29

This one :
the only solutions of \(\Omega(n) = \pi(n)\) are \(1, 2, 4\)

Answer 30

I have a proof, should I say it or leave it open?

Answer 31

Does it depend on Bertrand's conjecture ?

https://en.wikipedia.org/wiki/Bertrand%27s_postulate

Answer 32

Nope, it's nothing quite so complicated. Or at least I don't think it is unless I've got some flaw in my proof which is completely likely too.

Answer 33

the proof i have uses bertrand's conjecture..
may i see your prooof ?

Answer 34

Here is outline of my proof :

\(\Omega(n) \le \log_2n\) and bertrand's postulate together imply \(\Omega(n) \lt \pi(n)\) for all \(n\gt 4\)

Answer 35

I had typed up some stuff and my computer froze. I think my "proof" ultimately relied on a non-rigorous assumption that:

\[k < \pi(2^k)\]

is true for k > 2.

Answer 36

Isn't it same as saying that there exists at least one prime between \(2^{k-1}\) and \(2^k\) ?

Answer 37

Yeah, more or less, but it doesn't have to be, if there are 2 primes between \(2^{k-2}\) and \(2^{k-1}\) there doesn't have to be one between \(2^{k-1}\) and \(2^k\) I guess.

Answer 38

Any counterexample ?

Answer 39

Bertrand's conjecture :

\(n \lt p \lt 2n\)

letting \(n = 2^{k-1}\) we get \(2^{k-1}\lt p \lt 2^k\)

see anything wrong in above argument ?

Answer 40

nope, looks good, I guess that's the final piece in my proof, so I was using Bertrand's conjecture I guess haha

Answer 41

My proof is then this, for n sufficiently large,
\[\Omega(n) < \pi(n)\]
We can replace all the factors of n with 2 and prove the stronger statement:
\[\Omega(n) < \pi(2^{\Omega(n)}) \le \pi(n)\]

which relies on Bertrand's conjecture, so it's proven.

Answer 42

\[\pi(2^k) - \pi(2^{k-1})\ge 1\\~\\ \implies \sum\limits_{k=1}^{n}[\pi(2^k) - \pi(2^{k-1})\ge 1] \\~\\ \implies \pi(2^n) \ge n \]

Answer 43

Yeah I guess the strict inequality depends on the observation that there are two primes between 2^2 and 2^3

Answer 44

;;;

Answer 45

@Kainui I agree with your argument on the second problem. The argument the solution set for \[\Omega(\pi(n))=\Omega(n)\] is infinite can be made like this: start with some n, find the smallest next n for which pi(n) is prime (there are infinitely many such n). By definition, that n is prime and so it satisfies the above equation. So I guess this turns out not be as interesting as I thought. Thanks for your thoughts.