Generate the minimal remainder sequence

Question

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!

Answer 1

Mathematica, 60 53 bytes

#~Mod~FirstCase[2~Range~#&/@Range[#+2],x_/;LCM@@x>#]&

Somewhat fast (it handles 10000 in ~0.1 second, but will likely run out of memory for 100000).

The code throws an error but computes the result correctly.

Explanation

We've found earlier in chat that the required divisors can always be determined as the shortest list {1, 2, ..., n} whose least common multiple exceeds the input. A short argument for why that is: if the LCM is less than the input, then subtracting the LCM from the input would leave all the divisors unchanged, so the representation is not unique. However, for all inputs less than the LCM, the remainders will be unique, otherwise the difference between two numbers with equal remainders would be a smaller multiple of all divisors.

As for the code... as usual the reading order of golfed Mathematica is a bit funny.

Range[#+2]

This gets us a list [1, 2, 3, ..., n+2] for input n. The +2 is to ensure that it works correctly for 0 and 1.

2~Range~#&/@...

Map 2~Range~# (syntactic sugar for Range[2,#]) over this list, so we get

{{}, {2}, {2,3}, ..., {2,3,...,n+2}}

These are candidate divisor lists (of course in general that's a lot more than we'll need). Now we find the first one of them whose LCM exceeds the input with:

FirstCase[...,x_/;LCM@@x>#]

More syntax: x_ is a pattern which matches any of the lists and calls it x. The /; attaches a condition to that pattern. This condition is LCM@@x># where @@ applies the function to the list, i.e. LCM@@{1,2,3} means LCM[1,2,3].

Finally we simply get all the remainders, making use of the fact that Mod is Listable, i.e. it automatically maps over a list if one of the arguments is a list (or if both of them are lists of the same length):

#~Mod~...

Answer 2

MATL, 24 bytes

Thanks to @nimi for pointing out an error in a previous version of this answer (now corrected)

Q:qtQ!\t0Z)tb=YpsSP2):Q)

This runs out of memory in the online compiler for the two largest test cases (but it works on a computer with 4 GB RAM).

Try it online!

Explanation

This applies the definition in a straightforward manner. For input n it computes a 2D array containing mod(p,q) with p from 0 to n and q from 1 to n+1. Each p is a column, and each q is a row. For example, with input n=7 this array is

0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1
0 1 2 0 1 2 0 1
0 1 2 3 0 1 2 3
0 1 2 3 4 0 1 2
0 1 2 3 4 5 0 1
0 1 2 3 4 5 6 0
0 1 2 3 4 5 6 7

Now the last column, which contains the remainders of n, is element-wise compared with each column of this array. This yields

1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1
0 1 0 0 1 0 0 1
0 0 0 1 0 0 0 1
0 0 1 0 0 0 0 1
0 1 0 0 0 0 0 1
1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1

where 1 indicates equality. The last column is obviously equal to itself and thus contains all ones. We need to find the column that has the largest number of initial ones, other than the last column, and take note of that number of initial ones, m. (In this case it's the second column, which contains m=3 initial ones). To this end, we compute the cumulative product of each column:

1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1
0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1

then the sum of each column

1 3 1 2 1 2 1 8

and then sort non-increasingly and take the second value, which is 3. This is the desired m, which indicates how many remainders we need to pick.

Q:q    % take input n implicitly. Generare row array [0 1 ... n]
tQ!    % duplicate. Transform into column array [1; 2; ...; n-1]
\      % modulo, element-wise with broadcast. Gives the 2D array
t0Z)   % duplicate. Take last column
tb     % duplicate, bubble up
=      % test for equality, element-wise with broadcast
Yp     % cumumative product of each column
s      % sum of each column. This gives the number of initial coincidences
SP2)   % sort in decreasing order and take second value: m
:Q     % generate range [2 3 ... m+1]
)      % apply as index into array of remainders of n. Implicitly display

Answer 3

Jelly, 14 bytes

