4

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 N\tag{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 N\tag{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:

enter image description here

It turns out that the value 1.5 is reached only from time to time.

Saša
  • 15,906
  • 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. – lulu Dec 16 '18 at 20:02
  • I don't understand: where do you get the $2N$ from in your formula (1)? – Rob Arthan Dec 16 '18 at 20:06
  • there's no guarantee the distribution remains well-behaved. prime numbers become more sparse, for example. try different ranges for your sample – David P Dec 16 '18 at 20:09
  • 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$. – lulu Dec 16 '18 at 20:14
  • @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. – Saša Dec 16 '18 at 20:17
  • @lulu You are right, let me correct my post. – Saša Dec 16 '18 at 20:19

1 Answers1

3

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$,

$$c\sum_{k=1}^{n-1} \frac{2^k}{k}\cdot\frac{k+3}{2}$$

ones, and

$$c\sum_{k=1}^{n-1} \frac{2^k}{k}\cdot\frac{k-1}{2}$$

zeroes, in

$$c\sum_{k=1}^{n-1} \frac{2^k}{k}$$

primes. Letting

$$f(n)=c\sum_{k=1}^{n-1} 2^k,\ \ g(n)=c\sum_{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 $3\cdot 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 $3\cdot 2^{n-1}$ as well. We expect there to be about

$$c\frac{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}\cdot\frac{c2^{n-1}}{n}$$

ones and

$$\frac{f(n)-g(n)}{2}+\frac{n}{2}\cdot\frac{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$.

Carl Schildkraut
  • 32,931