5 ms·

(a) The test is the wrong way round for the Collatz Conjecture; (b) The Collatz Conjecture isn't one of the Millennium problems; (c) It's using bounded number

(a) The test is the wrong way round for the Collatz Conjecture; (b) The Collatz Conjecture isn't one of the Millennium problems; (c) It's using bounded numbers in the range where the Collatz Conjecture is known to be true; (d) It seems reasonable to say "If this routine exits then the value will be "true"; (e) None of what I say here is deep or new, so when people get excited about this sort of thing it makes me wonder what I've missed. So ... what have I missed?

lostcolony 5y ago
The joke.
- cies 5y ago
  Savage. I dont often laugh loud reading HN. Today I did. Thanks.
- cabaalis 5y ago
  I've only seen Veretasium YouTube video on this a few days ago, and I'm not a mathematician. Is the joke that LLVM has solved the mystery by optimizing out what it decided is an infinite loop?
  - junon 5y ago
    Yes.
  - Thiez 5y ago
    The C++ standard allows compilers to assume that loops terminate. Since there is only one way to exit the loop (`return true;`) the compiler can assume that this line will eventually be reached. Since the rest of the loop has no side effects, the compiler can optimize it out. So the compiler doesn't actually need to figure out if the loop is infinite or not.
    - Denvercoder9 5y ago
      > The C++ standard allows compilers to assume that loops terminate. Technically, it doesn't, but it requires programs to make forward progress, which is defined as either terminating, calling I/O functions, accessing a volatile variable or performing an atomic or synchronization operation. Infinite loops that'll eventually do one of these are perfectly valid C++ and don't have to terminate.
      - HelloNurse 5y ago
        It optimizes "waste an unpredictable time doing arithmetic without side effects, then return 1" to "return 1 without looking at the input". The relation between that machine arithmetic and the Collatz conjecture is irrelevant.
        Denvercoder9 5y ago
        I don't think you're responding to the right comment?
  - WJW 5y ago
    LLVM optimizes out the infinite loop, because the C++ standard defines that all programs must be able to make forward progress and so removing this loop does not alter the result of the program. Thus, collatz() as written in the tweet will always return true when optimized by LLVM. This says nothing about the conjecture being true or not, it is solely an artifact of the C++ standard being written a certain way. But also a layer deeper, collatz() takes a uint128 as input and the Collatz conjecture has already been proven to be true for all numbers that would fit into a uint128. So LLVM arrives to the correct answer (`return true`) because of the wrong reason, mathematically speaking.
    - ludocode 5y ago
      This doesn't exactly follow the Collatz conjecture because multiplication by 3 will be truncated to a 128-bit unsigned int. It is possible that this truncation causes a loop. Even though the Collatz conjecture has been tested for all numbers in this range, it has probably not been tested with this overflow effect.
      - plasticchris 5y ago
        Edit: removing my comment, I misunderstood.
        WJW 5y ago
        Not so, since the fact that it is in the range does not mean it will steadily go downwards. It might have numbers much bigger than the maximum value for a uint128 somewhere in its Collatz sequence and it is possible (though unlikely) that one of those numbers modulo the maximum value for a uint128 is the original number again. (That is, the modulo operation might introduce loops that are not present in the normal Collatz sequence because mathematical integers don't overflow)
- ColinWright 5y ago
  Ah ... I see my point(s) sailing over your head. I'm guessing you didn't realise that since the joke is presenting this as if it (i.e. "solving" the Collatz Conjecture) were real, I'm replying by treating it as if it were real, and thereby playing along with the joke. Never mind, on-line forums are really the right place for subtlety.
  - lostcolony 5y ago
    Oh, I understand your points. But I see the joke sailed right over your head; I'm guessing you didn't realize that this joke is presented as a joke, notably due to the phrase "pack it in mathematicians", since it's quite unreasonable to believe that anyone familiar with the Collatz Conjecture would believe that solving it is the only reason for mathematicians to exist (and also quite unreasonable for anyone familiar enough with LLVM and mathematics to assume a compiler's behavior constitutes a mathematical proof). I can't speak to online forums (I use them for so many things), but I'm sure Twitter is the right place for humor, and not the right place to announce a serious belief you've proved a long standing mathematical problem.
    - ColinWright 5y ago
      > "Oh, I understand your points. But I see the joke sailed right over your head ..." OK, I guess my sense of humour hasn't translated into your context. Clearly my comment makes you think I didn't get the joke, but I did. > "I'm guessing you didn't realize that this joke is presented as a joke, ..." Oh, I did. Really, I did. I guess we're just talking past each other. <shrug> You didn't get my joke, probably because you think I didn't get the original. Time to give up.
      - lostcolony 5y ago
        Okay. I'm not sure dissecting the technical inaccuracies of a joke ("but an imam would never walk into a bar!") is itself a joke (and I'm pretty sure you edited the comment just above to agree it was a joke, but maybe I just didn't read it closely enough), especially when you'd give the exact same response if you didn't know it was a joke, but did know it was technically incorrect, but fair enough.
