7 ms·

The 3n+1 problem

66 points by denzil_correa 14y ago

kachnuv_ocasek 14y 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 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
artursapek 14y ago
That's funny, I just did the Collatz in Racket for a class.
sixothree 14y ago
Sounds like a Project Euler problem.
- waterhouse 14y ago
  It is. http://projecteuler.net/problem=14 http://projecteuler.net/problem=14 Also: "A Modified Collatz sequence": http://projecteuler.net/problem=277 http://projecteuler.net/problem=277 There may be others.
- smilliken 14y ago
  Open invitation: drop by the MixRank office (SoMA, SF) on Wednesday evenings for friendly Project Euler competitions.
  - jboggan 14y ago
    I heartily recommend this.
dollarpizza 14y 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/ http://xkcd.com/710/
- Turing_Machine 14y ago
  Indeed. In undergrad I spent a significant chunk of my spare time for about a year working on that problem.
- DanielRibeiro 14y 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 http://en.wikipedia.org/wiki/Collatz_conjecture
deleted 14y ago
[deleted]
- esrauch 14y ago
  Whether or not this converges for all inputs is a famous unproved math problem, so it is somewhat humorous that you think you have a proof of convergence. Take your last case of f(f(f(even):odd):even) = (3/4)n+1/2. If you take one more step and this is odd then you end up at 3( (3/4)n+1/2) + 1 = (9n + 10) /4, which is larger than you started. In fact, the result of that could be odd which would then grow even larger (before becoming even as you note).
  - vy8vWJlco 14y ago
    I immediately regretted myself and backed out my comment -- but just to address your note about even:odd:even:odd, since you have a point: you are considering a 5 number string (starting with an even) when the skipping-monotonicity property I was toying with only applied to strings 4 long (again, beginning with an even number). It might look like a spike, but it's not a valid application. I'm not asserting it's strictly monotonic, of course -- as your other note implied -- but rather that every 4th (starting on an even, for n>=8) is less than n. But, IANAM. I don't even claim it's right ATM -- I redacted it to chew on more -- but for the sake of conversation, I'll reproduce it, and people can debug or ignore. Original comment: ---- Ok... ok ok ok. ok. Assume: n>1. I claim: an odd output can only occur after an even input. 'Cause: for 2n-1 (clearly odd), f(2n-1) = 3(2n-1)+1 = 2(3n-1), which is clearly even. [This made me redact my thoughts initially -- and they're just that -- thoughts. I thought I'd try to come at this property from a different angle...] Implying: an odd input can only come initially or immediately after a prior even event... There can't be two sequential odd results during normal (non-initial) iterations. For that matter, if the initial input is odd, the output will be even after at most two iterations (3(3n+1)+1=6n+4=2(3n+2), which is even), after which it's business as usual. So, we only really have to consider sequences beginning from an even n to see what's really going on. f(n:even) can yield an odd or an even value. Permuted: f(f(f(n:even):odd):odd) is impossible (see above). f(f(f(n:even):even):even)=((n/2)/2)/2=n/8 is less than the initial (n:even) for n>8 f(f(f(n:even):even):odd)=3((n/2)/2)+1=(3/4)n+1 is less than the initial (n:even) for n>4 f(f(f(n:even):odd):even)=(3(n/2)+1)/2=(3/4)n+1/2 is less than the initial (n:even) for n>4 I conclude: no cycles while n>8 and no infinite divergent trajectories while n>8. You can't have cycles OR divergent infinite trajectories while n>8 since no output, after 3 iterations, may exceed the initial (even) input. In other words, pick any 4 sequential numbers BEGINNING with an EVEN number (the initial even input and the results of 3 consecutive iterations) and the 4th number will always be smaller than the 1st number - whether the final number is even OR odd, or there were some biggies in the middle of the list. It's like... monotonic.

66 points by denzil_correa 14y 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 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

artursapek 14y ago

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

sixothree 14y ago

Sounds like a Project Euler problem.

waterhouse 14y ago
It is. http://projecteuler.net/problem=14 http://projecteuler.net/problem=14 Also: "A Modified Collatz sequence": http://projecteuler.net/problem=277 http://projecteuler.net/problem=277 There may be others.
smilliken 14y ago
Open invitation: drop by the MixRank office (SoMA, SF) on Wednesday evenings for friendly Project Euler competitions.
- jboggan 14y ago
  I heartily recommend this.

dollarpizza 14y 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/ http://xkcd.com/710/

Turing_Machine 14y ago
Indeed. In undergrad I spent a significant chunk of my spare time for about a year working on that problem.
DanielRibeiro 14y 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 http://en.wikipedia.org/wiki/Collatz_conjecture

deleted 14y ago

[deleted]

esrauch 14y ago
Whether or not this converges for all inputs is a famous unproved math problem, so it is somewhat humorous that you think you have a proof of convergence. Take your last case of f(f(f(even):odd):even) = (3/4)n+1/2. If you take one more step and this is odd then you end up at 3( (3/4)n+1/2) + 1 = (9n + 10) /4, which is larger than you started. In fact, the result of that could be odd which would then grow even larger (before becoming even as you note).
- vy8vWJlco 14y ago
  I immediately regretted myself and backed out my comment -- but just to address your note about even:odd:even:odd, since you have a point: you are considering a 5 number string (starting with an even) when the skipping-monotonicity property I was toying with only applied to strings 4 long (again, beginning with an even number). It might look like a spike, but it's not a valid application. I'm not asserting it's strictly monotonic, of course -- as your other note implied -- but rather that every 4th (starting on an even, for n>=8) is less than n. But, IANAM. I don't even claim it's right ATM -- I redacted it to chew on more -- but for the sake of conversation, I'll reproduce it, and people can debug or ignore. Original comment: ---- Ok... ok ok ok. ok. Assume: n>1. I claim: an odd output can only occur after an even input. 'Cause: for 2n-1 (clearly odd), f(2n-1) = 3(2n-1)+1 = 2(3n-1), which is clearly even. [This made me redact my thoughts initially -- and they're just that -- thoughts. I thought I'd try to come at this property from a different angle...] Implying: an odd input can only come initially or immediately after a prior even event... There can't be two sequential odd results during normal (non-initial) iterations. For that matter, if the initial input is odd, the output will be even after at most two iterations (3(3n+1)+1=6n+4=2(3n+2), which is even), after which it's business as usual. So, we only really have to consider sequences beginning from an even n to see what's really going on. f(n:even) can yield an odd or an even value. Permuted: f(f(f(n:even):odd):odd) is impossible (see above). f(f(f(n:even):even):even)=((n/2)/2)/2=n/8 is less than the initial (n:even) for n>8 f(f(f(n:even):even):odd)=3((n/2)/2)+1=(3/4)n+1 is less than the initial (n:even) for n>4 f(f(f(n:even):odd):even)=(3(n/2)+1)/2=(3/4)n+1/2 is less than the initial (n:even) for n>4 I conclude: no cycles while n>8 and no infinite divergent trajectories while n>8. You can't have cycles OR divergent infinite trajectories while n>8 since no output, after 3 iterations, may exceed the initial (even) input. In other words, pick any 4 sequential numbers BEGINNING with an EVEN number (the initial even input and the results of 3 consecutive iterations) and the 4th number will always be smaller than the 1st number - whether the final number is even OR odd, or there were some biggies in the middle of the list. It's like... monotonic.