Oblicz funkcję Carmichaela

36

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
Lynn
źródło
Co tu teoretycznie znaczy? Czy mogę założyć, że wejście n mieści się w 16-bitowej liczbie całkowitej? Czy mogę założyć, że n ^ λ (n) pasuje do podwójnego?
Dennis,
2
Tak i tak, powiedziałbym. Jak w teorii , teoretycznie obejmuje udawanie, że twoje rodzime typy są arbitralnie precyzyjne i duże (myślałem, że to był konsensus, ale nie jestem pewien).
Lynn,

Odpowiedzi:

48

Mathematica, 16 bajtów

CarmichaelLambda

Dobrze...

Martin Ender
źródło
38
..... naprawdę. ._.
acrolith
12
Nie lubię u mathematica
downrep_nation 19.09.16
29

Python, 76 73 67 bajtów

f=lambda n,k=1:1-any(a**-~k*~-a**k%n for a in range(n))or-~f(n,k+1)

Wypró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.

f=lambda n,k=1,a=1:a/n or(a**-~k*~-a**k%n<1)*f(n,k,a+1)or-~f(n,k+1)

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 .

f=lambda n,k=1,a=1:a/n or~-a**k*a**-~k%n<1==f(n,k,a+1)or-~f(n,k+1)

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 + 1k + 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 anyzwraca 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) .

Dennis
źródło
Możesz zapisać co najmniej 4 z rekurencją zamiast ze zrozumieniem listy: 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)).
feersum
1
Dzięki! W międzyczasie znalazłem ulepszenie mojego algorytmu, które wydaje się niwelować korzyści wynikające z rekurencji zamiast korzystania ze zrozumienia listy.
Dennis,
14

Mathematica bez wbudowanego, 58 57 bajtów

Dzię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:

LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&

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.

Greg Martin
źródło
Możesz użyć, EulerPhiaby uzyskać LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&za 57 bajtów.
mile
@miles ładnie zauważony! Liczę 56 bajtów, możesz sprawdzić?
Greg Martin
Tak, to 57 bajtów .
mile
najwyraźniej próbuję nawet pograć w golfa ...: /
Greg Martin
12

Szablony uważane za szkodliwe , 246 bajtów

Fun<Ap<Fun<If<Eq<A<2>,T>,A<1>,And<Eq<Ap<Fun<If<A<1>,Ap<A<0>,Rem<A<2>,A<1>>,A<1>>,A<2>>>,A<1,1>,A<2>>,T>,Sub<Ap<Fun<Rem<If<A<1>,Mul<A<2,1>,Ap<A<0>,Sub<A<1>,T>>>,T>,A<1,2>>>,A<1>>,T>>,Ap<A<0>,Add<A<1>,T>,A<1,1>>,Ap<A<0>,A<1>,Sub<A<2>,T>>>>,T,A<1>>>

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ę).

feersum
źródło
10

Haskell, 57 56 bajtów

f n=[k|k<-[1..],and[mod(m^k)n<2|m<-[1..n],gcd m n<2]]!!0
Dianne
źródło
8

Galaretka, 2 bajty

Æc

Dziękuję za wbudowane, @Lynn

Dianne
źródło
31
............. ._.
Maltysen
10
Nigdy nie rozumiem sensu wdrażania tak absurdalnie specyficznych wbudowanych funkcji.
Fatalize
31
To prawie dodatek do języka stworzonego specjalnie na potrzeby tego wyzwania. Zatwierdzenie przez Lynn 2 dni temu, wyzwanie przez @Lynn dzisiaj
edc65
5
@ edc65 Nie wspominając o tym, że ten wbudowany jest prawie bezużyteczny poza tym wyzwaniem i jego pochodnymi.
Fatalize
3
Cóż, funkcja Carmichaela jest ważna w teorii liczb (jak odzwierciedla obecnie najwyższa odpowiedź), więc nie nazwałbym tego bezużytecznym.
Greg Martin
6

Pyth - 19 18 17 bajtów

