Opis zadania
Teoretycznie numerów, funkcja Carmichael λ pozytywnie całkowitą n i powraca najmniej dodatnia k, tak, że K -tego moc każdej liczby całkowitej względnie pierwsze dla N jest równe 1 modulo n .
Biorąc pod uwagę dodatnią liczbę całkowitą n , twoje rozwiązanie musi obliczyć λ (n) . Najkrótszy kod w bajtach wygrywa.
Twój program powinien teoretycznie działać dla dowolnie dużych nakładów, ale nie musi być wydajny.
Porady
Sekwencja wszystkich λ (n) to OEIS A002322 .
Wygląda na to, że nie golfowa implementacja Pythona
from fractions import gcd
def carmichael(n):
coprimes = [x for x in range(1, n) if gcd(x, n) == 1]
k = 1
while not all(pow(x, k, n) == 1 for x in coprimes):
k += 1
return k
(W Pythonie pow(A, B, C)
wydajnie oblicza pow(A, B) % C
.)
Przypadki testowe
Input Output
1 1
2 1
3 2
10 4
35 12
101 100
530 52
3010 84
6511 3056
10000 500
Odpowiedzi:
Mathematica, 16 bajtów
Dobrze...
źródło
Python,
767367 bajtówWypróbuj online!
Kolejny bajt można zapisać, zwracając wartość True zamiast 1 .
Alternatywne wdrożenie
Stosując to samo podejście, istnieje również następująca implementacja @feersum, która nie korzysta ze zrozumienia listy.
Zauważ, że ta implementacja wymaga czasu O (n λ (n) ) . Wydajność można znacznie poprawić, jednocześnie zmniejszając wynik do 66 bajtów , ale funkcja zwraca wartość True dla wejścia 2 .
tło
Definicje i zapis
Wszystkie zastosowane zmienne będą oznaczać liczby całkowite; n , k i α będą oznaczać dodatnie liczby całkowite; a p oznacza dodatnią liczbę pierwszą .
a | b jeśli b jest podzielne przez a , tj. jeśli istnieje q takie, że b = qa .
≡ b ( mod m) jeśli i b mają tę samą resztę modulo m , to znaczy, gdy M | a - b .
λ (n) jest najmniejszym k takim, że a k ≡ 1 ( mod n) - tj. takim, że n | k - 1 - dla wszystkich A , które są względnie pierwsze do n .
r (n) jest najmniejsza K tak, że 2k + 1 ≡ k + 1 ( mod n), - czyli takie, że n | a k + 1 (a k - 1) - dla wszystkich a .
λ (n) ≤ f (n)
Fix n i pozwolić na BE względnie pierwsze dla N .
Z definicji f , n | a f (n) +1 (a f (n) - 1) . Ponieważ a i n nie mają wspólnego czynnika pierwszego, nie należy również f (n) +1 i n , co oznacza, że n | a f (n) - 1 .
Ponieważ λ (n) jest najmniejszą liczbą całkowitą k taką, że n | a k - 1 dla wszystkich liczb całkowitych a, które są kopiowane do n , wynika z tego, że λ (n) ≤ f (n) .
λ (n) = f (n)
Ponieważ już ustaliliśmy nierówność λ (n) ≤ f (n) , wystarczy zweryfikować, czy k = λ (n) spełnia warunek definiujący f , tj. Że n | a λ (n) +1 (a λ (n) - 1) dla wszystkich a . W tym celu ustalimy, że p α | a λ (n) +1 (a λ (n) - 1) ilekroć p α | n .
λ (k) | λ (n) ilekroć k | n ( źródło ), więc (a λ (k) - 1) (a λ (n) -λ (k) + a λ (n) -2λ (k) + ⋯ + a λ (k) + 1) = a λ (n) - 1, a zatem a λ (k) - 1 | a λ (n) - 1 | a λ (n) +1 (a λ (n) - 1) .
Jeśli a i p α są pierwszymi, zgodnie z definicją λ i powyżej, p α | a λ (p α ) - 1 | a λ (n) +1 (a λ (n) - 1) następuje zgodnie z potrzebą.
Jeśli a = 0 , to a λ (n) +1 (a λ (n) - 1) = 0 , który jest podzielny przez wszystkie liczby całkowite.
Na koniec musimy rozważyć przypadek, w którym a i p α mają wspólny czynnik pierwszy. Ponieważ p jest liczbą pierwszą, oznacza to, że p | . Twierdzenie Carmichaela ustala, że λ (p α ) = (p - 1) p α - 1, jeśli p> 2 lub α <3 i że λ (p α ) = p α - 2 w przeciwnym razie. We wszystkich przypadkach λ (p α ) ≥ p α - 2 ≥ 2 α - 2 > α - 2 .
Dlatego λ (n) + 1 ≥ λ (p α ) + 1> α - 1 , więc λ (n) + 1 ≥ α i p α | p λ (n) +1 | a λ (n) +1 | a λ (n) +1 (a λ (n) - 1) . To kończy dowód.
Jak to działa
Podczas gdy definicje f (n) i λ (n) uwzględniają wszystkie możliwe wartości a , wystarczy przetestować te, które leżą w [0, ..., n - 1] .
Gdy wywoływane jest f (n, k) , oblicza on k + 1 (a k - 1)% n dla wszystkich wartości a w tym zakresie, czyli 0 wtedy i tylko wtedy, gdy n | a k + 1 (a k - 1) .
Jeśli wszystkie obliczone reszty są równe zero, k = λ (n) i
any
zwraca False , więc f (n, k) zwraca 1 .Z drugiej strony, podczas gdy k <λ (n) ,
1-any(...)
zwróci 0 , więc f jest wywoływane rekurencyjnie z przyrostową wartością k . Wiodąca-~
zwiększa wartość zwracaną f (n, k + 1) , więc dodajemy 1 do f (n, λ (n)) = 1 raz dla każdej liczby całkowitej w [1, ..., λ (n) - 1 ] . Ostateczny wynik to zatem λ (n) .źródło
f=lambda n,k=1,a=1:a/n or(a**k*~-a**k%n<1)*f(n,k,a+2-n%2)or-~f(n,k+1)
(Dodaj jeden bajt, jeśli nie chcesz, aby zajmował on czas n ** λ (n)).Mathematica bez wbudowanego,
5857 bajtówDzięki Martinowi Enderowi za znalezienie błędu, a następnie zapisanie mi bajtów potrzebnych do naprawy!
Dzięki milom za zaoszczędzenie 1 bajtu! (co wydawało mi się 2)
Wbudowane są całkowicie w porządku ... ale dla tych, którzy chcą je wdrożyć bez użycia brutalnej siły, oto formuła dla funkcji Carmichael:
Jeśli p jest liczbą pierwszą, funkcja Carmichaela λ (p ^ r) jest równa φ (p ^ r) = (p-1) * p ^ (r-1) - z wyjątkiem sytuacji, gdy p = 2 i r≥3, w takim przypadku to połowa tego, a mianowicie 2 ^ (r-2).
A jeśli rozkład na czynniki pierwsze n wynosi p1 ^ r1 * p2 ^ r2 * ..., to λ (n) jest najmniejszą wspólną wielokrotnością {λ (p1 ^ r1), λ (p2 ^ r2), .. .}.
Środowisko wykonawcze to w pierwszej kolejności więcej niż faktoring liczby całkowitej.
źródło
EulerPhi
aby uzyskaćLCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&
za 57 bajtów.Szablony uważane za szkodliwe , 246 bajtów
Funkcja bez nazwy (nie to, że istnieją funkcje nazwane).
To mój zapomniany esolang interpretowany przez szablony instancji kompilatora C ++. Przy domyślnej maksymalnej głębokości szablonu
g++
, może on wykonać λ (35), ale nie może zrobić λ (101) (leniwa ocena pogarsza sytuację).źródło
Haskell,
5756 bajtówźródło
Galaretka, 2 bajty
Dziękuję za wbudowane, @Lynn
źródło
Pyth -
191817 bajtówJeden bajt zapisany dzięki @TheBikingViking.
Prosta brutalna siła.
Wypróbuj online tutaj .
źródło
f!smt
jest o jeden bajt krótszy.Rubin,
5956 bajtówźródło
JOT,
2827 bajtówFunkcja Carmichaela to λ ( n ), a funkcja totalna to φ ( n ).
Wykorzystuje definicję, w której λ ( p k ) = φ ( p k ) / 2, jeśli p = 2, a k > 2 else φ ( p k ). Następnie, dla ogólnego n = p 1 k 1 p 2 k 2 ⋯ p i k i , λ ( n ) = LCM [λ ( p 1 k 1 ) λ ( p 2 k 2 ) ⋯ λ ( p i k i )] .
Stosowanie
Dodatkowe polecenia używane do formatowania wielu wejść / wyjść.
Wyjaśnienie
źródło
Właściwie
3028251926 bajtówFunkcja Carmichaela,
λ(n)
gdzien = p_0**k_0 * p_1**k_1 * ... * p_a**k_a
, jest definiowana jako najmniejsza wspólna wielokrotność (LCM)λ(p_i**k_i)
dla maksymalnych mocy pierwszychp_i**k_i
dzielących się nan
. Biorąc pod uwagę, że dla każdej potęgi pierwotnej, z wyjątkiem tego, gdzie jest liczba pierwsza2
, funkcja Carmichaela jest równoważna z funkcją totalną Euleraλ(n) == φ(n)
,φ(n)
zamiast niej używamy . Dla szczególnego przypadku2**k
, w którymk ≥ 3
, po prostu sprawdzić, czy2**3 = 8
dzieli sięn
na początku programu, i podzielić przez 2, jeśli to robi.Niestety, tak naprawdę nie ma obecnie wbudowanego LCM, więc zrobiłem LCM z brutalną siłą. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!
Ungolfing
źródło
totient
igcd
. Byłoby to krótsze, gdyby faktycznie miałlcm
bezpośrednio, ale nie przeszkadza mi to aż tak bardzo, a to i tak zrzuciłoby maksymalnie 4 bajty.JavaScript (ES6),
143135 bajtówEdycja: zapisano 8 bajtów dzięki Neilowi
Implementacja z wykorzystaniem programowania funkcjonalnego.
Nie golfił i skomentował
Próbny
Mimo, że działa dla
6511
i10000
, nie uwzględnię ich tutaj, ponieważ wydaje się być trochę powolny.źródło
0..n-1
zakresy dość łatwo:[...Array(n).keys()]
. Wymaga to nie jednego, ale dwóch specjalnych przypadków, ale wciąż jestem na czele:n=>(a=[...Array(n).keys()]).find(k=>k&&!c.some(c=>a.slice(0,k).reduce(y=>y*c%n,1)-1),c=a.filter(x=>(g=(x,y)=>x?g(y%x,x):y)(x,n)==1))||1
Ruby,
101869190 bajtówRubinowy port mojej odpowiedzi . Sugestie dotyczące gry w golfa mile widziane.
Edycja: -4 bajtów od usunięcia,
a
ale +9 bajtów od naprawienia błędu w miejscu1
powrotunil
. -1 bajt dzięki Cyoce.Ungolfing
źródło
a=
. Niestety, wrócisznil
po n = 1 :(. To(n.prime_division<<[2,1])
naprawia. Nie jestem pewien, czy istnieje bardziej golfowy sposób.(n%8<1?n/2:n).prime_division...
zapisuje kolejne 2 bajty.a
jest pozostałością po wcześniejszej próbie golfa. Dzięki za przypomnieniea
i za heads up1
..reduce :lcm
zamiast.reduce(:lcm)
.JavaScript (ES 2016) 149
Implementacja referencji Python przeniesiona do JS. Brakuje jakiegoś fantazyjnego wbudowanego Pyhton w js, jak
gcd
ipow
, a rozumienie tablic nie jest standardowe w ES 6. Działa to w Firefoksie.Mniej golfa
źródło
p=(a,b,c)=>b?a*p(a,b-1,c)%c:1;
Jawa,
209207202194192 bajtyKod (96 bajtów):
dodatkowe funkcje (96 bajtów):
Testy i bez golfa
Notatki
a
bycia anint
jest krótsze niż gdybym musiał użyć aboolean
do wykonania moich testów.valueOf
wszystkich nowych jest krótszyBigInteger
niż utworzenie osobnej funkcji (jest ich 5, aONE
stała jest gratis).gcd
jest obliczany wielokrotnie dla tych samych wartości.Goli
if(...)a=...;
->a=...?...:1;
a==1
->a<2
BigInteger
przez golfagcd
imodPow
dlaint
.modPow
-> rekurencyjne==1
-><2
(wydaje się działać dla wszystkich przypadków testowych, nie wiem dla innych liczb).źródło
p
całkiem sprytna. Starałem się używać tylko liczb całkowitych na początku też, ale jak już wspomniałem w mojej odpowiedzi, miałem problemy z precyzją i dlatego został przeniesiony doBigInteger
(czyliMath.pow(3, 100)%101
zwracane60.0
zamiast1
). Twoja implementacja jest na to odporna, ponieważ wykonuje modyfikację w każdej iteracji. Nadal jednak występuje błąd. Dla dużychm
p
może nadal zwracać złe wyniki. Również z powodu rekurencjiStackOverflowError
może łatwo wystąpić w przypadku dużych danych wejściowych z domyślnym rozmiarem stosu.int
typów. Mógłbym użyć długich zamiast ints, czyli 8 dodatkowych bajtów. Ale moim zdaniem wszystkie przypadki testowe są ważne, więc tak to zostawiam.StackOverflowError
może się zdarzyć, ale tak właśnie działa rekurencja. Istnieją metody ograniczania do 32 stosów, ale wykorzystują one znacznie więcej bajtów. Ta implementacja jest krucha, tak, masz całkowitą rację. Ale jest wystarczająco silny dla przypadków testowych.Java8
3819 +287295253248241 =325333272267260 bajtówImport, 19 bajtów
Wyjaśnienie
Jest to prosta implementacja. Współ-liczby pierwsze są obliczane w
Set p
i każda k-ta moc jest używana do sprawdzenia, czy wynosi ona 1 moduł.Musiałem użyć z
BigInteger
powodu problemów z precyzją.Stosowanie
Bez golfa
Wszelkie sugestie dotyczące gry w golfa są mile widziane :-)
Aktualizacja
B()
k()
metodę ip
zestaw (współrzędnych).źródło
k(int)
do pętli, ponieważ jest to jedna linijka i można to zrobić. Dodatkowo wc
metodzie można również wprowadzić stałą O. Myślę, że robiąc to, wygrasz bajty!while(n>1&&!p.stream().allMatch(x->B((int)x).modPow(B(k), B(n)).equals(O)))
goli bajty i naprawia problemy, o których wspomniałem, jeśli ponownie umieścisz zestaw i stałą w metodzie. Ponadto używaszO
dwa razy, zamień na,B(1)
aby golić bajty.Java,
165 163 158 152143 bajtyKolejny port moim realizacji C .
Wypróbuj na Ideone
źródło
C ++,
208 200 149 144 140134 bajtówPort mojego realizacji C .
Wypróbuj na Ideone
źródło
Rakieta 218 bajtów
Wersja bez golfa:
Testowanie:
Wydajność:
źródło
C,
278 276 272 265 256 243 140 134125 bajtówWykorzystuje on wolny modułowy algorytm potęgowania, zbyt często oblicza GCD i nie przecieka pamięci!
Nie golfowany:
Wypróbuj na Ideone
źródło
Axiom 129 bajtów
mniej golfa
wyniki
źródło