Frankly, all solutions here I saw but for 54d7ac's one (mathematically optimal, but won't scale to big integers, transformation matrix is better for that, although brings O(log(n)) instead of O(1)) are heavily suboptimal anyway so it depends what you aim for. ;) I aimed for Iterator approach.