‘Ræl\>iṠ2»2r⁸%

This uses the fact a the solution (if any) of a system of linear congruences is unique modulo the LCM of the moduli. Try it online! or verify all test cases.

How it works

‘Ræl\>iṠ2»2r⁸%  Main link. Argument: n

‘               Increment; yield n+1.
 R              Range; yield [1, ..., n+1].
  æl\           Cumulatively reduce by LCM.
                This yields [LCM(1), ..., LCM(1, ..., n+1)].
     >          Compare all LCMs with n.
      iṠ        Find the first index of sign(n).
                This yields the first m such that LCM(2, ..., m) > n if n > 0, and
                0 if n == 0.
        2»      Take the maximum of the previous result and 2, mapping 0 to 2.
          2r    Yield the range from 2 up to and including the maximum.
            ⁸%  Compute n modulo each integer in that range.

Answer 4

Jelly, 13 11 bytes

r¬µ%€R‘$ḟ/Ṫ

This won't win any velocity brownie points... Try it online! or verify the smaller test cases.

How it works

r¬µ%€R‘$ḟ/Ṫ  Main link. Argument: n

r¬           Range from n to (not n).
             This yields [n, ..., 0] if n > 0 and [0, 1] otherwise.

  µ          Begin a new, monadic chain. Argument: A (range)

       $     Combine the previous two links into a monadic chain:
     R         Range; turn each k in A into [1, ..., k] or [] if k == 0.
      ‘        Increment to map k to [2, ..., k+1].
   %€        Take each k in A modulo all the integers in the 2D list to the right.
        ḟ/   Reduce by filter-not; sequentially remove all remainder sequences of
             n-1, ..., (not n) from the remainder sequences of n.
          Ṫ  Tail; take the last remainder sequence.
             This gives the shortest sequence for descending A and the longest one
             (i.e., [0]) for ascending A.

Answer 5

Haskell, 66 60 51 50 bytes

f i=mod i<$>[2..2+sum[1|l<-scanl1 lcm[2..i],l<=i]]

Usage example: f 42-> [0,0,2,2]. It's the algorithm described in @Martin Büttner's answer.

I'll keep the previous version for reference, because it's pretty fast:

Haskell, 51 bytes

f i=mod i<$>[[2..x]|x<-[2..],foldl1 lcm[2..x]>i]!!0

It takes 0.03s for f (10^100) on my five year old laptop.

Edit: @xnor found a byte to save. Thanks!

Answer 6

Python 3.5, 117 95 78 bytes

import sympy
r=lambda n,m=2,M=1,*l:M>n and l or r(n,m+1,sympy.lcm(m,M),*l,n%m)

Requires Python 3.5 and sympy (python3 -m pip install --user sympy). Credit to @Dennis to notify me that Python 3.5 allows the *l trick with default arguments.

Answer 7

Python 2, 73 70 69 65 bytes

i=l=1
n=input()
while l<=n|1:
 i+=1;a=l;print n%i
 while l%i:l+=a

A full program. @Dennis saved 4 bytes by improving the way zero is handled.

Answer 8

Pyth, 51 Bytes 66 Bytes

