Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote -4 down vote favorite

How can I write (in pseudocode) a program that halts only if the Collatz Conjecture is false ?

Here is pseudocode for the case that it is true:

function collatz(n)  
  while n > 1  
    show n 
    if n is odd then  
      set n = 3n + 1 
    else  
      set n = n / 2 
    endif
  endwhile
  show n

Thanks much in advance!

share|improve this question
I believe you cannot do it. You could consider an approximate, such as monitoring a certain number of iterations or a certain execution time, and exit when it's reached. – Silver Quettier Feb 1 at 12:00
You may find the collatz tag on the math stack exchange interesting to read. – MichaelT Feb 1 at 14:34

closed as not a real question by ElYusubov, Glenn Nelson, Walter, MichaelT, GlenH7 Feb 1 at 15:07

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.

1 Answer

up vote 1 down vote

We can not do it if it is not known whether the algorithm is going to terminate or not.

http://en.wikipedia.org/wiki/Collatz_conjecture

From Wikipedia article: The conjecture has been checked by computer for all starting values up to 5 × 2^60 ≈ 5.764×10^18 Such computer evidence is not a proof that the conjecture is true.

share|improve this answer
+1 For pointing out that failure to prove something false isn't the same as proving it true. – KChaloux Feb 1 at 13:45
Yes, we have not proven that it is true, but sometimes you can construct something that satisfies an implication even if it's not completely known whether the premises of the implication are true or not. For example, there are some proofs of artificial functions that lie strictly between the P and NP complexity domains, that exist if and only if P != NP, as well as proofs of things that would be true if and only if P = NP. However, the problem of P = NP is still unsolved. – Joe Z. Feb 1 at 21:02

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