Berechnen Sie die Carmichael-Funktion

36

Aufgabenbeschreibung

In der Zahlentheorie nimmt die Carmichael-Funktion  λ eine positive ganze Zahl  n und gibt die am wenigsten positive ganze Zahl k zurück, so dass die k- te Potenz jedes ganzzahligen Coprimes zu n gleich 1 Modulo n ist .

Bei einer positiven ganzen Zahl n muss Ihre Lösung λ (n) berechnen . Der kürzeste Code in Bytes gewinnt.

Ihr Programm sollte theoretisch für beliebig große Eingaben funktionieren, muss aber nicht effizient sein.

Tipps

Die Sequenz von allen λ (n) ist OEIS A002322 .

Eine ungolfed Python-Implementierung würde so aussehen

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

(In Python wird pow(A, B, C)effizient berechnet pow(A, B) % C.)

Testfälle

Input    Output
1        1
2        1
3        2
10       4
35       12
101      100
530      52
3010     84
6511     3056
10000    500
Lynn
quelle
Was heißt hier theoretisch ? Kann ich davon ausgehen, dass der Eingang n in eine 16-Bit-Ganzzahl passt? Kann ich annehmen, dass n ^ λ (n) in ein Double passt?
Dennis
2
Ja und ja, würde ich sagen. Wie in, die theoretisch beinhaltet so tun , als ob Ihre einheimischen Typen beliebig genau und groß sind (ich dachte, das war Konsens, aber ich bin nicht sicher).
Lynn

Antworten:

47

Mathematica, 16 Bytes

CarmichaelLambda

Gut...

Martin Ender
quelle
38
..... Ja wirklich. ._.
Acrolith
12
Ich mag dich nicht mathematica
downrep_nation
29

Python, 76 73 67 Bytes

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

Probieren Sie es online!

Ein weiteres Byte könnte durch Rückgabe von True anstelle von 1 gespeichert werden .

Alternative Implementierung

Mit dem gleichen Ansatz gibt es auch die folgende Implementierung von @feersum, die keine Listenverständnisse verwendet.

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)

Es ist zu beachten, dass diese Implementierung eine O (n & lgr; (n) ) - Zeit erfordert . Die Effizienz könnte drastisch verbessert werden, während der Score tatsächlich auf 66 Bytes verringert wird , aber die Funktion würde True für Eingabe 2 zurückgeben .

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)

Hintergrund

Definitionen und Notation

Alle verwendeten Variablen bezeichnen ganze Zahlen. n , k und α bezeichnen positive ganze Zahlen; und p bezeichnet eine positive Primzahl .

a | b wenn b durch a teilbar ist , dh wenn q so ist, dass b = qa .

a ≡ b ( mod m) wenn a und b den gleichen Rest modulo m haben , dh wenn m | a - b .

λ (n) ist das kleinste k, so dass a k ≡ 1 ( mod n) - dh so, dass n | a k - 1 - für alle a , die koprime zu n sind .

f (n) ist das kleinste k, so dass a 2k + 1 ≤ a k + 1 ( mod n) - dh so, dass n | a k + 1 (a k - 1) - für alle a .

λ (n) ≤ f (n)

Fixiere n und lasse a zu n koprimieren .

Nach der Definition von f , n | a f (n) + 1 (a f (n) - 1) . Da ein und n keinen gemeinsamen Primfaktor hat, auch nicht ein f (n) + 1 und n , die das bedeutet , n | a f (n) - 1 .

Da λ (n) die kleinste ganze Zahl k ist, so dass n | a k - 1 für alle ganzen Zahlen a , die zu n koprime sind , folgt λ (n) ≤ f (n) .

λ (n) = f (n)

Da wir bereits die Ungleichung λ (n) ≤ f (n) festgestellt haben, reicht es aus, zu überprüfen, dass k = λ (n) die Bedingung erfüllt, die f definiert , dh dass n | a λ (n) +1 (a λ (n) - 1) für alle a . Zu diesem Zweck legen wir fest, dass p α | eine λ (n) + 1 (a λ (n) - 1) , wenn p & agr; | n .

λ (k) | λ (n) wann immer k | n ( Quelle ), also (a & lgr; (k) - 1) (a & lgr; (n) - & lgr; (k) + a & lgr; (n) - 2 & lgr; (k) + & lgr; + a & lgr; (k) + 1) = a λ (n) - 1 und daher a λ (k) - 1 | a λ (n) - 1 | eine λ (n) + 1 (a λ (n) - 1) .

Wenn a und p α Coprime sind, ist nach der Definition von λ und dem oben Gesagten p α | a λ ( ) - 1 | eine λ (n) + 1 (a λ (n) - 1) folgt, wie gewünscht.

