Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to write a pseudocode program that halts only if the Collatz Conjecture is false.

Thanks much in advance!!!

share|cite|improve this question
In general, if you want code written you should ask in a computer forum, not in a math forum. In THIS forum, if you want help with homework, first you should show what you have done so far. – GEdgar Jan 31 '13 at 19:51
There's a Collatz Tag! – jspecter Jan 31 '13 at 20:19
"If Collatz conjecture is false then halt else go to infinite loop." I don't think code comes more pseudo than that! – Gerry Myerson Feb 1 '13 at 2:24
@GEdgar This question isn't phrased in the most sophisticated way, but (as I read it) it is a mathematical question, not a CS one. Is there an algorithm which we can prove halts iff Collatz is false? The sophisticated framing is "can we find a $\Pi^0_1$ reformulation of Collatz"? I don't see how to do it, but I will certainly be interested to see if someone can find one. – David Speyer Feb 1 '13 at 15:19
See… , where this same problem is discussed in much more sophisticated language, but without finding a solution. – David Speyer Feb 1 '13 at 20:59
up vote 0 down vote accepted

If the Collatz-conjecture is false, then we have either a "nontrivial" cycle (we have some in the domain of negative integers) or a divergent trajectory.

If we check all numbers, whether their trajectory arrives at 1 and find, that on a certain trajectory an earlier number occurs a second time, then the program may halt and print "collatz conjecture false for integer [n]" where [n] is the first number which signalled the occurence of a cycle.

However, this does not detect (and then halt the program) if we arrive at a divergent trajectory - so this answers your question only half way...

share|cite|improve this answer
I would modify to loop and each step advance all the previously started sequences - if possible; and start the one at the next integer. If you found a cycle then it halts. Sort of a diagonalization-walk. – Asaf Karagila Jan 31 '13 at 19:57
Since "verifying" that a trajectory is divergent is highly non-trivial, an algorithm that finds other cycles (like this) is probably the best you can do. – TMM Jan 31 '13 at 20:00
@Asaf : well, there is another cycle-detecting method which procceds for each conjectured cycle-length (say "L") and for L=1 to infinity: <perform check>" the <perform check>-routine needs only finitely many steps (however increasing with L) - but that needs a bit more pseudocode... – Gottfried Helms Jan 31 '13 at 20:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.