Chaque nombre peut être représenté en utilisant une séquence de reste infiniment longue. Par exemple, si nous prenons le nombre 7 et que nous effectuons 7mod2, alors 7mod3, alors 7mod4, et ainsi de suite, nous obtenons 1,1,3,2,1,0,7,7,7,7,.....

Cependant, nous avons besoin de la sous- séquence de reste la plus courte possible qui peut encore être utilisée pour la distinguer de tous les nombres inférieurs. Utiliser à nouveau 7 [1,1,3]est la sous-séquence la plus courte, car toutes les sous-séquences précédentes ne commencent pas par [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...

Notez que [1,1] cela ne fonctionne pas pour représenter 7, car il peut également être utilisé pour représenter 1. Cependant, vous devez sortir [1]avec une entrée de 1.

Entrée sortie

Votre entrée est un entier non négatif. Vous devez générer une séquence ou une liste de la séquence de reste de longueur minimale définie ci-dessus.

Cas de test:

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

Voici les 10 000 premières séquences , au cas où vous seriez intéressé (les numéros de ligne sont décalés de 1).

Il s'agit d'un code-golf , alors faites-le aussi court que possible dans votre langue préférée. Faux points bonus pour toutes les réponses rapides!

Mathematica, 60 53 octets

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

Un peu rapide (il gère 10000 en ~ 0,1 seconde, mais manquera probablement de mémoire pour 100000).

Le code renvoie une erreur mais calcule correctement le résultat.

Explication

Nous avons constaté plus tôt dans le chat que les diviseurs requis peuvent toujours être déterminés comme la liste la plus courte {1, 2, ..., n}dont le multiple le plus commun dépasse l'entrée. Un court argument pour expliquer pourquoi: si le LCM est inférieur à l'entrée, alors la soustraction du LCM de l'entrée laisserait tous les diviseurs inchangés, de sorte que la représentation n'est pas unique. Cependant, pour toutes les entrées inférieures au LCM, les restes seront uniques, sinon la différence entre deux nombres avec des restes égaux serait un plus petit multiple de tous les diviseurs.

Quant au code ... comme d'habitude, l'ordre de lecture de Mathematica au golf est un peu drôle.

Range[#+2]

Cela nous donne une liste [1, 2, 3, ..., n+2]d'entrée n. Il +2s'agit de s'assurer qu'il fonctionne correctement pour 0et 1.

2~Range~#&/@...

Carte 2~Range~#(sucre syntaxique pour Range[2,#]) sur cette liste, nous obtenons donc

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

Ce sont des listes de diviseurs candidats (bien sûr, en général, c'est beaucoup plus que ce dont nous aurons besoin). Maintenant, nous trouvons le premier d'entre eux dont le LCM dépasse l'entrée avec:

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

Plus de syntaxe: x_est un modèle qui correspond à l'une des listes et l'appelle x. Le /;attache une condition à ce modèle. Cette condition est l' LCM@@x>#endroit où @@ s'applique la fonction à la liste, c'est-à-dire les LCM@@{1,2,3}moyens LCM[1,2,3].

Enfin, nous obtenons simplement tous les restes, en utilisant le fait que Modc'est-à Listable-dire qu'il mappe automatiquement sur une liste si l'un des arguments est une liste (ou si les deux sont des listes de la même longueur):

#~Mod~...

Gelée , 14 octets

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

Ceci utilise le fait que la solution (le cas échéant) d'un système de congruences linéaires est unique modulo le LCM des modules. Essayez-le en ligne! ou vérifiez tous les cas de test .

Comment ça marche

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

Merci à @nimi d'avoir signalé une erreur dans une version précédente de cette réponse (maintenant corrigée)

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

Cela manque de mémoire dans le compilateur en ligne pour les deux plus grands cas de test (mais cela fonctionne sur un ordinateur avec 4 Go de RAM).

Essayez-le en ligne!

Explication

Cela applique la définition de manière simple. Pour l'entrée, nil calcule un tableau 2D contenant mod(p,q)avec pde 0à net qde 1à n+1. Chacun pest une colonne et chacun qest une ligne. Par exemple, avec l'entrée, n=7ce tableau est

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

Maintenant, la dernière colonne, qui contient les restes de n, est par élément par rapport à chaque colonne de ce tableau. Cela donne

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

où 1indique l'égalité. La dernière colonne est évidemment égale à elle-même et contient donc toutes celles-ci. Nous devons trouver la colonne qui a le plus grand nombre de initiaux , autres que la dernière colonne, et de prendre note de ce nombre de rapports initiaux, m. (Dans ce cas, c'est la deuxième colonne, qui contient les m=3initiales). À cette fin, nous calculons le produit cumulatif de chaque colonne:

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

puis la somme de chaque colonne

1 3 1 2 1 2 1 8

puis triez de manière non croissante et prenez la deuxième valeur, qui est 3. C'est le souhait m, qui indique combien de restes nous devons ramasser.

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ée , 13 11 octets

r¬µ%€R‘$ḟ/Ṫ

Cela ne gagnera pas de points brownie de vitesse ... Essayez-le en ligne! ou vérifiez les cas de test plus petits .

Comment ça marche

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 octets

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)

Nécessite Python 3.5 et sympy ( python3 -m pip install --user sympy). Nous remercions @Dennis de m'avoir informé que Python 3.5 autorise l' *lastuce avec des arguments par défaut.

Python 2, 73 70 69 65 octets

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

Un programme complet. @Dennis a économisé 4 octets en améliorant la façon dont le zéro est traité.

Haskell, 66 60 51 50 octets

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

Exemple d'utilisation: f 42-> [0,0,2,2]. C'est l'algorithme décrit dans la réponse de @Martin Büttner .

Je garderai la version précédente pour référence, car elle est assez rapide:

Haskell, 51 octets

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

Cela prend 0,03s pour f (10^100)mon portable de cinq ans.

Modifier: @xnor a trouvé un octet à enregistrer. Merci!

Pyth, 51 octets 66 octets

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

Essaye le!

Version 39 octets à vitesse beaucoup plus élevée (ne fonctionne pas pour 0-2):

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

Cela semble fonctionner pour des nombres absurdement grands comme 10 ^{10 3}

Remarque: cette réponse ne fonctionne pas pour 0, 1 et 2. Corrigé!

JavaScript (ES6), 81 77 octets

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)

