Einführung
Die Zahlentheorie steckt voller Wunder in Form unerwarteter Zusammenhänge. Hier ist einer von ihnen.
Zwei ganze Zahlen sind Co-Prime , wenn sie keine Faktoren gemeinsam andere als 1. Bei einer Zahl haben N , sollten alle Zahlen von 1 bis N . Ziehe zwei solcher Ganzzahlen nach dem Zufallsprinzip (alle Ganzzahlen haben die gleiche Wahrscheinlichkeit, bei jeder Ziehung ausgewählt zu werden; die Ziehungen sind unabhängig und werden ersetzt). Es sei p die Wahrscheinlichkeit, dass die beiden ausgewählten ganzen Zahlen Co-Primzahlen sind. Dann tendiert p zu 6 / π 2 ≈ 0,6079 ..., während N gegen unendlich tendiert.
Die Herausforderung
Der Zweck dieser Herausforderung besteht darin, p als Funktion von N zu berechnen .
Als Beispiel betrachten wir N = 4. Es gibt 16 mögliche Paare, die aus den ganzen Zahlen 1, 2, 3, 4 erhalten werden. 11 dieser Paare sind Co-Prime, nämlich (1,1), (1,2), (1,3), (1,4), (2,1), (3,1), (4,1 ), (2,3), (3,2), (3,4), (4,3). Somit ist p 11/16 = 0,6875 für N = 4.
Der genaue Wert von p muss mit mindestens vier Dezimalstellen berechnet werden . Dies impliziert, dass die Berechnung deterministisch sein muss (im Gegensatz zu Monte Carlo). Es muss sich aber nicht um eine direkte Aufzählung aller Paare wie oben handeln. Es kann jede Methode angewendet werden.
Funktionsargumente oder stdin / stdout können verwendet werden. Bei der Anzeige der Ausgabe können nachfolgende Nullen weggelassen werden. So kann zum Beispiel 0.6300
angezeigt werden als 0.63
. Es sollte als Dezimalzahl und nicht als Bruchzahl angezeigt werden (die Anzeige der Zeichenfolge 63/100
ist nicht zulässig).
Das Gewinnkriterium sind die wenigsten Bytes. Die Verwendung der integrierten Funktionen unterliegt keinen Einschränkungen.
Testfälle
Eingabe / Ausgabe (nur vier Dezimalstellen sind obligatorisch, wie oben angegeben):
1 / 1.000000000000000
2 / 0.750000000000000
4 / 0.687500000000000
10 / 0.630000000000000
100 / 0.608700000000000
1000 / 0.608383000000000
quelle
63/100
es sich um ein gültiges Literal handelt, das sich für die Berechnung eignet. (Langs ich spreche über: Faktor , Schläger )Antworten:
Gelee ,
128 BytesProbieren Sie es online!
Der folgende Binärcode funktioniert mit dieser Version des Jelly-Interpreters .
Idee
Es ist klar, dass die Anzahl der Paare (j, k), so dass j ≤ k und j und k Co-Primzahlen sind, gleich der Anzahl der Paare (k, j) ist , die die gleichen Bedingungen erfüllen. Auch wenn j = k , ist j = 1 = k .
Um also die Anzahl der Co-Prim-Paare mit Koordinaten zwischen 1 und n zu zählen , genügt es, die Anzahl m der Paare (j, k) so zu berechnen , dass j ≤ k ist , und dann 2m - 1 zu berechnen .
Da schließlich die Eulersche Totientenfunktion φ (k) ergibt die Anzahl ganzer Zahlen zwischen zwischen 1 und K , die co-prim sind k , können wir berechnen , m als φ (1) + ... + φ (n) .
Code
quelle
Mathematica
4342 BytesDie vom Ursprung aus sichtbaren Gitterpunkte, von denen das folgende Bild stammt, haben sich als hilfreich erwiesen, um das Problem anhand der folgenden Fragen in Bezug auf einen bestimmten quadratischen Bereich des Einheitsgitters neu zu definieren:
Beispiele
Nachgestellte Nullen werden weggelassen.
Zeitliche Koordinierung
Das Timing in Sekunden geht der Antwort voraus.
quelle
Pyth -
1311 BytesTest Suite .
quelle
Mathematica,
4232 BytesAnonyme Funktion, verwendet einfache rohe Gewalt. Der letzte Fall dauert auf meinem Computer etwa 0,37 Sekunden. Erläuterung:
quelle
Count[Array[GCD,{#, #}],1,2]/#^2.&
Seien Sie mein Gast.Dyalog APL, 15 Bytes
Ziemlich einfach. Es ist ein monadischer Funktionszug. Iota ist die Zahl von 1 bis zur Eingabe, also nehmen wir das äußere Produkt mit gcd und zählen dann den Anteil der Einsen.
quelle
Oktave,
4947 BytesEinfach die Summe
gcd
aller Paare berechnen und zählen.quelle
kron
! Gute Idee!meshgrid
, aber dann habe ich gemerkt, dass ich dasselbe mitkron
Inline machen kann! (-> anonyme Funktion)JavaScript (ES6), 88 Byte
Erläuterung
Prüfung
Dauert eine Weile für große (
>100
) Werte vonn
.Code-Snippet anzeigen
quelle
Im Ernst, 15 Bytes
Hex Dump:
Probieren Sie es online
Ich werde mich nicht darum kümmern, es zu erklären, da es buchstäblich genau den gleichen Algorithmus verwendet wie Dennis 'Jelly-Lösung (obwohl ich es unabhängig abgeleitet habe).
quelle
J,
19BytesVerwendung:
Erläuterung:
Dennis 'Lösung gibt eine nette Erklärung, wie wir die Totientenfunktion verwenden können.
Probieren Sie es hier online aus.
quelle
Mathematica, 35 Bytes
Implementiert den @ Dennis-Algorithmus.
Berechnen Sie die Summe des Totienten (Euler-Phi-Funktion) über den Bereich von 1 bis zum Eingabewert. Multiplizieren Sie mit Gleitkomma zwei (mit vier Stellen Genauigkeit) und subtrahieren Sie eine. (Sie können die Genauigkeit erhöhen, indem Sie stattdessen "
2
" und "1`4
" verwenden.) Dies ist die Gesamtzahl der Coprime-Paare. Teilen Sie diese durch das Quadrat der Eingabe, um den gewünschten Bruch zu erhalten. Da es sich bei den beiden um eine ungefähre Zahl handelt, gilt dies auch für das Ergebnis.Testen (mit Timing-Daten in der linken Spalte, da mindestens einer von uns dies für interessant hält), mit der zugewiesenen Funktion,
f
damit die Testzeile leichter gelesen werden kann:Bearbeiten: Umfang des Eingabebereichs anzeigen (die Genauigkeit auf eins statt auf zwei ändern, da sonst die Ergebnisse eher eintönig werden) und andere dazu auffordern, dasselbe zu tun ...
RepeatedTiming[]
Führt die Berechnung mehrmals durch und nimmt einen Mittelwert der Zeiten, wobei versucht wird, Cold-Caches und andere Effekte zu ignorieren, die Timing-Ausreißer verursachen. Die asymptotische Grenze istFür Argumente> 10 ^ 4 können wir also einfach "0.6079" zurückgeben und die angegebenen Genauigkeits- und Genauigkeitsanforderungen erfüllen.
quelle
Julia, 95 Bytes
Nur der einfache Ansatz für den Moment; Ich werde bald auf kürzere / elegantere Lösungen eingehen. Dies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und einen Gleitkommawert zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.
Ungolfed:
quelle
collect
faules Objekt, um es zu nehmenlength
.length
keine Methode definiert ist, wie hier für den gefilterten Kombinationsiterator. Ähnlichendof
würde es nicht funktionieren, da es für diesen Typ keine Methode gibtgetindex
.range
gibt nicht dieselbe Art von Objekt zurück wiecombinations
. Letzterer gibt einen Iterator über Kombinationen zurück, die ein separater Typ ohne definiertelength
Methode sind. Sehen Sie hier . (Auch die:
Syntax wird vorgezogen, umrange
Bereiche zu konstruieren;)Salbei, 55 Bytes
Dank Sage Computing tauchen keine symbolischen Probleme mit dem Maschinen-Epsilon und den Gleitkommazahlen auf. Der Kompromiss ist, um der Ausgabeformatregel zu folgen, ein zusätzlicher Aufruf
n()
(der Dezimalnäherungsfunktion) erforderlich.Probieren Sie es online aus
quelle
MATL ,
2017 BytesDies verwendet die aktuelle Version (5.0.0) der Sprache.
Ansatz basiert auf der Antwort von @ flawr .
Bearbeiten (28. April 2015) : Probieren Sie es online! Nachdem diese Antwort gepostet wurde, wurde die Funktion
Y)
in umbenanntX:
. Der Link enthält diese Änderung.Beispiel
Erläuterung
Alte Antwort: 20 Bytes
Erläuterung
quelle
PARI / GP , 25 Bytes
Das Anonymisieren der Funktion würde ein Byte sparen, aber dann müsste
self
es insgesamt teurer werden.quelle
Faktor
120113 BytesIch habe Golf gespielt und kann es nicht kürzer machen.
Übersetzung von: Julia .
Das Beispiel wird für die ersten 5 Testfälle ausgeführt (ein Wert von 1000 bewirkt, dass der Editor eingefroren wird, und ich kann mich nicht mehr darum kümmern, eine ausführbare Datei zu kompilieren):
quelle
Samau , 12 Bytes
Haftungsausschluss: Kein Wettbewerb, da ich die Sprache nach dem Posten der Frage aktualisiert habe.
Hex-Dump (Samau verwendet CP737-Codierung):
Verwenden Sie denselben Algorithmus wie Dennis 'Antwort in Jelly.
quelle
Python2 / Pypy, 178 Bytes
Die
x
Datei:Laufen:
Der Code zählt die Co-Prim-Paare
(n,m) for m<n
zweimal (c+=2
). Dies ignoriert,(i,i) for i=1..n
was bis auf eine Ausnahme in Ordnung ist(1,1)
, und wird daher durch Initialisieren des Zählers mit1
(1.0
zur Vorbereitung auf die Schwebeteilung später) zur Kompensation korrigiert .quelle