Jeden bajt zapisany dzięki @TheBikingViking.

Prosta brutalna siła.

f!sm*t.^dTQq1iQdQ

Wypróbuj online tutaj .

Maltysen
źródło
f!smtjest o jeden bajt krótszy.
TheBikingViking
@ TheBikingViking och, tak, dziękuję
Maltysen
Boli mnie oczy, jak u licha jest ten python ...? Mimo to bardzo mi się podobało haha ​​:)
Yohan Obadia
6

Rubin, 59 56 bajtów

->x{a=1..x
a.detect{|k|a.all?{|y|x.gcd(y)>1||y**k%x<2}}}
m-chrzan
źródło
5

JOT, 28 27 bajtów

[:*./@(5&p:%2^0=8&|)2^/@p:]

Funkcja 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 2p 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ść.

   f =: [:*./@(5&p:%2^0=8&|)2^/@p:]
   f 530
52
   (,.f"0) 1 2 3 10 35 101 530 3010 6511 10000
    1    1
    2    1
    3    2
   10    4
   35   12
  101  100
  530   52
 3010   84
 6511 3056
10000  500

Wyjaśnienie

[:*./@(5&p:%2^0=8&|)2^/@p:]  Input: integer n
                          ]  Identity function, get n
                    2   p:   Get a table of prime/exponent values for n
                     ^/@     Raise each prime to its exponent to get the prime powers of n
[:    (            )         Operate on the prime powers
                8&|            Take each modulo 8
              0=               Test if its equal to 0, 1 if true else 0
            2^                 Raise 2 to the power of each
       5&p:                    Apply the totient function to each prime power
           %                   Divide it by the powers of 2
  *./@                       Reduce using LCM and return
mile
źródło
To daje złą odpowiedź dla 10000 (1000 zamiast prawidłowej 500), i rzeczywiście dla każdej wielokrotności liczby 8. 2 jest osobliwą liczbą pierwszą, a λ (2 ^ a) = 2 ^ {a-2} (nie 2 ^ { a-1}) gdy a≥3.
Greg Martin
Dzięki, że to zrozumiałem, wydaje mi się, że nie potrafię nawet odczytać własnych wyników
mil
czasami nie jesteś sam ... :)
Greg Martin
5

Właściwie 30 28 25 19 26 bajtów

Funkcja Carmichaela, λ(n)gdzie n = 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 pierwszych p_i**k_idzielących się na n. Biorąc pod uwagę, że dla każdej potęgi pierwotnej, z wyjątkiem tego, gdzie jest liczba pierwsza 2, funkcja Carmichaela jest równoważna z funkcją totalną Eulera λ(n) == φ(n), φ(n)zamiast niej używamy . Dla szczególnego przypadku 2**k, w którym k ≥ 3, po prostu sprawdzić, czy 2**3 = 8dzieli się nna 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!

;7&Yu@\w`iⁿ▒`M╗2`╜@♀%ΣY`╓N

Ungolfing

         Implicit input n.
;        Duplicate n.
7&       n&7 == n%8.
Yu       Logical NOT and increment. If n%8 == 0, return 2. Else, return 1.
@\       Integer divide n by 2 if n%8==0, by 1 otherwise.
          Thus, we have dealt with the special case where p_i == 2 and e_i >= 3.
w        Full prime factorization of n as a list of [prime, exponent] lists.
`...`M   Map the following function over the prime factorization.
  i        Flatten the array, pushing exponent, then prime to the stack.
  ⁿ▒       totient(pow(prime, exponent)).
╗        Save that list of totients in register 0.
2`...`╓  Get the first two values of n where the following function f(n) is truthy.
         Those two numbers will be 0 and our LCM.
  ╜@       Push the list in register 0 and swap with our n.
  ♀%       Get n mod (every number in the list)
  Σ        Sum the modulos. This sum will be 0, if and only if this number is 0 or LCM.
  Y        Logical NOT, so that we only get a truthy if the sum of modulos is 0.
