Timeline for Find the boolean logic to check if a number is prime!
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 2 at 0:33 | comment | added | Fmbalbuena | @Mukundan314 "You can use any format to represent the boolean expressions" | |
| Mar 1 at 20:33 | comment | added | Mukundan314 | Are we allowed to output in prefix/postfix notation? | |
| Mar 1 at 17:48 | answer | added | Mukundan314 | timeline score: 1 | |
| Feb 24 at 0:25 | history | edited | Fmbalbuena | CC BY-SA 4.0 | add something |
| Feb 23 at 16:15 | answer | added | l4m2 | timeline score: 3 | |
| Feb 23 at 10:40 | answer | added | 138 Aspen | timeline score: 2 | |
| Feb 19 at 2:18 | answer | added | DesmosEnthusiast | timeline score: 2 | |
| Feb 11 at 3:33 | comment | added | l4m2 | @Lucenaposition True but appending counterexamples isn't long | |
| Feb 11 at 3:31 | comment | added | Lucenaposition | @l4m2 2**341%341 is 2 but 341 is not prime. | |
| Feb 11 at 3:28 | comment | added | l4m2 | @Lucenaposition what replied to? | |
| Feb 11 at 3:04 | comment | added | Lucenaposition | @l4m2 It's not a valid test though. | |
| Feb 10 at 3:15 | comment | added | l4m2 | @Arnauld Is 2**n mod n == 2 easily built without let? | |
| Feb 9 at 17:43 | comment | added | Unrelated String | @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? | |
| Feb 9 at 17:19 | comment | added | att | 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. | |
| Feb 9 at 16:50 | comment | added | Fmbalbuena | @Arnauld There exists divisibility rules for binary numbers, and if applied correctly, it is only necessary to compute at most the square root of the maximum number to check for primality. If it's too hard, I may add the "definition" operator to make it easier. | |
| Feb 9 at 11:55 | comment | added | Arnauld | 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.) | |
| Feb 9 at 9:26 | comment | added | l4m2 | How likely is it good to output a truth table? | |
| Feb 8 at 23:28 | history | edited | Fmbalbuena | CC BY-SA 4.0 | clarification |
| Feb 8 at 23:25 | comment | added | Fmbalbuena | @xnor Yeah, like the example boolean expression also works for numbers 0-7. | |
| Feb 8 at 23:24 | comment | added | xnor | Not sure what you be by "or less". Does, say, our boolean expression for 5 digits also have to work for 4-digit primes, presumably setting the 5th digit to zero? | |
| Feb 8 at 23:20 | comment | added | Fmbalbuena | @xnor Yeah, as long as it works for all numbers with input binary digits or less, it is fine. | |
| Feb 8 at 23:14 | comment | added | xnor | 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? | |
| Feb 8 at 23:01 | history | asked | Fmbalbuena | CC BY-SA 4.0 |