Every number can be represented using an infinitely long remainder sequence. For example, if we take the number 7, and perform 7mod2
, then 7mod3
, then 7mod4
, and so on, we get 1,1,3,2,1,0,7,7,7,7,....
.
However, we need the shortest possible remainder subsequence that can still be used to distinguish it from all lower numbers. Using 7 again, [1,1,3]
is the shortest subsequence, because all of the previous subsequences don't start with [1,1,3]
:
0: 0,0,0,0...
1: 1,1,1,1...
2: 0,2,2,2...
3: 1,0,3,3...
4: 0,1,0,4...
5: 1,2,1,0...
6: 0,0,2,1...
Note that [1,1]
doesn't work to represent 7, because it can also be used to represent 1. However, you should output [1]
with an input of 1.
Input/Output
Your input is a non-negative integer. You must output a sequence or list of the minimal-length sequence of remainders as defined above.
Test cases:
0: 0
1: 1
2: 0,2
3: 1,0
4: 0,1
5: 1,2
6: 0,0,2
7: 1,1,3
8: 0,2,0
9: 1,0,1
10: 0,1,2
11: 1,2,3
12: 0,0,0,2
30: 0,0,2,0
42: 0,0,2,2
59: 1,2,3,4
60: 0,0,0,0,0,4
257: 1,2,1,2,5,5
566: 0,2,2,1,2,6,6
1000: 0,1,0,0,4,6,0,1
9998: 0,2,2,3,2,2,6,8,8,10
9999: 1,0,3,4,3,3,7,0,9,0
Here are the first 10,000 sequences, in case you are interested (the line numbers are off by 1).
This is a code-golf, so make it as short as you can in your favorite language. Fake bonus points for any answers that are fast!