N        Grab the second number, our LCM. Implicit return.
Sherlock9
źródło
2
Właściwie nie mam pojęcia, jak to zrobiłeś w zaledwie 19 bajtach.
Odczyt bufora
@TheBitByte Za pomocą wbudowanych totienti gcd. Byłoby to krótsze, gdyby faktycznie miał lcmbezpośrednio, ale nie przeszkadza mi to aż tak bardzo, a to i tak zrzuciłoby maksymalnie 4 bajty.
Sherlock9
1
Twierdzenie, że lcm (* a) = produkt (* a) / gcd (* a) jest prawdziwe, gdy * a jest listą dokładnie dwóch liczb; jednak ogólnie jest fałszem dla dłuższych list (przykład: jeśli * a wynosi {6,10,15}, daje 900 zamiast prawidłowej odpowiedzi 60). [Jeśli chodzi o to, to źle, że * a także jest listą jednej liczby!] I możesz sprawdzić, czy otrzymałeś złą odpowiedź na ponad połowę przypadków testowych wymienionych w PO.
Greg Martin
@GregMartin Dzięki za informacje. Naprawiony.
Sherlock9,
4

JavaScript (ES6), 143 135 bajtów

Edycja: zapisano 8 bajtów dzięki Neilowi

Implementacja z wykorzystaniem programowania funkcjonalnego.

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

Nie golfił i skomentował

n =>                                          // Given a positive integer n:
  (A = [...Array(n).keys()])                  // Build A = [0 ... n-1].
  .find(k =>                                  // Try to find k in [1 ... n-1] such as
    k && !c.some(c =>                         // for each coprime c: c^k ≡ 1 (mod n).
      A.slice(0, k).reduce(y =>               // We use reduce() to compute
        y * c % n, 1                          // c^k mod n.
      ) - 1                                   // Compare it with 1.
    ),                                        // The list of coprimes is precomputed
    c = A.filter(x =>                         // before the find() loop is executed:
      (                                       // for each x in [0 ... n-1], keep
        g = (x, y) => x ? g(y % x, x) : y     // only integers that verify:
      )(x, n) == 1                            // gcd(x, n) = 1
    )                                         // (computed recursively)
  ) || 1                                      // Default result is 1 (for n = 1)

Próbny

Mimo, że działa dla 6511i 10000, nie uwzględnię ich tutaj, ponieważ wydaje się być trochę powolny.

let f =
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

console.log(f(1));     // 1
console.log(f(2));     // 1
console.log(f(3));     // 2
console.log(f(10));    // 4
console.log(f(35));    // 12
console.log(f(101));   // 100
console.log(f(530));   // 52
console.log(f(3010));  // 84

Arnauld
źródło
1
JS można zrobić 0..n-1zakresy 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
Neil,
2

Ruby, 101 86 91 90 bajtów

Rubinowy port mojej odpowiedzi . Sugestie dotyczące gry w golfa mile widziane.

Edycja: -4 bajtów od usunięcia, aale +9 bajtów od naprawienia błędu w miejscu 1powrotu nil. -1 bajt dzięki Cyoce.

require'prime'
->n{((n%8<1?n/2:n).prime_division<<[2,1]).map{|x,y|x**~-y*~-x}.reduce :lcm}

Ungolfing

require 'prime'
def carmichael(n)
  if n%8 < 1
    n /= 2
  end
  a = []
  n.prime_division.do each |x,y|
    a << x**(y-1)*(x-1)
  end
  return a.reduce :lcm
