1
\$\begingroup\$

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")))
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Graipher Nov 18 '16 at 19:50
  • 1
    \$\begingroup\$ Also this will hit a RecursionLimit for some numbers. \$\endgroup\$ – Graipher Nov 18 '16 at 19:52
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Graipher Nov 18 '16 at 19:55
  • \$\begingroup\$ @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). \$\endgroup\$ – Papayaman1000 Nov 18 '16 at 20:01
  • 1
    \$\begingroup\$ The only way to check it is the recursion limit triggering it is to look at the error string. \$\endgroup\$ – Graipher Nov 18 '16 at 21:19
2
\$\begingroup\$

"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)

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Papayaman1000 Nov 18 '16 at 20:47
  • \$\begingroup\$ @Papayaman1000 well, this is code review, not code preview. You probably have to keep track of the numbers somehow, then check them. \$\endgroup\$ – I'll add comments tomorrow Nov 18 '16 at 21:32
  • 2
    \$\begingroup\$ @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 \$\endgroup\$ – Dair Nov 18 '16 at 22:03
  • \$\begingroup\$ @Dair yes right, my bad. Answer edited. \$\endgroup\$ – I'll add comments tomorrow Nov 18 '16 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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