Cela construit récursivement la réponse jusqu'à ce que le LCM dépasse le nombre d'origine. Le GCD est également calculé récursivement, bien sûr.

Edit: 4 octets enregistrés grâce à @ user81655.

Rubis, 52 octets

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

Cette solution vérifie tous les possibles à mpartir de 2, le reste qui rend la séquence unique. Ce qui rend le dernier munique n'est pas le reste lui-même, mais le fait qu'il mest le dernier membre de la plus petite plage (2..m)où le multiple le moins commun (LCM) de cette plage est supérieur à n. Cela est dû au théorème des restes chinois, où pour déterminer de manière unique quel nombre nest avec un certain nombre de restes, le LCM de ces restes doit être supérieur à n(si vous sélectionnez nde (1..n); si vous sélectionnez nde a..b, le LCM doit uniquement être supérieur à b-a)

Remarque: je mets a<<n%mà la fin du code car les until n<t=t.lcm(m+=1)courts-circuits avant aont reçu le dernier élément pour le rendre unique.

Si quelqu'un a des suggestions de golf, faites-le moi savoir dans les commentaires ou dans le chat 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 octets

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

Essayez-le en ligne!

Python 3.5, 194 181 181 169 152 149 146 octets:

( Merci à @ Sherlock9 pour 2 octets! )

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)

Fonctionne parfaitement et est également assez rapide. Le calcul de la séquence restante minimale de 100000sorties [0, 1, 0, 0, 4, 5, 0, 1, 0, 10, 4, 4]et n'a pris que 3 secondes environ. Il a même pu calculer la séquence de l'entrée 1000000(1 million), de la sortie [0, 1, 0, 0, 4, 1, 0, 1, 0, 1, 4, 1, 8, 10, 0, 9]et a pris environ 60 secondes.

Explication

Fondamentalement, cette fonction crée d'abord une liste, yavec tout j mod ioù jest chaque entier de la plage 0=>7(y compris 7) et ichaque entier de la plage 0=>100. Le programme passe ensuite dans une whileboucle infinie et compare le même nombre de contenus de chaque sous-liste dans les sous-listes de l'avant-dernier à y( y[:-1:]) avec le même nombre d'éléments dans la dernière sous-liste ( y[-1]) de la liste y. Lorsque la sous y[-1]- liste est différente de toute autre sous-liste, la boucle est rompue et la séquence de reste minimale correcte est renvoyée.

Par exemple, si l'entrée est 3, yserait:

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

Puis, lorsqu'il entre dans la boucle while, il compare chaque sous-liste dans la liste y[:-1:]avec le même nombre d'éléments dans la sous-liste y[-1]. Par exemple, il comparerait d'abord [[0],[1],[0]]et [1]. Étant donné que la dernière sous-liste se trouve dans le reste dey , elle continuerait, puis comparerait [[0,0],[0,1],[0,2]]et [1,0]. Étant donné que [1,0]n'est maintenant PAS dans le reste de y cet ordre spécifique , c'est la séquence de rappel minimale et, par conséquent, [1,0]serait correctement retournée.

C89, 105 octets

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

Compile (avec des avertissements) en utilisant gcc -std=c89. Prend un nombre unique sur stdin et génère la séquence de restes séparés par des espaces sur stdout.

C, 89 octets

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

Compilez avec gcc. Essayez-le en ligne: n = 59 , n = 0 .