Skip to main content
3 of 3
Commonmark migration

Generate the minimal remainder sequence

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 , so make it as short as you can in your favorite language. Fake bonus points for any answers that are fast!

Nathan Merrill
  • 14.5k
  • 3
  • 48
  • 128