# [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.
>
> Victor

Me: So consider the sequence
a(n) = smallest number of steps needed to reach 1

I think this begins (for n = 1,2,3,...)
0,1,2,1,2,2,2,1,2,2,2,2,2,2,2,1,...

For example, 14 = 1110_2 -> 1 + 11 + 0 = 4 = 100_2 -> 1 + 0 + 0 = 1
so a(14)=2

Could someone check this and extend it?

Neil

```