The 3n+1 problem

http://blog.racket-lang.org/2012/10/the-3n1-problem_4990.html

by denzil_correa • 14 years ago

66 15 14 years ago

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• 14 years 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• 14 years 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.

waterhouse2• 14 years 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• 14 years ago

Of course, though it does mean you should examine it further to check.

Dove• 14 years 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• 14 years 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

artursapek• 14 years ago

That's funny, I just did the Collatz in Racket for a class.

sixothree• 14 years ago

Sounds like a Project Euler problem.

waterhouse2• 14 years ago

It is.

http://projecteuler.net/problem=14

Also: "A Modified Collatz sequence": http://projecteuler.net/problem=277

There may be others.

smilliken• 14 years ago

Open invitation: drop by the MixRank office (SoMA, SF) on Wednesday evenings for friendly Project Euler competitions.

jboggan• 14 years ago

I heartily recommend this.

dollarpizza• 14 years ago

Funny how now matter where they start out, just about everybody who attempts to take on the 3x+1 problem eventually ends up in pretty much the same place:

http://xkcd.com/710/

Turing_Machine• 14 years ago

Indeed. In undergrad I spent a significant chunk of my spare time for about a year working on that problem.

DanielRibeiro• 14 years ago

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

The 3n+1 problem

Related Stories