Finally passed all tests with my Python3 implementation without timing out. Some lessons learned:

• Casting is very expensive, so instead of doing divide + cast to int, try doing shift
• Python dictionaries are insanely expensive compared to lists
• Lists are expensive compared to storing state in the framestack, aka recursion
• Getting fancy with pre-computing low-hanging fruit results usually doesn't pay off, just keep it simple. Exhaustive search with memoization is fast enough.