[seqfan] Re: A puzzle from Emissary

franktaw at netscape.net franktaw at netscape.net
Mon Nov 28 23:04:39 CET 2011


I guess I need to explicate this. Take a number ending in 1. Separate 
out the final 1. From my conjecture, the rest of the number will sum to 
a power of two minus 1, so you add in the final 1 and get a power of 2.

Franklin T. Adams-Watters

-----Original Message-----
From: franktaw <franktaw at netscape.net>

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/


  



More information about the SeqFan mailing list