Formuła na kongregacje

10

Chińskie twierdzenie o resztach może być bardzo przydatna w arytmetyce modularnej.

Rozważmy na przykład następujący zestaw relacji zgodności:

Zestaw zgodności

W przypadku zestawów warunków kongruencji jak ten, w którym wszystkie zasady ( 3, 5, 7w tym przykładzie) są wspólnie pierwsza z siebie, że będzie jeden i tylko jeden całkowitą nod 1i produkt z zasady ( 3*5*7 = 105w tym przykładzie) włącznie, który spełnia stosunki .

W tym przykładzie liczba byłaby 14wygenerowana według tej formuły:

formuła

gdzie 2, 4, and 0podano z powyższego przykładu.

70, 21, 15współczynniki o wzorze i są one zależne od podstawach 3, 5, 7.

Aby obliczyć współczynniki wzoru ( 70, 21, 15w naszym przykładzie) dla zestawu zasad, stosujemy następującą procedurę.

Dla każdej liczby aw zestawie zasad:

  1. Znajdź produkt wszystkich innych baz, oznaczonych jako P.
  2. Znajdź pierwszą wielokrotność, Pktóra pozostawia resztę 1po podzieleniu przez a. Jest to współczynnik a.

Na przykład, aby obliczyć współczynnik odpowiadający podstawie 3, znajdujemy iloczyn wszystkich pozostałych zasad (tj. 5*7 = 35), A następnie znajdujemy pierwszą wielokrotność tego produktu, która pozostawia resztę 1po podzieleniu przez zasadę.

W tym przypadku 35pozostawia resztę 2po podzieleniu przez 3, ale 35*2 = 70pozostawia resztę 1po podzieleniu przez 3, więc 70jest to odpowiedni współczynnik dla 3. Podobnie 3*7 = 21pozostawia resztę 1po podzieleniu przez 5i 3*5 = 15pozostawia resztę 1po podzieleniu przez 7.

W skrócie

Dla każdej liczby aw zestawie liczb:

  1. Znajdź iloczyn wszystkich pozostałych liczb oznaczonych jako P.
  2. Znajdź pierwszą wielokrotność, Pktóra pozostawia resztę 1po podzieleniu przez a. Jest to współczynnik a.

Wyzwanie

  • Wyzwaniem dla zestawu dwóch lub więcej zasad jest znalezienie zestawu odpowiednich współczynników.
  • Zestaw podstaw jest gwarantowany jako para-podstawowa, a każda podstawa jest większa niż 1.
  • Twoje dane wejściowe to lista liczb całkowitych jako [3,4,5]ciąg wejściowy lub ciąg znaków oddzielonych spacjami "3 4 5"lub dane wejściowe działają.
  • Wynik powinien być albo listą liczb całkowitych, albo ciągiem znaków oddzielonych spacją, który oznacza zbiór współczynników.

Przypadki testowe

input             output
[3,5,7]           [70,21,15]
[2,3,5]           [15,10,6]
[3,4,5]           [40,45,36]
[3,4]             [4,9]
[2,3,5,7]         [105,70,126,120]
[40,27,11]        [9801,7480,6480]
[100,27,31]       [61101,49600,56700]
[16,27,25,49,11]  [363825,2371600,2794176,5583600,529200]

Wielkie dzięki dla Dziurawej Zakonnicy za pomoc w napisaniu tego wyzwania. Jak zawsze, jeśli problem jest niejasny, daj mi znać. Powodzenia i dobrej gry w golfa!

Sherlock9
źródło
Czy na wejściu zawsze będą 3 liczby?
xnor
@xnor Nope. Edytowano przypadki testowe.
Sherlock9,

Odpowiedzi:

5

Haskell, 61 55 53 bajtów

f x=[[p|p<-[0,product x`div`n..],p`mod`n==1]!!0|n<-x]

Definiuje funkcję, fktóra pobiera dane wejściowe i podaje dane wyjściowe jako listę liczb całkowitych.

f x=[                                          |n<-x]  (1)
              product x                                (2)
                       `div`n                          (3)

