Skip to main content
Code Golf

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

16
  • \$\begingroup\$ When you say the boolean expression depends on the the number of digits in the input, does that mean we can write a totally different expression for each input length? \$\endgroup\$ Commented Feb 8 at 23:14
  • \$\begingroup\$ @xnor Yeah, as long as it works for all numbers with input binary digits or less, it is fine. \$\endgroup\$ Commented Feb 8 at 23:20
  • 3
    \$\begingroup\$ I can't really think of anything better than a truth table (except for bit #0, obviously). In which case, the challenge boils down to implementing a fast primality test, such as a deterministic variant of Miller-Rabin with a large enough set of bases. (But I wish I can be proven wrong.) \$\endgroup\$ Commented Feb 9 at 11:55
  • 2
    \$\begingroup\$ I also think this ends up being "implement a (fast) primality test", since it's fairly trivial to convert a list of numbers to a boolean expression that only matches them. Would be happy to be proven wrong, of course. \$\endgroup\$ Commented Feb 9 at 17:19
  • 1
    \$\begingroup\$ @att I think the idea might be to produce a Boolean expression that actually performs the primality testing itself--the challenge being to do so in a way that maximally offloads the computation into the output, essentially? \$\endgroup\$ Commented Feb 9 at 17:43