Die Brunsche Konstante ist der Wert, zu dem die Summe der Kehrwerte der Twin-Prim- Paare ( 1/p
und 1/(p+2)
wo p
und wo p+2
beide Primzahlen sind) konvergiert. Es ist ungefähr 1.902160583104
.
Bei einer positiven ganzen Zahl N
approximieren Sie die Brunsche Konstante, indem Sie die Kehrwerte der Twin-Prim-Paare addieren, wobei beide Primzahlen im Paar kleiner als sind N
, und geben Sie die Approximation aus.
Regeln
N
wird eine positive ganze Zahl innerhalb des für Ihre Sprache darstellbaren Bereichs sein.- Die Ausgabe muss innerhalb der Grenzen der Gleitkommaimplementierung Ihrer Sprache so genau wie möglich sein und mögliche Probleme aufgrund von arithmetischen Gleitkommaungenauigkeiten ignorieren. Wenn Ihre Sprache in der Lage ist, Arithmetik mit willkürlicher Genauigkeit auszuführen, muss sie mindestens so genau sein wie Arithmetik mit doppelter Genauigkeit nach IEEE 754.
- Alternativ kann ein exakter Bruch in einem beliebigen konsistenten, eindeutigen Format ausgegeben werden.
- Wenn ein Primzahl in mehreren Doppelprimzahlpaaren vorkommt (z. B.
5
als Teil von beiden(3, 5)
und(5, 7)
), trägt sein Reziprokwert jedes Mal zur Summe bei.
Testfälle
2 -> 0
6 -> 0.5333333333333333
10 -> 0.8761904761904762
13 -> 0.8761904761904762
100 -> 1.3309903657190867
620 -> 1.4999706034568274
100000 -> 1.67279958482774
Antworten:
Python 3 ,
787775706862 BytesVielen Dank an @xnor für das Abschlagen von
2 bis4 Bytes und das Vorbereiten des Weges für weitere 4 Bytes!Probieren Sie es online!
Hintergrund
Erinnern wir uns, dass Wilsons Satz besagt, dass für alle ganzen Zahlen k> 1 ,
wobei a ≡ b (mod d) bedeutet, dass a - b gleichmäßig durch d teilbar ist , dh a und b haben den gleichen Rest, wenn sie durch d geteilt werden .
In Wilson Theorems for Double-, Hyper-, Sub- und Super-Fakultäten beweisen die Autoren Verallgemeinerungen für Double Factorials, auf denen diese Antwort aufbaut. Die doppelte Fakultät einer ganzen Zahl k ≥ 0 ist definiert durch
Satz 4 der oben genannten Arbeit besagt Folgendes.
Indem wir beide Seiten der Kongruenzen zur vierten Potenz erheben, schließen wir daraus
für alle ungeraden Primzahlen p . Schon seit 1 !! = 1 gilt die Äquivalenz auch für p = 2 .
Das Gleiche gilt für Wilsons Theorem
Schon seit
es folgt dem
wann immer p prime ist.
Nun sei k eine ungerade, positive, zusammengesetzte ganze Zahl. Per Definition existieren ganze Zahlen a, b> 1, so dass k = ab ist .
Da k ungerade ist, sind auch a und b ungerade . Somit treten beide in der Reihenfolge 1, 3,…, k - 2 und auf
wo | zeigt die Teilbarkeit an.
Zusammenfassend gilt für alle ungeraden ganzen Zahlen k> 1
wobei p (k) = 1 ist, wenn k prim ist, und p (k) = 0 ist, wenn k zusammengesetzt ist.
Wie es funktioniert
Wenn die Funktion f mit einem einzelnen Argument aufgerufen wird, werden k , m und j als 3 , 1 und initialisiert 0 .
Beachten Sie, dass ((k - 2) !!) 4 = 1 !! 4 = 1 = m . Tatsächlich gilt immer die Gleichheit m = ((k - 2) !!) 4 . j ist ein float und wird immer gleich ((k - 4) !!) 4 % (k - 2) / (k - 2) sein .
Während k <n ist , wird das richtige Argument von
and
ausgewertet. Da j = ((k - 4) !!) 4 % (k - 2) / (k - 2) ist , wie im ersten Absatz bewiesen, gilt j = 1 / (k - 2), wenn k - 2 eine Primzahl ist und j = 0 wenn nicht. Da m% k = ((k - 2) !!) 4 gleich 1 ist, wenn k eine Primzahl ist, und 0, wenn nicht, ist -m% k = k - 1, wenn k eine Primzahl ist, und -m% k = 0, wenn nicht. Wertet daher aus, dass-m%k*j*2/k
er 2 (k - 1) / (k (k - 2)) = ((k - 2) + k) / (k (k - 2)) = 1 / k + 1 / (k - 2) wenn das Paar (k - 2, k)besteht aus zwei Primzahlen und 0, wenn nicht.Nach der Berechnung des oben genannten addieren wir das Ergebnis zum Rückgabewert des rekursiven Aufrufs
f(n,k+2,m*k**4,m%k/k)
. k wird um 2 inkrementiert, sodass nur ungerade Werte ‡ † verwendet werden. Wir multiplizieren m mit k 4, da mk 4 = ((k - 2) !!) 4 k 4 = (k !!) 4 und übergeben den aktuellen Wert von m% k / k - entspricht 1 / k, wenn das "alte" k eine Primzahl ist, und 0, wenn nicht - als Parameter j für den Funktionsaufruf.Schließlich, wenn k gleich oder größer ist , als n , f kehrt Falsch und die Rekursion stoppt. Der Rückgabewert von f (n) ist die Summe aller 1 / k + 1 / (k - 2), so dass (k - 2, k) ein Doppelprimuspaar ist und k <n , wie gewünscht.
‡ Die Ergebnisse aus dem Hintergrund- Absatz gelten nur für ungerade ganze Zahlen. Da auch ganze Zahlen keine Doppelprimzahlen sein können, können wir sie sicher überspringen.
quelle
m%k*(j/k+j/(k-2))
.((k-2)!!)^4 = p(k)
modulo . Ich habe Ihr Argument nicht durchgearbeitet, aber hier ist eines, das ich mir ausgedacht habe (das könnte im Wesentlichen dasselbe sein). Modulo im Set arbeiten , die Abschlüsse sind genau die Negative der Chancen. Also . Wilsons Satz sagt uns das . Da haben wir und so .p
p
p
{1,2,..,p-1}
prod(odds) = ± prod(evens)
prod(all) = - p(k)
prod(all) = prod(odds) * prod(evens) = prod(odds) * ± prod(evens)
prod(odds)^2 = ±p(k)
prod(odds)^4 = p(k)^2 = p(k)
Jelly ,
15 bis14 BytesProbieren Sie es online!
Wie es funktioniert
quelle
Jelly ,
16 bis14 Bytes (mit ein wenig Hilfe von @Dennis)Probieren Sie es online!
Beim Versuch, meine vorherige Antwort zu verbessern, habe ich mir einen völlig anderen Algorithmus ausgedacht, der etwas kürzer ist. Ich benutze dafür einen anderen Beitrag, wie hier der Standard für eine Antwort, die eine andere Technik verwendet.
Dennis was darauf hindeutet , ersetzt
_/2+$$Ðḟ
mitIċ¥Ðf2
; Ich hatte die Möglichkeit eines dyadischen Filters völlig vergessen. Als solcher knüpft dieser Algorithmus jetzt an die Antwort von Dennis an.Erläuterung
quelle
2_/2+$$Ðḟ
werden kannIċ¥Ðf2
.Brachylog , 17 Bytes
Probieren Sie es online!
Dies ist die brandneue Version von Brachylog mit einer glänzenden Codepage!
Erläuterung
quelle
MATL , 16 Bytes
Probieren Sie es online!
Betrachten Sie die Eingabe
13
als Beispiel.quelle
Mathematica,
4847 BytesVielen Dank an JungHwan Min für das Speichern von 1 Byte!
Unbenannte Funktion, die eine positive Ganzzahl als Eingabe verwendet und einen genauen Bruch zurückgibt; beispielsweise,
If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&[10]
kehrt zurück92/105
.If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]
testet, ob beidei
undi-2
prim sind und gibt die Summe ihrer Reziprozitäten zurück, wenn ja und0
wenn nicht.~Sum~{i,#-1}&
gibt dann die Summe dieser Beiträge für alle Werte von zurücki
kleiner als die Eingabe sind.Vorherige Einreichung:
quelle
If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&
N@
vor dem Code hinzufügt .N
eine dezimale Annäherung an eine reelle Zahl zurückgegeben wird. Es sind jedoch zusätzliche Bytes erforderlich, um mehr als etwa 6 Sig Feigen anzuzeigen. Unabhängig davon, wie viele Sig Feigen angezeigt werden, ist die Genauigkeit immer noch geringer als der Bruchteil selbst.Oktave, 45 Bytes
Erläuterung:
Probieren Sie es online!
quelle
JavaScript (ES6),
6766 Bytes1 Byte dank @Arnauld gespeichert
Ausgänge
false
für Testfall2
, das ist standardmäßig zulässig sind .Testschnipsel
Code-Snippet anzeigen
quelle
1/n+++1/++n
spart ein Byte.+++
das nicht immer einen Fehler05AB1E ,
1914 Bytes (-5 @Emigna)Probieren Sie es online!
quelle
<LDpÏÍDpÏDÌ«zO
um 5 Bytes zu sparen.Jelly , 19 Bytes
Probieren Sie es online!
Ich habe das Gefühl, dass dies verbesserungsfähig ist, aber ich kann nicht sofort sehen, wie.
Erläuterung
Sie
µ
verbinden alle diese Abschnitte im Pipeline-Stil miteinander, wobei jeder den Ausgang des vorherigen als Eingang verwendet.quelle
Pyth -
222117 BytesIch denke, dass Refactoring helfen wird.
Test Suite .
quelle
Perl 6 ,
5951 Bytes{sum 1 «/»grep((*-(2&0)).is-prime,^$_).flatmap:{$_-2,$_}}
-2..* Z ^$_
Zippt die unendliche Liste-2, -1, 0, 1, ...
mit der Liste0, 1, ... $_-1
($_
als Argument für die Funktion) und erstellt die Liste(-2, 0), (-1, 1), (0, 2), ..., ($_-3, $_-1)
. (Offensichtlich kann keine dieser Zahlen kleiner als 3 zu einem Primzahlpaar gehören, aber3..* Z 5..^$_
einige Bytes länger und keine der zusätzlichen Zahlen sind Primzahlen.)Der
grep
Befehl wählt nur die Paare aus, bei denen alle (dh beide) Zahlen Primzahlen sind, undflat
fasst sie zu einer einfachen Liste von Zahlen zusammen.«/»
ist der Divisionshyperoperator; Mit der Liste auf der rechten und1
linken Seite wird die Liste der Primpaare in ihre Kehrwerte umgewandelt, die dann durch summiert werdensum
.quelle
Clojure, 147 Bytes
Und Clojure stirbt wie immer als letzter.
Ungolfed:
quelle
Julia 0,4 ,
4846 BytesProbieren Sie es online!
quelle
Bash + GNU-Dienstprogramme,
86-85ByteProbieren Sie es online!
Erstellt einen großen arithmetischen Ausdruck und fügt ihn dann ein
bc -l
, um ihn auszuwerten.Bearbeiten: Aus Versehen in einem $ (...) -Paar einer alten Version mit verschachtelter Befehlsersetzung belassen; wurde in Backticks geändert, um ein Byte zu speichern.
quelle
APL NARS, 216 Byte, 108 Zeichen
dies würde das "Crivello di Eratostene" verwenden, um die Unterliste in 1..arg der Anfrage-Primzahlen zu finden. Prüfung:
quelle