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.

A positive integer is $B$-smooth if and only if all of its prime divisors are less than or equal to a positive real $B$. For example, the $3$-smooth integers are of the form $2^{a} 3^{b}$ with non-negative exponents $a$ and $b$, and those integers less than or equal to $20$ are $\{1,2,3,4,6,8,9,12,16,18\}$.

In Ramanujan's first letter to G. H. Hardy, Ramanujan emphatically quotes (without proof) his result on the number of $3$-smooth integers less than or equal to $N > 1$, \begin{eqnarray} \frac{\log 2 N \ \log 3N}{2 \log 2 \ \log 3}. \end{eqnarray} This is an amazingly accurate approximation, as it differs from the exact value by less than 3 for the first $2^{1000} \approx 1.07 \times 10^{301}$ integers, as shown by Pillai.

Question: Knowing full well that Ramanujan only gave proofs of his own claims while working in England, I wonder if a proof of this particular estimate appears somewhere in the literature. Is this problem still open? If not, what is a reference discussing its proof?

Thanks!

share|improve this question
    
I take it that this problem is still wide open. That is, there is no closed form representation of the exact number of 3-smooth integers as a function of $N$. –  user02138 May 12 '11 at 18:42
add comment

3 Answers

Taking logs, one finds that $2^a 3^b \leq N$ if and only if $a \log 2 + b \log 3 \leq \log N.$ So estimating the number of 3-smooth integers $\leq N$ is the same as estimating the number of integer lattice points in the region $a, b \geq 0, a \log 2 + b \log 3 \leq \log N.$ The standard estimate for the number of integer lattice points in a convex region is the area of the region. In our case the region is a triangle, of area equal to $$\dfrac{1}{2}\dfrac{\log N}{\log 2}\dfrac{\log N}{\log 3},$$ which is close to the estimate you attribute to Ramanujan.

More precisely, the estimate you wrote down is equal to $$\dfrac{1}{2}\dfrac{\log N + \log 2}{\log 2}\dfrac{\log N + \log 3}{\log 3} = \dfrac{1}{2}\left(\dfrac{\log N}{\log 2} + 1\right)\left(\dfrac{\log N}{\log 3} + 1\right).$$ This probably improves the estimate coming from the area, by including correction terms coming from the integer points along the boundary of the region (in particular, the contributions coming from $a = 0$ or $b = 0$).

(The fact that these "boundary" contributions come with a multiplicity of $1/2$ seems similar to other contexts in which one approximates a discrete sum by an area, e.g. in Euler--MacLaurin summation, and perhaps thinking from that point of view would let one get a better handle on the precise estimates.)

share|improve this answer
3  
You can probably get Ramanujan's estimate by tweaking Pick's theorem. –  Qiaochu Yuan Dec 31 '10 at 8:30
    
I understood "tweaking" to mean using integral triangles to understand the area above. I suppose if we generalize Pick's theorem to irrational triangles, it would help. –  user02138 Mar 25 '11 at 15:18
add comment

For any reference requirement related to Ramanujan, it is always a good idea to check the series of volumes, titled Ramanujan's notebooks, compiled and annotated by Bruce C. Berndt and others.

This is a special case of Entry 15 in Ramanujan's second notebook, which is about numbers of the form $\displaystyle a^p b^q$.

A reference to this can be found here: Ramanujan's notebooks, Volume 4.

(I suggest you read page 66 onwards)

A snapshot (from the google books link itself):

alt text

This volume talks about the "proof" Ramanujan gave (pages 68 and 69), provides references to Hardy's book (which apparently has a whole chapter on this) and also mentions a paper by Hardy and Littlewood which deals with it.

De Bruijn has considered the number of $y$-smooth numbers in this paper: On the number of positive integer less than x and free of prime factors greater than y.

The number of $y$-smooth numbers $\le x$ is apparently now known in literature as the DeBruijn function: $\psi(x,y)$.

A closely related function is the DeBruijn-Dickman function.

There is also a survey by Hildebrand and Tenenbaum which should be helpful.

share|improve this answer
add comment

If $2^a3^b \lt N, a \ln 2 + b \ln 3 \lt \ln N$ or $a+\frac{b \ln 3}{\ln 2}\lt \frac{\ln N}{\ln 2}$. For large $N$, we can ignore +1s, so to count the number less than $N$, we have $$\sum_{i=0}^\frac{\ln N}{\ln 3}\frac{\ln N-i\ln 3}{\ln 2}=\frac{(\ln N)^2}{\ln 2 \ln 3}-\frac{(\ln N)^2}{2\ln 2 \ln 3}$$ which is within a constant of the Ramanujan result.

share|improve this answer
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.