What is the longest number written in hexadecimal notation as $x_1x_2x_3...x_n$ ($x_i$ is a hexadecimal digit), provided that $x_1x_2...x_k$ when divided by $k$ gives the remainder $k-1$ for all $k \le n$ and the middle digit of the number is b.
I tried writing a Python program that iterated through and found numbers that match a given condition. But it is not clear what the program stop condition might be. I understand that this problem should have a simpler solution than going through all possible numbers that match the problem condition.
I don't know where to start solving the problem. Can you give me a hint on which direction to look for a solution?
So you want $x_1 \equiv 0 \mod 1$, $x_1x_2 \equiv 1 \mod 2$, $x_1x_2x_3 \equiv 2 \mod 3$ etc. Notice that each digit you add to the number will not affect the previous digits - $x_1x_2\cdots x_{n-1}$ still satisfies the previous conditions, even after you add $x_n$. Therefore, we can start from a 1-digit hexadecimal number and "build up".
Other than that I am not sure if there's any shortcut/approach. Here's my code that solves the problem for every b.The code used is implementing a BFS - it attempts to generate all the cases in ascending order. This is useful if we want to find, let's say, all the cases. However, a better approach here is to use DFS - which attempts to generate the largest possible number from a specific configuration. For example, from
Fit can generateFFEB.... This is a more efficient approach for this problem, as it attempts to generate the largest (longest) number.I've also implemented a better check condition. Notice that $x_1x_2\cdots x_n = 16(x_1x_2\cdots x_{n-1}) + x_n \equiv n-1 \mod n$. Now since we know that $0 \leq x_n \leq 15$, we can check if $16(x_1x_2\cdots x_{n-1}) \equiv n-1-t \mod n$ for some $t$ between 0 and 15.
Code: https://repl.it/repls/YellowFrigidComputer