## Phil Harvey’s Puzzle

### November 15, 2011

Today’s exercise comes to us from Michi’s blog:

Phil Harvey wants us to partition {1,…,16} into two sets of equal size so each subset has the same sum, sum of squares and sum of cubes.

Your task is to find the partition. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Here’s my Python interactive session, with one (typo, error) removed.

If you run my version of the program, you’ll see that there are two unique solutions, only one of which divides { 1..16 } into subsets of equal size. Both solutions have the same sums though. Interesting.

Ah. That teaches me to code before breakfast. I have a small error in the program above: the line which reads val = i should be “val = i + 1 ;”.

When that change is made, it finds the single, unique solution to the problem. My hint that something was wrong was that the sum of the numbers was 60. The sum of the numbers from 1 to 16 should be 136, and since they are divided into two partitions, they should each sum to 68.

Since Michi and kernelbob already posted some Python, here’s a Common Lisp solution:

and here’s a Haskell one:

In both, I calculated the sums of the integers, squares of integers, and cubes of integers in {1, …, 16} via formulae for the first three types of figurate numbers.

Here’s a ruby version …

This problem can be formulated as a (binary) integer programming problem.

For example, using GMPL

I just found the “snoob” function over here. http://www.steike.com/code/useless/evil-c/ That led to this somewhat golfed C solution.

Basically, snoob(n) returns the next integer after n with the same number of bits set. If we use a bit mask to denote the members of the first partition, we can use snoob() to iterate through the partitions directly.

for (i = 0xFF; i <= 0xFF00; i = snoob(i)) { …}

// 0xFF is the first partition, {1, 2, 3, 4, 5, 6, 7, 8}.

// 0xFF00 is the last partition, {9, 10, 11, 12, 13, 14, 15, 16}.

snoob() should be blazingly fast since it's about 7 arithmetic operations and no memory references.

#include <stdio.h>

#include <string.h>

unsigned snoob(unsigned x) {

unsigned smallest = x & -x;

unsigned ripple = x + smallest;

unsigned ones = x ^ ripple;

ones = (ones >> 2) / smallest;

return ripple | ones;

}

int main()

{

unsigned i, j, k, l;

for (i = 0xFF; i <= 0xFF00; i = snoob(i)) {

unsigned sums[2][3] = { { 0, 0, 0 }, { 0, 0, 0 } };

for (j = 0; j < 16; j++)

for (k = 0, l = 1; k < 3; k++)

sums[!(i & 1 << j)][k] += l *= j + 1;

if (!memcmp(sums[0], sums[1], sizeof sums[0])) {

for (j = 0; j < 16; j++)

if (i & 1 << j)

printf("%d ", j + 1);

printf("\n");

}

}

return 0;

}

Oops. Formatted.

A haskell one-liner in ghci:

And a little sorter solution with list comprehension:

@neez Nice Haskell solution. You can also do it without precalculating the constants.

@Jan Van lent

Wow, beautiful soution, especially using the i=0 case to partition into equal sized sets!

@neez Well, it is only a small change from your solution. I used the same trick in the GMPL solution. Note that the constraint that the sets be of equal size is actually redundant. You can try with [1..3], [2..3] and even just 3 and they all give the same solution.

Create 2 (random) partitions, and swap between them, making sure the difference is less. Keep doing this until we get a difference of 0.

package com.algorithm;

import java.util.Arrays;

public class SameSumSquareCube {

private static int[] set1;

private static int[] set2;

public static void main(String[] args) {

set1 = new int[] {1, 2, 3, 4, 5, 6, 7, 8};

set2 = new int[] {9, 10, 11, 12, 13, 14, 15, 16};

recursive(7);

System.out.println(“completed”);

}

private static void recursive(int count) {

for (int i=count; i>=0; i–) {

for (int j=7; j>=0; j–) {

int temp = set1[i];

set1[i] = set2[j];

set2[j] = temp;

if (isCubeSumEqual(set1, set2) && isSquareSumEqual(set1, set2) && isSumEqual(set1, set2)) {

System.out.println(Arrays.toString(set1));

System.out.println(Arrays.toString(set2));

}

}

recursive(–count);

}

}

private static boolean isCubeSumEqual(int[] set1, int[] set2) {

int set1CubeSum = 0;

for (int number : set1) {

set1CubeSum += number * number * number;

}

int set2CubeSum = 0;

for (int number : set2) {

set2CubeSum += number * number * number;

}

return set1CubeSum == set2CubeSum;

}

private static boolean isSquareSumEqual(int[] set1, int[] set2) {

int set1SquareSum = 0;

for (int number : set1) {

set1SquareSum += number * number;

}

int set2SquareSum = 0;

for (int number : set2) {

set2SquareSum += number * number;

}

return set1SquareSum == set2SquareSum;

}

private static boolean isSumEqual(int[] set1, int[] set2) {

int set1Sum = 0;

for (int number : set1) {

set1Sum += number;

}

int set2Sum = 0;

for (int number : set2) {

set2Sum += number;

}

return set1Sum == set2Sum;

}

}

[…] the weekend, I was amusing myself with this problem from the always entertaining Programming Praxis. The problem is to partition the set {1, 2, […]