1:  using System;
   2:   
   3:  namespace ZumkellerPartitions
   4:  {
   5:      /// <summary>
   6:      /// Computes Zumkeller numbers and partitions
   7:      /// </summary>
   8:      class ZumkellerNumber
   9:      {
  10:          static int[] divisors;
  11:          static int[] partition;
  12:          static int currentSum;
  13:          static int partitionCount;
  14:          static int divisorCount;
  15:          static int numbersFound;
  16:          static int sigma2;
  17:          static int test;
  18:          static bool found;
  19:          static bool printPartition;
  20:   
  21:          static void SearchDivisors()
  22:          {
  23:              divisorCount = 0;
  24:   
  25:              for (int i = 1; i <= test; i++)
  26:              {
  27:                  if ((test % i) == 0)
  28:                  {
  29:                      divisors[divisorCount++] = i;
  30:                  }
  31:              }
  32:          }
  33:   
  34:          static int SumDivisors()
  35:          {
  36:              int sum = 0;
  37:              for (int i = 0; i < divisorCount; i++)
  38:              {
  39:                  sum += divisors[i];
  40:              }
  41:              return sum;
  42:          }
  43:   
  44:          static bool IsInPartition(int n)
  45:          {
  46:              for (int i = 0; i < partitionCount; i++)
  47:              {
  48:                  if (partition[i] == n) return true;
  49:              }
  50:              return false;
  51:          }
  52:   
  53:          static void PrintPartitions()
  54:          {
  55:              if (!printPartition)
  56:              {
  57:                  Console.WriteLine(test);
  58:                  return;
  59:              }
  60:   
  61:              bool first = true;
  62:              Console.Write("{0} [", test);
  63:              for (int i = 0; i < divisorCount; i++)
  64:              {
  65:                  int divisor = divisors[i];
  66:                  if (!IsInPartition(divisor))
  67:                  {
  68:                      if (first)
  69:                      {
  70:                          first = false;
  71:                      }
  72:                      else
  73:                      {
  74:                          Console.Write(", ");
  75:                      }
  76:                      Console.Write(divisor);
  77:                  }
  78:              }
  79:   
  80:              Console.Write("] [");
  81:              first = true;
  82:              for (int i = 0; i < partitionCount; i++)
  83:              {
  84:                  if (first)
  85:                  {
  86:                      first = false;
  87:                  }
  88:                  else
  89:                  {
  90:                      Console.Write(", ");
  91:                  }
  92:                  Console.Write(partition[i]);
  93:              }
  94:              Console.WriteLine("]");
  95:          }
  96:   
  97:          static void SearchPartitions(int depth)
  98:          {
  99:              if (depth == divisorCount) return;
 100:              for (int i = depth; i < divisorCount; i++)
 101:              {
 102:                  int n = divisors[i];
 103:                  currentSum += n;
 104:                  partition[partitionCount++] = n;
 105:                  if (currentSum == sigma2)
 106:                  {
 107:                      PrintPartitions();
 108:                      found = true;
 109:                      numbersFound++;
 110:                      break;
 111:                  }
 112:                  SearchPartitions(i + 1);
 113:                  if (found) break;
 114:                  currentSum -= n;
 115:                  partitionCount--;
 116:              }
 117:          }
 118:   
 119:          static public int Search(int max, bool _printPartition)
 120:          {
 121:              divisors = new int[max];
 122:              partition = new int[max];
 123:   
 124:              printPartition = _printPartition;
 125:   
 126:              for (test = 0; test <= max; test++)
 127:              {
 128:                  SearchDivisors();
 129:                  int sigma = SumDivisors();
 130:                  if ((sigma % 2) == 0 && (2 * test) <= sigma)
 131:                  {
 132:                      sigma2 = sigma / 2;
 133:                      currentSum = 0;
 134:                      partitionCount = 0;
 135:                      found = false;
 136:                      SearchPartitions(0);
 137:                  }
 138:              }
 139:              return numbersFound;
 140:          }
 141:   
 142:          static void Main()
 143:          {
 144:              var watch = new System.Diagnostics.Stopwatch();
 145:              watch.Start();
 146:   
 147:              int numbersFound = ZumkellerNumber.Search(1000, true);
 148:   
 149:              watch.Stop();
 150:              Console.WriteLine("Zumkeller numbers found " + numbersFound);
 151:              Console.WriteLine("Elapsed milliseconds " + watch.ElapsedMilliseconds);
 152:              Console.ReadLine();
 153:          }
 154:      }
 155:  }
 156: