odd prime numbers

Question

For $m \geq 4$, set $P_m$ to be the set of all odd prime numbers strictly less than $m$ that do not divide $m$. For example, $P_4=\{3\}$, $P_7=\{3,5\}$, $P_{15}=\{7,11,13\}$.

Now, for $n \geq 1$, set $M_n$ to be the set of all $m$ such that $|P_m|=n$. For example, $4$ belongs to $M_1$, $7$ belongs to $M_2$, and $15$ belongs to $M_3$. I have proven that for $m \geq 4$, $P_m$ is always nonempty. Here are two questions:

a) For $n \geq 1$, are all $M_n$ non-empty? My early computations seem to show that $M_{24} =\{101\}$, a singleton.

b) If $M_n$ is non-empty, what is $\max(M_n)$? Or, what is an upper bound for $\max(M_n)$?

For future reference: http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference — Todd Wilcox, Apr 30 '15 at 13:56
should it be $\max|M_n|$ rather than $\max(M_n)$ (though both might make sense)? — Mirko, Apr 30 '15 at 14:02
Yes, please disregard the first question, of course, M_n contains the n+2th prime number as Michael pointed out. — Alejandro Saldivar, Apr 30 '15 at 14:06
My main question is for Max(M_n), not Max|M_n|, though the later could also be interesting. Thank you for pointing this out, Mirko. — Alejandro Saldivar, Apr 30 '15 at 14:10
@AlejandroSaldivar $|M_n|$ appears to be approximately of the same order as $\sigma_0(n)$ — martin, May 05 '15 at 17:51

score 1 · Accepted Answer · answered Apr 30 '15 at 14:36

max$(M_n)$ is not very much greater than min$(M_n)$, which obviously has to be greater than $p_{n+1}$, the $(n+1)$th prime. Each $M_n$ includes exactly one prime number, $p_{n+2}$. You can only possibly include values up to (not including) $k-1$ more primes after that, where $k$ is determined by the maximum value such that $$ \prod_{i=2}^k p_i <p_{n+k} $$

So the values where $k$ increases are $\{3,15,105,1155,\ldots\}$, the primorials with $2$ divided out.

Empy2 · Answer 2 · 2015-04-30T17:18:38.393

http://en.wikipedia.org/wiki/Primorial
This article states that the product of all the odd primes below $m$ is roughly $n=\frac12e^m$.
There are roughly $m/\log m$ primes below $m$.
So numbers below $n$ have at most $k=\log(2n)/\log\log(2n)$ different odd prime factors.
A rough upper bound on $M_n$ is $p_{n+k}$
Since the numbers are near $p_{n+k}\approx n\log n$, instead of near $n$, I should adjust $k$ to $\hat{k}=\log(2n\log n/\log\log(2n\log n)$, but $\hat{k}$ is still near $\log n/\log\log n$

odd prime numbers

2 Answers2