Cada número se puede representar usando una secuencia de resto infinitamente larga. Por ejemplo, si tomamos el número 7 y realizamos 7mod2, entonces 7mod3, luego 7mod4, y así sucesivamente, obtenemos 1,1,3,2,1,0,7,7,7,7,.....

Sin embargo, necesitamos la subsecuencia remanente más corta posible que aún pueda usarse para distinguirla de todos los números más bajos. Usar 7 nuevamente, [1,1,3]es la subsecuencia más corta, porque todas las subsecuencias anteriores no comienzan con [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...

Tenga en cuenta que [1,1] no funciona para representar 7, porque también se puede usar para representar 1. Sin embargo, debe generar [1]una entrada de 1.

De entrada y salida

Su entrada es un entero no negativo. Debe generar una secuencia o lista de la secuencia de restos de longitud mínima como se definió anteriormente.

Casos de prueba:

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

Aquí están las primeras 10,000 secuencias , en caso de que esté interesado (los números de línea están apagados en 1).

Este es un código de golf , así que hágalo lo más corto posible en su idioma favorito. ¡Puntos de bonificación falsos por cualquier respuesta que sea rápida!

Mathematica, 60 53 bytes

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

Algo rápido (maneja 10000 en ~ 0.1 segundos, pero probablemente se quedará sin memoria para 100000).

El código arroja un error pero calcula el resultado correctamente.

Explicación

Hemos descubierto anteriormente en el chat que los divisores necesarios siempre se pueden determinar como la lista más corta {1, 2, ..., n}cuyo múltiplo menos común excede la entrada. Un breve argumento de por qué es eso: si el LCM es menor que la entrada, restar el LCM de la entrada dejaría todos los divisores sin cambios, por lo que la representación no es única. Sin embargo, para todas las entradas menores que el MCM, los restos serán únicos, de lo contrario la diferencia entre dos números con restos iguales sería un múltiplo más pequeño de todos los divisores.

En cuanto al código ... como siempre, el orden de lectura de Mathematica es un poco divertido.

Range[#+2]

Esto nos da una lista [1, 2, 3, ..., n+2]de entrada n. El +2es para asegurarse de que funciona correctamente para 0y 1.

2~Range~#&/@...

Mapa 2~Range~#(azúcar sintáctico para Range[2,#]) sobre esta lista, así obtenemos

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

Estas son listas de divisores candidatos (por supuesto, en general, eso es mucho más de lo que necesitaremos). Ahora encontramos el primero de ellos cuyo LCM excede la entrada con:

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

Más sintaxis: x_es un patrón que coincide con cualquiera de las listas y lo llama x. El /;adjunta una condición a ese patrón. Esta condición es LCM@@x>#donde @@ aplica la función a la lista, es decir, LCM@@{1,2,3}significa LCM[1,2,3].

Finalmente, simplemente obtenemos todos los restos, haciendo uso del hecho de que Modes Listable, es decir, se asigna automáticamente sobre una lista si uno de los argumentos es una lista (o si ambos son listas de la misma longitud):

#~Mod~...

Jalea , 14 bytes

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

Esto utiliza el hecho de que la solución (si la hay) de un sistema de congruencias lineales es un módulo único del MCM de los módulos. Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

‘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.

MATL , 24 bytes

Gracias a @nimi por señalar un error en una versión anterior de esta respuesta (ahora corregida)

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

Esto se queda sin memoria en el compilador en línea para los dos casos de prueba más grandes (pero funciona en una computadora con 4 GB de RAM).

Pruébalo en línea!

Explicación

Esto aplica la definición de manera directa. Para la entrada nse calcula una matriz 2D que contiene mod(p,q)con pde 0a ny qdesde 1a n+1. Cada puna es una columna y cada quna es una fila. Por ejemplo, con entrada n=7esta matriz es

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

Ahora la última columna, que contiene los restos de n, es un elemento comparado con cada columna de esta matriz. Esto produce

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

donde 1indica igualdad. La última columna es obviamente igual a sí misma y, por lo tanto, contiene todas. Necesitamos encontrar la columna que tenga el mayor número de iniciales , que no sea la última columna, y tomar nota de ese número de iniciales m. (En este caso, es la segunda columna, que contiene las m=3iniciales). Para este fin, calculamos el producto acumulativo de cada columna:

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

entonces la suma de cada columna

1 3 1 2 1 2 1 8

y luego ordenar de manera no creciente y tomar el segundo valor, que es 3. Este es el deseado m, que indica cuántos residuos tenemos que recoger.

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

Jalea , 13 11 bytes

r¬µ%€R‘$ḟ/Ṫ

Esto no ganará puntos de velocidad de brownie ... ¡ Pruébelo en línea! o verificar los casos de prueba más pequeños .

Cómo funciona

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.

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)

Requiere Python 3.5 y sympy ( python3 -m pip install --user sympy). Gracias a @Dennis para notificarme que Python 3.5 permite el *ltruco con argumentos predeterminados.

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

Un programa completo @Dennis ahorró 4 bytes al mejorar la forma en que se maneja el cero.

Haskell, 66 60 51 50 bytes

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

Ejemplo de uso: f 42-> [0,0,2,2]. Es el algoritmo descrito en la respuesta de @Martin Büttner .

Conservaré la versión anterior como referencia, porque es bastante rápida:

Haskell, 51 bytes

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

Se necesitan 0.03s f (10^100)en mi laptop de cinco años.

Editar: @xnor encontró un byte para guardar. ¡Gracias!

Pyth, 51 bytes 66 bytes

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

¡Pruébalo!

Mucho una versión más alta velocidad de bytes 39 (no funciona para 0-2):

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

Parece funcionar para números absurdamente grandes como 10 ^{10 3}

Nota: esta respuesta no funciona para 0, 1 y 2. ¡Solucionado!

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)

