Friday, September 17, 2010

An Unusual Series

Which may not be all that interesting to you, unless you're interested in recreational math. For lots of you, that may be sort of an oxymoron. (Although, I'm hoping it's less likely among readers of my blog than it would be among the general population.)

Here's the idea. Start with an integer. Add its digits together. If that sum is even, halve the number (not the sum of digits) to get the next number. If the sum is odd, add one to the number.

For instance, suppose we start with the number 10. Its digits sum to 1+0 = 1, so we add 1 to get 11. Those digits sum to 1+1 = 2, so we halve it to get 11/2 = 5.5. Those digits sum up to 5+5 = 10, so we again halve the number to get 2.75. Those digits sum up to 2+7+5 = 14, so we again halve the number to get 1.375...well, I think you get the idea.

On the other hand, suppose you start out with the number 1. Its one digit sums to 1, so we add 1 to get 2. Its single digit sums to 2, so we halve it to get 1 again. Obviously, this series repeats forever: 1, 2, 1, 2, 1, etc.

The first eight numbers, 1 through 8, all end up at that same repeating sequence. The next number, 9, leads immediately to 10, which starts out as I worked out above, and then goes on indefinitely: Each number has one more digit after the decimal point than the preceding number, so the series never repeats, and it never reaches zero, either.

In my limited trials, every integer I've started out with either ends up with the repeating sequence 1, 2, 1, 2, 1, ..., or else it eventually merges with the same series that you get if you start with 10 (or 9, for that matter). So, two questions for those of you who might like to play with this kind of thing:
  1. Is it true that the series for any integer always either ends with the sequence 1, 2, 1, 2, 1, ..., or else merges with the series that starts with 10?
  2. Consider the series that starts with 10. As we said, it goes on forever, without repeating. What is the average of the numbers in that infinite series?
Neither of these questions can be answered definitively (as far as I can tell) with brute-force computation, although the results might be suggestive. If you do want to try some computations, use an infinite-precision package; our friend Bernie has already tried it with ordinary floating-point numbers (eight-byte doubles, I think), and roundoff error rendered everything after about the 15th number quickly invalid.

P.S. Don't ask me how I got started thinking about the series. It's inspired in part by this guy, but I've already forgotten how I decided to think about this variant.


  1. If you can figure out a good way to get the Sum of Digits then I already have the rest of the code to do the brute-force computation.
    Digital Root suggest that you can use congruences rather than adding up all the digits, a procedure that can save time in the case of very large numbers.

  2. @Bernie: You only need the parity of the sum, so one quick way is to XOR the digits together, and check the LSB: 0 means even, 1 means odd. Assuming the digits are stored in some easily accessible way, this should be pretty straightforward.

    for (i=0; i < x.size; i++) p ^= x[i];

    Or code to that effect. :)

    Digital roots reduce a number to its value modulo 9 (for base 10; for other bases b, it reduces to its value modulo b-1), except that positive numbers divisible by 9 have a digital root of 9. Since that's not really all that helpful for this problem, I'd stick with XOR'ing.