3 ms·
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 fact
by nkurz 11y ago
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?
- Grue3 11y agoI 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.
- JadeNB 11y agoAs 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 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 https://en.wikipedia.org/wiki/Euclid%27s_lemma).