# 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.
//
// To view a copy of this license, visit
// 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:
//    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
{
// This means our 'period' value is computed. We're done.

break;
}
}

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;

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.