Problem of the Week 1157

Add Plus And Add

MacPOW Home || Math Forum POWs || Search MacPOW

Solution Notes

The specific problem given (7423) was solved by Joseph DeVincentis, Jack Ritter, Stephen Morris, Bill Bass, and Aaron Laursen. Somewhat surprising is that one can reach 1 in two steps regardless of the starting value!

This was first proved by Ron Graham and Richard Stong, with contributions by Joe Buhler and Steve Butler, but at least one person, and perhaps more, found independent proofs. In particular, see the post by Zander at http://math.stackexchange.com/questions/157354/sumpartitionbinary-string-2k. Graham and Butler looked at the problem in larger bases, showing that 4 steps suffice for base 4 and beyond, while for base 3 there are finitely many integers that require 4 steps, the rest working in three.

PoW reader Stephen Morris (England) came up with a very slick algorithm that leads to a proof.

Morris Algorithm: Let n be the given number, Q the binary string for n, and m the number of 1s in Q (called the Hamming weight of n). If m is a power of two, then just sum all the bits in Q. Otherwise, let T, the target, be the first power of two greater than m; call this 2^r.

Version 1. Insert plus signs between every two digits. Start from the left and remove a plus sign provided it does not lead to an expression that is greater than T. The algorithm works in all cases except m = 5, which is handled separately as follows: Q has one of 101, 111, or 1111 in it. Make one of these a complete number (5, 7, 15, respectively) and use the remaining bits to hit 8, 8, 16, respectively.

Version 2. Same as in version 1 (and with the exception for m = 5), but stated a little differently. Start as in version 1 but without any plus signs, and scan the digits from left to right to build up a sequence of integers by inserting plus signs. As numbers A are completed, let Q and m decrease: that is, Q consists of the unused bits, and m becomes the number of 1s in Q.

Let S be the sum of the completed numbers, 0 at the start. At any step in either the construction of the list of numbers or the construction of an individual number, let the error E denote the gap T - (S + A + m). So at the start, E = T - m, which is positive. While E > 0, construct a new number A. Do this by starting with A = 0 and accepting digits moving right from the current position. For each new digit d, let A = 2 A + d until the error becomes negative (the target is passed by S + A + m). When this happens, back up one step so that the value of A has nonnegative error and let A be a new completed number. If E is nonzero, continue by starting a new number.

Working out version 2 in more detail leads to a formulation of the algorithm that is remarkably succinct. H is used for the Hamming weight, and the output is just printed in sequence. A key point is that upon completion of A, the sum of S and the remaining 1-bits — and hence the error E — changes by A - H(A). The Do loop below scans the digits X in Q.

Input: Q, the binary digits of n.
Initialize: m = H[Q]; A = 0; e = 2^Ceiling[Log2[m]] - m;
Do[A = X + If[A ≤ e, e = e - A; 2 A, Print["+"]; 0]; Print[X], {X, Q}]

Using this algorithm, one can in under two minutes check that the algorithm works up to 10⁶; I also checked it to 10⁷ (20 minutes). Stephen has proved that the algorithm works; his proof is posted at http://mathforum.org/wagon/current_solutions/1157SolnMorris.pdf

There are two main ideas in the proof. As one starts a number A, let the current error E be such that 2^q < E ≤ 2^{(q + 1)}.

1. After completing A, the error E ≤ 2^q. Thus, roughly speaking, the error after completing each number gets cut in half (or more).

2. The number of bits used in forming A is no greater than q + 1.

These facts are then used as follows (ignoring some small cases). The number of 1-bits used is at most

2 + 2 + 2 + 3 + 4 + 5 + 6 + ... + (r - 1) = r(r - 1)/2 + 3.

This cannot exhaust all the 1-bits, since there are m, or at least 2^{(r - 1)}, of them and this power is greater than the quadratic expression when r is 5 or more. Therefore the process ends before all the bits are scanned.

The displayed equation is not valid for small values. For m = 5, the desired inequality 5 ≥ 2 + 2 + 2 fails, and that is what makes 5 a special case.

Here is complete Mathematica code for handling any input, including the singular m = 5 case.

case5[QQ_] := (Q = Riffle[QQ, "+"];
   t = Select[Range[0, Length[Q] - 5],
            MemberQ[{{1, "+", 0, "+", 0}, {1, "+", 0, "+", 1}},
                 Q[[#1 + {1, 2, 3, 4, 5}]]] & , 1];
   If[t != {}, ans = Delete[Q, t[[1]] + {{2}, {4}}],
     s =  Position[Partition[Q, 7, 1], {1, "+", 1, "+", 1, "+", 1}, {1}, 1][[1, 1]] - 1;
     ans = Delete[Q, s + {{2}, {4}, {6}}]];
   If[ans[[1]] == "+", ans = Rest[ans]];
   If[ans[[-1]] == "-", ans = Most[ans]]; ans)

MorrisTotal[n_] := (Q = IntegerDigits[n, 2]; m = Total[Q];
   Which[
     IntegerQ[Log2[m]], Riffle[Q, "+"],
       m == 5, case5[Q],
       True, e = 2^Ceiling[Log2[m]] - m; A = 0;
          Reap[Do[
           A = X + If[A <= e, e -= A; 2*A,
           Sow["+"]; 0]; Sow[X], {X, Q}]][[2, 1]]])

[Back to Problem 1157]

© Copyright 2012 Stan Wagon. Reproduced with permission.