7
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.