Dan Hoey replying to Don Reble:
More likely, a(n)/n should tend to log_2(3)/2 = 0.79248+, since a bit is equally likely to be 0 or 1. (Well, the first and last bits are ones; I meant the other bits.)
The fours bit is always zero. Other bits (at least up to the 2^29s position) are exactly balanced.
Of course this has to happen. Well, specifically, the 2^k bit is either always zero, or else is 0 or 1 each half the time, asymptotically. After all, the first k bits are just acted on by "multiply by 11 (base 2)" each time n increases; this has to be periodic, and so will result in a carry into the 2^k bit at regular time steps. Oops -- that's true, but doesn't prove the assertion, since there could be an even number of carries to 2^k in each period, but spaced so the bit is more likely to be in one position. It's still the case that for each k, you can check the behavior forever by looking at what happens until some finite time, after which it's periodic. But I don't immediately see why the 0:1 ratio is 1:1, as it were. --Michael Kleber kleber@brandeis.edu