Итак, у нас есть последовательность, составленная из
1 1 digit 1 digit total
12 2 digits 3 digits total
123 3 digits 3*(3+1)/2 = 6 digits total
1234 4 digits 4*(4+1)/2 = 10 digits total
...
123..89 9 digits 9*(9+1)/2 = 45 digits total
123..8910 11 digits 10*(10+1)/2 + 1 = 56
123..891011 13 digits 11*(10+1)/2 + 3 = 69
123..89101112 15 digits 12*(12+1)/2 + 3*(3+1)/2 = 84 digits
Это OEIS Sequence A165145 , а также см. Связанную последовательность OEIS A058183 .
Формула для общего количества цифр:
f(n) = n*(n+1)/2 + {(n-9)*(n-8)/2 : if n>=10} + {(n-99)*(n-98)/2 : if n>=100) + ...
Некоторые ключевые моменты f (9) = 45, f (99) = 99 * 100/2 + 90 * 91/2 = 9045, f (999) = 1 395 495.
Контурный алгоритм для нахождения k-й цифры будет
- Найти, какая часть последовательности находится в n <= 9, 10<= n <= 99, 100 <= n <= 999 путем сравнения k со значениями границы 45, 9045, 1395495. </li>
- Восстановите значение n
- Найдите фактическую цифру, которая будетбыть kf (n) вдоль последовательности для n-го числа.
Если мы берем 10 <= n <= 99, формула для количества цифр будет </p>
n*(n+1)/2 + (n-9)*(n-8)/2
= 1/2( n^2 + n + n^2 - 17 n + 72)
= n^2 - 8 n + 36
Таким образом, учитывая 45
n = ceil( ( 8 + sqrt(64 - 4 (36 - k)))/2)
. Нам нужна другая квадратная формула для k вне диапазона.
Например, взять k = 100, используя формулу дает n = 13.Есть f (12) = 84 цифры для всех чисел до 12, поэтому первая цифра 13-й строки находится в позиции 85. Итак, мы ищем 16-ю цифру.Мы можем использовать формулу
digit(l) := l <= 9 ? l : (l%2==0 ? floor((l+10)/20) : ((l-11)/2)%10 )
, чтобы найти действительную цифру, которая равна 1.