What are the specific rules for constant folding?

There are no rules for constant folding. There are only implementation details. They have changed before, and they will change again.

Heck, you can't even talk about the "Python 3 behavior", or the "Python 3.6 behavior", because these implementation details changed between 3.6.4 and 3.6.5. On 3.6.4, the 2**66 example gets constant-folded.

For now, and no one knows how long "for now" will last, the implementation details are that the AST optimizer includes safeguards to prevent spending too much time or memory on constant folding. The safeguard for 2**66 or 4**33 is based on the number of bits in the LHS and the value of the RHS:

if (PyLong_Check(v) && PyLong_Check(w) && Py_SIZE(v) && Py_SIZE(w) > 0) {    size_t vbits = _PyLong_NumBits(v);    size_t wbits = PyLong_AsSize_t(w);    if (vbits == (size_t)-1 || wbits == (size_t)-1) {        return NULL;    }    if (vbits > MAX_INT_SIZE / wbits) {        return NULL;    }}

MAX_INT_SIZE is #defined earlier as 128. Since 2 is a 2-bit number and 4 is a 3-bit number, the estimated result size is smaller for 4**33, so it passes the check and gets constant-folded.

On Python 3.6.5, the implementation details are mostly similar, but this constant folding happens in the bytecode peephole optimizer instead of the AST optimizer, which doesn't exist on 3.6.5.

On Python 3.6.4, the pre-check safeguard doesn't exist. The peephole optimizer will discard too-large constant-folding results after computing them, which results in different thresholds than the pre-checks.