Wenn a = 0 , dann ist a λ (n) + 1 (a λ (n) - 1) = 0 , was durch alle ganzen Zahlen teilbar ist.

Schließlich müssen wir den Fall betrachten, in dem a und p α einen gemeinsamen Primfaktor haben. Da p eine Primzahl ist, impliziert dies, dass p | a . Carmichaels Theorem legt fest, dass λ ( ) = (p - 1) pα - 1, wenn p> 2 oder α <3, und dass λ ( ) = pα - 2, wenn nicht. In allen Fällen ist λ ( ) ≥ pα - 22α - 2 > α - 2 .

Daher ist & lgr; (n) + 1 ≥ & lgr; (p & agr; ) + 1> & agr; - ​​1 , so dass & lgr; (n) + 1 ≥ & agr; und p & agr; | p λ (n) +1 | a λ (n) +1 | eine λ (n) + 1 (a λ (n) - 1) . Damit ist der Beweis abgeschlossen.

Wie es funktioniert

Während die Definitionen von f (n) und λ (n) alle möglichen Werte von a berücksichtigen , ist es ausreichend, diejenigen zu testen, die in [0, ..., n - 1] liegen .

Wenn f (n, k) aufgerufen wird, berechnet es ein k + 1 (a k - 1)% n für alle Werte von a in diesem Bereich, der genau dann 0 ist, wenn n | a k + 1 (a k - 1) .

Wenn alle berechneten Reste gleich null sind, k = λ (n) und anykehrt Falsch , so f (n, k) liefert 1 .

Wenn andererseits k <λ (n) ist , 1-any(...)wird 0 zurückgegeben , so dass f rekursiv mit einem inkrementierten Wert von k aufgerufen wird . Der führende -~erhöht den Rückgabewert von f (n, k + 1) , also addieren wir 1 zu f (n, λ (n)) = 1 einmal für jede ganze Zahl in [1, ..., λ (n) - 1 ] . Das Endergebnis ist somit λ (n) .

Dennis
quelle
Sie können mindestens 4 mit Rekursion anstelle eines Listenverständnisses 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)speichern : (Fügen Sie ein Byte hinzu, wenn Sie nicht möchten, dass es n ** λ (n) Mal dauert.)
Feersum
1
Vielen Dank! In der Zwischenzeit habe ich eine Verbesserung an meinem Algorithmus gefunden, die den Vorteil der Rekursion aufzuheben scheint, anstatt ein Listenverständnis zu verwenden.
Dennis
14

Mathematica ohne eingebauten, 58 57 Bytes

Vielen Dank an Martin Ender, der einen Fehler entdeckt und mir dann die Bytes erspart hat, die zur Behebung des Fehlers benötigt wurden!

Vielen Dank an Meilen für das Sparen von 1 Byte! (Was mir wie 2 erschien)

Built-Ins sind völlig in Ordnung ... aber für diejenigen, die es ohne brachiale Gewalt implementieren möchten, hier eine Formel für die Carmichael-Funktion:

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

Wenn p eine Primzahl ist, ist die Carmichael-Funktion λ (p ^ r) gleich φ (p ^ r) = (p-1) * p ^ (r-1) - außer in diesem Fall, wenn p = 2 und r≥3 ist es ist die Hälfte davon, nämlich 2 ^ (r-2).

Und wenn die Primzahlfaktorisierung von n gleich p1 ^ r1 * p2 ^ r2 * ... ist, dann ist λ (n) gleich dem kleinsten gemeinsamen Vielfachen von {λ (p1 ^ r1), λ (p2 ^ r2), .. .}.

Die Laufzeit ist einen Augenblick länger als die ganze Zahl.

Greg Martin
quelle
Sie können verwenden EulerPhi, um LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&für 57 Bytes zu erhalten.
Meilen
@ Meilen schön entdeckt! Ich zähle 56 Bytes, können Sie das überprüfen?
Greg Martin
Ja, es sind 57 Bytes .
Meilen
klar, ich versuche sogar, mein Zählen Golf ....: /
Greg Martin
12

Als schädlich eingestufte Vorlagen , 246 Byte

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

Eine unbenannte Funktion (nicht, dass es benannte Funktionen gibt).

Dies ist ein vergessener Teil von mir, der von einem C ++ - Compiler interpretiert wird, der Vorlagen instanziiert. Mit der voreingestellten maximalen Vorlagentiefe von g++kann es λ (35), aber nicht λ (101) (die verzögerte Auswertung macht die Sache noch schlimmer).

Feersum
quelle
10

Haskell, 57 56 Bytes

