Do primes, expressed in binary, have more "random" bits on average than natural numbers?

395 Views Asked by At

In my programming projects I sometimes pick large primes when I want somewhat "random" bits, e.g. for hashing or trivial obfuscation via XOR or modular mutiplication. My intuitive sense is that primes in binary are a little more "random", but I'm not sure if reality bears that out.

So a couple of questions I was curious about:

  1. After stripping the leading and trailing $1$'s, is the probability of a $1$ in the remaining binary digits of a prime much different than the $0.5$ that one would assume for $\Bbb N$ at large?

  2. Is the "diffusion" or distribution of bits after the leading $1$ any more "random" in the primes than in $\Bbb N$? I'm not sure the statistical metric to ask about here, so apologies if the question is vague; intuitively I'm wondering if "randomly distributed" bits like $10010111$, as opposed to $11110000$, are more common in the primes.

If it helps, the question could be confined to common integer representations on computers, e.g. unsigned 64-bit: $0 \le x \lt 2^{64}$.

1

There are 1 best solutions below

0
On BEST ANSWER

OK, just wrote a quick program to tally up bit count statistics for primes and non-primes (composites), to take a crack at this empirically. You can view the C++ code here. I used the Sieve of Eratosthenes method to generate primes, so it gets exponentially slower as the upper limit increases, but for 32-bit integers it only took about 2 minutes.

For question #1 I simply counted percentage of inner bits that were 1 (inner bits being the bits left after stripping the leading 1 and trailing bit).

For question #2 I decided to measure the number of "transitions" from $0 \rightarrow 1$ and $1 \rightarrow 0$ out of all possible transitions in the inner bits. So $111000$ has 1 out of a possible 3 transitions, for 33%, and $110100$ has 3 of 3 for 100%.

Here are the results of runs for the 8-, 16- and 32-bit unsigned integers:

From 4 .. 255:  55 primes, 197 composites.

After stripping leading & trailing binary digits:

Primes had     51.3636% 1's.
Composites had 49.6193% 1's.
Primes had     49.1212% of all possible 0<->1 transitions.
Composites had 49.2301% of all possible 0<->1 transitions.


From 4 .. 65535:  6549 primes, 58983 composites.

Averages after stripping leading & trailing binary digits:

Primes had     49.8745% 1's.
Composites had 50.0139% 1's.
Primes had     49.9531% of all possible 0<->1 transitions.
Composites had 50.0018% of all possible 0<->1 transitions.


From 4 .. 4294967295:  203280748 primes, 4091686544 composites.

Averages after stripping leading & trailing binary digits:

Primes had     49.9719% 1's.
Composites had 50.0014% 1's.
Primes had     49.9974% of all possible 0<->1 transitions.
Composites had 50.0001% of all possible 0<->1 transitions.

So from the looks of it my intuition is wrong - there appear to be no significant differences in either 1-counts or "randomness" between prime and composite numbers, at least with these particular measurements and ranges.