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
Antworten:
Mathematica, 16 Bytes
Gut...
quelle
Python,
767367 BytesProbieren 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.
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 .
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 λ ( pα ) - 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α ) = (p - 1) pα - 1, wenn p> 2 oder α <3, und dass λ ( pα ) = pα - 2, wenn nicht. In allen Fällen ist λ ( pα ) ≥ pα - 2 ≥ 2α - 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
any
kehrt 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) .quelle
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.)Mathematica ohne eingebauten,
5857 BytesVielen 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:
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.
quelle
EulerPhi
, umLCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&
für 57 Bytes zu erhalten.Als schädlich eingestufte Vorlagen , 246 Byte
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).quelle
Haskell,
5756 Bytesquelle
Gelee, 2 Bytes
Vielen Dank für die eingebaute, @Lynn
quelle
Pyth -
191817 BytesEin Byte gespart dank @TheBikingViking.
Gerade herauf rohe Kraft.
Probieren Sie es hier online aus .
quelle
f!smt
ist ein Byte kürzer.Rubin,
5956 Bytesquelle
J
2827 BytesDie 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 2 ≤ p 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.
Erläuterung
quelle
Eigentlich
3028251926 BytesDie Carmichael - Funktion,
λ(n)
won = 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 Primzahlpotenzenp_i**k_i
dass teilen sich inn
. Da für jede Primzahl, mit Ausnahme der Primzahl2
, die Carmichael-Funktion der Euler-Totientenfunktion entsprichtλ(n) == φ(n)
, verwenden wirφ(n)
stattdessen. Für den speziellen Fall ,2**k
wok ≥ 3
, überprüfen wir nur , wenn2**3 = 8
teilt sich inn
zu 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!
Ungolfing
quelle
totient
undgcd
eingebauten. Das wäre kürzer, wennlcm
ich es direkt hätte, aber ich habe nichts dagegen und das würde sowieso höchstens 4 Bytes kosten.JavaScript (ES6),
143135 ByteBearbeiten: 8 Bytes dank Neil gespeichert
Eine Implementierung mit funktionaler Programmierung.
Ungolfed und kommentiert
Demo
Obwohl es für
6511
und funktioniert10000
, werde ich sie hier nicht einschließen, da es ein bisschen langsam ist.quelle
0..n-1
reicht 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
Ruby,
101869190 BytesEin Ruby Port von meiner Antwort . Golfvorschläge sind willkommen.
Bearbeiten: -4 Bytes vom Entfernen,
a
aber +9 Bytes vom Beheben eines Fehlers, der1
zurückgegeben wurdenil
. -1 Byte dank Cyoce.Ungolfing
quelle
a=
. Leider kehrst dunil
fü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.(n%8<1?n/2:n).prime_division...
Speichert weitere 2 Bytes.a
ist ein Überbleibsel eines früheren Golfversuchs . Vielen Dank für die Erinnerung übera
und für die Hinweise1
..reduce :lcm
anstelle von verwenden.reduce(:lcm)
.JavaScript (ES 2016) 149
Nach JS portierte Python-Referenzimplementierung. Einige ausgefallene Pyhton-Funktionen fehlen in js, wie
gcd
undpow
, und das Array-Verständnis ist in ES 6 nicht Standard. Dies funktioniert in Firefox.Weniger golfen
quelle
p=(a,b,c)=>b?a*p(a,b-1,c)%c:1;
Java,
209207202194192 BytesCode (96 Bytes):
Zusatzfunktionen (96 Bytes):
Testing & ungolfed
Anmerkungen
a
anint
ist kürzer als wenn ich a benutzen müssteboolean
, um meine tests durchzuführen.valueOf
alle neuenBigInteger
als eine separate Funktion erstellen (es gibt 5, plus dieONE
Konstante ist ein Freebie).gcd
immer wieder für dieselben Werte berechnet wird.Rasiert
if(...)a=...;
->a=...?...:1;
a==1
->a<2
BigInteger
durch Golfengcd
undmodPow
für losint
.modPow
-> rekursiv==1
-><2
(scheint für alle Testfälle zu funktionieren, weiß nicht für andere Nummern.)quelle
p
ziemlich 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 zuBigInteger
(dhMath.pow(3, 100)%101
zurückgekehrt60.0
statt1
) 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ßenm
p
kann es dennoch zu falschen Ergebnissen kommen. Aufgrund der RekursionStackOverflowError
kann es bei großen Eingaben mit der Standardstapelgröße leicht vorkommen.int
Typen. 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.StackOverflowError
kann 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.Java8
3819 +287295253248241 =325333272267260 BytesImporte, 19 Bytes
Erläuterung
Es ist eine einfache Implementierung. Die Ko-Primzahlen werden in der
Set p
und jeder k-ten Potenz berechnet , um zu überprüfen, ob sie 1 Modulo n entspricht.Ich musste
BigInteger
wegen Präzisionsproblemen verwenden.Verwendung
Ungolfed
Anregungen zum Golfspielen sind willkommen :-)
Aktualisieren
B()
k()
Verfahren undp
(Co-Primzahlen) Sets.quelle
k(int)
in die Schleife aufzunehmen, da es ein Einzeiler ist und getan werden kann. Außerdem kann die Konstante O auch in diec
Methode eingefügt werden. Ich denke, Sie werden Bytes gewinnen, indem Sie dies tun!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 SieO
zweimal, ersetzen durchB(1)
, um Bytes zu rasieren.Java,
165 163 158 152143 BytesEin weiterer Port meiner C-Implementierung .
Probieren Sie es auf Ideone
quelle
C ++,
208 200 149 144 140134 BytesEin Port meiner C-Implementierung .
Probieren Sie es auf Ideone
quelle
Schläger 218 Bytes
Ungolfed-Version:
Testen:
Ausgabe:
quelle
C
278 276 272 265 256 243 140 134125 BytesDies verwendet einen langsamen modularen Exponentiationsalgorithmus, berechnet die GCD zu oft und verliert keinen Speicher mehr!
Ungolfed:
Probieren Sie es auf Ideone
quelle
Axiom 129 Bytes
weniger golfen
Ergebnisse
quelle