Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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
    
@Pranasas: Yes, you are correct. I have fixed it. –  Ross Millikan Jul 9 '13 at 13:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.