[EDITED to add: And I did say to test it on the primes up to 100.]
[EDITED again to add …] Here, just for reference, is what I would write, in less than a minute, to do the job. It is only intended to work for integers >= 2, and need not be bearably efficient for integers that aren’t very small.
def is_prime(n):
for i in range(2,n):
if n%i == 0: return False
return True
Four short, simple lines corresponding quite exactly to the definition of primality.
So, what could be wrong in this program that could make it give a wrong answer for 1159? I can think of the following things. (1) I could have messed up the range of values of i to test against. (2) I could have got my variables muddled up, testing i%n instead of n%i or something of the kind. (3) I could have got my return conditions backwards, making this a not-prime test. (4) I could have messed up the control flow in some way that, e.g., does something crazy when we fall off the end of that loop. (5) I could have mixed up the % (modulus) operator with something else like division or exclusive-or. (6) I could have got myself confused about what the condition for primality actually is. (7) I could have done something else that I haven’t been able to think of.
Well, most of those are very low-probability, especially given that I’ve listed them explicitly and checked the program. Further, it’s easy to see that all of them would almost certainly fail on testing against the numbers from 2 to 100, and it seems likely that most errors in category 7 would do so too. (E.g., one can imagine messing up the test in such a way that numbers of the form prime^2 get mistakenly identified as prime, or so that it only catches primes of the form 4k+1, or something.)
which has 25 entries (which I know, or think I know, is the right answer), consists entirely of numbers I believe I know to be prime, and includes every number < 100 that I believe I know to be prime.
I am very comfortable indeed reckoning this as at least 1000:1 evidence that any specific positive integer on the order of 1000 is prime iff my is_prime function says it is and gives the same result on repeated runs.
Other failure modes I haven’t listed above but want to mention that I have thought of: There could be integer overflow problems. (But not for numbers this small, and not in Python unless there’s a weird Python bug I haven’t heard of.) There could be ridiculous errors in Python itself that make it get simple arithmetic on small numbers wrong. (But I’m running Python 2.7.3, which was released some time ago and was for some time the most commonly used Python version; I would surely have heard if it had that sort of error; in any case that class of error is very, very rare.) My computer could be messed up by cosmic rays or something. (Which is why I’d run the program multiple times on 1159.)
Or, of course, my brain could be messed up in some way that specifically interferes with my understanding of prime numbers or of what it takes to check a program’s correctness. The first is already dealt with in the discussion above. The second is one of the reasons why I would also check against someone else’s list of smallish prime numbers and do a number-theoretic test by hand. (And also, I think, rather improbable.)
(7): indentation error. But I guess the interpreter will tell you i is used out of scope. That, or you would have gotten another catastrophic result on numbers below 10.
def is_prime(n):
for i in range(2,n):
if n%i == 0: return False
return True
(Edit: okay, that was LessWrong screwing up leading spaces. We can cheat that with unbreakable spaces.)
Yes, good point. I’d generalize: “I could have committed some syntax error—wrong indentation, wrong sort of brackets somewhere, etc. -- that just happens to leave a program with correct syntax but unintended semantics.”
I guess the interpreter will tell you i is used out of scope.
Depends on exactly what error occurs. (With the formatting the way it actually looks here it would just be a syntax error.)
That, or you would have gotten another catastrophic result on numbers below 10.
This (aside from the simplicity of the code) is the real reason why I’m still happy with an error probability less than 0.001. It takes a really odd sort of error to produce correct results for the first 100 candidate primes and wrong results thereafter. I could write some programs with that sort of error, but they wouldn’t look at all like naive primality checkers with simple typos.
OK. I agree. Checking the output on numbers less than 100 vastly decreases the probability of error, especially after enumerating simple errors and realizing that none of them would return anything remotely correct on those numbers.
A program this simple? Yes.
[EDITED to add: And I did say to test it on the primes up to 100.]
[EDITED again to add …] Here, just for reference, is what I would write, in less than a minute, to do the job. It is only intended to work for integers >= 2, and need not be bearably efficient for integers that aren’t very small.
Four short, simple lines corresponding quite exactly to the definition of primality.
So, what could be wrong in this program that could make it give a wrong answer for 1159? I can think of the following things. (1) I could have messed up the range of values of i to test against. (2) I could have got my variables muddled up, testing i%n instead of n%i or something of the kind. (3) I could have got my return conditions backwards, making this a not-prime test. (4) I could have messed up the control flow in some way that, e.g., does something crazy when we fall off the end of that loop. (5) I could have mixed up the % (modulus) operator with something else like division or exclusive-or. (6) I could have got myself confused about what the condition for primality actually is. (7) I could have done something else that I haven’t been able to think of.
Well, most of those are very low-probability, especially given that I’ve listed them explicitly and checked the program. Further, it’s easy to see that all of them would almost certainly fail on testing against the numbers from 2 to 100, and it seems likely that most errors in category 7 would do so too. (E.g., one can imagine messing up the test in such a way that numbers of the form prime^2 get mistakenly identified as prime, or so that it only catches primes of the form 4k+1, or something.)
And, lo and behold, I then did
and got
which has 25 entries (which I know, or think I know, is the right answer), consists entirely of numbers I believe I know to be prime, and includes every number < 100 that I believe I know to be prime.
I am very comfortable indeed reckoning this as at least 1000:1 evidence that any specific positive integer on the order of 1000 is prime iff my is_prime function says it is and gives the same result on repeated runs.
Other failure modes I haven’t listed above but want to mention that I have thought of: There could be integer overflow problems. (But not for numbers this small, and not in Python unless there’s a weird Python bug I haven’t heard of.) There could be ridiculous errors in Python itself that make it get simple arithmetic on small numbers wrong. (But I’m running Python 2.7.3, which was released some time ago and was for some time the most commonly used Python version; I would surely have heard if it had that sort of error; in any case that class of error is very, very rare.) My computer could be messed up by cosmic rays or something. (Which is why I’d run the program multiple times on 1159.)
Or, of course, my brain could be messed up in some way that specifically interferes with my understanding of prime numbers or of what it takes to check a program’s correctness. The first is already dealt with in the discussion above. The second is one of the reasons why I would also check against someone else’s list of smallish prime numbers and do a number-theoretic test by hand. (And also, I think, rather improbable.)
(7): indentation error. But I guess the interpreter will tell you
iis used out of scope. That, or you would have gotten another catastrophic result on numbers below 10.(Edit: okay, that was LessWrong screwing up leading spaces. We can cheat that with unbreakable spaces.)
Yes, good point. I’d generalize: “I could have committed some syntax error—wrong indentation, wrong sort of brackets somewhere, etc. -- that just happens to leave a program with correct syntax but unintended semantics.”
Depends on exactly what error occurs. (With the formatting the way it actually looks here it would just be a syntax error.)
This (aside from the simplicity of the code) is the real reason why I’m still happy with an error probability less than 0.001. It takes a really odd sort of error to produce correct results for the first 100 candidate primes and wrong results thereafter. I could write some programs with that sort of error, but they wouldn’t look at all like naive primality checkers with simple typos.
OK. I agree. Checking the output on numbers less than 100 vastly decreases the probability of error, especially after enumerating simple errors and realizing that none of them would return anything remotely correct on those numbers.