If we ask instead how many nonzero digits there are in 2^n, there's actually a known lower bound on this, due to Cam Stewart, though it is unfortunately quite t

If we ask instead how many nonzero digits there are in 2^n, there's actually a known lower bound on this, due to Cam Stewart, though it is unfortunately quite tiny - on the order of (log log n)/(log log log n), much smaller than what empirically appears to be the case. In fact, the statement is much more general: Say you have two bases A and B (such that no power of A is a power of B, to prevent triviality), a base-A digit a, and a base-B digit b. For any n let L_A,a(n) denote the number of non-a digits in the base-A expansion of n, and L_B,b(n) similarly with B and b. Then for any n, L_A,a(n)+L_B,b(n)>(log log n / (log log log n + C)) - 1, where C is a constant depending only on A and B. So while it's certainly impossible to say "large numbers have complicated base-A expansions", it is in some sense possible to say that they can't simultaneously have simple base-A and base-B representations! In particular you get a lower bound on number of nonzero digits (or more generally non-b digits) of powers of A written to base B by just taking n to be powers of A and taking a=0. Paper: http://www.math.uwaterloo.ca/PM_Dept/Homepages/Stewart/Jour_Books/J-reine-ange-Math-1980.pdf http://www.math.uwaterloo.ca/PM_Dept/Homepages/Stewart/Jour_... Unfortunately, not only is the lower bound tiny even asympotically, but the constant involved is absolutely huge. (The paper doesn't explicitly state how to compute this constant, but once I was trying to bound below the number of nonzero digits in powers of 2 written to base 3, so I traced through all the computations and references, and it's ridiculously large, much too large for what I was trying to do... I forget just how large, except that it was the sort of number most conveniently described as being "about 10^[something]" rather than in words.) So again, not close to what appears to be true empirically.