Here is the empirical data I promised. The number of calls to seq4_inc gives the number of passes through the G3 loop of >>67, and this can be obtained with cProfile. The numbers are R(10^16)->171, R(10^24)->1796, R(10^32)->18219 and R(10^40)->183011. The successive ratios are increasingly good approximations of 10:
>>> 1796 / 171
10.502923976608187
>>> 18219 / 1796
10.144209354120267
>>> 183011 / 18219
10.04506284647895Therefore the number of steps of the corrected version increases roughly by a factor of 10 when the index of R increases by a factor of 10^8. This backs up the runtime of O(n^(1/8)).