LateNightHacking Louis Journal

Auth

So I had this side problem. I wanted a set of numbers such that no sum of numbers in the set was also in the set. This would also mean that, given a sum, you could figure out which numbers in the set were added to create that sum. For multiplying, you use the set of prime numbers. Every number has a unique prime factorization. I wasn't sure what the equivalent was for addition. Did it have something to do with Golomb Rulers? No, that's for subtraction. I wasn't really sure what the answer was. So, I wrote a little program to test it out.

//--------------------------------------------------------------------
/** Prints a set of numbers whose sums are all unique.
 * @author Created by Louis Thomas on 2012-02-01. */
public class SumsDemo {

    //----------------------------------------------------------------
    public static void main(String[] args) {
        Set prohibited=new HashSet();
        for (int nIndex=1; nIndex<100; nIndex++) {
            if (!prohibited.contains(nIndex)) {
                System.out.println(nIndex);
                Set newProhibited=new HashSet();
                for (Integer bad : prohibited) {
                    newProhibited.add(bad);
                    newProhibited.add(bad+nIndex);
                }
                newProhibited.add(nIndex);
                prohibited=newProhibited;
            }
        }
    }
}

What was the result?

1
2
4
8
16
32
64

OK. I felt pretty silly. Of course! I've used bit fields a bazillion times before. I should have known. That's pretty much the definition right there. Basic math. Nothing to see here. Go feel stupid in a corner.

Then for kicks, I set the initial value to 10.

10
11
12
13
14
15
16
17
18
19
20

Wait, what? Starting at 1, I get 7 unique values less than 100 (and it takes exponentially larger values to increase the size of the set). Yet, starting at 10, I get 11 unique values? If you start from 50, you get 50 unique numbers, 50-99.

Clearly, there's more going on here than I first thought.

If you start from 5 and go up to 1000, you get

5
6
7
8
9
10
41
42
43
44
211
212
213
214

What does it really mean? I'm not sure. I need to get back to my main task. But it certainly bears further investigation. How do the contiguous sequences relate to the normal exponential pattern? (Possibly the size of the sum of all the elements in the set is the same for a given set size?) Also, are the two set definitions I gave above truly the same? (I think not.) What about a set where no sum of any multiple of set elements was in the set?

˜ ™

So I was worried for a while when I noticed that while 1+2+4+8+16+32+64=127 (and log2(127)≈6.99), 10+11+12+13+14+15+16+17+18=126 which suggested you should be able squeeze 9 fields into a number that previously could only hold 7 fields. Then I noticed the obvious problem that 10+13=11+12=23.

The problem is with my conflicting definitions of the set of numbers. The sets given above meet the rule (A) "No sum of numbers in the set is also in the set." That is, 13 cannot be created by adding any combination of 10, 11, and 12. Also, 23 is not in the set. However, as shown above, this does not mean that you can figure out which numbers in the set were added to create a given sum. Restated, (!B) there is not a unique subset that adds up to each sum. While B implies A, A does not imply B.

If I add a rule to my program that enforces (B) types sets, then the results are much more what you would expect.

10 - 000 1010
11 - 000 1011
12 - 000 1100
14 - 000 1110
17 - 001 0001
34 - 010 0010
68 - 100 0100

50 - 011 0010
51 - 011 0011
52 - 011 0100
54 - 011 0110
57 - 011 1001
63 - 011 1111
74 - 100 1010

Regarding "a set where no sum of any multiple of set elements was in the set", this is not too interesting. With (A) type sets, you have to start with large numbers to get many numbers in your set. If you start with 1, you have a single digit set. If you start with 2, you get a two digit set, and so on. With (B) type sets, you only get 1 element: given element x in the set, you can't add element y because x*y can be created with both y x's and x y's.