Mixing
![field are domains. [duplicate]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Fraction of $1$s in binary representation of $n!$
Clash Royale CLAN TAG#URR8PPP
up vote
8
down vote
favorite
3
I plotted a fraction of $1$s in binary representation of $n!$ (i.e. A079584/A072831) for $n$ from $1$ to $10^4$:
It appears it might converge to some limit for $ntoinfty$. Can we (dis-)prove that this limit exists, and find its exact value? Or, at least, find the limit inferior and limit superior of the sequence?
number-theory limits factorial limsup-and-liminf binary
asked Jul 21 at 22:43
Vladimir Reshetnikov
23.7k4115224
 |Â
show 4 more comments
up vote
8
down vote
favorite
3
I plotted a fraction of $1$s in binary representation of $n!$ (i.e. A079584/A072831) for $n$ from $1$ to $10^4$:
It appears it might converge to some limit for $ntoinfty$. Can we (dis-)prove that this limit exists, and find its exact value? Or, at least, find the limit inferior and limit superior of the sequence?
number-theory limits factorial limsup-and-liminf binary
asked Jul 21 at 22:43
Vladimir Reshetnikov
23.7k4115224
I can't think of any reason why it should do anything but converge to one-half. (I can't think of any way to prove this, either.)
– Gerry Myerson
Jul 21 at 22:45
This is related to $$1 cdot x cdot (x+1) cdot x^2 cdot (x^2+x)cdot (x^2 + x + 1) cdot (x^2 + 1) cdots (x^n + x^n-1 + dots + 1) = sum_k geq 0 a_kx^k,$$ where $a_k$ is the number of partitions of $k$ into parts $leq n$ each occurring with multiplicity $leq 2^n.$ When $m=2^n + 2^n-1+ dots + 1$, A079584 for $m$ is the number of nonzero $a_k pmod2$. When $m$ is not of that form, then A079584 for $m$ can still be interpreted in terms of partitions as above, but the conditions on the parts won't be a nice. Statistics of numbers of parts being well-distributed may be relevant.
– Dzoooks
Jul 21 at 23:38
1
Modelling the number as 1 & [mix] & trailing zeroes, with the mix being 50:50, I get expected values exactly down the trendline of what you see. My expectation is that the contribution of trailing zeroes will become steadily smaller, taking the limit towards $0.5$
– Joffan
Jul 22 at 0:09
2
@Joffan: We get exactly $frac12+frac14+frac18+cdots=1$ trailing zero per factor on average, whereas the number of digits grows as $sum_klog_2kapprox n(log n-1)/log2$, so we should expect the fraction of digits that are trailing zeros to decay like $log2/(log n-1)$.
– joriki
Jul 22 at 0:16
1
Your plot seems to fit very well with the observation that $n!$ has $approx n(ln n-1)/ln 2$ bits of which we know that the last $approx n$ bits are $0$ and the rest random
– Hagen von Eitzen
Jul 22 at 9:30
 |Â