Najpierw zapętlamy wszystkie liczby całkowite na wejściu (1). Następnie bierzemy iloczyn wszystkich liczb całkowitych (2) i dzielimy przez n, aby otrzymać tylko iloczyn nliczb całkowitych, czyli P(3).

           [0,               ..]                       (4)
     [p|p<-                     ,p`mod`n==1]           (5)
                                            !!0        (6)

Następnie wykorzystujemy wynik ( P) jako wartość kroku dla zakresu rozpoczynającego się od zera (4). Bierzemy wynik [0, P, 2P, 3P, ...]i filtrujemy go według wartości, dla których wynikiem operacji mod-n jest jeden (5). Na koniec bierzemy pierwszy element, który działa dzięki leniwej ocenie (6).

Dzięki @xnor za 2 bajty!

Klamka
źródło
1
Witamy w haskell! Myślę, że quotmożesz być divi headmoże być !!0.
xnor
4

Galaretka , 11 7 bajtów

P:*ÆṪ%P

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

Niech P i być ściśle dodatnich, względnie pierwsze liczby całkowite.

Dwuetapowy proces w pytaniu - znalezienie wielokrotności P, która pozostawia resztę 1, gdy dzieli się przez a - można opisać następującym równaniem zgodności.

liniowe równanie zgodności

Według twierdzenia Eulera-Fermata mamy

Twierdzenie Eulera-Fermata

gdzie φ oznacza funkcję całkowitą Eulera . Na podstawie tego wyniku wnioskujemy, co następuje.

wzór na liniowe równanie zgodności

Wreszcie, ponieważ wyzwanie wymaga od nas obliczenia Px , obserwujemy to

wzór na wynik końcowy

gdzie Pa można obliczyć jako iloczyn wszystkich modułów.

Jak to działa

P:*ÆṪ%P  Main link. Argument: A (list of moduli)

P        Yield the product of all moduli.
 :       Divide the product by each modulus in A.
   ÆṪ    Apply Euler's totient function to each modulus.
  *      Raise each quotient to the totient of its denominator.
     %P  Compute the remainder of the powers and the product of all moduli.
Dennis
źródło
2

J, 13 bajtów

*/|5&p:^~*/%]

Na podstawie niesamowitej odpowiedzi @Dennis .

Stosowanie

Niektóre przypadki testowe będą wymagały danych wejściowych jako rozszerzonych liczb całkowitych z sufiksem x.

   f =: */|5&p:^~*/%]
   f 3 5 7
70 21 15
   f 40x 27 11
9801 7480 6480
   f 16x 27 25 49 11
363825 2371600 2794176 5583600 529200

Wyjaśnienie

*/|5&p:^~*/%]  Input: list B
         */    Reduce B using multiplication to get the product of the values
            ]  Identity function, get B
           %   Divide the product by each value in B, call the result M
   5&p:        Apply the totient function to each value in B, call the result P
       ^~      Raise each value in M to the power of its corresponding value in P
*/             The product of the values in B
  |            Compute each power modulo the product and return

Wypróbuj tutaj.

mile
źródło
2

Mathematica, 27 bajtów

