//------------------------------------------------------------------- // enigma1357.c (c) 2005 by Charles Petzold (www.charlespetzold.com) // // "Diminishing Powers" by Richard England, // from New Scientist, 10 September 2005, page 54. // // Integers from 1 to 12 are divided into two groups where the sum // of the cubes of the integers are equal. A minimum number of // integers are switched from one group to another so that the // sums of the squares are equal. A minimum number of integers // are switched from one group to another so that the sum of the // integers are equal. What integers were switched? //------------------------------------------------------------------- #include #include // A function that counts the number of 1 bits in its argument. int CountBits(int number) { int i, bit = 1, total = 0; for (i = 0; i < 31; i++, bit <<= 1) if (number & bit) total++; return total; } int main(void) { int i, split, sum1 = 0, sum2 = 0, sum3 = 0; int numSplit1 = 0, numSplit2 = 0, numSplit3 = 0; int * pSplit1 = 0, * pSplit2 = 0, * pSplit3 = 0; int bit, i1, i2, i3, numChange, index1, index2, index3; // Sum the integers from 1 to 12, their squares, and their cubes for (i = 1; i <= 12; i++) { sum1 += i; sum2 += i * i; sum3 += i * i * i; } // Now split will be a integer between 0 and 0xFFF, where the bits // represent the distribution of the integers 1 to 12 between // two groups, ie, 0 bit means one group, 1 bit means the other. for (split = 0; split < 0xFFF; split++) { int subsum1 = 0, subsum2 = 0, subsum3 = 0; // The three subsum's are the sums of the integers, squares, // or cubes in one of the groups. for (i = 1, bit = 1; i <= 12; i++, bit <<= 1) { if (split & bit) { subsum1 += i; subsum2 += i * i; subsum3 += i * i * i; } } // If the split divides the sum in half (that is, subsum is half // of sum), then store the value of split. if (subsum1 == sum1 / 2) { pSplit1 = realloc(pSplit1, ++numSplit1 * sizeof(int)); pSplit1[numSplit1 - 1] = split; } if (subsum2 == sum2 / 2) { pSplit2 = realloc(pSplit2, ++numSplit2 * sizeof(int)); pSplit2[numSplit2 - 1] = split; } if (subsum3 == sum3 / 2) { pSplit3 = realloc(pSplit3, ++numSplit3 * sizeof(int)); pSplit3[numSplit3 - 1] = split; } } // Now find the smallest number of bits for the various splits // from cubes to squares. numChange = 12; for (i2 = 0; i2 < numSplit2; i2++) for (i3 = 0; i3 < numSplit3; i3++) { int numSwitch = CountBits(pSplit2[i2] ^ pSplit3[i3]); if (numSwitch != 0 && numSwitch < numChange) { index2 = i2; index3 = i3; numChange = numSwitch; } } // Now find the smallest number of bits for splits from the // square split found above to the integer split. numChange = 12; for (i1 = 0; i1 < numSplit1; i1++) { int numSwitch = CountBits(pSplit1[i1] ^ pSplit2[index2]); if (numSwitch != 0 && numSwitch < numChange) { index1 = i1; numChange = numSwitch; } } printf("%0.4x --> %0.4x --> %0.4x\n", pSplit3[index3], pSplit2[index2], pSplit1[index1]); // Print the actual numbers changing from one group to the other. printf("Transfer "); for (i = 0, bit = 1; i < 12; i++, bit <<= 1) if ((pSplit2[index2] ^ pSplit3[index3]) & bit) printf("%i ", i + 1); printf("then "); for (i = 0, bit = 1; i < 12; i++, bit <<= 1) if ((pSplit2[index2] ^ pSplit1[index1]) & bit) printf("%i ", i + 1); printf("\n"); return 0; }