IqQZ[Z).q)IqQ1[1))IqQ2,0 1))FdhhQJu/*GHiGHtUd1I>JQVQ aY%QhN)<tYd.q

Try it out!

Much higher speed 39 byte version (does not work for 0-2):

FdhhQJu/*GHiGHtUd1I>JQVtd aY%QhN)<tYd.q

It seems to work for absurdly large numbers like 10¹⁰³

Note: this answer does not work for 0, 1, and 2. Fixed!

Answer 9

JavaScript (ES6), 81 77 bytes

f=(n,r=[n%2],l=i=2,g=(j,k)=>j?g(k%j,j):k)=>l>n?r:f(n,[...r,n%++i],i/g(i,l)*l)

This recursively builds up the answer until the LCM exceeds the original number. The GCD is also calculated recursively, of course.

Edit: Saved 4 bytes thanks to @user81655.

Answer 10

Julia, 36 33 bytes

\(n,k=2)=lcm(2:k)>n?n%(2:k):n\-~k

Try it online!

Answer 11

Ruby, 52 bytes

->n{m=t=1;a=[];(a<<n%m)until n<t=t.lcm(m+=1);a<<n%m}

This solution checks every possible m starting from 2 that be the remainder that makes the sequence unique. What makes the last m unique is not the remainder itself, but that the m is the last member of the smallest range (2..m) where the least common multiple (LCM) of that range is greater than n. This is due to the Chinese Remainder Theorem, where to uniquely determine what number n is with a number of remainders, the LCM of those remainders must be greater than n (if selecting n from (1..n); if selecting n from a..b, the LCM needs only be greater than b-a)

Note: I put a<<n%m at the end of the code because until n<t=t.lcm(m+=1) short-circuits before a has received the last element to make it unique.

If anyone has any golfing suggestions, please let me know in the comments or in PPCG chat.

Ungolfing:

def remainder_sequence(num)
  # starting with 1, as the statements in the until loop immediately increments divisor
  divisor = 1
  # starts with 1 instead of 2, as the statements in the until loop
  # immediately change product to a new lcm
  product = 1
  remainders = []

  # this increments divisor first then checks the lcm of product and divisor
  # before checking if num is less than this lcm
  until num < (product = product.lcm(divisor = divisor + 1))
    remainders << num % divisor
  end

  # until always short circuits before the last element is entered
  # so this enters the last element and returns
  return remainders << num % divisor
end

Answer 12

Python 3.5, 194 181 169 152 149 146 bytes:

(Thanks to @Sherlock9 for 2 bytes!)

def r(o,c=0):
 y=[[j%i for i in range(2,100)]for j in range(o+1)]
 while 1:
  c+=1;z=y[-1][:c]
  if z not in[f[:c]for f in y[:-1]]:break
 print(z)

Works perfectly, and is also pretty quick. Calculating for the minimal remainder sequence of 100000 outputs [0, 1, 0, 0, 4, 5, 0, 1, 0, 10, 4, 4] and took only about 3 seconds. It was even able to calculate the sequence for the input 1000000 (1 million), output [0, 1, 0, 0, 4, 1, 0, 1, 0, 1, 4, 1, 8, 10, 0, 9], and took about 60 seconds.

Explanation

Basically what this function does is firstly create a list, y, with all j mod i where j is every integer in the range 0=>7 (including 7) and i is every integer in the range 0=>100. The program then goes into an infinite while loop and compares the same number of contents of each sublist within the first through second-to-last sublists of y (y[:-1:]) with the same number of items in the last sublist (y[-1]) of list y. When sublist y[-1] is different than any other sublist, the loop is broken out of, and the correct minimal remainder sequence is returned.

For instance, if the input is 3, y would be:

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], [1, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]]

Then, when it enters into the while loop, it compares each sublist in list y[:-1:] with the same number of items in sublist y[-1]. For example, it would first compare [[0],[1],[0]] and [1]. Since the last sublist is in the rest of y, it would continue on and then compare [[0,0],[0,1],[0,2]] and [1,0]. Since [1,0] is now NOT in the rest of y in that specific order, that is the minimal reminder sequence, and therefore, [1,0] would be correctly returned.

Answer 13

C89, 105 bytes

g(a,b){return b?g(b,a%b):a;}main(n,m,M){scanf("%d",&n);for(m=M=1;(M=++m*M/g(m,M))<=n;)printf("%d ",n%m);}

Compiles (with warnings) using gcc -std=c89. Takes a single number on stdin, and outputs the sequence of remainders separated by spaces on stdout.

Answer 14

C, 89 bytes

a,i=2;main(l,n){for(n=atoi(gets(n))?:!puts(n);n/l;printf("%d ",n%i++))for(a=l;l%i;l+=a);}

Compile with gcc. Try it online: n=59, n=0.