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: ==============================================================================