//cantor.cpp
//Program to do Cantor expansion of a positive integer.
//Here are examples of cantor expansions:
// 3:   1(2!) 1(1!)
// 27:  1(4!) 1(2!) 1(1!)
// 1213: 1(6!) 4(5!) 2(3!) 1(1!)
//WARNING: in Visual C++ the program goes tilt when 
//you enter an integer that is too large. Program does not 
//try to avoid this. Program works fine on Digital Alpha.

#include <iostream>
using namespace std;

void cantor(unsigned long number);

int main()
{
  unsigned long n;
  
  for(;;)
    {
      cout << "Enter an integer for which you want Cantor's decomposition: ";
      cin >> n;
      if (n == 0) return 0;
      cout << "\n" << "The Cantor expansion of  " << n << "  is: \n \t";
      cantor(n);
      cout << "\n";
    }
}

//Returns the factorial of n
unsigned long fact(unsigned long n)
{
	unsigned long val = 1;
	for (; n>1; --n)
	    val *= n;
	return val;
}

//Prints out Cantor expansion of number on current line.
//It works for all unsigned long integers, independently
//of the computer being used.
void cantor(unsigned long number)
{
  //Here the static variables are initialized only once
  enum{MAXFACT = 30}; // We should not have an unsigned long greater that 30!
  static unsigned long facts[MAXFACT];
  static int maxfact = MAXFACT; // number of values in facts array
  static int notFirstTime = 0;

  if(!notFirstTime) 
  // initialize the facts array the first time cantor is called
  {
	notFirstTime = 1;
	facts[0] = 1; 
	for (int k = 1; k<MAXFACT; ++k)
	{
	  unsigned long val;
	  val = fact(k+1);
	  if (val < facts[k-1]) // we have fact(k+1) < fact(k) only if overflow
	    {
	      maxfact = k;
	      break;
	    }
	  facts[k] = val;
	}
  }

  while (number > 0)
    {
      int factor;
      for (factor=0; (factor < maxfact) && (facts[factor] <= number); factor ++);
      --factor;
      cout << number/facts[factor] << "(" << (factor+1) << "!) ";
      number %= facts[factor];
    }
}