[seqfan] Re: A puzzle from Emissary

[Charles Greathouse]

>> All this numbers excepting 2^k-1 will contain a 0 and hence eliminate
>> that 0 you will get a (k-1) length number and we are done.
> Not OK

Right.  It can be used to show that C <= 3 (assuming you have a
separate proof that shows that 2^n - 1 takes at most 2 steps), but not
that C = 2.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Mon, Nov 28, 2011 at 2:17 PM, Dan Dima <dimad72 at gmail.com> wrote:
> All this numbers excepting 2^k-1 will contain a 0 and hence eliminate
> that 0 you will get a (k-1) length number and we are done.
> Not OK
>
>
> On Mon, Nov 28, 2011 at 9:10 PM, Dan Dima <dimad72 at gmail.com> wrote:
>> Proof by induction.
>> Suppose this is true by all odd numbers with exactly (k-1) binary digits 0 or 1.
>> Show that this is true for all odd numbers with exactly k binary digits.
>> All this numbers excepting 2^k-1 will contain a 0 and hence eliminate
>> that 0 you will get a (k-1) length number and we are done.
>> A separate proof is required for 11..1, k times 2^k-1 but this is simply
>> 11...1 + 1 as 2^(k-1)+1 = 2^(k-1)
>>
>>
>>
>>
>>
>> On Mon, Nov 28, 2011 at 8:53 PM,  <franktaw at netscape.net> wrote:
>>> A sufficient condition is that every number not already one less than a
>>> power of 2 can be transformed into one less than a power of 2 in one step.
>>> Is this true? Again, it will suffice to prove it for odd numbers greater
>>> than 1.
>>>
>>> Franklin T. Adams-Watters
>>>
>>> -----Original Message-----
>>> From: Charles Greathouse <charles.greathouse at case.edu>
>>> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
>>> Sent: Mon, Nov 28, 2011 12:38 pm
>>> Subject: [seqfan] Re: A puzzle from Emissary
>>>
>>>
>>>> It looks like C=2 and for n>1,
>>>> a(n) = 1 if n=2^k a power of 2,
>>>> a(n) = 2 otherwise
>>>
>>> Hmm.  The necessary and sufficient condition needed for that to hold
>>> is that any non-power of two can be transformed by the 'binary +
>>> insertion' procedure to a power of 2 in one step.
>>>
>>> In fact, it suffices (and is necessary) to show that this works for
>>> odd numbers greater than 1.  Anyone up for a proof by strong
>>> induction?
>>>
>>> Charles Greathouse
>>> Analyst/Programmer
>>> Case Western Reserve University
>>>
>>> On Mon, Nov 28, 2011 at 11:52 AM, Dan Dima <dimad72 at gmail.com> wrote:
>>>>
>>>> It looks like C=2 and for n>1,
>>>> a(n) = 1 if n=2^k a power of 2,
>>>> a(n) = 2 otherwise
>>>>
>>>>
>>>>
>>>> On Mon, Nov 28, 2011 at 6:04 PM, N. J. A. Sloane
>>>
>>> <njas at research.att.com>
>>> wrote:
>>>>>
>>>>> 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
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>>
>>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>>
>>>>
>>>> _______________________________________________
>>>>
>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>
>>>
>>> _______________________________________________
>>>
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>>
>>> _______________________________________________
>>>
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>