The 3n+1 problem(blog.racket-lang.org)
blog.racket-lang.org
The 3n+1 problem
http://blog.racket-lang.org/2012/10/the-3n1-problem_4990.html
5 comments
And it gets more interesting:
In 2007, researchers Kurtz and Simon, building on earlier work by J.H. Conway in the 1970s,[8] proved that a natural generalization of the Collatz problem is algorithmically undecidable.[7]
From http://en.wikipedia.org/wiki/Collatz_conjecture
In 2007, researchers Kurtz and Simon, building on earlier work by J.H. Conway in the 1970s,[8] proved that a natural generalization of the Collatz problem is algorithmically undecidable.[7]
From http://en.wikipedia.org/wiki/Collatz_conjecture
Indeed. In undergrad I spent a significant chunk of my spare time for about a year working on that problem.
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.
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.
In that case, I'd be much too excited about making progress in mathematics to be bothered by my toy program not working right.
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
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
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.
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.
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.
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.
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".
Of course, though it does mean you should examine it further to check.
[deleted](1)
That's funny, I just did the Collatz in Racket for a class.
Sounds like a Project Euler problem.
It is.
http://projecteuler.net/problem=14
Also: "A Modified Collatz sequence": http://projecteuler.net/problem=277
There may be others.
http://projecteuler.net/problem=14
Also: "A Modified Collatz sequence": http://projecteuler.net/problem=277
There may be others.
http://xkcd.com/710/