Counting zeros and ones in binary representations of prime numbers
$begingroup$
If you write down binary representations of all prime numbers starting from 3 up to some (very big) $N^{th}$
prime number and denote with $S_1(N)$ the total number of ones (1) and with $S_0(N)$ the total number of zeros (0) used in all binary representations, what kind of relation would you expect between $S_1$ and $S_0$?
I did not expect to see anything like 50:50 distribution. All binary representations start with 1 and all primes end with 1. So it looks like digit 1 is favored: binary representation of every odd prime is guranteed to have at least two ones. There's no such guarantee for zeros.
But what is the ratio between ones and zeros if you remove the first and the last digit from all binary representations? I meen, what happens if you look only at the "central" part of the number?
I might be too naive but I expected to see that, with the first and the last digit removed from every binary presentation, the ratio between ones and zeros would be close to 50:50. In other words, I expected to see something like:
$$S_1(N)approx S_0(N) + 2 Ntag{1}$$
But in reality it's not like that and I would say not even close. I did an experiment with the first 10 million primes and got the following results (BTW, 10,000,000th odd prime turned out to be 179,424,691):
$$N=10,000,000$$
$$S_1=139,605,415$$
$$S_0=124,501,052$$
Proper relationship seems to be:
$$S_1(N) approx S_0(N) + frac32 Ntag{2}$$
The margin of error in my experiment is less then 0.1%.
Is there a simple explanation why the correct factor seems to be equal to $frac32$, not 2?
(I can also share the Java code if someone wants to validate it.)
EDIT: Here is the graph of function:
$$frac{S_1(N)-S_0(N)}{N}$$
for the first 20 million primes:
It turns out that the value 1.5 is reached only from time to time.
prime-numbers
$endgroup$
|
show 1 more comment
$begingroup$
If you write down binary representations of all prime numbers starting from 3 up to some (very big) $N^{th}$
prime number and denote with $S_1(N)$ the total number of ones (1) and with $S_0(N)$ the total number of zeros (0) used in all binary representations, what kind of relation would you expect between $S_1$ and $S_0$?
I did not expect to see anything like 50:50 distribution. All binary representations start with 1 and all primes end with 1. So it looks like digit 1 is favored: binary representation of every odd prime is guranteed to have at least two ones. There's no such guarantee for zeros.
But what is the ratio between ones and zeros if you remove the first and the last digit from all binary representations? I meen, what happens if you look only at the "central" part of the number?
I might be too naive but I expected to see that, with the first and the last digit removed from every binary presentation, the ratio between ones and zeros would be close to 50:50. In other words, I expected to see something like:
$$S_1(N)approx S_0(N) + 2 Ntag{1}$$
But in reality it's not like that and I would say not even close. I did an experiment with the first 10 million primes and got the following results (BTW, 10,000,000th odd prime turned out to be 179,424,691):
$$N=10,000,000$$
$$S_1=139,605,415$$
$$S_0=124,501,052$$
Proper relationship seems to be:
$$S_1(N) approx S_0(N) + frac32 Ntag{2}$$
The margin of error in my experiment is less then 0.1%.
Is there a simple explanation why the correct factor seems to be equal to $frac32$, not 2?
(I can also share the Java code if someone wants to validate it.)
EDIT: Here is the graph of function:
$$frac{S_1(N)-S_0(N)}{N}$$
for the first 20 million primes:
It turns out that the value 1.5 is reached only from time to time.
prime-numbers
$endgroup$
$begingroup$
Well...in base $2$, $179424691$ begins $10$ so you've, presumably got a huge number of primes near there (but smaller) which also start $10$ so you have a variant of a Benford's Law issue going on. for this reason it's a bit hard to read much into single values.
$endgroup$
– lulu
Dec 16 '18 at 20:02
$begingroup$
I don't understand: where do you get the $2N$ from in your formula (1)?
$endgroup$
– Rob Arthan
Dec 16 '18 at 20:06
$begingroup$
there's no guarantee the distribution remains well-behaved. prime numbers become more sparse, for example. try different ranges for your sample
$endgroup$
– David Peterson
Dec 16 '18 at 20:09
$begingroup$
Note: I assume that by $S_i(N)$ you mean that you count up to the $N^{th}$ prime. That's not what you say, but you imply that when you remark that the $10,000,000^{th}$ prime is $179,424,691$ and reading it this way explains the additive factor of $2N$.
$endgroup$
– lulu
Dec 16 '18 at 20:14
$begingroup$
@RobArthan Take some very big prime number. It has to start with one and end with one. What digits are in between? I supposed that, on average, there was an equal number of zeros and ones in between.
$endgroup$
– Oldboy
Dec 16 '18 at 20:17
|
show 1 more comment
$begingroup$
If you write down binary representations of all prime numbers starting from 3 up to some (very big) $N^{th}$
prime number and denote with $S_1(N)$ the total number of ones (1) and with $S_0(N)$ the total number of zeros (0) used in all binary representations, what kind of relation would you expect between $S_1$ and $S_0$?
I did not expect to see anything like 50:50 distribution. All binary representations start with 1 and all primes end with 1. So it looks like digit 1 is favored: binary representation of every odd prime is guranteed to have at least two ones. There's no such guarantee for zeros.
But what is the ratio between ones and zeros if you remove the first and the last digit from all binary representations? I meen, what happens if you look only at the "central" part of the number?
I might be too naive but I expected to see that, with the first and the last digit removed from every binary presentation, the ratio between ones and zeros would be close to 50:50. In other words, I expected to see something like:
$$S_1(N)approx S_0(N) + 2 Ntag{1}$$
But in reality it's not like that and I would say not even close. I did an experiment with the first 10 million primes and got the following results (BTW, 10,000,000th odd prime turned out to be 179,424,691):
$$N=10,000,000$$
$$S_1=139,605,415$$
$$S_0=124,501,052$$
Proper relationship seems to be:
$$S_1(N) approx S_0(N) + frac32 Ntag{2}$$
The margin of error in my experiment is less then 0.1%.
Is there a simple explanation why the correct factor seems to be equal to $frac32$, not 2?
(I can also share the Java code if someone wants to validate it.)
EDIT: Here is the graph of function:
$$frac{S_1(N)-S_0(N)}{N}$$
for the first 20 million primes:
It turns out that the value 1.5 is reached only from time to time.
prime-numbers
$endgroup$
If you write down binary representations of all prime numbers starting from 3 up to some (very big) $N^{th}$
prime number and denote with $S_1(N)$ the total number of ones (1) and with $S_0(N)$ the total number of zeros (0) used in all binary representations, what kind of relation would you expect between $S_1$ and $S_0$?
I did not expect to see anything like 50:50 distribution. All binary representations start with 1 and all primes end with 1. So it looks like digit 1 is favored: binary representation of every odd prime is guranteed to have at least two ones. There's no such guarantee for zeros.
But what is the ratio between ones and zeros if you remove the first and the last digit from all binary representations? I meen, what happens if you look only at the "central" part of the number?
I might be too naive but I expected to see that, with the first and the last digit removed from every binary presentation, the ratio between ones and zeros would be close to 50:50. In other words, I expected to see something like:
$$S_1(N)approx S_0(N) + 2 Ntag{1}$$
But in reality it's not like that and I would say not even close. I did an experiment with the first 10 million primes and got the following results (BTW, 10,000,000th odd prime turned out to be 179,424,691):
$$N=10,000,000$$
$$S_1=139,605,415$$
$$S_0=124,501,052$$
Proper relationship seems to be:
$$S_1(N) approx S_0(N) + frac32 Ntag{2}$$
The margin of error in my experiment is less then 0.1%.
Is there a simple explanation why the correct factor seems to be equal to $frac32$, not 2?
(I can also share the Java code if someone wants to validate it.)
EDIT: Here is the graph of function:
$$frac{S_1(N)-S_0(N)}{N}$$
for the first 20 million primes:
It turns out that the value 1.5 is reached only from time to time.
prime-numbers
prime-numbers
edited Dec 16 '18 at 21:04
Oldboy
asked Dec 16 '18 at 19:42
OldboyOldboy
8,4521936
8,4521936
$begingroup$
Well...in base $2$, $179424691$ begins $10$ so you've, presumably got a huge number of primes near there (but smaller) which also start $10$ so you have a variant of a Benford's Law issue going on. for this reason it's a bit hard to read much into single values.
$endgroup$
– lulu
Dec 16 '18 at 20:02
$begingroup$
I don't understand: where do you get the $2N$ from in your formula (1)?
$endgroup$
– Rob Arthan
Dec 16 '18 at 20:06
$begingroup$
there's no guarantee the distribution remains well-behaved. prime numbers become more sparse, for example. try different ranges for your sample
$endgroup$
– David Peterson
Dec 16 '18 at 20:09
$begingroup$
Note: I assume that by $S_i(N)$ you mean that you count up to the $N^{th}$ prime. That's not what you say, but you imply that when you remark that the $10,000,000^{th}$ prime is $179,424,691$ and reading it this way explains the additive factor of $2N$.
$endgroup$
– lulu
Dec 16 '18 at 20:14
$begingroup$
@RobArthan Take some very big prime number. It has to start with one and end with one. What digits are in between? I supposed that, on average, there was an equal number of zeros and ones in between.
$endgroup$
– Oldboy
Dec 16 '18 at 20:17
|
show 1 more comment
$begingroup$
Well...in base $2$, $179424691$ begins $10$ so you've, presumably got a huge number of primes near there (but smaller) which also start $10$ so you have a variant of a Benford's Law issue going on. for this reason it's a bit hard to read much into single values.
$endgroup$
– lulu
Dec 16 '18 at 20:02
$begingroup$
I don't understand: where do you get the $2N$ from in your formula (1)?
$endgroup$
– Rob Arthan
Dec 16 '18 at 20:06
$begingroup$
there's no guarantee the distribution remains well-behaved. prime numbers become more sparse, for example. try different ranges for your sample
$endgroup$
– David Peterson
Dec 16 '18 at 20:09
$begingroup$
Note: I assume that by $S_i(N)$ you mean that you count up to the $N^{th}$ prime. That's not what you say, but you imply that when you remark that the $10,000,000^{th}$ prime is $179,424,691$ and reading it this way explains the additive factor of $2N$.
$endgroup$
– lulu
Dec 16 '18 at 20:14
$begingroup$
@RobArthan Take some very big prime number. It has to start with one and end with one. What digits are in between? I supposed that, on average, there was an equal number of zeros and ones in between.
$endgroup$
– Oldboy
Dec 16 '18 at 20:17
$begingroup$
Well...in base $2$, $179424691$ begins $10$ so you've, presumably got a huge number of primes near there (but smaller) which also start $10$ so you have a variant of a Benford's Law issue going on. for this reason it's a bit hard to read much into single values.
$endgroup$
– lulu
Dec 16 '18 at 20:02
$begingroup$
Well...in base $2$, $179424691$ begins $10$ so you've, presumably got a huge number of primes near there (but smaller) which also start $10$ so you have a variant of a Benford's Law issue going on. for this reason it's a bit hard to read much into single values.
$endgroup$
– lulu
Dec 16 '18 at 20:02
$begingroup$
I don't understand: where do you get the $2N$ from in your formula (1)?
$endgroup$
– Rob Arthan
Dec 16 '18 at 20:06
$begingroup$
I don't understand: where do you get the $2N$ from in your formula (1)?
$endgroup$
– Rob Arthan
Dec 16 '18 at 20:06
$begingroup$
there's no guarantee the distribution remains well-behaved. prime numbers become more sparse, for example. try different ranges for your sample
$endgroup$
– David Peterson
Dec 16 '18 at 20:09
$begingroup$
there's no guarantee the distribution remains well-behaved. prime numbers become more sparse, for example. try different ranges for your sample
$endgroup$
– David Peterson
Dec 16 '18 at 20:09
$begingroup$
Note: I assume that by $S_i(N)$ you mean that you count up to the $N^{th}$ prime. That's not what you say, but you imply that when you remark that the $10,000,000^{th}$ prime is $179,424,691$ and reading it this way explains the additive factor of $2N$.
$endgroup$
– lulu
Dec 16 '18 at 20:14
$begingroup$
Note: I assume that by $S_i(N)$ you mean that you count up to the $N^{th}$ prime. That's not what you say, but you imply that when you remark that the $10,000,000^{th}$ prime is $179,424,691$ and reading it this way explains the additive factor of $2N$.
$endgroup$
– lulu
Dec 16 '18 at 20:14
$begingroup$
@RobArthan Take some very big prime number. It has to start with one and end with one. What digits are in between? I supposed that, on average, there was an equal number of zeros and ones in between.
$endgroup$
– Oldboy
Dec 16 '18 at 20:17
$begingroup$
@RobArthan Take some very big prime number. It has to start with one and end with one. What digits are in between? I supposed that, on average, there was an equal number of zeros and ones in between.
$endgroup$
– Oldboy
Dec 16 '18 at 20:17
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
If you consider the primes between $2^n$ and $2^{n+1}-1$, inclusive, you would expect there to be approximately $frac{c2^n}{n}$ of them for some fixed $c$ (I believe it's $frac{1}{ln 2}$), and each should have "on average" $frac{n+3}{2}$ ones and $frac{n-1}{2}$ zeroes (assuming the middle bits are chosen uniformly at random. This gives, up through $2^n$,
$$csum_{k=1}^{n-1} frac{2^k}{k}cdotfrac{k+3}{2}$$
ones, and
$$csum_{k=1}^{n-1} frac{2^k}{k}cdotfrac{k-1}{2}$$
zeroes, in
$$csum_{k=1}^{n-1} frac{2^k}{k}$$
primes. Letting
$$f(n)=csum_{k=1}^{n-1} 2^k, g(n)=csum_{k=1}^{n-1} frac{2^k}{k},$$
we have, out of $g(n)$ primes, $frac{f(n)+3g(n)}{2}$ ones and $frac{f(n)-g(n)}{2}$ zeroes; the difference is thus $2g(n)$, as expected.
Let's say, however, that you count up to $3cdot 2^{n-1}$ instead. You still have the same number of $0$s and $1$s you did before, but now you have all the numbers from $2^n$ to $3cdot 2^{n-1}$ as well. We expect there to be about
$$cfrac{2^{n-1}}{n}$$
of them, and they have two ones, a zero, and $n-2$ "free digits," for "on average" $frac{n+2}{2}$ ones and $frac{n}{2}$ zeroes. This gives us, across our
$$g(n)+frac{c2^{n-1}}{n}$$
primes, approximately
$$frac{f(n)+3g(n)}{2}+frac{n+2}{2}cdotfrac{c2^{n-1}}{n}$$
ones and
$$frac{f(n)-g(n)}{2}+frac{n}{2}cdotfrac{c2^{n-1}}{n}$$
zeroes, for a difference of
$$2g(n)+frac{c2^{n-1}}{n}.$$
The ratio between this and the number of primes we have is
$$frac{2g(n)+frac{c2^{n-1}}{n}}{g(n)+frac{c2^{n-1}}{n}};$$
since $g(n)sim frac{c2^n}{n-1}$, this gives us a ratio of
$$frac{4+1}{2+1}=frac{5}{3}.$$
This isn't exactly the $frac{3}{2}$ you got, but it's certainly not $2$ either. As such, we should expect this "difference ratio" to differ from $2$ significantly depending on where your cutoff is. It's possible that if you stop at $frac{5}{4}cdot 2^n$ instead, you'll get a different number; the bottom line is that your heuristics can still be right without $frac{S_1(N)-S_0(N)}{N}to 2$.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3043070%2fcounting-zeros-and-ones-in-binary-representations-of-prime-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If you consider the primes between $2^n$ and $2^{n+1}-1$, inclusive, you would expect there to be approximately $frac{c2^n}{n}$ of them for some fixed $c$ (I believe it's $frac{1}{ln 2}$), and each should have "on average" $frac{n+3}{2}$ ones and $frac{n-1}{2}$ zeroes (assuming the middle bits are chosen uniformly at random. This gives, up through $2^n$,
$$csum_{k=1}^{n-1} frac{2^k}{k}cdotfrac{k+3}{2}$$
ones, and
$$csum_{k=1}^{n-1} frac{2^k}{k}cdotfrac{k-1}{2}$$
zeroes, in
$$csum_{k=1}^{n-1} frac{2^k}{k}$$
primes. Letting
$$f(n)=csum_{k=1}^{n-1} 2^k, g(n)=csum_{k=1}^{n-1} frac{2^k}{k},$$
we have, out of $g(n)$ primes, $frac{f(n)+3g(n)}{2}$ ones and $frac{f(n)-g(n)}{2}$ zeroes; the difference is thus $2g(n)$, as expected.
Let's say, however, that you count up to $3cdot 2^{n-1}$ instead. You still have the same number of $0$s and $1$s you did before, but now you have all the numbers from $2^n$ to $3cdot 2^{n-1}$ as well. We expect there to be about
$$cfrac{2^{n-1}}{n}$$
of them, and they have two ones, a zero, and $n-2$ "free digits," for "on average" $frac{n+2}{2}$ ones and $frac{n}{2}$ zeroes. This gives us, across our
$$g(n)+frac{c2^{n-1}}{n}$$
primes, approximately
$$frac{f(n)+3g(n)}{2}+frac{n+2}{2}cdotfrac{c2^{n-1}}{n}$$
ones and
$$frac{f(n)-g(n)}{2}+frac{n}{2}cdotfrac{c2^{n-1}}{n}$$
zeroes, for a difference of
$$2g(n)+frac{c2^{n-1}}{n}.$$
The ratio between this and the number of primes we have is
$$frac{2g(n)+frac{c2^{n-1}}{n}}{g(n)+frac{c2^{n-1}}{n}};$$
since $g(n)sim frac{c2^n}{n-1}$, this gives us a ratio of
$$frac{4+1}{2+1}=frac{5}{3}.$$
This isn't exactly the $frac{3}{2}$ you got, but it's certainly not $2$ either. As such, we should expect this "difference ratio" to differ from $2$ significantly depending on where your cutoff is. It's possible that if you stop at $frac{5}{4}cdot 2^n$ instead, you'll get a different number; the bottom line is that your heuristics can still be right without $frac{S_1(N)-S_0(N)}{N}to 2$.
$endgroup$
add a comment |
$begingroup$
If you consider the primes between $2^n$ and $2^{n+1}-1$, inclusive, you would expect there to be approximately $frac{c2^n}{n}$ of them for some fixed $c$ (I believe it's $frac{1}{ln 2}$), and each should have "on average" $frac{n+3}{2}$ ones and $frac{n-1}{2}$ zeroes (assuming the middle bits are chosen uniformly at random. This gives, up through $2^n$,
$$csum_{k=1}^{n-1} frac{2^k}{k}cdotfrac{k+3}{2}$$
ones, and
$$csum_{k=1}^{n-1} frac{2^k}{k}cdotfrac{k-1}{2}$$
zeroes, in
$$csum_{k=1}^{n-1} frac{2^k}{k}$$
primes. Letting
$$f(n)=csum_{k=1}^{n-1} 2^k, g(n)=csum_{k=1}^{n-1} frac{2^k}{k},$$
we have, out of $g(n)$ primes, $frac{f(n)+3g(n)}{2}$ ones and $frac{f(n)-g(n)}{2}$ zeroes; the difference is thus $2g(n)$, as expected.
Let's say, however, that you count up to $3cdot 2^{n-1}$ instead. You still have the same number of $0$s and $1$s you did before, but now you have all the numbers from $2^n$ to $3cdot 2^{n-1}$ as well. We expect there to be about
$$cfrac{2^{n-1}}{n}$$
of them, and they have two ones, a zero, and $n-2$ "free digits," for "on average" $frac{n+2}{2}$ ones and $frac{n}{2}$ zeroes. This gives us, across our
$$g(n)+frac{c2^{n-1}}{n}$$
primes, approximately
$$frac{f(n)+3g(n)}{2}+frac{n+2}{2}cdotfrac{c2^{n-1}}{n}$$
ones and
$$frac{f(n)-g(n)}{2}+frac{n}{2}cdotfrac{c2^{n-1}}{n}$$
zeroes, for a difference of
$$2g(n)+frac{c2^{n-1}}{n}.$$
The ratio between this and the number of primes we have is
$$frac{2g(n)+frac{c2^{n-1}}{n}}{g(n)+frac{c2^{n-1}}{n}};$$
since $g(n)sim frac{c2^n}{n-1}$, this gives us a ratio of
$$frac{4+1}{2+1}=frac{5}{3}.$$
This isn't exactly the $frac{3}{2}$ you got, but it's certainly not $2$ either. As such, we should expect this "difference ratio" to differ from $2$ significantly depending on where your cutoff is. It's possible that if you stop at $frac{5}{4}cdot 2^n$ instead, you'll get a different number; the bottom line is that your heuristics can still be right without $frac{S_1(N)-S_0(N)}{N}to 2$.
$endgroup$
add a comment |
$begingroup$
If you consider the primes between $2^n$ and $2^{n+1}-1$, inclusive, you would expect there to be approximately $frac{c2^n}{n}$ of them for some fixed $c$ (I believe it's $frac{1}{ln 2}$), and each should have "on average" $frac{n+3}{2}$ ones and $frac{n-1}{2}$ zeroes (assuming the middle bits are chosen uniformly at random. This gives, up through $2^n$,
$$csum_{k=1}^{n-1} frac{2^k}{k}cdotfrac{k+3}{2}$$
ones, and
$$csum_{k=1}^{n-1} frac{2^k}{k}cdotfrac{k-1}{2}$$
zeroes, in
$$csum_{k=1}^{n-1} frac{2^k}{k}$$
primes. Letting
$$f(n)=csum_{k=1}^{n-1} 2^k, g(n)=csum_{k=1}^{n-1} frac{2^k}{k},$$
we have, out of $g(n)$ primes, $frac{f(n)+3g(n)}{2}$ ones and $frac{f(n)-g(n)}{2}$ zeroes; the difference is thus $2g(n)$, as expected.
Let's say, however, that you count up to $3cdot 2^{n-1}$ instead. You still have the same number of $0$s and $1$s you did before, but now you have all the numbers from $2^n$ to $3cdot 2^{n-1}$ as well. We expect there to be about
$$cfrac{2^{n-1}}{n}$$
of them, and they have two ones, a zero, and $n-2$ "free digits," for "on average" $frac{n+2}{2}$ ones and $frac{n}{2}$ zeroes. This gives us, across our
$$g(n)+frac{c2^{n-1}}{n}$$
primes, approximately
$$frac{f(n)+3g(n)}{2}+frac{n+2}{2}cdotfrac{c2^{n-1}}{n}$$
ones and
$$frac{f(n)-g(n)}{2}+frac{n}{2}cdotfrac{c2^{n-1}}{n}$$
zeroes, for a difference of
$$2g(n)+frac{c2^{n-1}}{n}.$$
The ratio between this and the number of primes we have is
$$frac{2g(n)+frac{c2^{n-1}}{n}}{g(n)+frac{c2^{n-1}}{n}};$$
since $g(n)sim frac{c2^n}{n-1}$, this gives us a ratio of
$$frac{4+1}{2+1}=frac{5}{3}.$$
This isn't exactly the $frac{3}{2}$ you got, but it's certainly not $2$ either. As such, we should expect this "difference ratio" to differ from $2$ significantly depending on where your cutoff is. It's possible that if you stop at $frac{5}{4}cdot 2^n$ instead, you'll get a different number; the bottom line is that your heuristics can still be right without $frac{S_1(N)-S_0(N)}{N}to 2$.
$endgroup$
If you consider the primes between $2^n$ and $2^{n+1}-1$, inclusive, you would expect there to be approximately $frac{c2^n}{n}$ of them for some fixed $c$ (I believe it's $frac{1}{ln 2}$), and each should have "on average" $frac{n+3}{2}$ ones and $frac{n-1}{2}$ zeroes (assuming the middle bits are chosen uniformly at random. This gives, up through $2^n$,
$$csum_{k=1}^{n-1} frac{2^k}{k}cdotfrac{k+3}{2}$$
ones, and
$$csum_{k=1}^{n-1} frac{2^k}{k}cdotfrac{k-1}{2}$$
zeroes, in
$$csum_{k=1}^{n-1} frac{2^k}{k}$$
primes. Letting
$$f(n)=csum_{k=1}^{n-1} 2^k, g(n)=csum_{k=1}^{n-1} frac{2^k}{k},$$
we have, out of $g(n)$ primes, $frac{f(n)+3g(n)}{2}$ ones and $frac{f(n)-g(n)}{2}$ zeroes; the difference is thus $2g(n)$, as expected.
Let's say, however, that you count up to $3cdot 2^{n-1}$ instead. You still have the same number of $0$s and $1$s you did before, but now you have all the numbers from $2^n$ to $3cdot 2^{n-1}$ as well. We expect there to be about
$$cfrac{2^{n-1}}{n}$$
of them, and they have two ones, a zero, and $n-2$ "free digits," for "on average" $frac{n+2}{2}$ ones and $frac{n}{2}$ zeroes. This gives us, across our
$$g(n)+frac{c2^{n-1}}{n}$$
primes, approximately
$$frac{f(n)+3g(n)}{2}+frac{n+2}{2}cdotfrac{c2^{n-1}}{n}$$
ones and
$$frac{f(n)-g(n)}{2}+frac{n}{2}cdotfrac{c2^{n-1}}{n}$$
zeroes, for a difference of
$$2g(n)+frac{c2^{n-1}}{n}.$$
The ratio between this and the number of primes we have is
$$frac{2g(n)+frac{c2^{n-1}}{n}}{g(n)+frac{c2^{n-1}}{n}};$$
since $g(n)sim frac{c2^n}{n-1}$, this gives us a ratio of
$$frac{4+1}{2+1}=frac{5}{3}.$$
This isn't exactly the $frac{3}{2}$ you got, but it's certainly not $2$ either. As such, we should expect this "difference ratio" to differ from $2$ significantly depending on where your cutoff is. It's possible that if you stop at $frac{5}{4}cdot 2^n$ instead, you'll get a different number; the bottom line is that your heuristics can still be right without $frac{S_1(N)-S_0(N)}{N}to 2$.
answered Dec 16 '18 at 20:18
Carl SchildkrautCarl Schildkraut
11.5k11441
11.5k11441
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3043070%2fcounting-zeros-and-ones-in-binary-representations-of-prime-numbers%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
$begingroup$
Well...in base $2$, $179424691$ begins $10$ so you've, presumably got a huge number of primes near there (but smaller) which also start $10$ so you have a variant of a Benford's Law issue going on. for this reason it's a bit hard to read much into single values.
$endgroup$
– lulu
Dec 16 '18 at 20:02
$begingroup$
I don't understand: where do you get the $2N$ from in your formula (1)?
$endgroup$
– Rob Arthan
Dec 16 '18 at 20:06
$begingroup$
there's no guarantee the distribution remains well-behaved. prime numbers become more sparse, for example. try different ranges for your sample
$endgroup$
– David Peterson
Dec 16 '18 at 20:09
$begingroup$
Note: I assume that by $S_i(N)$ you mean that you count up to the $N^{th}$ prime. That's not what you say, but you imply that when you remark that the $10,000,000^{th}$ prime is $179,424,691$ and reading it this way explains the additive factor of $2N$.
$endgroup$
– lulu
Dec 16 '18 at 20:14
$begingroup$
@RobArthan Take some very big prime number. It has to start with one and end with one. What digits are in between? I supposed that, on average, there was an equal number of zeros and ones in between.
$endgroup$
– Oldboy
Dec 16 '18 at 20:17