Ruth's Recurrence Variation 2

//
// 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
// This is a variation on "Ruth's Recurrence" described below. In this
// variation, step (3) is modified such that the "1" or "2" is added to the
// front of the number rather than the end.
//
// As I experimented with this variation I noticed that the number sequence
// always repeated but not necessarily at the starting number. For instance,
// if I begin with 1, the sequence is:
//    1 21 7 27 9 3 *1* 21 7 27 9 3 *1* ...
// so every 6 iterations, the sequence repeats. Now, looking at values through
// 13, you'll see a similar pattern. But with 14, something changes:
//    14 114 38 138 46 246 82 282 94 294 98 198 66 22 222 74 174 58 258 86 186
//    62 162 54 18 6 2 12 4 24 8 *18* 6 2 12 4 24 8 *18* ...
// Did you notice it? The sequence will repeat forever but it never returns to
// 14. Instead, it repeats at 18. This property yields two notions:
//   1. There exists a 'distance to repetition'. That is, the number of
//      iterations that must be performed before a number is repeated.
//   2. There exists a 'period'. That is, the number of iterations after
//      observing a repetition before observing that number again.
//
// Description of Ruth's Recurrence:
// 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.)
//
// 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;
using System.Collections.Generic;

class RuthsRecurrence
{

const int IterationLimit = 1000000;
const int ValueCountLimit = 500;
static readonly BigInteger Ten = 10;
static readonly BigInteger Three = 3;

//
// Sum and count 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.
//
// Assumes the value is positive.
//

static int SumAndCountDigits(BigInteger value, out int count)
{
   int sum = 0;

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

   return sum;
}

//
// Do the recurrence for the given BigInteger.
//

static bool Recur(BigInteger start, out int distance, out int period)
{
   int iteration = 0;
   BigInteger current = start;
   HashSet<BigInteger> previous = new HashSet<BigInteger>();
   bool foundRepeat = false;
   distance = 0;
   period = 0;

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

   while (iteration < IterationLimit)
   {
      Trace.WriteLine(String.Format(
         "Iteration: {0}, Distance: {1}, Period: {2}, Current: {3}",
         iteration, distance, period, current));

      if (previous.Contains(current))
      {
         if (!foundRepeat)
         {
            // Found the first repeated value in the sequence. 'distance'
            // counts the number of steps to this point. Now we measure the
            // period at which repetition occurs.

            foundRepeat = true;
            previous.Clear();
         }
         else
         {
            // The sequence repeated after we had already found a repetition.
            // This means our 'period' value is computed. We're done.

            break;
         }
      }

      previous.Add(current);

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

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

         current = (inc * BigInteger.Pow(10, cnt)) + current;
      }

      if (!foundRepeat)
      {
         distance++;
      }
      else
      {
         period++;
      }
   }

   return (iteration < IterationLimit);
}

//
// 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 distance, period;

      if (Recur(value, out distance, out period))
      {
         Console.WriteLine(
            "Value {0} repeats in {1} iterations with period {2}",
            value, distance, period);
      }
      else
      {
         Console.WriteLine("Value {0} failed to repeat within {1} iterations",
            value, IterationLimit);
      }

      value += 1;
   }

   return 0;
}
}

Here's a plot of the 'distance' and 'period' for values 1 through 366. The period is generally very short and looks nearly regular (but it isn't quite) and the distance appears random. Viewing it from 20-feet back, this recurrence has less structure in the “iterations to repetition” (aka distance) but more structure in the period than the original Ruth's Recurrence.