A recursion related issue in c#

Question

This is the background to this question:

Background Take any integer n greater than 1 and apply the following algorithm

1. If n is odd then n = n × 3 + 1 else n = n / 2

2. If n is equal to 1 then stop, otherwise go to step 1

The following demonstrates what happens when using a starting n of 6

6 - 3 - 10 - 5 - 16 - 8 - 4 - 2 - 1

After 8 generations of the algorithm we get to 1. It is conjectured that for every number greater than 1 the repeated application of this algorithm will eventually get to 1.

The question is how can I find a number that takes exactly 500 generations to reduce to 1?

The code below is my version but appearntly got some wrong logic. Could you help me correct this? Thanks in advance.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sequence1
{
    class Program
    {
        static void Main(string[] args)
        {
            int start = 1;
            int flag = 0;
            int value;
            while(true){
                int temp = (start - 1) / 3;
                string sta = temp.ToString();
                    if (Int32.TryParse(sta, out value) )
                    {
                        if (((start - 1) / 3) % 2 == 1)
                        {
                            start = (start - 1) / 3;
                            flag++;
                            if (flag == 500)
                            {
                                break;
                            }
                        }
                        else
                        {
                            start = start * 2;
                            flag++;
                            if (flag == 500)
                            {
                                break;
                            }
                        }
                    }
                    else 
                    {
                        start = start * 2;
                        flag++;
                        if (flag == 500)
                        {
                            break;
                        }
                    }

                }


            Console.WriteLine("result is {0}", start);
            Console.ReadLine();
        }
    }
}

Answer 1

Since your question's title is "A recursion related issue", I will give you a recursive solution.

int Process(int input, int maxRecursionDepth)
{
    // condition to break recursion
    if (maxRecursionDepth == 0 || input == 1)
        return input;

    if (input % 2 == 1) // odd case
        return Process(input * 3 + 1, maxRecursionDepth - 1);
    else // even case
        return Process(input / 2, maxRecursionDepth - 1);
}

Now to find all number in a specified range, that return 1 after exactly 500 recursions:

int startRange = 1, endRange = 1000;
int maxDepth = 500;

List<int> resultList = new List<int>();
for (int i = startRange; i <= endRange; i++)
{
    if (Process(i, maxDepth) == 1)
        resultList.Add(i);
}

Answer 2

Your problem is a part of Collatz conjecture (about recursively defined function) which has not been solved yet:

http://en.wikipedia.org/wiki/Collatz_conjecture

so I think brute force is a good way out:

public static int GetMinNumber(int generations) {
  if (generations < 0)
    throw new ArgumentOutOfRangeException("generations");

  // Memoization will be quite good here
  // but since it takes about 1 second (on my computer) to solve the problem
  // and it's a throwaway code (all you need is a number "1979515")
  // I haven't done the memoization

  for (int result = 1; ; ++result) {
    int n = result;
    int itterations = 0;

    while (n != 1) {
      n = (n % 2) == 0 ? n / 2 : 3 * n + 1;
      itterations += 1;

      if (itterations > generations)
        break;
    }

    if (itterations == generations)
      return result;
  }
}

...

int test1 = GetMinNumber(8);   // <- 6
int test2 = GetMinNumber(500); // <- 1979515

Answer 3

Observing the problem,

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

In the third iteration we hit the number 10, which is smaller than 13

So instead of calculating the sequence count every time we can use a cache.

    static int GetMinCollatz(int maxChain)
    {
        const long number = 1000000;
       
        int minNumber = 0;
        // Temporary values
        int tempCount = 0;
        long temp = 0;
        // Cache 
        int[] sequenceCache = new int[number + 1];
        // Fill the array with -1
        for (int index = 0; index < sequenceCache.Length; index++)
        {
            sequenceCache[index] = -1;
        }
        sequenceCache[1] = 1;

        for (int index = 2; index <= number; index++)
        {
            tempCount = 0;
            temp = index;
            // If the number is repeated then we can find 
            // sequence count from cache
            while (temp != 1 && temp >= index)
            {
                if (temp % 2 == 0)
                    temp = temp / 2;
                else
                    temp = temp * 3 + 1;
                tempCount++;
            }
            sequenceCache[index] = tempCount + sequenceCache[temp];
            if (sequenceCache[index] == maxChain)
            {
                minNumber = index;
            }
        }
       
        return minNumber;
    }

For more details refer project euler and this.

Answer 4

A recursive solution

private void ReduceTo1(int input, ref int totalCount)
        {
            totalCount++;
            if (input % 2 == 0)
            {
                input = input / 2;
            }
            else
            {
                input = input * 3 + 1;
            }
            if (input != 1)
                ReduceTo1(input, ref totalCount);               

        }

to test

int desireValue = 0;
            for (int i = 1; i < 100000; i++)
            {
                int totalCount = 0;
                ReduceTo1(i, ref totalCount);
                if (totalCount >= 500)
                {
                    desireValue = i;
                    break;
                }
            }