Saturday, May 22, 2004
Factoring, continued
Here's the first part in a series about my investigations into factoring. As I said earlier, I think that any "algorithm" (I'll use that word to mean both computer programs (classical or quantum) and equations) that successfully factors numbers in polynomial time should output all the factors and simultaneously output Bigomega.
Let's begin by looking at the _function_ Bigomega. It is defined as a function which outputs all of the factors of a number with multiplicity. Bigomega of 1 thru 10 is {1, 1, 1, 2, 1, 2, 1, 3, 2, 2}. Now, let's say we want to know Bigomega of any number x multiplied by 1 thru 10. The answer will be Bigomega{1..10} + Bigomega(x). So, if we were to use the number 3, then Bigomega of our new set (i.e., 3 * {1..10}) is {1, 2, 2, 3, 2, 3, 2, 4, 3, 3}. Note what happens with the number 1. When you multiply any number by 1, you get the same number, thus multiplying by 1 has no effect on Bigomega, so from here on out when speaking about multiplication we'll skip the number 1 (one, though, will become much more interesting in a moment...).
For now, let's formalize this a bit:
I = set of all positive integers
S = some subset {n1...nx} of I
x = member of I
So, Bigomega(S * x) = Bigomega S + Bigomega x, S > 1
For S = 1, Bigomega(S * x) = Bigomega x
Multiplication, then, is pretty straightforward...right? Let's now examine the case of addition. Before getting into sets, we'll start simple. Take, for instance, the case of the number 3. Add 1 to 3 we get 4. Bigomega of 3 = 1, while Bigomega of 4 = 2. Add 1 again, we get 5, and Bigomega of 5 is 1. If we do this on to infinity, we'll end up with Bigomega I, I > 3. Let's make this more interesting. Consider, for a moment, what multiplication really means. If we write "3 * 5", we could just as easily say "add three to itself 5 times", or "add 5 to itself 3 times". In other words, multiplication is just a special case of addition. It's some "unit" x (which is a member of I) added to itself n number of times. So, multiplciation is just "unit addition". Let's consider that for a moment -- "unit addition" creates the same Bigomega output as multiplication. Whether we add 1 to itself some n number of times or 5 to itself some n number of times, the result will be the same - Bigomega(x) + Bigomega(n).
So, if that's the case... Let me introduce a concept I've been playing with that I call "offset". I'm still looking into it, which means I don't understand everything about it. Anyway, it works like this. Say we use a unit of 10. 10 + 10 = 10 * 2 = 20. Bigomega(20) = 3 (because 20 = 2 * 2 * 5). What if, instead of doing 10 + 10, we do 10 + 9, 10 + 9 + 9, etc.? We'll get 10, 19, 28, 37, and so on. In this case, the "offset" is +1. This is so because our series could also be expressed as 1 + 9, 1 + 9 + 9, etc. These "offset" series produce different patterns of output for Bigomega. One of the areas I'm interested in examining is how these sets relate to each other. You may have noticed that for some set created by using 9 as the unit of addition, there are exactly 9 possible offisets which won't repeat themselves. Note that if you extended all 9 sets to infinity and combined them, you'd end up with the set I, I > 9. Now, if you're really paying attention you'll notice something cool here. If we start with, say, 1 + 9, then continue on up to 8 + 9, we'll get every number except multiples of 9. So, we now add in 9 + 9, or offset 0... This system is feeding back on itself, i.e. that last set is simply 9 * I. We _have_ to have a "unit" set if we want to recombine the sets to get I, I > 9. The implications of this are very interesting, namely, that within the set of integers I, the basic pattern Bigomega(I) + Bigomega(x) repeats itself many, many times. Bigomega I _is_ the basic pattern, but it's composed on an infinite number of copies of itself!
I'll go ahead and stop here for now. In the meantime, let me give you something to think about until my next post (whenever that is). What is the smallest possible number with n number of factors? Or, in other words, what's the smallest possible number with 3 factors? with 4? And so on.
Let's begin by looking at the _function_ Bigomega. It is defined as a function which outputs all of the factors of a number with multiplicity. Bigomega of 1 thru 10 is {1, 1, 1, 2, 1, 2, 1, 3, 2, 2}. Now, let's say we want to know Bigomega of any number x multiplied by 1 thru 10. The answer will be Bigomega{1..10} + Bigomega(x). So, if we were to use the number 3, then Bigomega of our new set (i.e., 3 * {1..10}) is {1, 2, 2, 3, 2, 3, 2, 4, 3, 3}. Note what happens with the number 1. When you multiply any number by 1, you get the same number, thus multiplying by 1 has no effect on Bigomega, so from here on out when speaking about multiplication we'll skip the number 1 (one, though, will become much more interesting in a moment...).
For now, let's formalize this a bit:
I = set of all positive integers
S = some subset {n1...nx} of I
x = member of I
So, Bigomega(S * x) = Bigomega S + Bigomega x, S > 1
For S = 1, Bigomega(S * x) = Bigomega x
Multiplication, then, is pretty straightforward...right? Let's now examine the case of addition. Before getting into sets, we'll start simple. Take, for instance, the case of the number 3. Add 1 to 3 we get 4. Bigomega of 3 = 1, while Bigomega of 4 = 2. Add 1 again, we get 5, and Bigomega of 5 is 1. If we do this on to infinity, we'll end up with Bigomega I, I > 3. Let's make this more interesting. Consider, for a moment, what multiplication really means. If we write "3 * 5", we could just as easily say "add three to itself 5 times", or "add 5 to itself 3 times". In other words, multiplication is just a special case of addition. It's some "unit" x (which is a member of I) added to itself n number of times. So, multiplciation is just "unit addition". Let's consider that for a moment -- "unit addition" creates the same Bigomega output as multiplication. Whether we add 1 to itself some n number of times or 5 to itself some n number of times, the result will be the same - Bigomega(x) + Bigomega(n).
So, if that's the case... Let me introduce a concept I've been playing with that I call "offset". I'm still looking into it, which means I don't understand everything about it. Anyway, it works like this. Say we use a unit of 10. 10 + 10 = 10 * 2 = 20. Bigomega(20) = 3 (because 20 = 2 * 2 * 5). What if, instead of doing 10 + 10, we do 10 + 9, 10 + 9 + 9, etc.? We'll get 10, 19, 28, 37, and so on. In this case, the "offset" is +1. This is so because our series could also be expressed as 1 + 9, 1 + 9 + 9, etc. These "offset" series produce different patterns of output for Bigomega. One of the areas I'm interested in examining is how these sets relate to each other. You may have noticed that for some set created by using 9 as the unit of addition, there are exactly 9 possible offisets which won't repeat themselves. Note that if you extended all 9 sets to infinity and combined them, you'd end up with the set I, I > 9. Now, if you're really paying attention you'll notice something cool here. If we start with, say, 1 + 9, then continue on up to 8 + 9, we'll get every number except multiples of 9. So, we now add in 9 + 9, or offset 0... This system is feeding back on itself, i.e. that last set is simply 9 * I. We _have_ to have a "unit" set if we want to recombine the sets to get I, I > 9. The implications of this are very interesting, namely, that within the set of integers I, the basic pattern Bigomega(I) + Bigomega(x) repeats itself many, many times. Bigomega I _is_ the basic pattern, but it's composed on an infinite number of copies of itself!
I'll go ahead and stop here for now. In the meantime, let me give you something to think about until my next post (whenever that is). What is the smallest possible number with n number of factors? Or, in other words, what's the smallest possible number with 3 factors? with 4? And so on.
