# Relation between a parameter and cardinality of a set

For some fixed $n \in \mathbb{N}$ I have a set (dependent on parameter $p$)

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

If I know a cardinality $|M(p)|$ what can I say about $p$?

Even for $0 < |M| < 2^{2n}$ and $p \in \mathbb{N}$ the solution is not unique (thanks to comments below)... I don't really know how to approach this problem hence I would be satisfied with any mapping $f(n) = p \Rightarrow |M(p)| = n$ (extended to $p \in \mathbb{R}$).

-
I don't know whether the ... is meant to be all the numbers between $2$ and $2^n$, or just the powers of $2$. – Gerry Myerson May 7 '13 at 12:47
If $n=1$, don't $M(2)$ and $M(3)$ both have cardinality $3$? – Gerry Myerson May 7 '13 at 12:49
@GerryMyerson Thanks for the remarks! It's meant to be all natural numbers up to $2^n$. You are also correct about solution not being unique. – Pranasas May 7 '13 at 13:00

If $n \gt \lceil \log_2 p \rceil$ it doesn't matter what $n$ is, so initially one might assume it is large enough and ignore it. Then $M(p)=\sum_{k=1}^p\lfloor \frac pk \rfloor$. The solution will then be unique as $M(p+1) \ge 2+M(p)$ considering the first and last terms in the sum for $M(p+1)$ compared to the first term in $M(p)$. An upper bound for $M(p)$ is $pH_p$, where $H_p$ is the $p^{\text{th}}$ Harmonic number. This gives $M(p) \ge p \log p+p\gamma$. Considering smaller $n$, the sum becomes $M(p,n)=\sum_{k=1}^{2^n}\min (\lfloor \frac pk \rfloor,2^n)$ but I don't see an easy way to approach this.
Thanks. I am processing your thoughts at the moment, but didn't you mean $M(p,n)=\sum_{k=1}^{2^n}\min(\lfloor \frac pk \rfloor,2^n)$ in the end? – Pranasas May 7 '13 at 13:47