(2) I'm too lazy to do the calculation right now, but it should not be too difficult to calculate the sum of the lengths of all numbers smaller than n, and then you've got the index of n.
(3) In any feasible encoding, the expected size of the start index of n will be much larger than the size of n. And every recursive step will just blow up the sizes even more.
If you slightly modify it to 0. 0 1 2 3 4 5 6 7 8 9 00 01 02 03 04 05... then the number n padded with zeros to k digits can be found starting at position 10 * floor(10^(k - 1) / 9) + k * n.
Comments
(1) Yes, 0.1234567891011121314151617181920212223242526....
(2) I'm too lazy to do the calculation right now, but it should not be too difficult to calculate the sum of the lengths of all numbers smaller than n, and then you've got the index of n.
(3) In any feasible encoding, the expected size of the start index of n will be much larger than the size of n. And every recursive step will just blow up the sizes even more.
If you slightly modify it to 0. 0 1 2 3 4 5 6 7 8 9 00 01 02 03 04 05... then the number n padded with zeros to k digits can be found starting at position 10 * floor(10^(k - 1) / 9) + k * n.