f n=[k|k<-[1..],and[mod(m^k)n<2|m<-[1..n],gcd m n<2]]!!0
Dianne
quelle
8

Gelee, 2 Bytes

Æc

Vielen Dank für die eingebaute, @Lynn

Dianne
quelle
31
............. ._.
Maltysen
10
Ich verstehe nie den Sinn, solche lächerlich spezifischen Einbauten zu implementieren.
Fatalize
31
Dies ist fast eine Ergänzung zu der Sprache, die speziell für diese Herausforderung entwickelt wurde. Commit von Lynn vor 2 Tagen, Herausforderung von @Lynn heute
edc65
5
@ edc65 Ganz zu schweigen davon, dass dieses eingebaute Modul außerhalb dieser Herausforderung und ihrer Ableitungen so gut wie nutzlos ist.
Fatalize
3
Nun, die Carmichael-Funktion ist in der Zahlentheorie wichtig (wie die derzeit beste Antwort zeigt), daher würde ich sie nicht als nutzlos bezeichnen.
Greg Martin
6

Pyth - 19 18 17 Bytes

Ein Byte gespart dank @TheBikingViking.

Gerade herauf rohe Kraft.

f!sm*t.^dTQq1iQdQ

Probieren Sie es hier online aus .

Maltysen
quelle
f!smtist ein Byte kürzer.
TheBikingViking
@TheBikingViking oh, ja danke
Maltysen
Tut mir in den Augen weh, wie zum Teufel ist diese Python ..? Liebte es trotzdem haha ​​:)
Yohan Obadia
6

Rubin, 59 56 Bytes

->x{a=1..x
a.detect{|k|a.all?{|y|x.gcd(y)>1||y**k%x<2}}}
m-chrzan
quelle
5

J 28 27 Bytes

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

Die Carmichael-Funktion ist λ ( n ) und die Totientenfunktion ist φ ( n ).

Verwendet die Definition mit λ ( p k ) = φ ( p k ) / 2, wenn p = 2 und k > 2, sonst φ ( p k ). Dann ist für allgemein 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 )] .

Verwendung

Zusätzliche Befehle zum Formatieren mehrerer Ein- / Ausgaben.

   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

Erläuterung

[:*./@(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
Meilen
quelle
Dies gibt die falsche Antwort für 10000 (1000 statt der richtigen 500) und in der Tat für jedes Vielfache von 8. 2 ist eine eigenartige Primzahl, und λ (2 ^ a) = 2 ^ {a-2} (nicht 2 ^ { a-1}) wenn a≥3.
Greg Martin
Vielen Dank, dass Sie das verstanden haben. Ich kann anscheinend nicht einmal meine eigene Ausgabe lesen
Meilen vom
du bist manchmal nicht allein ... :)
Greg Martin
5

Eigentlich 30 28 25 19 26 Bytes

Die Carmichael - Funktion, λ(n)wo n = p_0**k_0 * p_1**k_1 * ... * p_a**k_a, wie der kleinste gemeinsame Vielfache (LCM) definiert ist , der λ(p_i**k_i)für die maximalen Primzahlpotenzen p_i**k_idass teilen sich in n. Da für jede Primzahl, mit Ausnahme der Primzahl 2, die Carmichael-Funktion der Euler-Totientenfunktion entspricht λ(n) == φ(n), verwenden wir φ(n)stattdessen. Für den speziellen Fall , 2**kwo k ≥ 3, überprüfen wir nur , wenn 2**3 = 8teilt sich in nzu Beginn des Programms, und durch 2 , wenn es der Fall ist.

Leider verfügt Actually derzeit nicht über ein eingebautes LCM, daher habe ich ein Brute-Force-LCM erstellt. Golfvorschläge sind willkommen. Probieren Sie es 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
quelle
2
Eigentlich habe ich keine Ahnung, wie Sie das in nur 19 Bytes gemacht haben.
Buffer Over Read
@TheBitByte Bei Verwendung der totientund gcdeingebauten. Das wäre kürzer, wenn lcmich es direkt hätte, aber ich habe nichts dagegen und das würde sowieso höchstens 4 Bytes kosten.
Sherlock9
1
Die Behauptung, dass lcm (* a) = product (* a) / gcd (* a) ist wahr, wenn * a eine Liste von genau zwei Zahlen ist; Bei längeren Listen ist dies jedoch im Allgemeinen falsch (Beispiel: Wenn * a {6,10,15} ist, wird 900 anstelle der richtigen Antwort von 60 ausgegeben). [Im Übrigen ist es falsch, dass * a auch eine Liste mit einer Nummer ist!] Und Sie können überprüfen, ob Sie für mehr als die Hälfte der im OP aufgelisteten Testfälle die falsche Antwort erhalten.
Greg Martin
@ GregMartin Vielen Dank für die Heads-up. Fest.
Sherlock9
4

JavaScript (ES6), 143 135 Byte

Bearbeiten: 8 Bytes dank Neil gespeichert

Eine Implementierung mit funktionaler Programmierung.

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

Ungolfed und kommentiert

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)