Esto acumula recursivamente la respuesta hasta que el LCM excede el número original. El GCD también se calcula de forma recursiva, por supuesto.

Editar: Guardado 4 bytes gracias a @ user81655.

Ruby, 52 bytes

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

Esta solución verifica cada posible a mpartir de 2, que es el resto que hace que la secuencia sea única. Lo que hace que el último sea múnico no es el resto en sí, sino que mes el último miembro del rango más pequeño (2..m)donde el mínimo común múltiplo (LCM) de ese rango es mayor que n. Esto se debe al Teorema del resto chino, donde para determinar de forma única qué número nes con un número de restos, el MCM de esos restos debe ser mayor que n(si selecciona nde (1..n); si selecciona ndea..b , el LCM solo necesita ser mayor que b-a)

Nota: pongoa<<n%m al final del código porque until n<t=t.lcm(m+=1)los cortocircuitos antes ahan recibido el último elemento para hacerlo único.

Si alguien tiene alguna sugerencia de golf, hágamelo saber en los comentarios o en el chat PPCG .

No golfista:

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

Julia, 36 33 bytes

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

Pruébalo en línea!

Python 3.5, 194 181 169 152 149 146 bytes:

(¡ Gracias a @ Sherlock9 por 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)

Funciona perfectamente y también es bastante rápido. Calculando para la secuencia mínima restante de 100000salidas [0, 1, 0, 0, 4, 5, 0, 1, 0, 10, 4, 4]y tomó solo unos 3 segundos. Incluso fue capaz de calcular la secuencia para la entrada1000000 (1 millón), la salida [0, 1, 0, 0, 4, 1, 0, 1, 0, 1, 4, 1, 8, 10, 0, 9]y tardó unos 60 segundos.

Explicación

Básicamente, lo que hace esta función es, en primer lugar, crear una lista, ycon todos j mod idonde jestá cada número entero en el rango 0=>7(incluyendo 7) y ies cada número entero en el rango 0=>100. Luego, el programa entra en un whilebucle infinito y compara la misma cantidad de contenido de cada sublista dentro de las sublistas primera a última de y( y[:-1:]) con la misma cantidad de elementos en la última sublista ( y[-1]) de la lista y. Cuando la sublista y[-1]es diferente a cualquier otra sublista, el bucle se separa y se devuelve la secuencia mínima restante correcta.

Por ejemplo, si la entrada es 3, ysería:

[[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]]

Luego, cuando entra en el ciclo while, compara cada sublista en la lista y[:-1:]con el mismo número de elementos en la sublista y[-1]. Por ejemplo, primero compararía [[0],[1],[0]]y [1]. Como la última sublista está en el resto de y, continuaría y luego compararía [[0,0],[0,1],[0,2]]y [1,0]. Dado [1,0]que ahora NO está en el resto de y ese orden específico , esa es la secuencia mínima de recordatorio y, por [1,0]lo tanto, se devolverá correctamente.

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);}

Compila (con advertencias) usando gcc -std=c89. Toma un solo número en stdin y genera la secuencia de residuos separados por espacios en stdout.

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);}

Compilar con gcc. Pruébelo en línea: n = 59 , n = 0 .