Problem of the Week 1157

Add Plus And Add

MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW

Start with a number written in base two (e.g., 7423 = 1110011111111). Insert some plus signs at any places in the sequence (e.g., 11100 + 11 + 111 + 111) and form the resulting sum (e.g., 28 + 3 + 7 + 7 = 45, which is 101101). Iterate this process until 1 is reached.

Starting with 7423, how quickly can you get to 1?

The general question, where the starting value is arbitrary, is more difficult. And results are known when base 2 is replaced by other bases.

Source: Fall 2011 MSRI Emissary newsletter puzzle column by Joe Buhler and Elwyn Berlekamp; problem due to Gregory Galperin.

© Copyright 2012 Stan Wagon. Reproduced with permission.

[View the solution]