You need to identify a pattern.
We should be able to build a fairly simple pattern by grouping numbers in specific ways.
123456789 # One dimensional
10111213141516171819 # Two dimensional
20212223242526272829
30313233343536373839
...
90919293949596979899
100101102103104105106107108109 200201202203204205206207208209 # Three dimensional
110111112113114115116117118119
120121122123124125126127128129
...
190191192193194195196197198199
1000100110021003100410051006100710081009 # Four dimensional
We know if \$k\$ is less than 10 the value is \$k\$.
To see the pattern look at the one dimensional group and see the index where each number belongs.
We can see each digit has only one possible position.
- \$k \in \{1\} \therefore 1\$
(if \$k = 1\$ then the digit is 1)
- \$k \in \{2\} \therefore 2\$
(if \$k = 2\$ then the digit is 2)
$$
f_1(k) = k
$$
To make the pattern easier to see \$k_2 = k - 10\$.
Now \$f_2(0) = 1\$, \$f_2(1) = 0\$, \$f_2(2) = 1\$, \$f_2(3) = 1\$.
If we focus on how to build each section of the number we can see similar patterns.
For example the end digit is 0 in the 2nd column in the entire two dimensional block.
Since we know the width of the two dimensional block is 20 we know every \$20n + 1\$ number results in 0.
End digits (Odd numbers, \$k_2\ \%\ 2 = 1\$)
Just like we did for 0 we can look at every second column and see the value repeats all the way down.
- \$k_2 \in \{1, 21, 41, ..., 161\} \therefore 0\$
(if \$k_2 = 1\$ or \$k_2 = 21\$ or etc, the digit is 0)
- \$k_2 \in \{3, 23, 43, ..., 163\} \therefore 1\$
- \$k_2 \in \{5, 25, 45, ..., 165\} \therefore 2\$
We can then calculate the digit from the input number.
First we can modulo the number, \$k_2 % 20\$, to truncate each of the sets to the same number.
For example \$21 \% 20 = 1\$, \$41 \% 20 = 1\$, etc.
Now the sets are much simpler.
- \$k_2\ \%\ 20 \in \{1\} \therefore 0\$
(if \$k_2\ \%\ 20 = 1\$ the digit is 0)
- \$k_2\ \%\ 20 \in \{3\} \therefore 1\$
- \$k_2\ \%\ 20 \in \{5\} \therefore 2\$
Now getting the same digit for each input is really easy.
We can just floor divide by 2.
Since \$\lfloor\frac{1}{2}\rfloor = 0\$, \$\lfloor\frac{3}{2}\rfloor = 1\$, etc.
So we know if the number is odd we can get the digit by using the following formula:
$$\lfloor\frac{k_2\ \%\ 20}{2}\rfloor$$
Head digits (Even numbers, \$k_2\ \%\ 2 = 0\$)
Just like we did for the columns we can see a pattern in the rows.
Every two columns the first number is the same.
We can build the sets for where each number is.
- \$k_2 \in \{ 0, 2, 4, ..., 18\} \therefore 1\$
- \$k_2 \in \{20, 22, 24, ..., 38\} \therefore 2\$
- \$k_2 \in \{40, 42, 44, ..., 58\} \therefore 3\$
We can see any less than 20 are 1, then any less than 40 are 2.
We can floor divide by 20 and add 1.
And so the formula is:
$$\lfloor\frac{k_2}{20}\rfloor + 1$$
We can merge both the previous functions into one function.
$$
f_2(k_2) =
\begin{cases}
\lfloor\frac{k_2}{20}\rfloor + 1, & \text{if $k_2 \% 2 = 0$ (head)} \\
\lfloor\frac{k_2\ \%\ 20}{2}\rfloor, & \text{if $k_2 \% 2 = 1$ (end)}
\end{cases}
$$
To make the pattern easier to see \$k_3 = k_2 - 180\$.
Again we'll focus on building each digit.
End digits \$k_3\ \%\ 3 = 2\$
Ok the end digits are following the same pattern again.
Every \$30n + 2 = 0\$, \$30n + 5 = 1\$.
- \$k_3 \in \{2, 32, 62, ..., 2672\} \therefore 0\$
- \$k_3 \in \{5, 35, 65, ..., 2675\} \therefore 1\$
- \$k_3 \in \{8, 38, 68, ..., 2678\} \therefore 2\$
Again we can use a similar algorithm as before to truncate the sets to just one number each.
Afterwards we can figure out how to convert each of the numbers to the digit.
We can modulo \$k_3\$ by 30 to truncate each set to one number each, leaving 2, 5, 8, ....
The final numbers can be converted to the correct output by just floor dividing by 3.
$$\lfloor\frac{k_3\ \%\ 30}{3}\rfloor$$
Mid digits \$k_3\ \%\ 3 = 1\$
The mid digits have an interesting pattern.
Because the numbers are repeating in the 3rd dimension each time starting from around 100, 200, 300, etc.
As such I have used nested sets to show the split patterns.
The nested sets are just to show the start, end and step of the repeating patterns.
- \$k_3 \in \{\{1, 4, 7, ..., 28\}, \{301, 304, ... 328\}, ..., \{2401, 2404, ..., 2428\}\} \therefore 0\$
- \$k_3 \in \{\{31, 34, 37, ..., 58\}, \{331, 334, ... 358\}, ..., \{2431, 2434, ..., 2458\}\} \therefore 1\$
- \$k_3 \in \{\{61, 64, 67, ..., 88\}, \{361, 364, ... 388\}, ..., \{2461, 2464, ..., 2488\}\} \therefore 2\$
Just like in both the previous end digits we can use modulo to reduce the size of the set.
We can see the outer sets repeat every 300 digits so using modulo 300 we can reduce the sets to something more manageable.
- \$k_3 \% 300 \in \{1, 4, 7, ..., 28\} \therefore 0\$
- \$k_3 \% 300 \in \{31, 34, 37, ..., 58\} \therefore 1\$
- \$k_3 \% 300 \in \{61, 64, 67, ..., 88\} \therefore 2\$
Now the sets look like sets we got in the head digit.
Now we can just floor divide by 30 to get the digit.
$$\lfloor\frac{k_3\ \%\ 300}{30}\rfloor$$
Head digits \$k_3\ \%\ 3 = 0\$
- \$k_3 \in \{ 0, 3, 6, ..., 297\} \therefore 1\$
- \$k_3 \in \{300, 303, 306, ..., 597\} \therefore 2\$
- \$k_3 \in \{600, 603, 606, ..., 797\} \therefore 3\$
Again the head digit pattern is the same, just with a different number.
We can just floor divide by 300 and add one to get the digit.
$$\lfloor\frac{k_3}{300}\rfloor + 1$$
Again we can merge the patterns into a single function:
$$
f_3(k_3) =
\begin{cases}
\lfloor\frac{k_3}{300}\rfloor + 1, & \text{if $k_3\ \%\ 3 = 0$ (head)} \\
\lfloor\frac{k_3\ \%\ 300}{30}\rfloor, & \text{if $k_3\ \%\ 3 = 1$ (mid)} \\
\lfloor\frac{k_3\ \%\ 30}{3}\rfloor, & \text{if $k_3\ \%\ 3 = 2$ (end)}
\end{cases}
$$
We can see a pattern emerging. Lets have \$k_1 = k - 1\$.
We can see similar values 2, 20, 3, 30 and 300.
So we can move the dimension, \$n\$, out of the numbers and get \$1n\$, \$10n\$, \$1n\$, \$10n\$ and \$100n\$ respectively.
Looking at the previous numbers we can see a pattern again 1, 10 and 100.
The pattern between the numbers is \$10^?\$ where we currently don't know what \$?\$ is.
We can see the numerator's modulo is always \$? + 1\$ the denominator's \$?\$.
As such we can change the above functions to a very similar pattern.
$$
f_3(k_3) =
\begin{cases}
\lfloor\frac{k_3\ \%\ (3 * 10^{3 - 0})}{3 * 10^{3 - 1}}\rfloor + 1, & \text{if $k_3\ \%\ 3 = 0$} \\
\lfloor\frac{k_3\ \%\ (3 * 10^{3 - 1})}{3 * 10^{3 - 2}}\rfloor, & \text{if $k_3\ \%\ 3 = 1$} \\
\lfloor\frac{k_3\ \%\ (3 * 10^{3 - 2})}{3 * 10^{3 - 3}}\rfloor, & \text{if $k_3\ \%\ 3 = 2$}
\end{cases}\\
f_2(k_2) =
\begin{cases}
\lfloor\frac{k_2\ \%\ (2 * 10^{2 - 0})}{2 * 10^{2 - 1}}\rfloor + 1, & \text{if $k_2 \% 2 = 0$} \\
\lfloor\frac{k_2\ \%\ (2 * 10^{2 - 1})}{2 * 10^{2 - 2}}\rfloor, & \text{if $k_2 \% 2 = 1$}
\end{cases}\\
f_1(k_1) =
\begin{cases}
\lfloor\frac{k_1\ \%\ (1 * 10^{1 - 0})}{1 * 10^{1 - 1}}\rfloor + 1, & \text{if $k_1 \% 1 = 0$}
\end{cases}
$$
Here we have found what \$?\$ is.
Looking at the "if" we can see \$?\$ is based on the modulo of \$k\$.
As such we can improve the function further to:
$$
f_n(k_n) =
\lfloor\frac{k_n\ \%\ (n10^{n - (k_n\ \%\ n)})}{n10^{n - (k_n\ \%\ n) - 1}}\rfloor + \begin{cases}
1, & \text{if $k_n \% n = 0$}\\
0, & \text{otherwise}
\end{cases}
$$
I'll leave getting \$n\$ and \$k_n\$ from \$k\$ as a challenge for the OP.
We can check the equation works with the following code.
def fn(k, n):
mod = k % n
return (
(
(k % (n * 10 ** (n - mod)))
// (n * 10 ** (n - mod - 1))
)
+ (0 if mod else 1)
)
for row in range(0, 180, 20):
digits = [
fn(index, 3)
for index in range(row, row + 20)
]
print("".join(str(d) for d in digits))
10111213141516171819
20212223242526272829
30313233343536373839
40414243444546474849
50515253545556575859
60616263646566676869
70717273747576777879
80818283848586878889
90919293949596979899
Note: The function doesn't work correctly on the 'last chunk' of numbers, fn(180, 2) == 10
but when the function loops back around we get the correct numbers fn(200, 2) == 1
.
Because we don't need to generate \$00\ \to\ 09\$ I defiled the function.
To get the 'pure' function remove + (0 if mod else 1)
and adjust the input accordingly.
I.e start at 20 not 0.