Occurrence of only 0, 2, 8, a, c in a sequence of hexadecimal representation of binary classification of prime numbers.

46 Views Asked by At

I recently began experimenting with prime numbers and made a quite interesting discovery. I stored 1 if a number is prime and 0 if the number is composite as shown in the table below.

15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
0 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0

This gives the following binary number: $(0010 1000 1010 1100)_2$

Writing it in hexadecimal base I get: $28ac_{16}$

Now if I repeat this for other numbers I get the sequence: $28ac_{16}$, $a08a_{16}$, $8a20_{16}$, $2820_{16}$, $8288_{16}$, $0208_{16}$, $28a2_{16}$, $8002_{16}$, ...

Now repeating the process for $1,000,000$ whole numbers, and counting the number of occurrences of each digit of the hexadecimal base using this C++ program, I am getting:

1 : 0
2 : 35129
3 : 0
4 : 0
5 : 0
6 : 0
7 : 0
8 : 35275
9 : 0
a : 4046
b : 0
c : 1
d : 0
e : 0
f : 0

What really interests me is why only the numbers $\{0, 2, 8, a, c\}$ occurs in the numbers of this sequence and that too $c$ with only 1 occurrence and $2$ and $8$ having relatively similar number of occurrences.

1

There are 1 best solutions below

0
On BEST ANSWER

Since you started counting at 0 that means your hexadecimal digits contain the bits indicating the primeness of 0-3, 4-7, etc.

This means that the numbers indicating the 1st and 3rd bit of your hexademical digit will always be 0 since they represent even numbers (except for in the very first digit where 2 is a prime number).

So this eliminates the hexadecimal digits of 1, 3, 4, 5, 6, 7, 9, b, c, d, e, and f since those have a bit value of 1 in either the 1st or 3rd spot. This only leaves the possible values of 2, 8 and a. The exception being the first occurrence of c which is due to 2 being the only even prime number.

Now the reason why 2 and 8 are more common than a is that 2 and 8 only have 1 bit that has value 1 while a has 2 bits of value 1. Prime numbers are more "rare" than non prime numbers so we would expect hexadecimal digits with less 1 bits to be more common indeed.