tantalor 5y ago
> The test is the wrong way round Specifically, Collatz says "if x is even then x /= 2" but the code checks "x is odd".
stephencanon 5y ago
(a) part of the joke (b) the Millennium problems are not the only million-dollar prizes in mathematics (c) part of the joke (d) part of the joke (and part of the C++ standard)
- ColinWright 5y ago
  (b) There are other prizes, but I'm not aware of any others worth a million dollars. Do you have any pointers? A quick interwebs search didn't turn up anything, but they might just be being swamped by the results with the Millennium Problems.
  - tpush 5y ago
    > A quick interwebs search didn't turn up anything [...] Searching 'collatz conjecture prize' quite literally puts a prize of a bout 120MM Yen (~ $1MM) as the top result.
    - ColinWright 5y ago
      Hah! I didn't search specifically for that, I was searching for bounties in general. Thanks.
  - ithinkso 5y ago
    There is also a Beal Conjecture[0] worth a million [0] https://en.wikipedia.org/wiki/Beal_conjecture https://en.wikipedia.org/wiki/Beal_conjecture
    - ColinWright 5y ago
      My initial search for bounties didn't turn up that one, either. I wonder if my connection(s) with Erdos have polluted my search history, so it was showing me mostly those, and not showing me this. <shrug> Thanks for finding this and letting me know, I've learned something.
rtkwe 5y ago
> (b) The Collatz Conjecture isn't one of the Millennium problems; It's not but there are more bounties out there than just the Millenium list. For the Collatz Conjecture specifically there's a 120M Japanese Yen prize which at this moment is a bit more than 1 million USD. https://www.prnewswire.com/news-releases/bakuage-offers-prize-of-120-million-jpy-to-whoever-solves-collatz-conjecture-math-problem-unsolved-for-84-years-301326629.html https://www.prnewswire.com/news-releases/bakuage-offers-priz...
- ColinWright 5y ago
  (Also commented elsewhere) ... I didn't search specifically for that, I was searching for bounties in general. Thanks.
gameswithgo 5y ago
You have no sense of humor or curiosity about compiler optimization details that led to this, I guess. For instance not all languages that target LLVM will get this result. That is interesting.
yissp 5y ago
> (c) It's using bounded numbers in the range where the Collatz Conjecture is known to be true; The input is an unsigned __int128, and I believe Collatz has only been verified up to 2^68.
jens-c 5y ago
Not to mention that the answer by itself is pretty much worthless, but Mathematicians are rather interested in a proof of the conjecture (or its negation). I get that it is supposed to be a joke, but it kind of falls flat because it misses the point entirely.

lostcolony 5y ago

The joke.

cies 5y ago
Savage. I dont often laugh loud reading HN. Today I did. Thanks.
cabaalis 5y ago
I've only seen Veretasium YouTube video on this a few days ago, and I'm not a mathematician. Is the joke that LLVM has solved the mystery by optimizing out what it decided is an infinite loop?
- junon 5y ago
  Yes.
- Thiez 5y ago
  The C++ standard allows compilers to assume that loops terminate. Since there is only one way to exit the loop (`return true;`) the compiler can assume that this line will eventually be reached. Since the rest of the loop has no side effects, the compiler can optimize it out. So the compiler doesn't actually need to figure out if the loop is infinite or not.
  - Denvercoder9 5y ago
    > The C++ standard allows compilers to assume that loops terminate. Technically, it doesn't, but it requires programs to make forward progress, which is defined as either terminating, calling I/O functions, accessing a volatile variable or performing an atomic or synchronization operation. Infinite loops that'll eventually do one of these are perfectly valid C++ and don't have to terminate.
    - HelloNurse 5y ago
      It optimizes "waste an unpredictable time doing arithmetic without side effects, then return 1" to "return 1 without looking at the input". The relation between that machine arithmetic and the Collatz conjecture is irrelevant.
      - Denvercoder9 5y ago
        I don't think you're responding to the right comment?
