I’ve finally figured out a mathematical problem, this is no small achievement for me since I’ve never studied mathematics beyond algebra and what extra I’ve learned has been strictly to do with the practical problems when programming computers.
Here is the problem: List out all positive integers that all contain a x number of bits and do not go over a given length. It’s a combinatorics problem at heart, since your asking for combinations of two kinds of things (1 and 0) in a pre-set number of spaces.
You can produce the number of expected results using a factorial: C = N! / [r! × (N-r)!] where N is length (number of slots) and r is the number of bits. This is useful for checking and gives us some clues into the problem, but doesn’t produce a list of combinations.
This is easy if you want to slog it out and you know some basic programming, just loop from 1 to 2 ^ length, convert the number to a binary string and print if the number of ‘1’ strings is equal to the number of bits required. This is also incredibly slow (download code).
I used the slow method as a check and as raw data and piled through it trying to see if I could find some patterns. The first thing I found was that all even numbers in the set could be generated from a list of odd numbers in the set by simply multiplying them by 2:
AAAABBB (007) AAABBBA (014) AABBBAA (028) ABBBAAA (056) BBBAAAA (112)
AAABABB (011) AABABBA (022) ABABBAA (044) BABBAAA (088)
AAABBAB (013) AABBABA (026) ABBABAA (052) BBABAAA (104)
AABAABB (019) ABAABBA (038) BAABBAA (076)
AABABAB (021) ABABABA (042) BABABAA (084)
AABBAAB (025) ABBAABA (050) BBAABAA (100)
ABAAABB (035) BAAABBA (070)
ABAABAB (037) BAABABA (074)
ABABAAB (041) BABAABA (082)
ABBAAAB (049) BBAAABA (098)
BAAAABB (067)
BAAABAB (069)
BAABAAB (073)
BABAAAB (081)
BBAAAAB (097)
I created a program using the slog method mentioned above to separate out the two sets and produce the output shown above, the second even set produces a steped output where each steps size is the C factorial method mentioned above and inputting the difference between the First set bit and the last set bit (always bit 1 with an odd number).
All the numbers in the first column are odd and I count as my odd set. You’ll also notice that all the odd numbers in the following step are always between the odd and last even value of the last line of the previous step.
The first odd number is always ( 2 ^ N ) – 1 and gives us a starting point in the odd set.
This part took a week on and off to think about, but I worked around the idea that there is a relationship between each of the odd numbers in a given step and then numbers in the next step. The relationship is N = (S * 2) – 1 / N is next value and S is this value. This doesn’t catch all numbers though and it doesn’t explain the factorial like nature.
Not until today did I figure it out, first I drew a tree view of all the numbers and their relationships on my whiteboard board (very useful):
As you can see, each Blue relationship produces a single child in the next step, each Green relationship produces 2 children in the next step and each Red relationship produces 3 children in the next step in a very consistent manner.
So long as you know the factor by which this number was generated from the previous, you could generate all children from it. The start factor is just n – 1 and each factor after can be done as x when looping from 1 to current factor. Add this odd number generation to the even number generation and you have the making of the solution.
Taking all this together I encoded and tested some perl code to generate all integers that only contain a set number of bits, I then checked this against my slog logic above and got it all working:
Download Code Here