Cada número pode ser representado usando uma sequência restante infinitamente longa. Por exemplo, se pegarmos o número 7 e executar 7mod2, então 7mod3, então 7mod4e assim por diante, obteremos 1,1,3,2,1,0,7,7,7,7,.....

No entanto, precisamos da subsequência restante mais curta possível que ainda possa ser usada para distingui-la de todos os números inferiores. Usar 7 novamente, [1,1,3]é a subsequência mais curta, porque todas as subsequências anteriores não começam com [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...

Observe que [1,1] não funciona para representar 7, porque também pode ser usado para representar 1. No entanto, você deve produzir [1]com uma entrada 1.

Entrada / Saída

Sua entrada é um número inteiro não negativo. Você deve produzir uma sequência ou lista da sequência de tamanho mínimo dos restantes, conforme definido acima.

Casos de teste:

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

Aqui estão as primeiras 10.000 seqüências , caso você esteja interessado (os números das linhas são 1 em menos).

Como é um código de golfe , faça com que seja o mais curto possível no seu idioma favorito. Pontos de bônus falsos para respostas rápidas!

Mathematica, 60 53 bytes

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

Um pouco rápido (ele lida com 10000 em ~ 0,1 segundo, mas provavelmente ficará sem memória para 100000).

O código gera um erro, mas calcula o resultado corretamente.

Explicação

Descobrimos anteriormente no bate-papo que os divisores necessários sempre podem ser determinados como a lista mais curta {1, 2, ..., n}cujo múltiplo menos comum excede a entrada. Um breve argumento sobre o motivo: se o LCM for menor que a entrada, subtrair o LCM da entrada deixaria todos os divisores inalterados, para que a representação não seja exclusiva. No entanto, para todas as entradas menores que o LCM, os restantes serão únicos; caso contrário, a diferença entre dois números com restos iguais seria um múltiplo menor de todos os divisores.

Quanto ao código ... como sempre, a ordem de leitura do Mathematica golfado é um pouco engraçada.

Range[#+2]

Isso nos fornece uma lista [1, 2, 3, ..., n+2]para entrada n. O +2é garantir que ele funcione corretamente para 0e 1.

2~Range~#&/@...

Mapeie 2~Range~#(açúcar sintático para Range[2,#]) sobre esta lista, para obter

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

Essas são listas de divisores candidatos (é claro que em geral isso é muito mais do que precisamos). Agora encontramos o primeiro deles cujo LCM excede a entrada com:

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

Mais sintaxe: x_é um padrão que corresponde a qualquer uma das listas e o chama x. Ele /;anexa uma condição a esse padrão. Esta condição é LCM@@x>#onde @@ aplica a função à lista, ou seja, LCM@@{1,2,3}significa LCM[1,2,3].

Por fim, simplesmente obtemos todos os demais, usando o fato de que Modé Listable, ou seja, ele mapeia automaticamente uma lista se um dos argumentos for uma lista (ou se os dois forem listas do mesmo tamanho):

#~Mod~...

Gelatina , 14 bytes

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

Isso usa o fato de que a solução (se houver) de um sistema de congruências lineares é o único módulo do LCM dos módulos. Experimente online! ou verifique todos os casos de teste .

Como 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

Agradecemos a @nimi por apontar um erro em uma versão anterior desta resposta (agora corrigida)

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

Isso fica sem memória no compilador online para os dois maiores casos de teste (mas funciona em um computador com 4 GB de RAM).

Experimente online!

Explicação

Isso aplica a definição de maneira direta. Para entrada nque calcula uma matriz 2D contendo mod(p,q)com pde 0para ne qa partir de 1a n+1. Cada pum é uma coluna e cada qum é uma linha. Por exemplo, com entrada, n=7essa matriz é

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

Agora, a última coluna, que contém o restante de n, é comparada a cada elemento com cada coluna dessa matriz. Isso gera

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

onde 1indica igualdade. A última coluna é obviamente igual a si mesma e, portanto, contém todas. Precisamos encontrar a coluna que tem o maior número de iniciais , além da última coluna, e anotar esse número de iniciais m. (Nesse caso, é a segunda coluna, que contém as m=3iniciais). Para esse fim, calculamos o produto cumulativo de cada coluna:

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

então a soma de cada coluna

1 3 1 2 1 2 1 8

e depois classifique de forma não crescente e pegue o segundo valor, que é 3. Este é o desejado m, que indica quantos restos precisamos escolher.

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

Geléia , 13 11 bytes

r¬µ%€R‘$ḟ/Ṫ

Isso não ganhará nenhum ponto de velocidade brownie ... Experimente online! ou verifique os casos de teste menores .

Como 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)

Requer Python 3.5 e sympy ( python3 -m pip install --user sympy). Agradecemos a @Dennis que me notifique que o Python 3.5 permite o *ltruque com argumentos padrão.

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

Um programa completo. O @Dennis salvou 4 bytes, melhorando a maneira como o zero é tratado.

Haskell, 66 60 51 50 bytes

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

Exemplo de uso: f 42-> [0,0,2,2]. É o algoritmo descrito na resposta de @Martin Büttner .

Manterei a versão anterior para referência, porque é bem rápida:

Haskell, 51 bytes

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

Leva 0,03s para o f (10^100)meu laptop de cinco anos.

Edit: @xnor encontrou um byte para salvar. Obrigado!

Pyth, 51 Bytes 66 Bytes

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

Experimente!

Versão com 39 bytes de velocidade muito mais alta (não funciona para 0-2):

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

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

Nota: esta resposta não funciona para 0, 1 e 2. Corrigido!

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)

