Content-Type: text/shitpost

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 2-smooth numbers are exactly the powers of 2, and the set of 3-smooth 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 half-assing 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.