Demo

Obwohl es für 6511und funktioniert 10000, werde ich sie hier nicht einschließen, da es ein bisschen langsam ist.

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
quelle
1
JS tun können , 0..n-1reicht ganz einfach: [...Array(n).keys()]. Dies erfordert nicht nur einen, sondern zwei Sonderfälle, aber ich bin immer noch voraus: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 Bytes

Ein Ruby Port von meiner Antwort . Golfvorschläge sind willkommen.

Bearbeiten: -4 Bytes vom Entfernen, aaber +9 Bytes vom Beheben eines Fehlers, der 1zurückgegeben wurde nil. -1 Byte dank 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
quelle
Das brauchst du nicht a=. Leider kehrst du nilfür n = 1 zurück :(. (n.prime_division<<[2,1])Behebt das. Ich bin mir nicht sicher, ob es einen besseren Weg zum Golfen gibt.
m-chrzan
(n%8<1?n/2:n).prime_division...Speichert weitere 2 Bytes.
m-chrzan
@ m-chrzan aist ein Überbleibsel eines früheren Golfversuchs . Vielen Dank für die Erinnerung über aund für die Hinweise 1.
Sherlock9
Sie können ein Byte speichern, indem Sie .reduce :lcmanstelle von verwenden .reduce(:lcm).
Cyoce
1

JavaScript (ES 2016) 149

Nach JS portierte Python-Referenzimplementierung. Einige ausgefallene Pyhton-Funktionen fehlen in js, wie gcdund pow, und das Array-Verständnis ist in ES 6 nicht Standard. Dies funktioniert in Firefox.

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')

Weniger golfen

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
quelle
rekursiver modpow ist kürzer:p=(a,b,c)=>b?a*p(a,b-1,c)%c:1;
Olivier Grégoire
1

Java, 209 207 202 194 192 Bytes

Code (96 Bytes):

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

Zusatzfunktionen (96 Bytes):

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

Testing & ungolfed

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

Anmerkungen

  • die nutzung von aan intist kürzer als wenn ich a benutzen müsste boolean, um meine tests durchzuführen.
  • Ja, es ist kürzer valueOfalle neuen BigIntegerals eine separate Funktion erstellen (es gibt 5, plus die ONEKonstante ist ein Freebie).
  • Der Algorithmus unterscheidet sich vom Algorithmus von @Master_ex, daher handelt es sich nicht nur um ein Golf-Repost. Außerdem ist dieser Algorithmus viel weniger effizient, da er gcdimmer wieder für dieselben Werte berechnet wird.

Rasiert

  1. 209 -> 207 Bytes:
    • if(...)a=...; -> a=...?...:1;
    • a==1 -> a<2
  2. 207 -> 202 Bytes
    • Wurde BigIntegerdurch Golfen gcdund modPowfür los int.
  3. 202 -> 194 Bytes
    • Schleife modPow-> rekursiv
  4. 194 -> 192 Bytes
    • ==1-> <2(scheint für alle Testfälle zu funktionieren, weiß nicht für andere Nummern.)
Olivier Grégoire
quelle
Hallo! Mir ist aufgefallen, dass die Ausgabe nicht die erwartete ist. Siehe die Frage für die erwarteten Ergebnisse. Persönlich schreibe ich oft Unit-Tests, bevor ich anfange, meinen Code zu spielen. Das hilft! Ich vermute, dass das Problem der ModPow auf ganzen Zahlen sein könnte, ich hatte auch dieses Problem und deshalb habe ich am Ende BigInteger verwendet.
Master_ex
Hmmm ... ich bin überrascht, dass ich meine Tests bei jeder Änderung laufen lasse. Ich werde nachsehen, was los ist.
Olivier Grégoire
1
@Master_ex Ich habe es behoben. Zur vorherigen Version zurückzukehren ist in Ordnung.
Olivier Grégoire
Ich finde deine rekursive modpow Methode pziemlich clever. Anfangs habe ich auch versucht, nur Ganzzahlen zu verwenden, aber wie ich in meiner Antwort erwähnt habe, hatte ich Präzisionsprobleme und deshalb bin ich zu BigInteger(dh Math.pow(3, 100)%101zurückgekehrt 60.0statt 1) gewechselt. Ihre Implementierung ist dagegen immun, da sie den Mod in jeder Iteration ausführt. Es ist jedoch immer noch ein Fehler aufgetreten. Bei großen m pkann es dennoch zu falschen Ergebnissen kommen. Aufgrund der Rekursion StackOverflowErrorkann es bei großen Eingaben mit der Standardstapelgröße leicht vorkommen.
Master_ex
@Master_ex Ja, das ist eine Folge der Beschränkung auf intTypen. Ich könnte longs anstelle von ints verwenden, das wären 8 zusätzliche Bytes. Aber aus meiner Sicht sind alle Testfälle gültig, also lasse ich es so. StackOverflowErrorkann passieren, aber so funktioniert rekursiv. Es gibt Methoden, um die Anzahl der Stapel auf 32 zu begrenzen, diese verwenden jedoch sehr viel mehr Bytes. Diese Implementierung ist fragil, ja, Sie haben vollkommen recht. Aber es ist stark genug für die Testfälle.
Olivier Grégoire
1

Java8 38 19 + 287 295 253 248 241 = 325 333 272 267 260 Bytes

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

Importe, 19 Bytes

import java.math.*;

Erläuterung

Es ist eine einfache Implementierung. Die Ko-Primzahlen werden in der Set pund jeder k-ten Potenz berechnet , um zu überprüfen, ob sie 1 Modulo n entspricht.

Ich musste BigIntegerwegen Präzisionsproblemen verwenden.

Verwendung

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

Ungolfed

// 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];
}

