Ruth's Recurrence

//
// Written by Grant Jenks
// http://www.grantjenks.com/
//
// DISCLAIMER
// THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE
// LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR
// OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND,
// EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE
// ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.
// SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY
// SERVICING, REPAIR OR CORRECTION.
//
// Copyright
// This work is licensed under the
// Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
// To view a copy of this license, visit
// http://creativecommons.org/licenses/by-nc-nd/3.0/
// or send a letter to Creative Commons, 171 Second Street, Suite 300,
// San Francisco, California, 94105, US.A
//
// Description
// My in-laws visited on a recent weekend. During their stay with us, Shannon's
// Mom said she had created a kind of math-puzzle to keep herself busy. Curious,
// she described the following algorithm:
//    1. Start with an integer greater than 0.
//    2. If the number is divisible by 3, divide by 3.
//    3. Else, add a "1" or "2" to the end of it to make it divisible by 3.
//    4. If the current number is now 1, end. Else, go back to (2).
// She also shared that she had started with the number 141 and after a dozen
// or so iterations suspected that it would not reach 1.
// (Arithmetic-savvy readers will notice that step 3 works on a clever trick:
// if you sum the digits in an integer and the sum is divisible by 3 then the
// integer is divisible by 3.)
//
// I was intrigued by her puzzle and reminded of the Collatz Problem so I wrote
// this program to do the algorithm and report on results. Most interesting to
// me was which numbers converged. In order to keep things reasonable, I limited
// the iterations to 1,000.
//
// Notes
//  * Depends on .NET 4.0.
//  * Compile with /R:System.Numerics.dll
//  * To enable tracing, compile with /d:TRACE
//

using System;
using System.Numerics;
using System.Diagnostics;

class RuthsRecurrence
{

const int IterationLimit = 1000;
const int ValueCountLimit = 2000;
static readonly BigInteger Ten = 10;
static readonly BigInteger Three = 3;

//
// Sum the digits in the BigInteger.
//
// Note that this function accumulates the sum in an int. This limits the
// BigInteger to something on the order of 100,000,000 digits.
//

static int SumDigits(BigInteger value)
{
   int sum = 0;

   while (value > BigInteger.Zero)
   {
      BigInteger remainder;
      value = BigInteger.DivRem(value, Ten, out remainder);
      sum += (int)remainder;
   }

   return sum;
}

//
// Do the recurrence for the given BigInteger.
//
// Note that this function returns 'true' if the recurrence converged to 1
// and, in that case, the out parameter is a count of how many iterations were
// required to converge.
//

static bool Recur(BigInteger start, out int iterations)
{
   iterations = 0;
   BigInteger current = start;

   Trace.WriteLine(String.Format("Start: {0}", start));

   while (current != BigInteger.One && iterations < IterationLimit)
   {
      Trace.WriteLine(String.Format("Iteration: {0}, Current: {1}", iterations,
            current));

      BigInteger remainder;
      BigInteger quotient = BigInteger.DivRem(current, Three, out remainder);

      if (remainder == BigInteger.Zero)
      {
         current = quotient;
      }
      else
      {
         int sum = SumDigits(current);
         int rem = sum % 3;
         int inc = 3 - rem;

         current = current * 10 + inc;
      }

      iterations++;
   }

   return (current == BigInteger.One);
}

//
// Iteratively test values for convergence and print result.
//
// Program entry point. Arguments are ignored.
//

static int Main(string[] args)
{
   Trace.AutoFlush = true;
   Trace.Listeners.Add(new ConsoleTraceListener(true));

   BigInteger value = BigInteger.One;

   for (int i = 0; i < ValueCountLimit; i++)
   {
      int iterations;

      if (Recur(value, out iterations))
      {
         Console.WriteLine("Value {0} converged in {1} iterations", value,
            iterations);
      }
      else
      {
         Console.WriteLine("Value {0} failed to converge within {1} iterations",
            value, IterationLimit);
      }

      value += 1;
   }

   return 0;
}
}

Here's a plot of values (excluding those which took more than 1,000 iterations to converge) and the number of iterations they required. The value which Ruth started with, 141, would've kept her busy for a long time (it did not converge within 1,000 iterations)!