I have another blog that doesn't suck. Archive:
Comments disabled 
I spent some time over the last couple of days trying to estimate the number of smooth numbers up to !!N!!. (An !!n!!smooth number is one whose largest prime factor is no larger than !!n!!. So the 2smooth numbers are exactly the powers of 2, and the set of 3smooth numbers contains exactly the numbers of the form !!2^i3^j!! and begins !!1, 2, 3, 4, 6, 8, 9, 12, 16, 18…!!.) Let's write !!f_k(n)!! for the number of !!k!!smooth numbers up to !!n!!, so for example !!f_3(19) = 10!! and !!f_2(19) = 5!!, as above. Then obviously !!f_2(n) = 1+\lfloor \log_2 n\rfloor!! exactly. (Incidentally, I think there ought to be a simpler notation for !!\lfloor \log_k n\rfloor!!, which comes up really often.) After hacking around a bit, I settled on $$f_3(n) \approx \ell_3(n) \cdot f_2(n)  \frac{\ell_3(n)1}{2} \left( \ell_3(n)\log_2 3  \frac12 \right) $$ where !!\ell_3(n) = \lceil \log_3 n\rceil!!. I expect I can express !!f_5(n)!! in terms of !!f_3(n)!! in similar fashion but haven't yet tried. The may still contain some silly errors (I corrected a bunch), but at least the computer says it is not too far off. For example the approximation guesses !!f_3(10^6) \approx 139.4!! and the correct answer is !!142!!. I wanted something I could compute in the woods with no calculator, because Toph and I went camping this weekend and I had my phone off and didn't want to turn it on. I think the formula above answers the requirement pretty well. Note that calculating !!\ell_3!! exactly is quite easy, much easier than calculating !!\log_3 n!!. The only possibly tricky bit is the !!\log_2 3!!, which I should have memorized but don't. But in the woods I estimated that as 1.6 off the top of my head just by halfassing it: !!2^{3/2} \approx 2.828!!, so it must be a little bigger than !!\frac32!!, which it is. This formula comes without absolutely no warranty, not even the implied warranty of merchantability or fitness for a particular purpose.
