3 ms·

Beal's Conjecture Revisited

27 points by dmit 11y ago

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 ago
  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.
  - JadeNB 11y ago
    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 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).
JadeNB 11y ago
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 http://sweet.ua.pt/tos/3x+1.html , where experimental verification is currently up to 2^(60) \approx 10^(18).
- dmit 11y ago
  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: http://norvig.com/beal2000.html http://norvig.com/beal2000.html
  - JadeNB 11y ago
    Good point! I just saw the beginning, had that negative reaction, and closed the tab; I should have given Norvig more credit.

27 points by dmit 11y ago

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 ago
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.
- JadeNB 11y ago
  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 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).

JadeNB 11y ago

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 http://sweet.ua.pt/tos/3x+1.html , where experimental verification is currently up to 2^(60) \approx 10^(18).

dmit 11y ago
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: http://norvig.com/beal2000.html http://norvig.com/beal2000.html
- JadeNB 11y ago
  Good point! I just saw the beginning, had that negative reaction, and closed the tab; I should have given Norvig more credit.