show 4 more comments
up vote
8
down vote
favorite
3
up vote
8
down vote
favorite
3
3
I plotted a fraction of $1$s in binary representation of $n!$ (i.e. A079584/A072831) for $n$ from $1$ to $10^4$:
It appears it might converge to some limit for $ntoinfty$. Can we (dis-)prove that this limit exists, and find its exact value? Or, at least, find the limit inferior and limit superior of the sequence?
number-theory limits factorial limsup-and-liminf binary
asked Jul 21 at 22:43
Vladimir Reshetnikov
23.7k4115224
I plotted a fraction of $1$s in binary representation of $n!$ (i.e. A079584/A072831) for $n$ from $1$ to $10^4$:
It appears it might converge to some limit for $ntoinfty$. Can we (dis-)prove that this limit exists, and find its exact value? Or, at least, find the limit inferior and limit superior of the sequence?
number-theory limits factorial limsup-and-liminf binary
asked Jul 21 at 22:43
Vladimir Reshetnikov
23.7k4115224
asked Jul 21 at 22:43
Vladimir Reshetnikov
23.7k4115224
asked Jul 21 at 22:43
Vladimir Reshetnikov
23.7k4115224
asked Jul 21 at 22:43
Vladimir Reshetnikov
23.7k4115224
23.7k4115224
I can't think of any reason why it should do anything but converge to one-half. (I can't think of any way to prove this, either.)
– Gerry Myerson
Jul 21 at 22:45
This is related to $$1 cdot x cdot (x+1) cdot x^2 cdot (x^2+x)cdot (x^2 + x + 1) cdot (x^2 + 1) cdots (x^n + x^n-1 + dots + 1) = sum_k geq 0 a_kx^k,$$ where $a_k$ is the number of partitions of $k$ into parts $leq n$ each occurring with multiplicity $leq 2^n.$ When $m=2^n + 2^n-1+ dots + 1$, A079584 for $m$ is the number of nonzero $a_k pmod2$. When $m$ is not of that form, then A079584 for $m$ can still be interpreted in terms of partitions as above, but the conditions on the parts won't be a nice. Statistics of numbers of parts being well-distributed may be relevant.
– Dzoooks
Jul 21 at 23:38
1
Modelling the number as 1 & [mix] & trailing zeroes, with the mix being 50:50, I get expected values exactly down the trendline of what you see. My expectation is that the contribution of trailing zeroes will become steadily smaller, taking the limit towards $0.5$
– Joffan
Jul 22 at 0:09
2
@Joffan: We get exactly $frac12+frac14+frac18+cdots=1$ trailing zero per factor on average, whereas the number of digits grows as $sum_klog_2kapprox n(log n-1)/log2$, so we should expect the fraction of digits that are trailing zeros to decay like $log2/(log n-1)$.
– joriki
Jul 22 at 0:16
1
Your plot seems to fit very well with the observation that $n!$ has $approx n(ln n-1)/ln 2$ bits of which we know that the last $approx n$ bits are $0$ and the rest random
– Hagen von Eitzen
Jul 22 at 9:30
 |Â
show 4 more comments
I can't think of any reason why it should do anything but converge to one-half. (I can't think of any way to prove this, either.)
– Gerry Myerson
Jul 21 at 22:45
This is related to $$1 cdot x cdot (x+1) cdot x^2 cdot (x^2+x)cdot (x^2 + x + 1) cdot (x^2 + 1) cdots (x^n + x^n-1 + dots + 1) = sum_k geq 0 a_kx^k,$$ where $a_k$ is the number of partitions of $k$ into parts $leq n$ each occurring with multiplicity $leq 2^n.$ When $m=2^n + 2^n-1+ dots + 1$, A079584 for $m$ is the number of nonzero $a_k pmod2$. When $m$ is not of that form, then A079584 for $m$ can still be interpreted in terms of partitions as above, but the conditions on the parts won't be a nice. Statistics of numbers of parts being well-distributed may be relevant.
– Dzoooks
Jul 21 at 23:38
1
Modelling the number as 1 & [mix] & trailing zeroes, with the mix being 50:50, I get expected values exactly down the trendline of what you see. My expectation is that the contribution of trailing zeroes will become steadily smaller, taking the limit towards $0.5$
– Joffan
Jul 22 at 0:09
2
@Joffan: We get exactly $frac12+frac14+frac18+cdots=1$ trailing zero per factor on average, whereas the number of digits grows as $sum_klog_2kapprox n(log n-1)/log2$, so we should expect the fraction of digits that are trailing zeros to decay like $log2/(log n-1)$.
– joriki
Jul 22 at 0:16
1
Your plot seems to fit very well with the observation that $n!$ has $approx n(ln n-1)/ln 2$ bits of which we know that the last $approx n$ bits are $0$ and the rest random
– Hagen von Eitzen
Jul 22 at 9:30
I can't think of any reason why it should do anything but converge to one-half. (I can't think of any way to prove this, either.)
– Gerry Myerson
Jul 21 at 22:45
I can't think of any reason why it should do anything but converge to one-half. (I can't think of any way to prove this, either.)
– Gerry Myerson
Jul 21 at 22:45
This is related to $$1 cdot x cdot (x+1) cdot x^2 cdot (x^2+x)cdot (x^2 + x + 1) cdot (x^2 + 1) cdots (x^n + x^n-1 + dots + 1) = sum_k geq 0 a_kx^k,$$ where $a_k$ is the number of partitions of $k$ into parts $leq n$ each occurring with multiplicity $leq 2^n.$ When $m=2^n + 2^n-1+ dots + 1$, A079584 for $m$ is the number of nonzero $a_k pmod2$. When $m$ is not of that form, then A079584 for $m$ can still be interpreted in terms of partitions as above, but the conditions on the parts won't be a nice. Statistics of numbers of parts being well-distributed may be relevant.
– Dzoooks
Jul 21 at 23:38
This is related to $$1 cdot x cdot (x+1) cdot x^2 cdot (x^2+x)cdot (x^2 + x + 1) cdot (x^2 + 1) cdots (x^n + x^n-1 + dots + 1) = sum_k geq 0 a_kx^k,$$ where $a_k$ is the number of partitions of $k$ into parts $leq n$ each occurring with multiplicity $leq 2^n.$ When $m=2^n + 2^n-1+ dots + 1$, A079584 for $m$ is the number of nonzero $a_k pmod2$. When $m$ is not of that form, then A079584 for $m$ can still be interpreted in terms of partitions as above, but the conditions on the parts won't be a nice. Statistics of numbers of parts being well-distributed may be relevant.
– Dzoooks
Jul 21 at 23:38
1
1
Modelling the number as 1 & [mix] & trailing zeroes, with the mix being 50:50, I get expected values exactly down the trendline of what you see. My expectation is that the contribution of trailing zeroes will become steadily smaller, taking the limit towards $0.5$
– Joffan
Jul 22 at 0:09
Modelling the number as 1 & [mix] & trailing zeroes, with the mix being 50:50, I get expected values exactly down the trendline of what you see. My expectation is that the contribution of trailing zeroes will become steadily smaller, taking the limit towards $0.5$
– Joffan
Jul 22 at 0:09
2
2
@Joffan: We get exactly $frac12+frac14+frac18+cdots=1$ trailing zero per factor on average, whereas the number of digits grows as $sum_klog_2kapprox n(log n-1)/log2$, so we should expect the fraction of digits that are trailing zeros to decay like $log2/(log n-1)$.
– joriki
Jul 22 at 0:16
@Joffan: We get exactly $frac12+frac14+frac18+cdots=1$ trailing zero per factor on average, whereas the number of digits grows as $sum_klog_2kapprox n(log n-1)/log2$, so we should expect the fraction of digits that are trailing zeros to decay like $log2/(log n-1)$.
– joriki
Jul 22 at 0:16
1
1
Your plot seems to fit very well with the observation that $n!$ has $approx n(ln n-1)/ln 2$ bits of which we know that the last $approx n$ bits are $0$ and the rest random
– Hagen von Eitzen
Jul 22 at 9:30
Your plot seems to fit very well with the observation that $n!$ has $approx n(ln n-1)/ln 2$ bits of which we know that the last $approx n$ bits are $0$ and the rest random
– Hagen von Eitzen
Jul 22 at 9:30
 |Â