end
Sherlock9
źródło
Nie trzeba a=. Niestety, wrócisz nilpo n = 1 :(. To (n.prime_division<<[2,1])naprawia. Nie jestem pewien, czy istnieje bardziej golfowy sposób.
m-chrzan,
(n%8<1?n/2:n).prime_division...zapisuje kolejne 2 bajty.
m-chrzan
@ m-chrzan ajest pozostałością po wcześniejszej próbie golfa. Dzięki za przypomnienie ai za heads up 1.
Sherlock9,
Możesz zapisać bajt, używając .reduce :lcmzamiast .reduce(:lcm).
Cyoce
1

JavaScript (ES 2016) 149

Implementacja referencji Python przeniesiona do JS. Brakuje jakiegoś fantazyjnego wbudowanego Pyhton w js, jak gcdi pow, a rozumienie tablic nie jest standardowe w ES 6. Działa to w Firefoksie.

n=>eval('for(g=(a,b)=>b?g(b,a%b):a,p=(a,b,c)=>eval("for(r=1;b--;)r=r*a%c"),c=[for(_ of Array(i=n))if(g(i--,n)<2)i+1],k=1;c.some(x=>p(x,k,n)-1);)++k')

Mniej golfa

n=>{
  g=(a,b)=>b?g(b,a%b):a
  p=(a,b,c)=>{ 
    for(r=1;b--;)
      r=r*a%c
    return r
  }
  c=[for(_ of Array(i=n)) if(g(i--,n)<2) i+1]
  for(k=1;c.some(x=>p(x,k,n)-1);)
    ++k
  return k
} 
edc65
źródło
rekursywny modpow jest krótszy:p=(a,b,c)=>b?a*p(a,b-1,c)%c:1;
Olivier Grégoire,
1

Jawa, 209 207 202 194 192 bajty

Kod (96 bajtów):

n->{for(int x,k=1,a;;k++){for(a=1,x=0;++x<=n&&a<2;)a=g(x,n)<2?p(x,k,n):1;if(a<2||n<2)return k;}}

dodatkowe funkcje (96 bajtów):

int g(int a,int b){return b<1?a:g(b,a%b);}int p(int n,int p,int m){return p<2?n:n*p(n,p-1,m)%m;}

Testy i bez golfa

import java.util.Arrays;
import java.util.function.IntUnaryOperator;

public class Main2 {

  static int g(int a,int b) { // recursive gcd
    return b < 1
        ? a
        : g(b,a%b);
  }

  static int p(int n, int p, int m) { // recursive modpow
    return p < 2
      ? n
      : n * p(n, p - 1, m) % m;
  }

  public static void main(String[] args) {

    IntUnaryOperator f = n -> {
      for(int x,k=1,a;;k++) { // for each k
        for(a=1,x=0;++x<=n&&a<2;) // for each x
          a=g(x,n)<2?p(x,k,n):1; // compute modpow(x,k,n) if g(x,n)
        if(a<2||n<2) // if all modpow(x,k,n)=1. Also check for weird result for n=1.
          return k;
      }
    };

    Arrays.stream(new int[]{1, 2, 3, 10, 35, 101, 530, 3010, 6511, 10000})
        .map(f)
        .forEach(System.out::println);
  }
}

Notatki

  • użycie abycia an intjest krótsze niż gdybym musiał użyć a booleando wykonania moich testów.
  • Tak, dla valueOfwszystkich nowych jest krótszy BigIntegerniż utworzenie osobnej funkcji (jest ich 5, a ONEstała jest gratis).
  • Algorytm różni się od algorytmu @Master_ex ', więc nie jest to tylko gra w golfa. Ponadto ten algorytm jest znacznie mniej wydajny, ponieważ gcdjest obliczany wielokrotnie dla tych samych wartości.

Goli

  1. 209 -> 207 bajtów:
    • if(...)a=...; -> a=...?...:1;
    • a==1 -> a<2
  2. 207 -> 202 bajty
    • Pozbyłem się BigIntegerprzez golfa gcdi modPowdla int.
  3. 202 -> 194 bajty
    • zapętlanie modPow-> rekurencyjne
  4. 194 -> 192 bajty
    • ==1-> <2(wydaje się działać dla wszystkich przypadków testowych, nie wiem dla innych liczb).
Olivier Grégoire
źródło
Hej! Zauważyłem, że wynik nie jest oczekiwany. Zobacz pytanie dotyczące oczekiwanych rezultatów. Osobiście często piszę testy jednostkowe przed rozpoczęciem gry w golfa, to pomaga! Myślę, że problemem może być modPow na liczbach całkowitych, miałem również ten problem i dlatego na końcu użyłem BigInteger.
Master_ex,
Hmmm ... Jestem zaskoczony, że pozwalam na przeprowadzanie testów przy każdej zmianie. Sprawdzę, co jest nie tak.
Olivier Grégoire,
1
@Master_ex Naprawiłem to. Powrót do poprzedniej wersji jest w porządku.
Olivier Grégoire,
Uważam, że twoja rekurencyjna metoda modpow jest pcał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 do BigInteger(czyli Math.pow(3, 100)%101zwracane 60.0zamiast 1). Twoja implementacja jest na to odporna, ponieważ wykonuje modyfikację w każdej iteracji. Nadal jednak występuje błąd. Dla dużych m pmoże nadal zwracać złe wyniki. Również z powodu rekurencji StackOverflowErrormoże łatwo wystąpić w przypadku dużych danych wejściowych z domyślnym rozmiarem stosu.
Master_ex,
@Master_ex Tak, jest to konsekwencja ograniczenia inttypó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. StackOverflowErrormoż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.
Olivier Grégoire
1

Java8 38 19 + 287 295 253 248 241 = 325 333 272 267 260 bajtów

BigInteger B(int i){return new BigInteger(""+i);}int c(int...k){int n=k[0];for(k[0]=1;n>1&!java.util.stream.IntStream.range(0,n).filter(i->B(n).gcd(B(i)).equals(B(1))).allMatch(x->B(x).modPow(B(k[0]),B(n)).equals(B(1)));k[0]++);return k[0];}

Import, 19 bajtów

import java.math.*;

Wyjaśnienie

Jest to prosta implementacja. Współ-liczby pierwsze są obliczane w Set pi każda k-ta moc jest używana do sprawdzenia, czy wynosi ona 1 moduł.

Musiałem użyć z BigIntegerpowodu problemów z precyzją.

Stosowanie

public static void main(String[] args) {
    Carmichael c = new Carmichael();
    System.out.println(c.c(3)); // prints 2
}

Bez golfa

// returns the BigInteger representation of the given interger
BigInteger B(int i) {
    return new BigInteger(""+i);
}
// for a given integer it returns the result of the carmichael function again as interger
// so the return value cannot be larger
int c(int... k) {
    int n = k[0];
    // iterate k[0] until for all co-primes this is true: (x^n) mod n == 1, if n==1 skip the loop
    for (k[0]=1;n > 1 && !java.util.stream.IntStream.range(0, n)
                .filter(i -> B(n).gcd(B(i)).equals(B(1)))
                .allMatch(x -> B((int) x).modPow(B(k[0]), B(n)).equals(B(1)));k[0]++);
    return k[0];
}

Wszelkie sugestie dotyczące gry w golfa są mile widziane :-)

