1. :?

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?

2.

3. 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.

4. Which version of density are you talking about here talanum1?

5. 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.

6. 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.

7. 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.

8. In other words, S is the set of all odd multiples of 3: S = {3,9,15,21,27,33,…}

S<sub>0</sub> = {9,21,33,…}

S<sub>1</sub> = {3,15,27,…}

The elements of S<sub>0</sub> are of the form 9+12k while those of S<sub>1</sub> are of the form 3+12k (k a non-negative integer). Hence the natural density of both the sets is 1*⁄*12.

9. 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.

10. Exercise for today - what is the density of the primes

12. Okay, so let's remember that:

π(n) = #{primes p : p ≤ n} ~ n/ln(n)

13. 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.

 Bookmarks
##### Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement