[seqfan] A puzzle from Emissary
N. J. A. Sloane
njas at research.att.com
Mon Nov 28 17:04:49 CET 2011
Dear Seq Fans,
Victor Miller posted the following on the math-fun list:
> In the lastest issue of Emissary (the newsletter from MSRI) there's the
> following challenging puzzle:
> For every positive integer n, write it in binary, and allow the following
> possible set of transformations:
> You can insert "+" signs at arbitrary points within the binary expansion,
> and interpret that as a sum of binary numbers. For example
> 110101_2 --> 11_2+01_2+01_2 = 3 + 1 + 1 = 5 = 101_2.
> Show that there is an absolute constant C such that for any positive
> integer n there is a sequence of at most C such transformations that
> results in 1.
> Note: The minimal value of C is a real shocker
> This made me wonder about the obvious generalization to other bases, where
> now we ask for a sequence of such transformation that results in a single
> digit base b number.
Me: So consider the sequence
a(n) = smallest number of steps needed to reach 1
I think this begins (for n = 1,2,3,...)
For example, 14 = 1110_2 -> 1 + 11 + 0 = 4 = 100_2 -> 1 + 0 + 0 = 1
Could someone check this and extend it?
More information about the SeqFan