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 Miller

--Infuriating! OK, I will employ general radix R. Work backwards from the single-digit end-number. Let K denote a constant (which may change with different uses). In K backsteps we can reach any "sparse" number, meaning one with at most a constant number of nonzero digits. On the other hand (this time thinking forward) in 1 step where all the summands are either 1 or 2 or 3 digits long, we can reach (starting from a D-digit number) more than 1.6^D different numbers, each upperbounded by D*(D^3-1)<D^4. Well, obviously, for large D, that means most of the "different" numbers actually are the same, just got in different ways. There is vast overcoverage. Now if the original number was "random" then we can argue that with probability-->1 that EVERY number between about D*(R-1) and D^4 (or some not-too-shrunk subinterval of this to play it safe) is thus-reachable in 1 step. There are plenty of sparse numbers in that interval with only, say, 2, nonzero digits. They must be reachable in 1 step. We conclude that THEOREM: almost every number can reach a single-digit number in at most a constant number of steps (this works in any radix R>1, the constant is at most iteratedlogarithmic in R). "Almost every" means the fraction approaches 1. This however does not answer the puzzle because of the "almost". But I think one ought to be able to prove the approach to 1 is extremely fast asymptotically, prob=1-delta where delta=exponential(-D) small. Now if you believe that after a random step of our type, a nonrandom number gets randomized, then the probability we keep missing out on the gold (i.e. on the sparse numbers) for K consecutive steps no matter what steps we take ought to be exponential(-K*Dfinal) small, which for K of order R outweighs the factor R^Dfinal from counting Dfinal-digit numbers in radix R. Then there can be at most a finite number of exceptions because the probability that an exception exists shrinks small enough fast enough that the total number of exceptions ought to be finite. Unfortunately this paragraph seems likely to be unrigorizable. (The others look rigorizable.) Hence CONJECTURE: every number can reach a single-digit number in at most O(R) steps where this works in any radix R>1. -- Warren D. Smith http://RangeVoting.org  <-- add your endorsement (by clicking "endorse" as 1st step)