# Nth number in a infinite sequence of numbers

This was interview question.

When the input is a infinite sequence of numbers starting from 1, what is the nth digit?

e.g.) 123456789101112131415161718192021.....

here 28th digit is 1.

• What have you tried? Where did you get stuck? What are you looking for in an answer? Are you looking for an algorithm? Note that coding questions are off-topic here. If you're looking for an algorithm, what approaches did you consider? – D.W. Feb 29 '16 at 7:05
• You'll find a lot of references on OEIS. – Gilles 'SO- stop being evil' Mar 11 '16 at 21:29

Just to add a concrete implementation to what was already said:

(defun nth-digit (n)
(loop :with previous := 0
:for i :upfrom 0
:sum (* 9 (expt 10 i) (1+ i)) :into digits
:if (> digits n) :do
(multiple-value-bind (whole remainder)
(floor (- n previous) (1+ i))
(return (aref (write-to-string (+ (expt 10 i) whole)) remainder)))
:else :do (setf previous digits)))


The idea for implementation is to:

1. Sum the length of all 1-digit numbers (of which there are $9*10^0$), then sum all 2-digit numbers (of which there are $9*10^1$), 3-digit numbers, of which there are $9*10^2$ and so on. This gives:

$$N = \sum_{i=0}^m 9\times 10^i \times (i+1)$$

1. Notice that $x = \lfloor\frac{n - N}{i+1}\rfloor$ will be a positive integer which counts the number of numbers having $m+1$ digits in them.
2. Finally, after you've already found what number contains your digit, you can find $e$ s.t. $r - e = 10^i + \frac{n - N}{i+1}$, and $e \leq i$ the $e'th$ digit of $x$ is going to be the one you are looking for.
• Probably, i + 1 instead of i in step 1? – Sungguk Lim Feb 29 '16 at 4:05
• @SunggukLim yup, it should be i +1. – wvxvw Feb 29 '16 at 6:44

The idea here is as follows:

• The first 9 digits are 123456789.
• The next 90 pairs of digits are (10)(11)...(99).
• The following 900 triplets of digits are (100)(101)...(999).
• And so on.

Given an index $n$, you calculate which group you are (singles, pairs, triplets, ...), then which tuple you belong to and which digit inside the tuple. For example, if $n=28$ then this is digit no. 19 in the second group, which is the first digit of the 10th tuple 19, that is, 1.