014.cpp

Go to the documentation of this file.

#include <iostream>
using namespace std;

class sequence
{
  unsigned x;
public:
    sequence (unsigned k)
  {
    x = k;
  }
  unsigned next ()
  {
    if (x & 1)                  //much more efficient than modulus
      x = x * 3 + 1;
    else
      x /= 2;
    return x;
  }
  bool end ()
  {
    return x == 1;
  }
};

class table_list                //look up table
{
  bool list[500000];
public:
    table_list ()
  {
    bool *p = list;
    for (unsigned k = 0; k < 500000; k++, p++)
       *p = 0;
  }
  void insert (unsigned k)
  {
    list[k - 500001] = 1;
  }
  bool find (unsigned k)
  {
    return list[k - 500001];
  }
};

int
main ()
{
  unsigned long long max_count = 0;
  unsigned starting_number;

  table_list table;
  //if k is found in this set, then length of sequence of k should be smaller.

  for (unsigned k = 500001; k < 1000000; k++)
    {
      if (table.find (k))
        continue;               //skip if k is in the table.
      sequence N (k);
      unsigned count = 1;
      while (!N.end ())
        {
          unsigned y = N.next ();
          if (y < 1000000 && y > k)
            table.insert (y);   //insert other exceptions
          count++;
        }
      if (count > max_count)
        {
          starting_number = k;
          max_count = count;
        }
    }
  cout << starting_number << endl;
  return 0;
}