- WJW 5y ago
  LLVM optimizes out the infinite loop, because the C++ standard defines that all programs must be able to make forward progress and so removing this loop does not alter the result of the program. Thus, collatz() as written in the tweet will always return true when optimized by LLVM. This says nothing about the conjecture being true or not, it is solely an artifact of the C++ standard being written a certain way. But also a layer deeper, collatz() takes a uint128 as input and the Collatz conjecture has already been proven to be true for all numbers that would fit into a uint128. So LLVM arrives to the correct answer (`return true`) because of the wrong reason, mathematically speaking.
  - ludocode 5y ago
    This doesn't exactly follow the Collatz conjecture because multiplication by 3 will be truncated to a 128-bit unsigned int. It is possible that this truncation causes a loop. Even though the Collatz conjecture has been tested for all numbers in this range, it has probably not been tested with this overflow effect.
    - plasticchris 5y ago
      Edit: removing my comment, I misunderstood.
      - WJW 5y ago
        Not so, since the fact that it is in the range does not mean it will steadily go downwards. It might have numbers much bigger than the maximum value for a uint128 somewhere in its Collatz sequence and it is possible (though unlikely) that one of those numbers modulo the maximum value for a uint128 is the original number again. (That is, the modulo operation might introduce loops that are not present in the normal Collatz sequence because mathematical integers don't overflow)
ColinWright 5y ago
Ah ... I see my point(s) sailing over your head. I'm guessing you didn't realise that since the joke is presenting this as if it (i.e. "solving" the Collatz Conjecture) were real, I'm replying by treating it as if it were real, and thereby playing along with the joke. Never mind, on-line forums are really the right place for subtlety.
- lostcolony 5y ago
  Oh, I understand your points. But I see the joke sailed right over your head; I'm guessing you didn't realize that this joke is presented as a joke, notably due to the phrase "pack it in mathematicians", since it's quite unreasonable to believe that anyone familiar with the Collatz Conjecture would believe that solving it is the only reason for mathematicians to exist (and also quite unreasonable for anyone familiar enough with LLVM and mathematics to assume a compiler's behavior constitutes a mathematical proof). I can't speak to online forums (I use them for so many things), but I'm sure Twitter is the right place for humor, and not the right place to announce a serious belief you've proved a long standing mathematical problem.
  - ColinWright 5y ago
    > "Oh, I understand your points. But I see the joke sailed right over your head ..." OK, I guess my sense of humour hasn't translated into your context. Clearly my comment makes you think I didn't get the joke, but I did. > "I'm guessing you didn't realize that this joke is presented as a joke, ..." Oh, I did. Really, I did. I guess we're just talking past each other. <shrug> You didn't get my joke, probably because you think I didn't get the original. Time to give up.
    - lostcolony 5y ago
      Okay. I'm not sure dissecting the technical inaccuracies of a joke ("but an imam would never walk into a bar!") is itself a joke (and I'm pretty sure you edited the comment just above to agree it was a joke, but maybe I just didn't read it closely enough), especially when you'd give the exact same response if you didn't know it was a joke, but did know it was technically incorrect, but fair enough.

tantalor 5y ago

> The test is the wrong way round Specifically, Collatz says "if x is even then x /= 2" but the code checks "x is odd".

stephencanon 5y ago

(a) part of the joke (b) the Millennium problems are not the only million-dollar prizes in mathematics (c) part of the joke (d) part of the joke (and part of the C++ standard)

ColinWright 5y ago
(b) There are other prizes, but I'm not aware of any others worth a million dollars. Do you have any pointers? A quick interwebs search didn't turn up anything, but they might just be being swamped by the results with the Millennium Problems.
- tpush 5y ago
  > A quick interwebs search didn't turn up anything [...] Searching 'collatz conjecture prize' quite literally puts a prize of a bout 120MM Yen (~ $1MM) as the top result.
  - ColinWright 5y ago
    Hah! I didn't search specifically for that, I was searching for bounties in general. Thanks.
- ithinkso 5y ago
  There is also a Beal Conjecture[0] worth a million [0] https://en.wikipedia.org/wiki/Beal_conjecture https://en.wikipedia.org/wiki/Beal_conjecture
  - ColinWright 5y ago
    My initial search for bounties didn't turn up that one, either. I wonder if my connection(s) with Erdos have polluted my search history, so it was showing me mostly those, and not showing me this. <shrug> Thanks for finding this and letting me know, I've learned something.

rtkwe 5y ago

> (b) The Collatz Conjecture isn't one of the Millennium problems; It's not but there are more bounties out there than just the Millenium list. For the Collatz Conjecture specifically there's a 120M Japanese Yen prize which at this moment is a bit more than 1 million USD. https://www.prnewswire.com/news-releases/bakuage-offers-prize-of-120-million-jpy-to-whoever-solves-collatz-conjecture-math-problem-unsolved-for-84-years-301326629.html https://www.prnewswire.com/news-releases/bakuage-offers-priz...

ColinWright 5y ago
(Also commented elsewhere) ... I didn't search specifically for that, I was searching for bounties in general. Thanks.

gameswithgo 5y ago

You have no sense of humor or curiosity about compiler optimization details that led to this, I guess. For instance not all languages that target LLVM will get this result. That is interesting.

yissp 5y ago

> (c) It's using bounded numbers in the range where the Collatz Conjecture is known to be true; The input is an unsigned __int128, and I believe Collatz has only been verified up to 2^68.

jens-c 5y ago

Not to mention that the answer by itself is pretty much worthless, but Mathematicians are rather interested in a proof of the conjecture (or its negation). I get that it is supposed to be a joke, but it kind of falls flat because it misses the point entirely.