Aktualizacja

  • Brak elementów poza funkcjami utrzymującymi stan
  • Postępował zgodnie z radą Oliviera Grégoire'a i oszczędził 1 bajt B()
  • Usunięto k()metodę i pzestaw (współrzędnych).
  • Usunięto nie wymagane rzutowanie na int.
  • Dodano zmienne i używaj zamiast zamiast.
Master_ex
źródło
Czy możesz mieć wersję bez golfa (z łamaniem linii, komentarzami tu i tam itd.)
OldBunny2800
@ OldBunny2800: Tak, jasne. Jednak zrobię to dzisiaj, ponieważ teraz jestem zajęty!
Master_ex
@ OldBunny2800: Dodałem wersję bez golfa :-)
Master_ex
Hmmm ... Nie jestem pewien, czy to się liczy, ponieważ nie jest to ani funkcja, ani program. Jeśli jest to funkcja, istnieją poza nią elementy, które utrzymują ten stan, co czyni ją de facto metodą (funkcja jest czystym wejściem -> wyjściem bez stanu zewnętrznego), jeśli jest to program, brakuje całej metody głównej. Jeśli moje interpretacje są niepoprawne, proszę o informację! Myślę, że lepiej jest dołączyć k(int)do pętli, ponieważ jest to jedna linijka i można to zrobić. Dodatkowo w cmetodzie można również wprowadzić stałą O. Myślę, że robiąc to, wygrasz bajty!
Olivier Grégoire,
Konkretnie, 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żywasz Odwa razy, zamień na, B(1)aby golić bajty.
Olivier Grégoire,
1

