What is the least prime which has 32 1-bits?

241 Views Asked by At

On the many prime number investigation sites across the web I haven't been able to find the answer. Also my math isn't good enough to compute it from first principles.

So, what is the least prime that has 32 1-bits? Of course this refers to its base 2, i.e., binary representation. Programmer-speak for this would be, "32 'set' bits.'

Layperson explanation of the logic behind finding the answer would be an appreciated bonus.



[edit:] Summary of Answers

The answer is $8581545983$. By assuming the answer has just a single 0-bit, we discover that there are $5$ such ($33$-bit) primes with exactly $32$ 1-bits. Failing that, we would have gone on to try two 0-bits, etc.

The subtle point that confused both of the experts (and myself) is that even though we're seeking the lowest value here, it's incorrect to scan the substitution positions in right←to←left order of increasing significance.

The mis-intuition is caused by the fact that each trial replaces a $1$ with a $0$ at the given bit position—and not the other way around—so the higher the bit significance, the greater the reduction of numeric power. If we were to begin evaluating at the LSB (from the bottom of the following list) and proceed leftwards (upwards), we'd be fruitlessly starting at the candidate with the highest (i.e., least-reduced) overall value.

So the correct scan of values instead proceeds by testing 0-bit positions from left→to→right, as follows (from top-to-bottom):

011111111111111111111111111111111  4294967295              value
101111111111111111111111111111111  6442450943             increase
110111111111111111111111111111111  7516192767                ↓
111011111111111111111111111111111  8053063679                ↓
111101111111111111111111111111111  8321499135                ↓
111110111111111111111111111111111  8455716863                ↓
111111011111111111111111111111111  8522825727
111111101111111111111111111111111  8556380159
111111110111111111111111111111111  8573157375
111111111011111111111111111111111  8581545983  prime     ←- answer
111111111101111111111111111111111  8585740287
111111111110111111111111111111111  8587837439  prime
111111111111011111111111111111111  8588886015
111111111111101111111111111111111  8589410303  prime
111111111111110111111111111111111  8589672447
111111111111111011111111111111111  8589803519
111111111111111101111111111111111  8589869055
111111111111111110111111111111111  8589901823  prime
111111111111111111011111111111111  8589918207
111111111111111111101111111111111  8589926399
111111111111111111110111111111111  8589930495
111111111111111111111011111111111  8589932543
111111111111111111111101111111111  8589933567
111111111111111111111110111111111  8589934079
111111111111111111111111011111111  8589934335
111111111111111111111111101111111  8589934463
111111111111111111111111110111111  8589934527                 ↑
111111111111111111111111111011111  8589934559                 ↑
111111111111111111111111111101111  8589934575                 ↑
111111111111111111111111111110111  8589934583  prime          ↑
111111111111111111111111111111011  8589934587              higher
111111111111111111111111111111101  8589934589               0-bit
111111111111111111111111111111110  8589934590           significance
2

There are 2 best solutions below

2
On BEST ANSWER

Knowing $2^{32}-1$ isn't prime, I found $2^{33}-1 - 2^{23}=8581545983 $ just by starting with a string of 33 ones and replacing a one with a zero starting from second most significant bit and moving right.

Robert Israel's OEIS link (https://oeis.org/A061712) doesn't list any non-trivial math properties, but this seems pretty trivial to write a program for. Start with a long string of binary ones ($2^k-1$) and try setting 1 one to zero, 2 ones to zero with $2^{k+1}-1$, etc.

4
On

Since you know about Mersenne primes, you know that $2^{32} - 1$ is composite, right? It's not a safe assumption in the age of Betsy DeVos.

So the next best thing would be a string of thirty-two $1$s with a $0$ in there somewhere. Obviously $2^{33} - 2$ is even, but take the binary representation $111111111111111111111111111111110$ and rotate carry right within the $33$-bit word, $111111111111111111111111111111101$, $111111111111111111111111111111011$, etc., until you find a prime.

Easy as pie, right?