3 ms·

Interesting article. For those not familiar with the problem, it's called the Collatz conjecture. I'm curious how this would behave in case of the conjecture b

Interesting article. For those not familiar with the problem, it's called the Collatz conjecture. I'm curious how this would behave in case of the conjecture being false, i.e. found a number that wouldn't reduce to 1 by the algorithm.

Avshalom 14y ago
Not knowing much about the internals of the interpreter (other than proper tco) I would assume just your old fashioned infinite loop unless it got into bignum territory and got too large for memory. I'm sure you could use contracts to prevent the latter and reasonably sure there's some option somewhere to set maximum recursion depth to prevent the prior. EDIT: as opposed to boring method of just putting/checking a loop count accumulator and if not bignum? into the function body.
lmm 14y ago
The function doesn't look to be tail-recursive, so my guess would be a stack overflow. Of course, if you run it and get a stack overflow, you have no way of knowing whether the number was really a counterexample or just one that took many steps to reach 1.
- waterhouse 14y ago
  It would be a stack overflow, except Racket does not stack overflow--it will grab more memory, make a bigger stack, and continue. Eventually your problem would be "out of memory".
- masterzora 14y ago
  Of course, though it does mean you should examine it further to check.
Dove 14y ago
In that case, I'd be much too excited about making progress in mathematics to be bothered by my toy program not working right.
denzil_correa 14y ago
Yup - there are some other names to it too. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanisław Ulam), Kakutani's problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse's algorithm (after Helmut Hasse), or the Syracuse problem; the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers,or as wondrous numbers. http://en.wikipedia.org/wiki/Collatz_conjecture http://en.wikipedia.org/wiki/Collatz_conjecture

Avshalom 14y ago

Not knowing much about the internals of the interpreter (other than proper tco) I would assume just your old fashioned infinite loop unless it got into bignum territory and got too large for memory. I'm sure you could use contracts to prevent the latter and reasonably sure there's some option somewhere to set maximum recursion depth to prevent the prior. EDIT: as opposed to boring method of just putting/checking a loop count accumulator and if not bignum? into the function body.

lmm 14y ago

The function doesn't look to be tail-recursive, so my guess would be a stack overflow. Of course, if you run it and get a stack overflow, you have no way of knowing whether the number was really a counterexample or just one that took many steps to reach 1.

waterhouse 14y ago
It would be a stack overflow, except Racket does not stack overflow--it will grab more memory, make a bigger stack, and continue. Eventually your problem would be "out of memory".
masterzora 14y ago
Of course, though it does mean you should examine it further to check.

Dove 14y ago

In that case, I'd be much too excited about making progress in mathematics to be bothered by my toy program not working right.

denzil_correa 14y ago

Yup - there are some other names to it too. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanisław Ulam), Kakutani's problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse's algorithm (after Helmut Hasse), or the Syracuse problem; the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers,or as wondrous numbers. http://en.wikipedia.org/wiki/Collatz_conjecture http://en.wikipedia.org/wiki/Collatz_conjecture