From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Subject: Re: Least number of steps
Date: 11 May 1999 18:27:09 GMT
Newsgroups: sci.math
Keywords: Length of chains in a dynamical system on Z
Ray, Rajarshi (EXCHANGE:SKY:7V31) wrote:
>Nobody seems to have noticed this question from Chris Wildhagen, so I'm
>reposting it here:
>
>??????????????????????????????????????????????????????????????????????????????
>
>Let n be a natural number. With successive operations +1, -1 or /2
>(dividing
>by 2, if the integer in question is even) transform n to 1 in the least
>number of steps. Find a formula for the least number of steps in terms
>of
>the binary expansion of n (i.e. the "distance" from n to 1).
>Example: 93->92->46->23->24->12->6->3->2->1. This cannot be done faster,
>hence the distance from 93 to 1 is 9.
I claim that no chain of transformations is shorter than the one starting
T(1)=1
T(2k)=k
T(4k+1)=4k
T(4k-1)=4k except T(3)=2
for all k>1. We can't easily prove this by induction on n, since
transformations may map integers to larger integers. But we can prove this
by induction on the number s of steps.
[Apology in advance: I didn't try to streamline this for optimal notation
or clarity of thought.]
Suppose there is a chain which transforms a number n to 1, and which
is shorter than the chain I just constructed for n. Among all such chains,
(for all possible n) choose one with s minimal. Then in particular, this
minimal better-chain begins with a transformation other than the one I gave.
Can this chain start with an even integer n? If n=2k, I have proposed
a chain starting n, n/2, ... of a certain length t. If there is a chain of
shorter length, it begins n, n-1, ... or n, n+1, ... by minimality. Since n
is even, the next terms, by minimality, must be n-2 and n+2, respectively.
There then follows a chain of length s-2 leading to 1. By minimality,
this is no shorter than the chain I would construct starting with n-2
(resp. n+2), so we may as well REPLACE the rest of the chain with the
one I propose. This gives a chain
n, n-1, n-2, n/2 - 1, ...
or
n, n+1, n+2, n/2 + 1, ...
In either case, replace the first three terms with just n/2 to get a
valid chain of length s-2 starting with n/2; this is certainly shorter
than the chain n/2, ... I propose, which has length t-1. This
contradicts our minimality assumption.
Similarly, if a shortest better-chain starts with n = 4k+1, where my
chain of length t begins
n, n-1=4k, 2k, k, ...
this competitor must begin
n, n+1=4k+2, ...
so again by minimality of s, the part of the chain beginning 4k+2, ...
will be no shorter than my chain of transformation starting with 4k+2,
which we may then substitute, and assume the competing chain is then
n, n+1=4k+2, 2k+1, ...
The next term cannot be 2k since this competitor would then be
longer, not shorter, than mine. So it must be 2k+2, followed by k+1.
But in that case, the sequence k, k+1, ... would have total length s-3,
whereas my proposed sequence starting with k has length t-3, which is
longer; this new sequence would then violate minimality of the chosen
competitor.
Finally, if the minimal-length shorter-chain begins with n=4k-1, then
we are assuming a sequence of length s which is shorter than my
sequence of length t:
n=4k-1, 4k, 2k, k, ... [assuming k>1]
So how does the competitor start? Must be n, 4k-2, ...; as in the
previous paragraph there is by minimality no harm in assuming that the
rest of the sequence is then as I would have constructed it, i.e.
n=4k-1, 4k-2, 2k-1, ...
If the next term were 2k, that would violate shorterness (:-)), so
it's 2k-2 next, then k-1. Then as in the other cases we patch k to the
rest of the sequence to get a chain of length s-3 starting k, k-1, ...
while my sequence k, ... has length t-3, supposedly longer, then violating
minimality of s.
(The smallest values of n might lead to sequences involving 3, 1, or
non-positive integers in these arguments; details left to the reader.
So no sequence of transformations is ever shorter than the one which begins,
T(1)=1, T(3)=2
T(2k)=k
T(4k+1)=4k
T(4k-1)=4k
It follows that the length of the sequence is given by
l(1)=0
l(2k) = 1 + l(k)
l(4k+1) = 3 + l(k)
l(4k-1) = 3 + l(k) except l(3) = 2
Example: l(93) = 3+l(23)=6+l(6)=7+l(3)=9.
Example: l( 2^k ) = k
Example: l( (2*4^k+1)/3 ) = 3*k
In general, l(n) is bounded by log_2(n) and (3/2)log_n(n) + O(1).
I don't know a good, nonrecursive way to describe it.
dave
==============================================================================
From: "Clive Tooth"
Subject: Re: Least number of steps
Date: Thu, 13 May 1999 20:26:45 +0100
Newsgroups: [missing]
To: "Dave Rusin"
>In article <7h9k8f$g1j$1@mail.pl.unisys.com> you write:
>>I believe that the number of steps required can be computed as follows:
>>
>>1) Convert the number into binary.
>>2) Discard the leading '1'.
>>3) Set a count to zero.
>>4) Partition the binary string into groups of 1's and groups of 0's.
>>5) For each group of 0's (length n) add n to the count.
>>6) For each group of 1's (length=1) add 2 to the count.
>>7) For each group of 1's (length n>1) add n+2 to the count.
>>8) For each group of zeros of length 1, with a group of ones on either
side
>>of it of length at least 2, subtract one from the count.
>>
>
>
>Well, I just posted a different algorithm, and it seems we disagree,
>e.g. if n=235. Here's Maple, first me then you:
>
>nxt:=proc(n)
> if n = 1 then 1
> elif n = 3 then 2
> elif n mod 2 = 0 then 1/2*n
> elif n mod 4 = 1 then n - 1
> else n + 1
> fi
>end:
>
>le:= proc(n) if n = 1 then 0 else 1 + le(nxt(n)) fi end:
>
>
>
>bin:=proc(n)
>local i, S, m;
> S := [];
> m := n;
> while 0 < m do S := [m mod 2, op(S)]; m := 1/2*m - 1/2*(m mod 2) od;
> S
>end:
>
>clumps:=proc(a)
>local i, ct, S;
> S := [];
> ct := 1;
> for i from 2 to nops(a) do
> if a[i] = a[i - 1] then ct := ct + 1
> else S := [op(S), ct]; ct := 1
> fi
> od;
> S := [op(S), ct]
>end:
>
>counts:=proc(a)
>local b, ct, i;
> b := [a[1] - 1, seq(a[i], i = 2 .. nops(a))];
> ct := 0;
> for i to floor(1/2*nops(b)) do ct := ct + b[2*i] od;
> for i to ceil(1/2*nops(b)) do
> if b[2*i - 1] = 0 then {}
> elif b[2*i - 1] = 1 then ct := ct + 2
> else ct := ct + 2 + b[2*i - 1]
> fi
> od;
> for i to floor(1/2*nops(b) - 1/2) do
> if b[2*i] = 1 and 1 < b[2*i - 1] and 1 < b[2*i + 1] then
> ct := ct - 1
> fi
> od;
> ct
>end:
>
>
>
>#Now compare
>for n to 1000 do if counts(clumps(bin(n)))<>le(n) then
> lprint(n, le(n), counts(clumps(bin(n))) ) fi:od:
>
>235 11 12
>363 12 13
>470 12 13
>471 12 13
>491 12 13
>619 13 14
>726 13 14
>727 13 14
>747 13 14
>875 14 15
>939 14 15
>940 13 14
>941 14 15
>942 13 14
>943 13 14
>982 13 14
>983 13 14
>
>In each of these cases, you're predicting a chain of length one less than
>the minimal I claim exists, e.g.
> [235, 236, 118, 59, 60, 30, 15, 16, 8, 4, 2, 1]
>
>Can you really find an 11 ? Did I miscode? Did you forget some condition
>relating to an "..010.." in the binary expansion?
>
>dave
Hi Dave,
{apologies for not replying sooner}
Um. The distance from 235 to 1 _is_ 11 ?!?!
The original poster says:
======================================
Let n be a natural number. With successive operations +1, -1 or /2
(dividing
by 2, if the integer in question is even) transform n to 1 in the least
number of steps. Find a formula for the least number of steps in terms
of
the binary expansion of n (i.e. the "distance" from n to 1).
Example: 93->92->46->23->24->12->6->3->2->1. This cannot be done faster,
hence the distance from 93 to 1 is 9.
======================================
For 93 my method gives...
93 = 1011101 (base 2)
Discard leading 1 and group:
0 111 0 1
1 +5 +1 +2 = 9, in agreement with the original poster.
For 235 my method gives...
235 = 11101011 (base 2)
Discard leading 1 and group:
11 0 1 0 11
4 +1 +2 +1 +4
......... -1 =11
The sequence
[235, 236, 118, 59, 60, 30, 15, 16, 8, 4, 2, 1]
means that 235 has a distance of 11 from 1, using the terminology used by
the original poster.
I believe that the count given by my algorithm always agrees with the count
for your method. I am not sure why you associate the number 12 with 235.
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
==============================================================================
From: Dave Rusin
Subject: Re: Least number of steps
Date: Thu, 13 May 1999 15:01:55 -0500 (CDT)
Newsgroups: [missing]
To: pisquaredoversix@pisquaredoversix.force9.co.uk
>I am not sure why you associate the number 12 with 235.
I'm stupid. I misread my own code and output:
> lprint(n, le(n), counts(clumps(bin(n))) ) fi:od:
>235 11 12
Clearly this means _I_ thought the length to be 11 and _you_ had calculated
it as 12, but in my last message I interpreted this the other way 'round.
Sorry.
With your new algorithm, we agree about 235. But now
what about 459? I get a distance of 13, with sequence
[459, 460, 230, 115, 116, 58, 29, 28, 14, 7, 8, 4, 2, 1]
Your algorithm:
>1) Convert the number into binary.
[1, 1, 1, 0, 0, 1, 0, 1, 1]
>2) Discard the leading '1'.
[1, 1, 0, 0, 1, 0, 1, 1]
>3) Set a count to zero.
Count=0
>4) Partition the binary string into groups of 1's and groups of 0's.
[2, 2, 1, 1, 2]
>5) For each group of 0's (length n) add n to the count.
Two groups, count=2.
>6) For each group of 1's (length=1) add 2 to the count.
One group, count=4.
>7) For each group of 1's (length n>1) add n+2 to the count.
Two groups with n=2 each, each adds 2+2=4, count=12
>8) For each group of zeros of length 1
One found...
> or run of alternating zeros and ones <<<< NEW <<<<
...which is part of the one maximal such run "0 1 0 1"...
> with a group of ones on either side of it of length at least 2,
...which doesn't meet this criterion
>subtract one from the count
So you get a count of 12. Is there really a sequence of length 12?
Your current algorithm as I understand it now (really) gives a count exactly
one less than mine in a few cases < 1000: it claims a distance of 11 for
475 when I think the distance is 12; you claim distances of 12 for
459, 731, 950, 951, 955, 987 when I think the distance to be 13; your
algorithm gives 13 and mine 14 for 715, 907, 918, 919, 923, 971.
I must confess I haven't really much idea how your algorithm is supposed
to give the right distances. The recursive algorithm I gave is easy enough
to code but not directly from the binary expansion, I think.
If you want I can send the complete list of lengths as I compute them, up
to say 1000 -- that way if you code your algorithm you can check it against
mine, in case my algorithm is unclear.
dave
==============================================================================
From: "Clive Tooth"
Subject: Re: Least number of steps
Date: Thu, 13 May 1999 21:24:33 +0100
Newsgroups: [missing]
To: "Dave Rusin"
Hi Dave!
See step (5) below.
[previous letter quoted back this far: -- djr]
>>5) For each group of 0's (length n) add n to the count.
> Two groups, count=2.
"add n to the count" --> add 2 then add 1 --> count=3, ok?
:)
[rest of letter also quoted back -- djr]
Clive Tooth
http://www.pisquaredoversix.force9.co.uk/
==============================================================================
From: Dave Rusin
Subject: Re: Least number of steps
Date: Thu, 13 May 1999 15:34:02 -0500 (CDT)
Newsgroups: [missing]
To: pisquaredoversix@pisquaredoversix.force9.co.uk
*Sigh* Looks like it's time to go home.
The error you pointed out means when I do your algorithm by hand we agree,
but upon closer examination I see I mis-coded your algorithm, allowing the
machine to get _that_ part right but mess up something else.
With my _current_ Maple attempt, our algorithms give the same answer
for inputs up to 10,000. Frankly I have more confidence in the analysis I
posted than on the computer code I wrote, but since at this point they
agree I'm not looking for any more errors!
:-)
dave
==============================================================================
[Maple code I used follows -- djr]
nxt:=proc(n)
if n = 1 then 1
elif n = 3 then 2
elif n mod 2 = 0 then 1/2*n
elif n mod 4 = 1 then n - 1
else n + 1
fi
end:
le:= proc(n) if n = 1 then 0 else 1 + le(nxt(n)) fi end:
bin:=proc(n)
local i, S, m;
S := [];
m := n;
while 0 < m do S := [m mod 2, op(S)]; m := 1/2*m - 1/2*(m mod 2) od;
S
end:
clumps:=proc(a)
local i, ct, S;
S := [];
ct := 1;
for i from 2 to nops(a) do
if a[i] = a[i - 1] then ct := ct + 1
else S := [op(S), ct]; ct := 1
fi
od;
S := [op(S), ct]
end:
counts:=proc(a)
local b, ct, i, j, sof:
b := [a[1] - 1, seq(a[i], i = 2 .. nops(a))];
ct := 0;#print(ct);
for i to floor(1/2*nops(b)) do ct := ct + b[2*i] od;#print(ct);
for i to ceil(1/2*nops(b)) do
if b[2*i - 1] = 0 then {}
elif b[2*i - 1] = 1 then ct := ct + 2:#print(ct);
else ct := ct + 2 + b[2*i - 1]:#print(ct);
fi
od;
#old:
# for i to floor(1/2*nops(b) - 1/2) do
# if 1 < b[2*i - 1] and b[2*i] = 1 and 1 < b[2*i + 1] then
# ct := ct - 1
# fi
# od;
#new:
for i to floor(1/2*nops(b) - 1/2) do
if 1 < b[2*i - 1] then sof:=1:
for j to floor((nops(b)+1)/2-i) do
if b[2*i+2*j-2]>1 then sof:=0:fi:
if sof = 1 and
b[2*i+2*j-1] > 1 then ct:= ct -1:sof:=0:fi:#print(j,ct);fi:
od:
fi
od;
ct
end:
#Now compare
#for n to 1000 do if counts(clumps(bin(n)))<>le(n) then
# lprint(n, le(n), counts(clumps(bin(n))) ) fi:od:
==============================================================================