Wednesday, June 16, 2004
Further results on composition of sets of the form {2^n..2^(n + 1) - 1}
A few posts ago I asked "what is the smallest number x with n = BigOmega(x)" (I didn't phrase the question quite that way, but that's what I meant...). The answer is 2^n. I.e., the smallest number with BigOmega(x) = 2 is 2^2, or 4 (BigOmega(4) = 2). Since this is the case, using successive values of 2^n to divide the integers is a logical way to examine the properties of BigOmega(x). These sets can be expressed generally like this: {2^n..2^(n+1) - 1}.
I've been interested in these sorts of sets for awhile, mostly because they have interesting properties. To give you a more concrete idea of what these sets look like, here a a few:
{2, 3} = {2^1..2^2 - 1}, or n = 1
{4, 5, 6, 7} = {2^2..2^3 - 1}, or n = 2
{8, 9, 10, 11, 12, 13, 14, 15} = {2^3..2^4 - 1}, or n = 3
and so on.
We can define rules that govern these sets fairly easily. Notice, for instance, that when we move from set to set, the even members of the next set are equal to the odd numbers of the previous set times 2. As an example, the even members of n = 2 are 4 and 6, which are derived as follows:
4 = 2 * 2
6 = 3 * 2
This can also be expressed as {2, 3} * 2.
If we were to take BigOmega of all the members of a set with n = y, we'd see that the _range_ of BigOmega is always (1..y), or all the integers beween 1 and y. For example, using n = 2 again we have BigOmega{4, 5, 6, 7} = {2, 1, 2, 1}. Therefore the range of BigOmega over (1..y) is "smooth" (meaning there are no skips). For some other set where n = 15, BigOmega of that set will range over (1..15), without skipping any integers between 1 and 15. Because of how these sets are constructed we can also deduce that the first member will always be even for n > 0. We will now use these rules, and some symbols defined below, to define a symbolic representation of the "composition" of these sets.
Let P represent any prime. E represents the only even prime, 2, and Cdn represents some odd composite number of degree n (ex: Cd3 is a 3rd degree, odd composite). For example, 27 is an odd composite number of degree 3, because BigOmega(27) = 3. In other words, we use BigOmega to determine the "degree" of a number. We use the pipe symbol, "|", to seperate even and odd elemets of a set or group of sets. Even elements will always be listed on the left, and odd elements on the right of the pipe symbol.
We now construct sets using these symbols to represent the "structure" of some set {2^n..2^(n+1) - 1}. For illustrative purposes, I'm going to list the members of these sets explicitly. Below each set is a short explanation of what all the symbols mean:
{2, 3} = {2^1..2^2 - 1} = {E, | P}
This set contains one prime P and the even prime, E.
{4, 5, 6, 7} = {{E, P} * 2} | {P}
This set contains all members of the previous set multiplied by 2, and at least one new member, an odd prime P. The rules governing these sets disallow an odd composite from appearing in this set.
{8, 9, 10, 11, 12, 13, 14, 15} =
{{{E, P} * 2} & P} * 2 | {Cd2} & {P}
This set contains all the members of the previous set multiplied by 2, and at least one new prime and one new second-degree odd composite.
If we count the number of members represented symbolically in each of our sets, we get our series.
Generating function: 1 + 1 = 2, 2 + 1 = 3, 3 + 2 = 5, 5 + 3 = 8, 8 + 4 = 12, 12 + 5 = 17, and so on.
The size of each set is easily determined (size = 2^n), thus we can see how our "error" grows as we progress from set to set:
We can also see how the error grows for the "even" numbers and "odd" numbers. Because of how our sets are constructed, the number of even and odd members is simply (2^n)/2, thus in set {2^2..2^3 - 1}, the size of the even and odd sets is (2^2/2), or 2. from our symbolic representation above, we can then determine the "error" for even and odd members seperately:
That's probably as much crazy math as any one person can handle for a day, so we'll stop here. More to come later.
I've been interested in these sorts of sets for awhile, mostly because they have interesting properties. To give you a more concrete idea of what these sets look like, here a a few:
{2, 3} = {2^1..2^2 - 1}, or n = 1
{4, 5, 6, 7} = {2^2..2^3 - 1}, or n = 2
{8, 9, 10, 11, 12, 13, 14, 15} = {2^3..2^4 - 1}, or n = 3
and so on.
We can define rules that govern these sets fairly easily. Notice, for instance, that when we move from set to set, the even members of the next set are equal to the odd numbers of the previous set times 2. As an example, the even members of n = 2 are 4 and 6, which are derived as follows:
4 = 2 * 2
6 = 3 * 2
This can also be expressed as {2, 3} * 2.
If we were to take BigOmega of all the members of a set with n = y, we'd see that the _range_ of BigOmega is always (1..y), or all the integers beween 1 and y. For example, using n = 2 again we have BigOmega{4, 5, 6, 7} = {2, 1, 2, 1}. Therefore the range of BigOmega over (1..y) is "smooth" (meaning there are no skips). For some other set where n = 15, BigOmega of that set will range over (1..15), without skipping any integers between 1 and 15. Because of how these sets are constructed we can also deduce that the first member will always be even for n > 0. We will now use these rules, and some symbols defined below, to define a symbolic representation of the "composition" of these sets.
Let P represent any prime. E represents the only even prime, 2, and Cdn represents some odd composite number of degree n (ex: Cd3 is a 3rd degree, odd composite). For example, 27 is an odd composite number of degree 3, because BigOmega(27) = 3. In other words, we use BigOmega to determine the "degree" of a number. We use the pipe symbol, "|", to seperate even and odd elemets of a set or group of sets. Even elements will always be listed on the left, and odd elements on the right of the pipe symbol.
We now construct sets using these symbols to represent the "structure" of some set {2^n..2^(n+1) - 1}. For illustrative purposes, I'm going to list the members of these sets explicitly. Below each set is a short explanation of what all the symbols mean:
{2, 3} = {2^1..2^2 - 1} = {E, | P}
This set contains one prime P and the even prime, E.
{4, 5, 6, 7} = {{E, P} * 2} | {P}
This set contains all members of the previous set multiplied by 2, and at least one new member, an odd prime P. The rules governing these sets disallow an odd composite from appearing in this set.
{8, 9, 10, 11, 12, 13, 14, 15} =
{{{E, P} * 2} & P} * 2 | {Cd2} & {P}
This set contains all the members of the previous set multiplied by 2, and at least one new prime and one new second-degree odd composite.
If we count the number of members represented symbolically in each of our sets, we get our series.
Generating function: 1 + 1 = 2, 2 + 1 = 3, 3 + 2 = 5, 5 + 3 = 8, 8 + 4 = 12, 12 + 5 = 17, and so on.
The size of each set is easily determined (size = 2^n), thus we can see how our "error" grows as we progress from set to set:
| known | total size | unknown |
| 2 | 2 | 0 |
| 3 | 4 | 1 |
| 5 | 8 | 3 |
| 8 | 16 | 8 |
| 12 | 32 | 20 |
| 17 | 64 | 47 |
| 23 | 128 | 105 |
| 30 | 256 | 226 |
| 38 | 512 | 474 |
| 47 | 1024 | 977 |
We can also see how the error grows for the "even" numbers and "odd" numbers. Because of how our sets are constructed, the number of even and odd members is simply (2^n)/2, thus in set {2^2..2^3 - 1}, the size of the even and odd sets is (2^2/2), or 2. from our symbolic representation above, we can then determine the "error" for even and odd members seperately:
| known even | size even | unknown |
| 1 | 1 | 0 |
| 2 | 2 | 0 |
| 3 | 4 | 1 |
| 5 | 8 | 3 |
| 8 | 16 | 8 |
| 12 | 32 | 20 |
| 17 | 64 | 47 |
| 23 | 128 | 105 |
| 30 | 256 | 226 |
| 38 | 512 | 474 |
| known odd | size odd | unknown |
| 1 | 1 | 0 |
| 1 | 2 | 1 |
| 2 | 4 | 2 |
| 3 | 8 | 5 |
| 4 | 16 | 12 |
| 5 | 32 | 27 |
| 6 | 64 | 58 |
| 7 | 128 | 121 |
| 8 | 256 | 248 |
| 9 | 512 | 503 |
That's probably as much crazy math as any one person can handle for a day, so we'll stop here. More to come later.
