Mixing
Natural density of set ${4^nk}$, where $k$ is odd
up vote
4
down vote
favorite
A starting point is this problem: $P subset Z_n = {1, 2, dots, n}$ is binary, if there exists a number $k$ such that both $k in P$ and $2k in P$, otherwise it is antibinary. One is supposed, for given $n$, to show antibinary set with maximum amount of elements (there might be many sets satisfying this property). One can show that set $P_n = {4^m(2k + 1) mid m, k in mathbb{N}} cap Z_n$ is a proper solution. My question is: how big is this set? I'm looking for $displaystylelim_{n to infty} p_n$, where $p_n = dfrac{|P_n|}{n}$. Simple program I wrote in Python suggests that the answer is $dfrac{2}{3}$, but I don't know, how to prove it.
sequences-and-series elementary-number-theory
edited 15 hours ago
Fabio Lucchini
7,60511226
asked 17 hours ago
Rakaho
504
add a comment |
up vote
4
down vote
favorite
A starting point is this problem: $P subset Z_n = {1, 2, dots, n}$ is binary, if there exists a number $k$ such that both $k in P$ and $2k in P$, otherwise it is antibinary. One is supposed, for given $n$, to show antibinary set with maximum amount of elements (there might be many sets satisfying this property). One can show that set $P_n = {4^m(2k + 1) mid m, k in mathbb{N}} cap Z_n$ is a proper solution. My question is: how big is this set? I'm looking for $displaystylelim_{n to infty} p_n$, where $p_n = dfrac{|P_n|}{n}$. Simple program I wrote in Python suggests that the answer is $dfrac{2}{3}$, but I don't know, how to prove it.
sequences-and-series elementary-number-theory
edited 15 hours ago
Fabio Lucchini
7,60511226
asked 17 hours ago
Rakaho
504
This set contains only about $frac{n}{2}$ elements, it is not an optimal solution.
– Rakaho
16 hours ago
I make it $frac n6$ but do not see immediately why that is not optimal.
– Ross Millikan
8 hours ago
add a comment |
up vote
4
down vote
favorite
up vote
4
down vote
favorite
A starting point is this problem: $P subset Z_n = {1, 2, dots, n}$ is binary, if there exists a number $k$ such that both $k in P$ and $2k in P$, otherwise it is antibinary. One is supposed, for given $n$, to show antibinary set with maximum amount of elements (there might be many sets satisfying this property). One can show that set $P_n = {4^m(2k + 1) mid m, k in mathbb{N}} cap Z_n$ is a proper solution. My question is: how big is this set? I'm looking for $displaystylelim_{n to infty} p_n$, where $p_n = dfrac{|P_n|}{n}$. Simple program I wrote in Python suggests that the answer is $dfrac{2}{3}$, but I don't know, how to prove it.
sequences-and-series elementary-number-theory
edited 15 hours ago
Fabio Lucchini
7,60511226
asked 17 hours ago
Rakaho
504
A starting point is this problem: $P subset Z_n = {1, 2, dots, n}$ is binary, if there exists a number $k$ such that both $k in P$ and $2k in P$, otherwise it is antibinary. One is supposed, for given $n$, to show antibinary set with maximum amount of elements (there might be many sets satisfying this property). One can show that set $P_n = {4^m(2k + 1) mid m, k in mathbb{N}} cap Z_n$ is a proper solution. My question is: how big is this set? I'm looking for $displaystylelim_{n to infty} p_n$, where $p_n = dfrac{|P_n|}{n}$. Simple program I wrote in Python suggests that the answer is $dfrac{2}{3}$, but I don't know, how to prove it.
sequences-and-series elementary-number-theory
sequences-and-series elementary-number-theory
edited 15 hours ago
Fabio Lucchini
7,60511226
asked 17 hours ago
Rakaho
504
edited 15 hours ago
Fabio Lucchini
7,60511226
asked 17 hours ago
Rakaho
504
edited 15 hours ago
Fabio Lucchini
7,60511226
edited 15 hours ago
Fabio Lucchini
7,60511226
edited 15 hours ago
Fabio Lucchini
7,60511226
7,60511226
asked 17 hours ago
Rakaho
504
asked 17 hours ago
Rakaho
504
asked 17 hours ago
Rakaho
504
504
This set contains only about $frac{n}{2}$ elements, it is not an optimal solution.
– Rakaho
16 hours ago
I make it $frac n6$ but do not see immediately why that is not optimal.
– Ross Millikan
8 hours ago
add a comment |
This set contains only about $frac{n}{2}$ elements, it is not an optimal solution.
– Rakaho
16 hours ago
I make it $frac n6$ but do not see immediately why that is not optimal.
– Ross Millikan
8 hours ago
This set contains only about $frac{n}{2}$ elements, it is not an optimal solution.
– Rakaho
16 hours ago
This set contains only about $frac{n}{2}$ elements, it is not an optimal solution.
– Rakaho
16 hours ago
I make it $frac n6$ but do not see immediately why that is not optimal.
– Ross Millikan
8 hours ago
I make it $frac n6$ but do not see immediately why that is not optimal.
– Ross Millikan
8 hours ago
add a comment |
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
Since $4^m (2k+1)leq n $ if and only if $kleqfrac {n/4^m-1}{2}$, we have
begin{align}
frac {P (n)}n
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}leftlfloor 1+frac {n/4^m-1}{2}rightrfloor\
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}leftlfloorfrac {n+4^m}{2cdot 4^m}rightrfloor\
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}frac {n+4^m}{2cdot 4^m}+Oleft(frac {log (n)}nright)\
&=frac 12sum_{m=0}^{lfloorlog_4(m)rfloor}frac 1{4^m}+Oleft(frac {log (n)}nright)\
&=frac 23left(1-4^{-1-lfloorlog_4 (n)rfloor}right)+Oleft(frac {log (n)}nright)\
&xrightarrow {ntoinfty}frac 23
end{align}
answered 15 hours ago
Fabio Lucchini
7,60511226
You lost a factor $frac 14$ when you went from the next to last equality to the last one. The sum starts with $frac 14$, not with $1$. That turns your $frac 23$ into my $frac 16$. Please see my start to the set and indicate what other numbers should be there or why the density increases dramatically later on.
– Ross Millikan
8 hours ago
@Ross Millikan: As pointed out by Rakaho, the sum starts with $1$ (i.e. $m=0$).
– Fabio Lucchini
5 hours ago
add a comment |
up vote
0
down vote
The set begins $${4,12,16,20,28,36,44,48,52,60,64,ldots }$$ The density is much less than $frac 23.$
Roughly $frac 18$ of the numbers are of the form $8k+4$, $frac 1{32}$ of the numbers are of the form $32k+16$, $frac 1{128}$ are of the form $128k+64$, so the density is
$$frac 18left(1+frac 14+frac 1{16}+ldotsright)=frac 18 cdot frac 1{1-frac 14}=frac 16$$
answered 12 hours ago
Ross Millikan
287k23195364
$m$ could be 0, so you're omitting all odd numbers
– Rakaho
6 hours ago
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Since $4^m (2k+1)leq n $ if and only if $kleqfrac {n/4^m-1}{2}$, we have
begin{align}
frac {P (n)}n
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}leftlfloor 1+frac {n/4^m-1}{2}rightrfloor\
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}leftlfloorfrac {n+4^m}{2cdot 4^m}rightrfloor\
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}frac {n+4^m}{2cdot 4^m}+Oleft(frac {log (n)}nright)\
&=frac 12sum_{m=0}^{lfloorlog_4(m)rfloor}frac 1{4^m}+Oleft(frac {log (n)}nright)\
&=frac 23left(1-4^{-1-lfloorlog_4 (n)rfloor}right)+Oleft(frac {log (n)}nright)\
&xrightarrow {ntoinfty}frac 23
end{align}
answered 15 hours ago
Fabio Lucchini
7,60511226
You lost a factor $frac 14$ when you went from the next to last equality to the last one. The sum starts with $frac 14$, not with $1$. That turns your $frac 23$ into my $frac 16$. Please see my start to the set and indicate what other numbers should be there or why the density increases dramatically later on.
– Ross Millikan
8 hours ago
@Ross Millikan: As pointed out by Rakaho, the sum starts with $1$ (i.e. $m=0$).
– Fabio Lucchini
5 hours ago
add a comment |
up vote
3
down vote
accepted
Since $4^m (2k+1)leq n $ if and only if $kleqfrac {n/4^m-1}{2}$, we have
begin{align}
frac {P (n)}n
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}leftlfloor 1+frac {n/4^m-1}{2}rightrfloor\
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}leftlfloorfrac {n+4^m}{2cdot 4^m}rightrfloor\
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}frac {n+4^m}{2cdot 4^m}+Oleft(frac {log (n)}nright)\
&=frac 12sum_{m=0}^{lfloorlog_4(m)rfloor}frac 1{4^m}+Oleft(frac {log (n)}nright)\
&=frac 23left(1-4^{-1-lfloorlog_4 (n)rfloor}right)+Oleft(frac {log (n)}nright)\
&xrightarrow {ntoinfty}frac 23
end{align}
answered 15 hours ago
Fabio Lucchini
7,60511226
You lost a factor $frac 14$ when you went from the next to last equality to the last one. The sum starts with $frac 14$, not with $1$. That turns your $frac 23$ into my $frac 16$. Please see my start to the set and indicate what other numbers should be there or why the density increases dramatically later on.
– Ross Millikan
8 hours ago
@Ross Millikan: As pointed out by Rakaho, the sum starts with $1$ (i.e. $m=0$).
– Fabio Lucchini
5 hours ago
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Since $4^m (2k+1)leq n $ if and only if $kleqfrac {n/4^m-1}{2}$, we have
begin{align}
frac {P (n)}n
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}leftlfloor 1+frac {n/4^m-1}{2}rightrfloor\
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}leftlfloorfrac {n+4^m}{2cdot 4^m}rightrfloor\
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}frac {n+4^m}{2cdot 4^m}+Oleft(frac {log (n)}nright)\
&=frac 12sum_{m=0}^{lfloorlog_4(m)rfloor}frac 1{4^m}+Oleft(frac {log (n)}nright)\
&=frac 23left(1-4^{-1-lfloorlog_4 (n)rfloor}right)+Oleft(frac {log (n)}nright)\
&xrightarrow {ntoinfty}frac 23
end{align}
answered 15 hours ago
Fabio Lucchini
7,60511226
Since $4^m (2k+1)leq n $ if and only if $kleqfrac {n/4^m-1}{2}$, we have
begin{align}
frac {P (n)}n
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}leftlfloor 1+frac {n/4^m-1}{2}rightrfloor\
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}leftlfloorfrac {n+4^m}{2cdot 4^m}rightrfloor\
&=frac 1nsum_{m=0}^{lfloorlog_4(m)rfloor}frac {n+4^m}{2cdot 4^m}+Oleft(frac {log (n)}nright)\
&=frac 12sum_{m=0}^{lfloorlog_4(m)rfloor}frac 1{4^m}+Oleft(frac {log (n)}nright)\
&=frac 23left(1-4^{-1-lfloorlog_4 (n)rfloor}right)+Oleft(frac {log (n)}nright)\
&xrightarrow {ntoinfty}frac 23
end{align}
answered 15 hours ago
Fabio Lucchini
7,60511226
edited 5 hours ago
answered 15 hours ago
Fabio Lucchini
7,60511226
answered 15 hours ago
Fabio Lucchini
7,60511226
answered 15 hours ago
Fabio Lucchini
7,60511226
7,60511226
You lost a factor $frac 14$ when you went from the next to last equality to the last one. The sum starts with $frac 14$, not with $1$. That turns your $frac 23$ into my $frac 16$. Please see my start to the set and indicate what other numbers should be there or why the density increases dramatically later on.
– Ross Millikan
8 hours ago
@Ross Millikan: As pointed out by Rakaho, the sum starts with $1$ (i.e. $m=0$).
– Fabio Lucchini
5 hours ago
add a comment |
You lost a factor $frac 14$ when you went from the next to last equality to the last one. The sum starts with $frac 14$, not with $1$. That turns your $frac 23$ into my $frac 16$. Please see my start to the set and indicate what other numbers should be there or why the density increases dramatically later on.
– Ross Millikan
8 hours ago
@Ross Millikan: As pointed out by Rakaho, the sum starts with $1$ (i.e. $m=0$).
– Fabio Lucchini
5 hours ago
You lost a factor $frac 14$ when you went from the next to last equality to the last one. The sum starts with $frac 14$, not with $1$. That turns your $frac 23$ into my $frac 16$. Please see my start to the set and indicate what other numbers should be there or why the density increases dramatically later on.
– Ross Millikan
8 hours ago
You lost a factor $frac 14$ when you went from the next to last equality to the last one. The sum starts with $frac 14$, not with $1$. That turns your $frac 23$ into my $frac 16$. Please see my start to the set and indicate what other numbers should be there or why the density increases dramatically later on.
– Ross Millikan
8 hours ago
@Ross Millikan: As pointed out by Rakaho, the sum starts with $1$ (i.e. $m=0$).
– Fabio Lucchini
5 hours ago
@Ross Millikan: As pointed out by Rakaho, the sum starts with $1$ (i.e. $m=0$).
– Fabio Lucchini
5 hours ago
add a comment |
up vote
0
down vote
The set begins $${4,12,16,20,28,36,44,48,52,60,64,ldots }$$ The density is much less than $frac 23.$
Roughly $frac 18$ of the numbers are of the form $8k+4$, $frac 1{32}$ of the numbers are of the form $32k+16$, $frac 1{128}$ are of the form $128k+64$, so the density is
$$frac 18left(1+frac 14+frac 1{16}+ldotsright)=frac 18 cdot frac 1{1-frac 14}=frac 16$$
answered 12 hours ago
Ross Millikan
287k23195364
$m$ could be 0, so you're omitting all odd numbers
– Rakaho
6 hours ago
add a comment |
up vote
0
down vote
The set begins $${4,12,16,20,28,36,44,48,52,60,64,ldots }$$ The density is much less than $frac 23.$
Roughly $frac 18$ of the numbers are of the form $8k+4$, $frac 1{32}$ of the numbers are of the form $32k+16$, $frac 1{128}$ are of the form $128k+64$, so the density is
$$frac 18left(1+frac 14+frac 1{16}+ldotsright)=frac 18 cdot frac 1{1-frac 14}=frac 16$$
answered 12 hours ago
Ross Millikan
287k23195364
$m$ could be 0, so you're omitting all odd numbers
– Rakaho
6 hours ago
add a comment |
up vote
0
down vote
up vote
0
down vote
The set begins $${4,12,16,20,28,36,44,48,52,60,64,ldots }$$ The density is much less than $frac 23.$
Roughly $frac 18$ of the numbers are of the form $8k+4$, $frac 1{32}$ of the numbers are of the form $32k+16$, $frac 1{128}$ are of the form $128k+64$, so the density is
$$frac 18left(1+frac 14+frac 1{16}+ldotsright)=frac 18 cdot frac 1{1-frac 14}=frac 16$$
answered 12 hours ago
Ross Millikan
287k23195364
The set begins $${4,12,16,20,28,36,44,48,52,60,64,ldots }$$ The density is much less than $frac 23.$
Roughly $frac 18$ of the numbers are of the form $8k+4$, $frac 1{32}$ of the numbers are of the form $32k+16$, $frac 1{128}$ are of the form $128k+64$, so the density is
$$frac 18left(1+frac 14+frac 1{16}+ldotsright)=frac 18 cdot frac 1{1-frac 14}=frac 16$$
answered 12 hours ago
Ross Millikan
287k23195364
answered 12 hours ago
Ross Millikan
287k23195364
answered 12 hours ago
Ross Millikan
287k23195364
answered 12 hours ago
Ross Millikan
287k23195364
287k23195364
$m$ could be 0, so you're omitting all odd numbers
– Rakaho
6 hours ago
add a comment |
$m$ could be 0, so you're omitting all odd numbers
– Rakaho
6 hours ago
$m$ could be 0, so you're omitting all odd numbers
– Rakaho
6 hours ago
$m$ could be 0, so you're omitting all odd numbers
– Rakaho
6 hours ago
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004068%2fnatural-density-of-set-4nk-where-k-is-odd%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
This set contains only about $frac{n}{2}$ elements, it is not an optimal solution.
– Rakaho
16 hours ago
I make it $frac n6$ but do not see immediately why that is not optimal.
– Ross Millikan
8 hours ago