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: