Każda liczba może być reprezentowana za pomocą nieskończenie długiej sekwencji pozostałych. Na przykład, jeśli weźmiemy liczbę 7 i wykonamy 7mod2, to 7mod3wtedy 7mod4, i tak dalej, otrzymamy 1,1,3,2,1,0,7,7,7,7,.....

Potrzebujemy jednak możliwie najkrótszego podsekwencji reszty, która wciąż może być użyta do odróżnienia jej od wszystkich niższych liczb. Ponowne użycie 7 [1,1,3]jest najkrótszym podsekwencją, ponieważ wszystkie poprzednie podsekwencje nie zaczynają się od [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...

Zauważ, że [1,1] to nie działa na reprezentację 7, ponieważ może być również użyte do reprezentacji 1. Jednak powinieneś [1]otrzymać dane wyjściowe z wejściem 1.

Wejście wyjście

Twoje dane wejściowe są nieujemną liczbą całkowitą. Musisz wygenerować sekwencję lub listę sekwencji reszt o minimalnej długości, jak zdefiniowano powyżej.

Przypadki testowe:

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

Oto pierwsze 10 000 sekwencji , jeśli jesteś zainteresowany (numery linii są wyłączone o 1).

Jest to gra w golfa kodowego , dlatego postaraj się , aby była ona jak najkrótsza w swoim ulubionym języku. Fałszywe punkty bonusowe za szybkie odpowiedzi!

Mathematica, 60 53 bajtów

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

Nieco szybko (obsługuje 10000 w ~ 0,1 sekundy, ale prawdopodobnie zabraknie pamięci dla 100000).

Kod zgłasza błąd, ale poprawnie oblicza wynik.

Wyjaśnienie

Wcześniej na czacie stwierdziliśmy, że wymagane dzielniki można zawsze określić jako najkrótszą listę, {1, 2, ..., n}której najmniejsza wspólna wielokrotność przekracza dane wejściowe. Krótki argument przemawiający za tym, dlaczego: jeśli LCM jest mniejszy niż dane wejściowe, to odjęcie LCM od danych wejściowych pozostawiłoby wszystkie dzielniki bez zmian, więc reprezentacja nie jest unikalna. Jednak dla wszystkich danych wejściowych mniejszych niż LCM pozostałe będą unikalne, w przeciwnym razie różnica między dwiema liczbami o równych resztach byłaby mniejszą wielokrotnością wszystkich dzielników.

Jeśli chodzi o kod ... jak zwykle kolejność czytania w matematyce golfowej jest trochę zabawna.

Range[#+2]

To daje nam listę [1, 2, 3, ..., n+2]danych wejściowych n. Ma +2to zapewnić, że działa poprawnie dla 0i 1.

2~Range~#&/@...

Mapa 2~Range~#(cukier składniowy Range[2,#]) na tej liście, więc otrzymujemy

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

Są to listy dzielników kandydujących (oczywiście ogólnie rzecz biorąc, to o wiele więcej, niż będziemy potrzebować). Teraz znajdujemy pierwszy z nich, którego LCM przekracza dane wejściowe za pomocą:

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

Więcej składni: x_to wzorzec, który pasuje do dowolnej listy i wywołuje ją x. /;Przywiązuje warunek do tego wzorca. Warunek ten jest LCM@@x>#gdzie @@ stosuje funkcję do listy, czyli LCM@@{1,2,3}środków LCM[1,2,3].

W końcu otrzymujemy wszystkie pozostałe, wykorzystując fakt, że Modto Listableznaczy, tzn. Automatycznie mapuje listę, jeśli jeden z argumentów jest listą (lub jeśli oba są listami o tej samej długości):

#~Mod~...

Galaretka , 14 bajtów

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

Wykorzystuje to fakt, że rozwiązaniem (jeśli w ogóle) systemu zgodności liniowej jest unikalny moduł LCM modułów. Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

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

Dzięki @nimi za wskazanie błędu w poprzedniej wersji tej odpowiedzi (teraz poprawionej)

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

Brakuje pamięci w kompilatorze online dla dwóch największych przypadków testowych (ale działa na komputerze z 4 GB pamięci RAM).

Wypróbuj online!

Wyjaśnienie

To stosuje definicję w prosty sposób. Dla wejścia nOblicza tablicę zawierającą 2D mod(p,q)z pod 0celu ni qod 1celu n+1. Każda pjest kolumną, a każda qjest rzędem. Na przykład przy wejściu n=7ta tablica to

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

Teraz ostatnia kolumna, która zawiera resztę n, jest elementarna w porównaniu z każdą kolumną tej tablicy. To daje

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

gdzie 1oznacza równość. Ostatnia kolumna jest oczywiście równa sobie i dlatego zawiera wszystkie. Musimy znaleźć kolumnę, która ma największą liczbę początkowych nich , inne niż w ostatniej kolumnie, i wziąć pod uwagę, że liczby te początkowe, m. (W tym przypadku jest to druga kolumna, która zawiera m=3początkowe). W tym celu obliczamy skumulowany iloczyn każdej kolumny:

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

następnie suma każdej kolumny

1 3 1 2 1 2 1 8

a następnie sortuj coraz rzadziej i bierz drugą wartość, czyli 3. Jest to pożądane m, które wskazuje, ile reszt musimy zebrać.

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

Galaretka , 13 11 bajtów

r¬µ%€R‘$ḟ/Ṫ

To nie zdobędzie żadnych punktów brownie prędkości ... Wypróbuj online! lub zweryfikuj mniejsze przypadki testowe .

Jak to działa

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 bajtów

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)

Wymaga Python 3.5 i sympy ( python3 -m pip install --user sympy). Podziękowania dla @Dennis za powiadomienie mnie, że Python 3.5 pozwala na *llewę z domyślnymi argumentami.

Python 2, 73 70 69 65 bajtów

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

Pełny program. @Dennis zapisał 4 bajty, poprawiając sposób, w jaki zero jest obsługiwane.

Haskell, 66 60 51 50 bajtów

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

Przykład użycia: f 42-> [0,0,2,2]. Jest to algorytm opisany w odpowiedzi @Martin Büttner .

Zachowam poprzednią wersję w celach informacyjnych, ponieważ jest ona dość szybka:

Haskell, 51 bajtów

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

To trwa 0,03 s dla f (10^100)mojego pięcioletniego laptopa.

Edycja: @xnor znalazł bajt do zapisania. Dzięki!

Pyth, 51 bajtów 66 bajtów

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

Wypróbuj to!

Znacznie wyższa prędkość 39-bajtowa wersja (nie działa dla 0-2):

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

Wydaje się, że działa na absurdalnie duże liczby, takie jak 10 ^{10 3}

Uwaga: ta odpowiedź nie działa dla 0, 1 i 2. Naprawiono!

JavaScript (ES6), 81 77 bajtów

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)

To rekurencyjnie buduje odpowiedź, dopóki LCM nie przekroczy pierwotnej liczby. Oczywiście GCD jest również obliczane rekurencyjnie.

Edycja: Zapisano 4 bajty dzięki @ user81655.

Ruby, 52 bajty

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

To rozwiązanie sprawdza każdą możliwą wartość, mzaczynając od 2, które są resztą, która czyni sekwencję unikalną. To, co czyni ostatnią munikalną, nie jest samą resztą, ale tym, że mjest ostatnim członkiem najmniejszego zakresu, w (2..m)którym najmniejsza wspólna wielokrotność (LCM) tego zakresu jest większa niż n. Wynika to z twierdzenia chińskiego reszty, w którym w celu jednoznacznego ustalenia, która liczba njest liczbą reszt, LCM tych reszt musi być większy niż n(w przypadku wyboru nz (1..n); w przypadku wyboru nz a..bLCM musi być większy niż b-a)

Uwaga: umieszczam a<<n%mna końcu kodu, ponieważ until n<t=t.lcm(m+=1)zwarcia wcześniej aotrzymały ostatni element, aby uczynić go unikalnym.

Jeśli ktoś ma jakieś sugestie dotyczące gry w golfa, daj mi znać w komentarzach lub na czacie 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 bajtów

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

Wypróbuj online!

Python 3.5, 194 181 169 152 149 146 bajtów:

( Dzięki @ Sherlock9 za 2 bajty! )

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)

Działa idealnie, a także jest dość szybki. Obliczenie minimalnej pozostałej sekwencji 100000wyjść [0, 1, 0, 0, 4, 5, 0, 1, 0, 10, 4, 4]i zajęło tylko około 3 sekund. Był nawet w stanie obliczyć sekwencję danych wejściowych1000000 (1 milion), wyjściową [0, 1, 0, 0, 4, 1, 0, 1, 0, 1, 4, 1, 8, 10, 0, 9]i zajęło to około 60 sekund.

Wyjaśnienie

Zasadniczo funkcja ta polega po pierwsze na utworzeniu listy, gdzie ywszystko, j mod igdzie jjest każda liczba całkowita z zakresu 0=>7(w tym 7) i ikażda liczba całkowita z zakresu 0=>100. Następnie program przechodzi w nieskończoną whilepętlę i porównuje tę samą liczbę treści każdej podlisty w ramach podrzędnych list podrzędnych od y( do ostatnich y[:-1:]) z taką samą liczbą elementów na ostatniej y[-1]liście podlisty ( ) y. Kiedy podlista y[-1]jest inna niż jakakolwiek inna podlista, pętla jest przerywana i zwracana jest poprawna minimalna sekwencja pozostałych reszt.

Na przykład, jeśli dane wejściowe to 3, yto:

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

Następnie, gdy wchodzi w pętlę while, porównuje każdą listę podlist na y[:-1:]tej samej liczbie elementów na liście podrzędnej y[-1]. Na przykład najpierw porównuje [[0],[1],[0]]i [1]. Ponieważ ostatnia podlista jest w pozostałej części y, będzie kontynuowana, a następnie porównywana [[0,0],[0,1],[0,2]]i [1,0]. Ponieważ [1,0]NIE jest teraz w pozostałej części y w tej określonej kolejności , jest to minimalna sekwencja przypomnień, a zatem [1,0]zostanie poprawnie zwrócona.

C89, 105 bajtów

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

Kompiluje (z ostrzeżeniami) przy użyciu gcc -std=c89. Pobiera pojedynczą liczbę na standardowym wyjściu i wyświetla sekwencję reszt oddzieloną spacjami na standardowym wyjściu.

C, 89 bajtów

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

Kompiluj z gcc. Wypróbuj online: n = 59 , n = 0 .