8
$\begingroup$

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 and proceed leftwards, we'd be starting with the highest (i.e., least-reduced) candidate value already.

So the correct scan of values instead proceeds 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            ↓       higher
111111111011111111111111111111111  8581545983  prime                bit
111111111101111111111111111111111  8585740287              significance
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
111111111111111111111111111111101  8589934589
111111111111111111111111111111110  8589934590
$\endgroup$
  • 4
    $\begingroup$ See OEIS sequence A061712. $\endgroup$ – Robert Israel Feb 5 '18 at 7:35
  • $\begingroup$ I would be surprised if the logic behind finding the answer is not "brute force", maybe with a little bit of number theory thrown in to exclude cases before you check them. $\endgroup$ – Arthur Feb 5 '18 at 7:35
  • $\begingroup$ @RobertIsrael Did you not need the +10 reputation? $\endgroup$ – Glenn Slayden Feb 5 '18 at 7:37
  • $\begingroup$ @GlennSlayden Robert is #3 in rep overall on the site, so probably not $\endgroup$ – qwr Feb 5 '18 at 7:40
  • 2
    $\begingroup$ The b-file goes up to $3320$. The Maple program returns $8581545983$ in a fraction of a second. $\endgroup$ – Robert Israel Feb 5 '18 at 7:44
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ But you should have found $8581545983 = 2^{33} -2^{23}-1$. You searched in the wrong direction. $\endgroup$ – Robert Israel Feb 5 '18 at 7:47
  • $\begingroup$ @RobertIsrael you're right. I fixed in my post. $\endgroup$ – qwr Feb 5 '18 at 7:53
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is the same mistake I made, you need to start on left and go right $\endgroup$ – qwr Feb 6 '18 at 0:59
  • 1
    $\begingroup$ @TheShortOne Sorry for being dense (in my case, despite DeVos, I fear): what makes you sure that the desired prime is guaranteed to have exactly one zero. I see that projecteuclid.org/download/pdf_1/euclid.em/999188636 proves that "there is no prime number with precisely 2^m bits, exactly two of which are zero bits," but what if none of the 33 candidates your method examines happen to be prime? Does the cited proof (or perhaps something else) require the target prime to have exactly one zero? (Obviously, it does: 1_1111_1111_1111_1111_1111_1111_1111_0111) $\endgroup$ – Glenn Slayden Feb 6 '18 at 2:32
  • 1
    $\begingroup$ @Glenn Then you try two zero bits, three zero bits, etc. Mwahahahahahahaha! $\endgroup$ – The Short One Feb 8 '18 at 22:40

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.