▲ 27 points
back
6 comments
However, I made an error back in 2000: my program ruled out all cases where A and B had a common factor, but actually, as long as C does not also share the factor, it is a valid counterexample.
Is there a proof for Norvig's less stringent "misinterpretation" that only A and B must share a prime factor? Or is it also unproved? What about C and just one of the others? Is it clear that all these cases are true or false together?
I don't know how Peter Norvig missed that, but if A and B have a common prime factor, then C obviously also shares that factor (by prime number theorem). The same is true for any other pair.
As a tiny matter of terminology, "prime number theorem" is usually reserved for the theorem on the asymptotic number of primes (https://en.wikipedia.org/wiki/Prime_number_theorem). I would probably just say "by prime factorisation", or, if you want to be really precise, "by Euclid's lemma" (https://en.wikipedia.org/wiki/Euclid%27s_lemma).
Aside from playing, what is the use of this? To be sure, there's nothing wrong with playing, but I think that intellectual honesty would demand that Norvig acknowledge that this (running a straightforward Python program) is not how the conjecture will eventually be resolved, even if it is false.
I suppose somebody has to check the small possibilities, but true numerical search uses algorithms that are either incredibly optimised or run on huge time scales in order to check truly huge numbers. See, for example, the discussion of the Collatz conjecture at http://sweet.ua.pt/tos/3x+1.html , where experimental verification is currently up to 2^(60) \approx 10^(18).
To be fair, he does cover this in the conclusion at the end of this article and mentions how everything started in the original post from 2000:
Good point! I just saw the beginning, had that negative reaction, and closed the tab; I should have given Norvig more credit.