Isso recursivamente cria a resposta até que o LCM exceda o número original. O GCD também é calculado recursivamente, é claro.

Editar: salvou 4 bytes graças a @ user81655.

Ruby, 52 bytes

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

Esta solução verifica todas as possíveis mpartidas a partir de 2 e o restante que torna a sequência única. O que torna o último mexclusivo não é o restante em si, mas mo último membro do menor intervalo em (2..m)que o mínimo múltiplo comum (LCM) desse intervalo é maior que n. Isso ocorre devido ao Teorema do Restante Chinês, onde para determinar exclusivamente qual né o número com um número de remanescentes, o LCM desses remanescentes deve ser maior que n(se selecionar nde (1..n); se selecionar nde a..b, o LCM precisa ser maior que b-a)

Nota: Coloquei a<<n%mno final do código porque os until n<t=t.lcm(m+=1)curtos-circuitos anteriores areceberam o último elemento para torná-lo único.

Se alguém tiver alguma sugestão de golfe, informe-me nos comentários ou no chat do PPCG .

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

Julia, 36 33 bytes

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

Experimente online!

Python 3,5, 194 181 169 152 149 146 bytes:

( Obrigado 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 perfeitamente e também é bastante rápido. O cálculo da sequência mínima restante de 100000saídas [0, 1, 0, 0, 4, 5, 0, 1, 0, 10, 4, 4]e levou apenas cerca de 3 segundos. Foi capaz de calcular a sequência para a entrada 1000000(1 milhão), a saída [0, 1, 0, 0, 4, 1, 0, 1, 0, 1, 4, 1, 8, 10, 0, 9]e levou cerca de 60 segundos.

Explicação

Basicamente, o que essa função faz é primeiro criar uma lista, ycom tudo j mod ionde jestá todo número inteiro no intervalo 0=>7(incluindo 7) e itodo número inteiro no intervalo 0=>100. O programa entra em um whileloop infinito e compara o mesmo número de conteúdos de cada sublist na primeira até a penúltima sublista de y( y[:-1:]) com o mesmo número de itens na última sublist ( y[-1]) da lista y. Quando sublist y[-1]é diferente de qualquer outra sublist, o loop é interrompido e a sequência mínima restante correta é retornada.

Por exemplo, se a entrada for 3, yseria:

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

Então, quando entra no loop while, compara cada sub-lista na lista y[:-1:]com o mesmo número de itens na sub-lista y[-1]. Por exemplo, ele primeiro compararia [[0],[1],[0]]e [1]. Como a última sub-lista está no restante y, ela continuaria e depois compararia [[0,0],[0,1],[0,2]]e [1,0]. Como [1,0]agora NÃO está no restante y nessa ordem específica , essa é a sequência mínima de lembrete e, portanto, [1,0]seria retornada corretamente.

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 (com avisos) usando gcc -std=c89. Pega um número único em stdin e gera a sequência de restos separados por espaços em 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);}

Compile com o gcc. Experimente online: n = 59 , n = 0 .