Binary Carry Sequence

The sequence a(n) given by the exponents of the highest power of 2 dividing n, i.e., the number of trailing 0s in the binary representation of n. For n=1, 2, ..., the first few are 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, ... (OEIS A007814).

Amazingly, this corresponds to one less than the number of disks to be moved at nth step in the optimal solution to the tower of Hanoi problem: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, ... (OEIS A001511). The parity of this sequence is given by 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, ... (OEIS A035263) which, amazingly, also corresponds to the accumulation point of 2^n cycles through successive bifurcations.

See also

Double-Free Set, Tower of Hanoi

Explore with Wolfram|Alpha


Atanassov, K. "On the 37th and the 38th Smarandache Problems. Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria 5, 83-85, 1999.Atanassov, K. On Some of the Smarandache's Problems. Lupton, AZ: American Research Press, pp. 16-21, 1999.Derrida, B.; Gervois, A.; and Pomeau, Y. "Iteration of Endomorphisms on the Real Axis and Representation of Number." Ann. Inst. Henri Poincaré, Section A: Physique Théorique 29, 305-356, 1978.Karamanos, K. and Nicolis, G. "Symbolic Dynamics and Entropy Analysis of Feigenbaum Limit Sets." Chaos, Solitons, Fractals 10, 1135-1150, 1999.Metropolis, M.; Stein, M. L.; and Stein, P. R. "On Finite Limit Sets for Transformations on the Unit Interval." J. Combin. Th. A 15, 25-44, 1973.Sloane, N. J. A. Sequences A001511/M0127, A007814, and A035263 in "The On-Line Encyclopedia of Integer Sequences."Smarandache, F. Only Problems, Not Solutions!, 4th ed. Phoenix, AZ: Xiquan, 1993.Vitanyi, P. M. B. "An Optimal Simulation of Counter Machines." SIAM J. Comput. 14, 1-33, 1985.

Referenced on Wolfram|Alpha

Binary Carry Sequence

Cite this as:

Weisstein, Eric W. "Binary Carry Sequence." From MathWorld--A Wolfram Web Resource.

Subject classifications