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