[seqfan] Re: A puzzle from Emissary

[franktaw at netscape.net]

This doesn't work. The 0 you are trying eliminate may be stuck in the 
middle of a number in the previous solution.

E.g., 1001111 has the solution 1001+111. Insert another 0 for 10001111 
and you can't eliminate that 0.

Franklin T. Adams-Watters

-----Original Message-----
From: Dan Dima <dimad72 at gmail.com>

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/