Java, 165 163 158 152 143 bajty

int l(int n){int k=1,x,a,b,t,d=1;for(;d>0;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;b>0;b=a%b,a=t)t=b;for(t=b=1;b++<=k;t=t*x%n);}return k;}

Kolejny port moim realizacji C .

Wypróbuj na Ideone

sufitowy
źródło
1

C ++, 208 200 149 144 140 134 bajtów

[](int n){int k=1,x,a,b,t,d=1;for(;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;};

Port mojego realizacji C .

Wypróbuj na Ideone

sufitowy
źródło
0

Rakieta 218 bajtów

(λ(n)(let((fl #f)(cl(for/list((i n) #:when(coprime? n i))i)))(for/sum((k(range 1 n))#:break fl)(set! fl #t)
(for((i(length cl))#:break(not fl))(when(not(= 1(modulo(expt(list-ref cl i)k)n)))(set! fl #f)))(if fl k 0))))

Wersja bez golfa:

(require math)
(define f
  (λ(n)
    (let ((fl #f)
          (cl (for/list ((i n) #:when (coprime? n i))
                i)))
             (for/sum ((k (range 1 n)) #:break fl)
               (set! fl #t)
               (for ((i (length cl)) #:break (not fl))
                 (when (not (= 1 (modulo (expt (list-ref cl i) k) n)))
                   (set! fl #f)))
               (if fl k 0)))))

Testowanie:

(f 2) 
(f 3)
(f 10)
(f 35)
(f 101)
(f 530)
(f 3010)
(f 6511)
(f 10000)

Wydajność:

1
2
4
12
100
52
84
3056
500
rnso
źródło
0

C, 278 276 272 265 256 243 140 134 125 bajtów

k,x,a,b,t,d;l(n){for(k=d=1;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;}

Wykorzystuje on wolny modułowy algorytm potęgowania, zbyt często oblicza GCD i nie przecieka pamięci!

Nie golfowany:

int gcd( int a, int b ) {
  int t;
  while( b ) {
    t = b;
    b = a%b;
    a = t;
  }
  return a;
}
int pw(int a,int b,int c){
  int t=1;
  for( int e=0; e<b; e++ ) {
    t=(t*a)%c;
  }
  return t;
}
int carmichael(int n) {
  int k = 1;
  for( ;; ) {
    int done = 1;
    for( int x=1; x<n; x++ ) {
      if( gcd(x,n)==1 && pw(x,k,n) != 1 ) {
        done = 0;
        k++;
      }
    }
    if( done ) break;
  }
  return k;
}

Wypróbuj na Ideone

sufitowy
źródło
0

Axiom 129 bajtów

c(n)==(r:=[x for x in 1..n|gcd(x,n)=1];(v,k):=(1,1);repeat(for a in r repeat(v:=powmod(a,k,n);v~=1=>break);v<=1=>break;k:=k+1);k)

mniej golfa

cml(n)==
 r:=[x for x in 1..n|gcd(x,n)=1];(v,k):=(1,1)
 repeat 
   for a in r repeat(v:=powmod(a,k,n);v~=1=>break)
   v<=1=>break
   k:=k+1
 k

wyniki

(3) -> [i,c(i)] for i in [1,2,3,10,35,101,530,3010,6511,10000]
   Compiling function c with type PositiveInteger -> PositiveInteger

   (3)
   [[1,1], [2,1], [3,2], [10,4], [35,12], [101,100], [530,52], [3010,84],
    [6511,3056], [10000,500]]
                                             Type: Tuple List PositiveInteger
RosLuP
źródło