0

I have created a small Python program in repl.it to illustrate the Collatz Conjecture, which says that if you start with any positive integer number n and you apply the following operations recursively: n/2 if n is even, 3n+1 if n is odd, you will always reach 1.

This is the code:

invalid_input = 0

while(invalid_input == 0):
  n = input("Give me a positive integer: ")

  try: #check for positive integer. If it cannot do int(n) it means a string was entered, and it goes to except.
    if(int(n)>0):
      invalid_input = 1 #this is to tell the while loop above that the right input was entered
      print("Thank you.")
      print("Now loading:")

    else: #an integer was entered, but it was negative
      print("Please enter a positive integer")
  except: #a string was entered
    print("Please enter a positive integer")

n=int(n)
nentered = n #this will keep track of the initial n
npeak = n #this will keep track of the highest n reached
iteration = 1 #this will keep track of the number of iterations
iterationmax = 1 #this will keep tack of the iteration at which npeak was reached

while(n != 1):
  print("%5i:    %5i" % (iteration,n))
  if(n % 2 == 0): #divide by 2 if even
    n=n/2
  else: #if it is odd, multiply by 3 and add 1
    n=3*n+1
  iteration = iteration + 1
  if(n>npeak): #record the higher n and its iteration
    npeak = n
    iterationmax = iteration

It works. But there is a problem: if the entered number is big enough, for example 6666666666666666666666666, then it does something really strange. This is what I get:

Give me a positive integer: 6666666666666666666666666
Thank you.
Now loading:
    1:    6666666666666666666666666
    2:    3333333333333333277409280
    3:    1666666666666666638704640
    4:    833333333333333319352320
    5:    416666666666666659676160
    6:    208333333333333329838080
    7:    104166666666666664919040
    8:    52083333333333332459520
    9:    26041666666666666229760
   10:    13020833333333333114880
etc

As you can see, I am expecting the second number to be exactly 3333333333333333333333333, but instead I am getting different numbers at the end. As another example, entering 1000000000000000000000000 returns 499999999999999991611392 in the second iteration.

What could be the reason for this?

Luismi98
  • 282
  • 3
  • 14

2 Answers2

1

Change your / operation to be //, so that they don't result in (inaccurate) floating point values.

So this:

if(n % 2 == 0): #divide by 2 if even
  n=n/2

Should be:

if(n % 2 == 0): #divide by 2 if even
  n=n//2

Or as properly formatted by Python conventions:

if n % 2 == 0:
    n //= 2
ruohola
  • 21,987
  • 6
  • 62
  • 97
  • Thank you very much. I am interested by the last thing you mentioned. Could I therefore do n=n+1 by writing n += 1 ? – Luismi98 May 09 '19 at 15:43
  • @Luismi98 Yes! They are called compound operators. You can read more from those for example here: https://www.programiz.com/python-programming/operators – ruohola May 09 '19 at 15:46
1

The reason of why what @ruohola said is true, is because when you use floating-point division with a single /, what happens is that a floating-point number is created. However, it cannot be represented as the number is so large, so it is rounded to the closest most accurate representation. So you will have to use // instead of /.

However, using //, is integer division. This results in an integer which can be represented much easier than a high float.

A very similar question can be found here, it contains some more explanation.

Elodin
  • 650
  • 5
  • 23