Crazy Math

Here'a a conjecture (my first):

Let S{n - x} represent the set of all numbers in the set {2^n .. 2^(n + 1) - 1} with n - x factors. If n = 3, S{n - 1} therefore represents the set of all numbers in the set {2^3..(2^4 - 1)} with n - 1, or 2, factors. Let us progress through the sets from n = 1 to n = infinity. As we progress from set to set, each subset S{n - x} will eventually reach a maximum "size". For instance, in any set {2^n .. 2^n - 1}, the maximum number of members with n - 1 factors is 5. Each subset S{n - x} "begins" with a set of prime numbers (these occur when n - x = 1), and "end" in some other set. Let us define the "length" of a set as the number of sets between the "beginning" set and the "ending" set, _not_ including those two sets.


Conjecture: The "length" of a set S(n - x) = the xth member of the Lower Wythoff sequence.


Or, in other words, the "length" of S(n - x); x = 1 is 1, x = 2 is 3, x = 3 is 4, x = 4 is 6, x = 5 is 8, and so on. If we add 2 to each member of the Lower Wythoff sequence, we get the absolute length (i.e., the length including the first and last set).

So, my somewhat scatterbrained post from yesterday (I was noticing several logical nonsequitirs, among other delights) also contained an interesting error, and one which kinda throws a wrench in the works. It's like this: All is fine and good with the symbolic representation of the composition of some set, up until n = 5. However, we run into a problem in n = 5. Namely, we can't say that Cd3 (i.e. the third degree composite) is odd. n = 5 is this set -- {32..65}. Now, the smallest n-degree odd composite is 3^x. The first few values are 3, 9, 27, 81... If you've noticed, there is no member of {32..63} with a factorization of 3^x. Since 3^x is the smallest possible odd composite of degree x, the only possible members of {Cd3} in {32..63} have to be even, since the range of the function BigOmega is smooth. No biggie, since that's the case we can just figure out whether or not 3^x lies in a set and work things out from there. The problem, though, lies in the symbolic representation I laid out in the last post. In it, I defined Cdn as representing an odd composite of degree n. It turns out this is not always the case -- Cdn could also represent an even composite. This means the set of all {Cdn} can include both even or odd numbers, that it overlaps with the even members and thus cannot be rigidly defined as meaning "an odd composite of degree n". Instead, the definition should be "a composite of degree n". This gums up our ability to count symbolically represented even and odd numbers in these sets. I.e., if we look at {E, P} (which has a symbol count of 2), there are two members represented symbolically. However, if we look now at {{{E, P} * 2} & P} * 2 | {Cd2} & {P} (which has a symbol count of 5), we can't say with a certainty whether Cd2 contains even numbers, odd numbers, or both. By definition all even numbers have been defined symbolically and we cannot assume that, say, {Cd2} doesn't include {P * 2}, which means we cannot say with certainty that the symbol count equals 5. Since we can't accurately count the symbolic representation of the set, we cannot say with accuracy how many symbolic representations there are in the set _without_ figuring out first if that particular set includes some number 3^x.

I kind of knew this was true in the back of my mind, but it wasn't until I worked out the symbolic representation for {32..63} that I realized the obvious error. That doesn't mean, though, that all is lost. Sometime in the next few days I'll post about an interesting consequence of the disjointed overlap of n = y and 3^x. We already know that, with the exception of the set {2, 3} we never have a set where the largest odd composite is 3^n. This would mean that 2^n and 3^n were in the same set, which they cannot be since the _smallest_ number with n possible factors is 2^n, and therefore 3^n has to occur in at least the next set, i.e. n + 1. Until then, you might want to consider the set of numbers output by performing BigOmega for each member of the set {2..256}. It will figure prominently in the next post...

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:

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.

Two thoughts:

a.) Factoring isn't the inverse of multiplication, it's the inverse of addition.

b.) While "unit" addition with any number other than 1 cannot produce a series which contains primes, addition using _offsets_ will. Example -- unit addition with 2 + 2(Z) (2, 4, 6, 8...) as opposed to unit addition of 2 with an offset of +1, i.e. 2 + 3(Z) (2, 5, 8, 11, 14, 17...). Not all offset series will contain primes.

The number 1. I've been thinking about it alot recently, due to the fact that it "acts" different than the other numbers. for instance, in the case of the primes they all have two factors -- the number one and themselves. These aren't useful (well, that's the prevailing opinion anyway...) factors, but they do point out the main difference between the number one and the other real numbers. Namely, one divided by itself is itself. While we can get any other integer to behave like the number one with respect to BigOmega (by performing what was described a few posts below as "unit addition"), none will act exactly the same. Any other integer will create a pattern where the least number of factors any member can have is two. In this sense, the only way to produce prime numbers is by performing unit addition with the number one. All the other "primes" using other units will have at least two factors. This is not counting, of course, our "universal" factors -- one and the number itself. The really interesting part of all this is that the concept of any number divided by itself equals one applies to all sorts of suspects outside the set of positive integers; rational numbers, irrational numbers, imaginary numbers, complex numbers, etc. PI divided by PI is one, even though no end has been found to the digits in PI. My gut tells me that part of the answer to knowing a number's factor base is found in a solid understanding of what the concept of one really means, and how to disassemble its behaviour and duplicate it elsewhere. That's an odd concept, transmuting the logical behaviour of 1 to another number, say, 22. But who says it's impossible? Perhaps it is, but 1 is still an interesting number (even if it is the loneliest).