| Author |
Message
|
| talanum1 |
 Posted: Mon May 12, 2008 8:15 am Post subject: Densities |
 |
|
Forum Freshman
Joined: 28 Jul 2007
Posts: 93
Location: South Africa
|
What is the density of the following sets S_0 and S_1 in the natural numbers?
S = {n element of Natural numbers | n = 0 (mod 3) and n/2 not = 0 (mod 3)}
S_0 = {n element of S | 1/2(3n+1) is even}
S_1 = {n element of S | 1/2(3n+1) is odd}
What is the general way to compute it? Would it be strange if their densities are equal?
_________________
Found cross product of two vectors in >3D. |
|
| Back to top |
|
 |
| serpicojr |
| Posted: Mon May 12, 2008 12:12 pm Post subject: |
|
|
Forum Professor
Joined: 17 Jul 2007
Posts: 1128
Location: JRZ
|
What do you mean when you write "n/2 not = 0 mod 3"? Presumably, you mean that the rational number n/2 is not 3 times an integer, which given that n is 3 time an integer, is equivalent to n/2 not being an integer. So you could say n is odd, or n = 3 mod 6. The density of this set is what you should expect it is: 1/6. To calculate this, note that for any N:
[1,N] intersect S = {3, 9, ..., [(N-3)/6]*6+3}
How many elements are in here? [(N-3)/6]+1, which is equal to (N-3)/6 + O(1), which when divided by N is (1-3/N)/6 + O(1/N), and as N goes to infinity, this is 1/6.
Now let me just say that "n/2 not = 0 mod 3" may take on different meanings. Since 2 is invertible mod 3, and its inverse is itself, so you might interpret this as "n*2 not = 0 mod 3", and this is the same as "n not = 0 mod 3". Clearly, you don't mean this, but you have to be careful. Similarly, another common interpretation would be "n/2 not = 0 mod 3" means that the prime factorization of n/2 (as a rational number) has no 3 in it. And this, again, would be the same as "n not = 0 mod 3". You would have been better off saying "n is not even" or "2 does not divide n" or "n = 1 mod 2", because these are unambiguous.
For S_0, if n is in S, S is 3 mod 6. We also want (3n+1)/2 even. Division by 2 here makes sense, as n is odd, so 3n is odd and 3n+1 is even. So (3n+1)/2 is even iff 3n+1 = 0 mod 4, which is the same as 3n = 3 mod 4, which is the same as n = 1 mod 4. Since we're already dealing with n = 3 mod 6, we see this gives us a congruence mod 12. If n = 1 mod 4, then n = 1, 5, or 9 mod 12. If n = 3 mod 6, then n = 3 or 9 mod 12. So n = 9 mod 12. Then calculating the density is easy.
For S_1, the same sort of argument gives you n = 3 mod 12. You clearly get the same density for this as for S_0. |
|
| Back to top |
|
|
| river_rat |
| Posted: Mon May 12, 2008 10:45 pm Post subject: |
|
|
Forum Ph.D.
Joined: 01 Jun 2006
Posts: 1043
Location: South Africa
|
Which version of density are you talking about here talanum1?
_________________
As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong. |
|
| Back to top |
|
|
| talanum1 |
| Posted: Tue May 13, 2008 7:12 am Post subject: |
|
|
Forum Freshman
Joined: 28 Jul 2007
Posts: 93
Location: South Africa
|
The greatest lower bound of A(n)/n where A(n) is the amount of elements <= n version.
serpicojr: I mean n/2 is an integer not devisable by 3, i.e n/2 is an integer congruent to 1 or 2 mod 3. Does this change your answer?
Thanks anyway.
_________________
Found cross product of two vectors in >3D. |
|
| Back to top |
|
|
| serpicojr |
| Posted: Tue May 13, 2008 12:08 pm Post subject: |
|
|
Forum Professor
Joined: 17 Jul 2007
Posts: 1128
Location: JRZ
|
Okay, so you should have learned a lemma that says something like:
Suppose a divides bc and gcd(a,b) = 1. Then a divides c.
Applying this to our situation, you're asking for an integer n divisible by 2, i.e. n = 2m for another integer m. And then you're assuming that 2m = n = 0 mod 3. Well, then 3 divides 2m, and since gcd(2,3) = 1, we have 3 divides m, so that n/2 = m = 0 mod 3.
So S is empty. |
|
| Back to top |
|
|
| talanum1 |
| Posted: Wed May 14, 2008 7:26 am Post subject: |
|
|
Forum Freshman
Joined: 28 Jul 2007
Posts: 93
Location: South Africa
|
That's right. In fact your first guess was correct, I ment:
S = {n element of natural numbers | n = 0 mod 3 and n odd}
giving you n = 3 mod 6.
_________________
Found cross product of two vectors in >3D. |
|
| Back to top |
|
|
| JaneBennet |
| Posted: Wed May 14, 2008 7:49 am Post subject: |
|
|
Forum Ph.D.
Joined: 06 Apr 2008
Posts: 792
|
In other words, S is the set of all odd multiples of 3: S = {3,9,15,21,27,33,…}
S0 = {9,21,33,…}
S1 = {3,15,27,…}
The elements of S0 are of the form 9+12k while those of S1 are of the form 3+12k (k a non-negative integer). Hence the natural density of both the sets is 1 ⁄ 12.
_________________
A problem worthy of attack
Proves its worth by fighting back.
(Piet Hein)
Did You Know?
Fact of the day: Homotopy |
|
| Back to top |
|
|
| serpicojr |
| Posted: Wed May 14, 2008 7:50 am Post subject: |
|
|
Forum Professor
Joined: 17 Jul 2007
Posts: 1128
Location: JRZ
|
So let's note that, for any integers a >= 0 and q > 0, the density of the set (which I'd call an arithmetic progression):
S = {qn+a: n a natural number}
is always 1/q. First, we may assume a < q, as this only changes our set by a finite number of elements, and a finite number of elements has density 0. Now let S(N) be the elements of S less than or equal to N. Assume S(N) is nonempty, and divide N by q--i.e., find integers m and b such that N = qm+b, 0 =< b < q. Now if b < a, it's easy to see that the number of elements in S(N) is m. If b >= a, it's easy to see that the number of elements in S(N) is m+1. Note that:
m = qm/q = (qm+b-b)/q = (N-b)/q = N/q - b/q
Now whatever b/q is, it's a quantity between 0 and 1. Thus dividing by N, we get:
1/q - b/qN
and the quantity b/qN goes to 0 as N goes to infinity no matter which of the finite number of choices for b we take, so it goes to 0 unconditionally. |
|
| Back to top |
|
|
| river_rat |
| Posted: Wed May 14, 2008 10:26 pm Post subject: |
|
|
Forum Ph.D.
Joined: 01 Jun 2006
Posts: 1043
Location: South Africa
|
Exercise for today - what is the density of the primes
_________________
As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong. |
|
| Back to top |
|
|
| talanum1 |
| Posted: Mon May 26, 2008 8:03 am Post subject: |
|
|
Forum Freshman
Joined: 28 Jul 2007
Posts: 93
Location: South Africa
|
About 0.131
_________________
Found cross product of two vectors in >3D. |
|
| Back to top |
|
|
| serpicojr |
| Posted: Mon May 26, 2008 10:43 am Post subject: |
|
|
Forum Professor
Joined: 17 Jul 2007
Posts: 1128
Location: JRZ
|
Okay, so let's remember that:
π(n) = #{primes p : p ≤ n} ~ n/ln(n) |
|
| Back to top |
|
|
| river_rat |
| Posted: Tue Jun 17, 2008 11:26 pm Post subject: |
|
|
Forum Ph.D.
Joined: 01 Jun 2006
Posts: 1043
Location: South Africa
|
I'm trying to recall some rather interesting results from my side of the maths wood with regard to densities of sequences. I think the definition is different though, I will have to attack my paper collection again.
_________________
As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong. |
|
| Back to top |
|
|
|
|