PowerMod[a=LCM@@#/#,-1,#]a&
alephalpha
źródło
1

Galaretka, 14 13 bajtów

P:×"Ḷð%"’¬æ.ḷ

Zapisano bajt dzięki @ Dennis !

Wykorzystuje proces opisany w specyfikacji wyzwania. Dane wejściowe to lista zasad, a dane wyjściowe to lista współczynników.

Wypróbuj online lub Zweryfikuj wszystkie przypadki testowe .

Wyjaśnienie

P:×"Ḷð%"’¬æ.ḷ  Input: a list B
P              Get the product of the list
 :             Divide it by each value in the B, call it M
    Ḷ          Get a range from 0 to k for k in B
  ×"           Vectorized multiply, find the multiples of each M
     ð         Start a new dyadic chain. Input: multiples of M and B
      %"       Vectorized modulo, find the remainders of each multiple by B
        ’      Decrement every value
               If the remainder was 1, decrementing would make it 0
         ¬     Logical NOT, zeros become one and everything else becomes 0
            ḷ  Get the multiples of M
          æ.   Find the dot product between the modified remainders and the multiples
               Return
mile
źródło
1

JavaScript (ES6), 80 bajtów

a.map(e=>[...Array(e).keys()].find(i=>p*i/e%e==1)*p/e,p=a.reduce((i,j)=>i*j))

Wypróbowałem rozszerzony algorytm euklidesowy, ale zajmuje on 98 bajtów:

a=>a.map(e=>(r(e,p/e)+e)%e*p/e,p=a.reduce((i,j)=>i*j),r=(a,b,o=0,l=1)=>b?r(b,a%b,t,o-l*(a/b|0)):o)

Jeśli wszystkie wartości są liczbą pierwszą, ES7 może to zrobić w 56 bajtach:

a=>a.map(e=>(p/e%e)**(e-2)%e*p/e,p=a.reduce((i,j)=>i*j))
Neil
źródło
1

Python + SymPy, 71 bajtów

from sympy import*
lambda x:[(prod(x)/n)**totient(n)%prod(x)for n in x]

Wykorzystuje algorytm z mojej odpowiedzi Jelly . I / O ma postać list numerów SymPy.

Dennis
źródło
1

Python 2, 87 84 bajtów

Prosta implementacja algorytmu. Sugestie dotyczące gry w golfa mile widziane.

a=input();p=1
for i in a:p*=i
print[p/i*j for i in a for j in range(i)if p/i*j%i==1]
Sherlock9
źródło
Pełny program zaoszczędziłby 3 bajty.
Dennis,
1

Cheddar , 64 bajty

n->n.map(i->(|>i).map(j->(k->k%i>1?0:k)(n.reduce((*))/i*j)).sum)
Leaky Nun
źródło
Powinienem dodać, .productktóry robi .reduce((*))dla tablic ...
Downgoat
0

GAP , 51 bajtów

GAP ma funkcję, która może obliczyć motywujący przykład ChineseRem([2,5,7],[2,4,0]), ale wciąż nie ułatwia to uzyskania współczynników. Możemy uzyskać n-ty współczynnik, używając listy z jednym w n-tej pozycji i zerami w innych pozycjach jako drugim argumentem. Musimy więc utworzyć te listy i zastosować funkcję do wszystkich:

l->List(Basis(Integers^Size(l)),b->ChineseRem(l,b))
Christian Sievers
źródło
0

Partia, 148 bajtów

@set p=%*
@set/ap=%p: =*%
@for %%e in (%*)do @for /l %%i in (1,1,%%e)do @call:l %%e %%i
@exit/b
:l
@set/an=p/%1*%2,r=n%%%1
@if %r%==1 echo %n%
Neil
źródło
0

Właściwie 14 bajtów

Wykorzystuje to algorytm w odpowiedzi Dennisa Jelly . Nadchodzi kolejna odpowiedź oparta na mojej odpowiedzi w języku Python. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

;π;)♀\;♂▒@♀ⁿ♀%

Jak to działa

                 Implicit input a.
;                Duplicate a.
 π;)             Take product() of a, duplicate and rotate to bottom.
    ♀\           Integer divide the product by each element of a. Call this list b.
      ;♂▒        Take that list, duplicate, and get the totient of each element.
         @♀ⁿ     Swap and take pow(<item in b>, <corresponding totient>)
            ♀%   Modulo each item by the remaining duplicate product on the stack.
                 Implicit return.

Kolejna odpowiedź oparta na mojej odpowiedzi w języku Python na 22 bajty. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

;π╖`╝╛╜\╛r*"╛@%1="£░`M

Jak to działa

            Implicit input a.
;π╖         Duplicate, take product of a, and save to register 0.
`...`M      Map over a.
  ╝           Save the item, b, in register 1.
  ╛╜\         product(a) // b. Call it P.
  ╛r          Take the range [0...b].
  *           Multiply even item in the range by P. Call this list x.
  "..."£░     Turn a string into a function f.
              Push values of [b] where f returns a truthy value.
    ╛@%         Push b, swap, and push <item in x> % b.
    1=          Does <item> % b == 1?
            Implicit return.
Sherlock9
źródło