show 4 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Â
draft saved
draft discarded
Â
draft saved
draft discarded
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858943%2ffraction-of-1s-in-binary-representation-of-n%23new-answer', 'question_page');
);
Post as a guest
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
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
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
I can't think of any reason why it should do anything but converge to one-half. (I can't think of any way to prove this, either.)
– Gerry Myerson
Jul 21 at 22:45
This is related to $$1 cdot x cdot (x+1) cdot x^2 cdot (x^2+x)cdot (x^2 + x + 1) cdot (x^2 + 1) cdots (x^n + x^n-1 + dots + 1) = sum_k geq 0 a_kx^k,$$ where $a_k$ is the number of partitions of $k$ into parts $leq n$ each occurring with multiplicity $leq 2^n.$ When $m=2^n + 2^n-1+ dots + 1$, A079584 for $m$ is the number of nonzero $a_k pmod2$. When $m$ is not of that form, then A079584 for $m$ can still be interpreted in terms of partitions as above, but the conditions on the parts won't be a nice. Statistics of numbers of parts being well-distributed may be relevant.
– Dzoooks
Jul 21 at 23:38
1
Modelling the number as 1 & [mix] & trailing zeroes, with the mix being 50:50, I get expected values exactly down the trendline of what you see. My expectation is that the contribution of trailing zeroes will become steadily smaller, taking the limit towards $0.5$
– Joffan
Jul 22 at 0:09
2
@Joffan: We get exactly $frac12+frac14+frac18+cdots=1$ trailing zero per factor on average, whereas the number of digits grows as $sum_klog_2kapprox n(log n-1)/log2$, so we should expect the fraction of digits that are trailing zeros to decay like $log2/(log n-1)$.
– joriki
Jul 22 at 0:16
1
Your plot seems to fit very well with the observation that $n!$ has $approx n(ln n-1)/ln 2$ bits of which we know that the last $approx n$ bits are $0$ and the rest random
– Hagen von Eitzen
Jul 22 at 9:30