current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

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
up vote 1 down vote favorite

This is a simple program to test if integers will follow an interesting, improvable statement that if disproven, calls for a bravo.

But, ignoring the pretentious poetry, this code allows the user to input a number, which, if it is a finite, positive integer, will be calculated according to the Collatz Conjecture as stated/commented out below. Any optimizations? Obvious mistakes? Formatting issues?

Maybe let me know how to inform the user that the function-ception went a few levels too deep?

# The Collatz conjecture states that
# when you take a finite, positive integer, and
# if it's even, divide by 2, or
# if it's odd, multiply by 3 and add 1,
# and repeat this process enough times,
# you will eventually end up with one.
# Here's a module to demonstrate it.

def collatz(x):
  if abs(int(x)) == x:
    if x == 1:
      print ("The Collatz Conjecture works with this number!")
      print ("It took %s repetitions to reach 1.") % (collatz.counter)
    elif x % 2 == 0:
      y = x / 2
      print ("%s") % (y)
      collatz.counter += 1
      collatz(y)
    elif x % 2 == 1:
      y = x * 3 + 1
      print ("%s") % (y)
      collatz.counter += 1
      collatz(y)
    else:
      print ("Oh, my god!")
      print ("This number does NOT work with the Collatz Conjecture!")
      print ("You've disproven it!")
      print ("...Or maybe this program is broken. Try viewing the source?")
  else:
    print ("That isn't a finite positive integer...")

collatz.counter = 0

#Here's our attempt:

collatz(int(raw_input("Enter a finite positive integer")))
share|improve this question
    
When you use this function twice the counter will have as a value the sum of the steps needed. It is never reset to zero. – Graipher yesterday
1  
Also this will hit a RecursionLimit for some numbers. – Graipher yesterday
2  
Also, this can never find a value for which the collatz conjecture is wrong. Any number is either even or odd, so the else will never be reached. – Graipher yesterday
    
@Graipher Yes, I'm aware of the Recursion Limit. It's in the question. Though, is except RecursionLimit the valid vocabulary? In that case, that does answer the question, though. Also, good on you pointing out the counter flaw (I'll just reset it after 1 has been reached, I suppose). – Papayaman1000 yesterday
1  
The only way to check it is the recursion limit triggering it is to look at the error string. – Graipher yesterday
up vote 2 down vote

"Oh, my god!" will only be reached if the number is neither odd nor even, which will never be the case for any integer.

For a number that will never reach 1 and thus disprove the conjecture, your program would run forever (yet still never reach "Oh, my god!"). Welcome to the halting problem.

But as computer resources are limited, you will run into a stack overflow with the depth of your recursive function calls, whether the number would reach 1 eventually or not. For very large numbers, your program will simply crash, which won't tell you anything about the conjecture.

One way to solve that would be to not use recursion. To do so, return the result y from your function instead of calling the function again. Then call your function in a while loop that stops at 1, feeding the output of a previous call to your function to the next one.

This is still the halting problem, though. Does the computation just take very long or does it never finish (the latter would disprove the conjecture)? You never know.

To solve that too, you'd have to check if your program is trapped in a cycle of numbers (that does not contain 1)

share|improve this answer
    
That's... a good point. Now the question is how to compare an output to prior ones, as to ensure no number is ever repeated? That's the only single case that would indicate an infinite loop. – Papayaman1000 yesterday
    
@Papayaman1000 well, this is code review, not code preview. You probably have to keep track of the numbers somehow, then check them. – I'll add comments tomorrow yesterday
2  
@I'lladdcommentstomorrow: "which will never be the case for any real number." Sorry to be pedantic 2.5 is never odd nor even, so I think you mean integers. :P – Dair yesterday
    
@Dair yes right, my bad. Answer edited. – I'll add comments tomorrow yesterday

Your Answer

 
discard

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.