Different results in Python v 3.5.2 and v 2.7.12, but the v 2.7.12 is correct?

Question

Let me preface my question by saying I know that around Python 3, the "limitless long" was integrated into the int so effectively ints in Python can be as large as your RAM.

I'm comparing Java and Python. The following are a Python and Java program. They do the same thing.

Python:

def answer(n):
    count = 0
    t = int(n)
    while (t!=1):
        t = t+1 if (t%2==1) else t/2
        count += 1
    return count

Java:

static int answer(String n){
    int count = 0;
    BigInteger t = new BigInteger(n)

    while(!t.equals(BigInteger.ONE)){
        t = ((t.remainder(new BigInteger("2"))).equals(BigInteger.ONE))
            ?t.add(new BigInteger("1"))
            :t.divide(new BigInteger("2"));
        count++;
    }
    return count;
}

Then I wrote a simple bash script to run the java and python (as version 2.7.12, and 3.5.2) and compares their output.

#!/bin/bash
    i=$1
    a=`java    Solution    $i`
    b=`python  Solution.py $i`
    c=`python3 Solution.py $1`

    echo "INPUT: $1"
    echo ""
    echo "LANGUAGE: VERSION:  RESULT:"
    echo "--------  --------- ------"
    echo "Java      1.8.0_151   $a"
    echo "Python    2.7.12      $b"
    echo "Python3   3.5.2       $c"

Here are a few sample runs. The RESULT column is what's important.

INPUT: 123

LANGUAGE: VERSION:  RESULT:
--------  --------- ------
Java      1.8.0_151   9
Python    2.7.12      9
Python3   3.5.2       9


INPUT: 123456789

LANGUAGE: VERSION:  RESULT:
--------  --------- ------
Java      1.8.0_151   39
Python    2.7.12      39
Python3   3.5.2       39


INPUT: 12345678998765

LANGUAGE: VERSION:  RESULT:
--------  --------- ------
Java      1.8.0_151   61
Python    2.7.12      61
Python3   3.5.2       61


INPUT: 123456789987654321

LANGUAGE: VERSION:  RESULT:
--------  --------- ------
Java      1.8.0_151   84
Python    2.7.12      84
Python3   3.5.2       82

So they all pretty much yield the same results until the input gets sufficiently large and then you can see for the last one, that the results are different. Pretty much every number larger than this yields differing results.

Shouldn't Python3's int and Java's BigInteger get the same result?

Shouldn't Python v.2 be the one getting different results?

Which one is actually wrong and why? Java and Python3 or just Python v.2.7.12?

How can I correct whichever is wrong to have the correct output?

Answer 1

The problem actually isn't related to the limit on integer literals in Python 2. That's just a red-herring. Your real problem is that the division operator / behaves different in Python 2 than in Python 3.

PEP 238 documents this change:

The current division (/) operator has an ambiguous meaning for numerical arguments: it returns the floor of the mathematical result of division if the arguments are ints or longs, but it returns a reasonable approximation of the division result if the arguments are floats or complex. This makes expressions expecting float or complex results error-prone when integers are not expected but possible as inputs.

We propose to fix this by introducing different operators for different operations: x/y to return a reasonable approximation of the mathematical result of the division ("true division"), x//y to return the floor ("floor division"). We call the current, mixed meaning of x/y "classic division".

Because of severe backwards compatibility issues, not to mention a major flamewar on c.l.py, we propose the following transitional measures (starting with Python 2.2):

• Classic division will remain the default in the Python 2.x series; true division will be standard in Python 3.0.

• The // operator will be available to request floor division
  unambiguously.

• The future division statement, spelled from __future__ import
division, will change the / operator to mean true division throughout the module.

• A command line option will enable run-time warnings for classic
  division applied to int or long arguments; another command line
  option will make true division the default.

• The standard library will use the future division statement and the
  // operator when appropriate, so as to completely avoid classic
  division.

Thus, if you want your Python code to behave correctly when the input is 123456789987654321, you need to use the floor division operator //:

def answer(n):
    count = 0
    t = int(n)
    while t != 1:
        t = t + 1 if (t % 2==1) else t // 2
        count += 1
    return count