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.

  • 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

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.

  • 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

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?

  • $\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.