Relación entre un parámetro y la cardinalidad de un conjunto

Question

Para algunos fijos $n \in \mathbb{N}$ Tengo un conjunto (dependiente del parámetro $p$ )

$$ M(p) = \left\{ \, (i,j) \mid i \cdot j \le p, \; (i,j) \in \{ \, 1,2,3,\ldots,2^n \, \}^2 \, \right\};$$

Si conozco una cardinalidad $|M(p)|$ ¿qué puedo decir sobre $p$ ?

Incluso para $0 < |M| < 2^{2n}$ y $p \in \mathbb{N}$ la solución no es única (gracias a los comentarios de abajo)... No sé realmente cómo enfocar este problema, por lo que estaría satisfecho con cualquier mapeo $f(n) = p \Rightarrow |M(p)| = n$ (ampliado a $p \in \mathbb{R}$ ).

Answer 1

Si $n \gt \lceil \log_2 p \rceil$ no importa lo que $n$ es, por lo que inicialmente se podría suponer que es lo suficientemente grande e ignorarlo. Entonces, $M(p)=\sum_{k=1}^p\lfloor \frac pk \rfloor$ . La solución será entonces única como $M(p+1) \ge 2+M(p)$ considerando el primer y el último término de la suma para $M(p+1)$ en comparación con el primer término en $M(p)$ . Un límite superior para $M(p)$ es $pH_p$ , donde $H_p$ es el $p^{\text{th}}$ Número armónico . Esto da $M(p) \ge p \log p+p\gamma$ . Teniendo en cuenta que los $n$ la suma se convierte en $M(p,n)=\sum_{k=1}^{2^n}\min (\lfloor \frac pk \rfloor,2^n)$ pero no veo una manera fácil de abordar esto.