Anregungen zum Golfspielen sind willkommen :-)

Aktualisieren

  • Keine Elemente außerhalb der Funktionen, die den Status beibehalten
  • Befolgte den Rat von Olivier Grégoire und sparte 1 Byte von B()
  • Entfernt , um das k()Verfahren und p(Co-Primzahlen) Sets.
  • Nicht benötigtes Casting auf int entfernt.
  • Varags hinzugefügt und stattdessen für verwenden.
Master_ex
quelle
Können Sie eine ungolfed Version haben (mit Zeilenumbrüchen, Kommentare hier und da, etc.)
OldBunny2800
@ OldBunny2800: Ja, sicher. Aber ich mache es später heute, weil ich jetzt beschäftigt bin!
Master_ex
@ OldBunny2800: Ich habe eine ungolfed Version hinzugefügt :-)
Master_ex
Hmmm ... Ich bin mir nicht sicher, ob dies zählt, da es sich weder um eine Funktion noch um ein Programm handelt. Wenn es sich um eine Funktion handelt, gibt es Elemente außerhalb davon, die den Status beibehalten, sodass es sich um eine De-facto-Methode handelt (Funktion ist reine Eingabe-> Ausgabe ohne externen Status). Wenn es sich um ein Programm handelt, fehlt die gesamte Hauptmethode. Wenn meine Interpretationen falsch sind, sagen Sie es mir bitte! Ich denke, es ist besser, k(int)in die Schleife aufzunehmen, da es ein Einzeiler ist und getan werden kann. Außerdem kann die Konstante O auch in die cMethode eingefügt werden. Ich denke, Sie werden Bytes gewinnen, indem Sie dies tun!
Olivier Grégoire
Konkret while(n>1&&!p.stream().allMatch(x->B((int)x).modPow(B(k), B(n)).equals(O)))Rasuren Bytes und behebt die Probleme , die ich erwähnt , wenn Sie den Satz und die Konstante wieder in das Verfahren setzen. Außerdem verwenden Sie Ozweimal, ersetzen durch B(1), um Bytes zu rasieren.
Olivier Grégoire
1

Java, 165 163 158 152 143 Bytes

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

Ein weiterer Port meiner C-Implementierung .

Probieren Sie es auf Ideone

Ceilingcat
quelle
1

C ++, 208 200 149 144 140 134 Bytes

[](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;};

Ein Port meiner C-Implementierung .

Probieren Sie es auf Ideone

Ceilingcat
quelle
0

Schläger 218 Bytes

(λ(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))))

Ungolfed-Version:

(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)))))

Testen:

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

Ausgabe:

1
2
4
12
100
52
84
3056
500
rnso
quelle
0

C 278 276 272 265 256 243 140 134 125 Bytes

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

Dies verwendet einen langsamen modularen Exponentiationsalgorithmus, berechnet die GCD zu oft und verliert keinen Speicher mehr!

Ungolfed:

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

Probieren Sie es auf Ideone

Ceilingcat
quelle
0

Axiom 129 Bytes

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)

weniger golfen

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

Ergebnisse

(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
quelle