Ungefähre Brunsche Konstante

25

Die Brunsche Konstante ist der Wert, zu dem die Summe der Kehrwerte der Twin-Prim- Paare ( 1/pund 1/(p+2)wo pund wo p+2beide Primzahlen sind) konvergiert. Es ist ungefähr 1.902160583104.

Bei einer positiven ganzen Zahl Napproximieren 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. 5als 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
Mego
quelle
Kann ein genauer Bruch ausgegeben werden?
LegionMammal978
@ LegionMammal978 Ja, das werde ich klären.
Mego
Randnotiz: Der Wert 1,902160583104 ... für Bruns Konstante wird nur vermutet; nicht einmal die erste signifikante Zahl wurde streng berechnet (dh es ist nicht einmal bekannt, ob sie größer oder kleiner als 2 ist).
Greg Martin
@ GregMartin Das ist zwar wahr, aber es ist auch die beste Annäherung, die wir derzeit haben.
Mego
5 ist die einzige Primzahl, die in zwei Primzahlenpaaren vorkommt
Christian Sievers

Antworten:

25

Python 3 , 78 77 75 70 68 62 Bytes

f=lambda n,k=3,m=1,j=0:k<n and-m%k*j*2/k+f(n,k+2,m*k**4,m%k/k)

Vielen Dank an @xnor für das Abschlagen von 2 bis 4 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 andausgewertet. 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/ker 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.

Dennis
quelle
Ich denke, dein Ausdruck ist der gleiche wie m%k*(j/k+j/(k-2)).
Xnor
Ja das funktioniert Vielen Dank!
Dennis
Schöne Beobachtung, die für ungerade ((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 . ppp{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)
Xnor
Nett! Ich habe versucht, die Summe als einen Bruch auszudrücken, aber es war mir nicht eingefallen, einen Teil davon in j zu berechnen . Danke noch einmal! Ihr Beweis ist viel einfacher als der aus dem Papier.
Dennis
7

Jelly , 15 bis 14 Bytes

’ÆRµ_2fµ+2;µİS

Probieren Sie es online!

Wie es funktioniert

’ÆRµ_2fµ+2;µİS  Main link. Argument: n

’               Decrement; yield n-1.
 ÆR             Prime range; yield all primes in [1, ..., n-1].
   µ            New chain. Argument: r (prime range)
    _2          Subtract 2 from all primes.
      f         Filter; keep all p-2 that appear in r.
       µ        New chain. Argument: t (filtered range)
        +2      Add 2 to all primes in s.
          ;     Concatenate with s.
           µ    New chain. Argument: t (twin primes)
            İ   Take the inverses.
             S  Sum.
Dennis
quelle
5

Jelly , 16 bis 14 Bytes (mit ein wenig Hilfe von @Dennis)

’ÆRṡ2_/2+$$ÐḟFİS

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

’ÆRṡ2Iċ¥Ðf2FİS
’                  Decrement.
 ÆR                Primes from 2 to the argument inclusive
                   (i.e. 2 to the original input exclusive).
   ṡ2              Take overlapping slices of size 2.
        Ðf         Keep only elements where the following is true:
       ¥           {the second parse of, which parses like this}
     Iċ   2          the differences (I) contain (ċ) 2
           F       Flatten.
            İ      Take 1/x {for every list element}.
             S     Sum.

quelle
2_/2+$$Ðḟwerden kann Iċ¥Ðf2.
Dennis
4

Brachylog , 17 Bytes

{>I-₂:I{ṗ/₁}ᵐ}ᶠc+

Probieren Sie es online!

Dies ist die brandneue Version von Brachylog mit einer glänzenden Codepage!

Erläuterung

{            }ᶠ        Find all valid outputs of the predicate in brackets
               c+      Output is the sum of that list after flattening it

 >I                    Input > I
   -₂:I                The list [I-2, I]
       {   }ᵐ          Map:
        ṗ/₁              Must be prime and the output is its inverse
Tödlich
quelle
3

MATL , 16 Bytes

liqZqtd2=)t2+h/s

Probieren Sie es online!

Betrachten Sie die Eingabe 13als Beispiel.

l     % Push 1
      %   STACK: 1
i     % Input N
      %   STACK: 1, 13
q     % Subtract 1
      %   STACK: 1, 12
Zq    % Primes up to that
      %   STACK: 1, [2 3 5 7 11]
t     % Duplicate
      %   STACK: 1, [2 3 5 7 11], [2 3 5 7 11]
d     % Consecutive differences
      %   STACK: 1, [2 3 5 7 11], [1 2 2 4]
2=    % Compare with 2, element-wise
      %   STACK: 1, [2 3 5 7 11], [0 1 1 0]
)     % Use as logical index to select elements from array
      %   STACK: 1, [3 5]
t     % Duplicate
      %   STACK: 1, [3 5], [3 5]
2+    % Add 2, element-wise
      %   STACK: 1, [3 5], [5 7]
h     % Concatenate horizontally
      %   STACK: 1, [3 5 5 7]
/     % Divide, element-wise
      %   STACK: [0.3333 0.2 0.2 0.1429]
s     % Sum of array. Implicitly display
      %   STACK: 0.8762
Luis Mendo
quelle
2

Mathematica, 48 47 Bytes

Vielen Dank an JungHwan Min für das Speichern von 1 Byte!

If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&

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ück 92/105.

If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]testet, ob beide iund i-2prim 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:

If[And@@PrimeQ@{i,g=i-2},1/i+1/g,0]~Sum~{i,#-1}&
Greg Martin
quelle
Das ist nur gruselig. Ich gebe auf. ⚐
LegionMammal978
Ich fragte mich, ob "exakter Bruch" Mathematica bedeutete :)
Greg Martin
-1 Byte:If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&
JungHwan Min
Man kann eine Zahl mit willkürlicher Genauigkeit erhalten, indem man zwei Bytes N@vor dem Code hinzufügt .
JungHwan Min
Schönes Golfen des Zustandes! Es ist wahr, dass Neine 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.
Greg Martin
2

Oktave, 45 Bytes

@(n)sum(all(isprime(m=[h=3:n-1;h-2]))*m'.^-1)

Erläuterung:

m=[h=3:n-1;h-2]             generate an concatenate two ranges 3:n-1 and 1:n-3
rec=m'.^-1                  transpose and reciprocal
idx=all(isprime(m))         create a logical [0 1 ..] array  if both ranges are prime set 1 else set 0
sum1 = idx * rec            matrix multiplication(extrat elements with logical index and sum along the first dimension)
sum(sum1)                   sum along the second dimension  

Probieren Sie es online!

rahnema1
quelle
2

JavaScript (ES6), 67 66 Bytes

1 Byte dank @Arnauld gespeichert

f=n=>--n>1&&((p=x=>n%--x?p(x):x==1)(n)&&p(n-=2)&&1/n+++1/++n)+f(n)

Ausgänge falsefür Testfall 2, das ist standardmäßig zulässig sind .

Testschnipsel

ETHproductions
quelle
Ich denke, 1/n+++1/++nspart ein Byte.
Arnauld
@ Arnauld Danke. Aus irgendeinem Grund wusste ich nicht, dass +++das nicht immer einen Fehler
auslöst
1

Jelly , 19 Bytes

’ÆRḊµ_Æp=2Tịµ_2;µİS

Probieren Sie es online!

Ich habe das Gefühl, dass dies verbesserungsfähig ist, aber ich kann nicht sofort sehen, wie.

Erläuterung

’ÆRḊµ_Æp=2Tịµ_2;µİS
 ÆR                  Generate all primes from 2 to n inclusive
’                    Subtract 1
   Ḋ                 Remove first element
’ÆRḊ                 Generate all primes from 3 to n-1 exclusive

     _Æp             Subtract the previous prime (i.e. calculate the prime gap)
        =2           Compare to 2
          Tị         Take elements of the input where the comparison is true
     _Æp=2Tị         Filter a list of primes to the latter halves of prime pairs

             _2      Subtract 2
               ;     Append
             _2;     Append the list to the list with 2 subtracted from it
                 İ   Take reciprocals
                  S  Sum
                 İS  Take the sum of the reciprocals

Sie µverbinden alle diese Abschnitte im Pipeline-Stil miteinander, wobei jeder den Ausgang des vorherigen als Eingang verwendet.


quelle
1

Pyth - 22 21 17 Bytes

Ich denke, dass Refactoring helfen wird.

scL1sf.APM_MTm,tt

Test Suite .

Maltysen
quelle
1

Perl 6 , 59 51 Bytes

{sum 1 «/»grep((*-(2&0)).is-prime,^$_).flatmap:{$_-2,$_}}

{sum 1 «/»grep(*.all.is-prime,(-2..*Z ^$_)).flat}

-2..* Z ^$_Zippt die unendliche Liste -2, -1, 0, 1, ...mit der Liste 0, 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 grepBefehl wählt nur die Paare aus, bei denen alle (dh beide) Zahlen Primzahlen sind, und flatfasst sie zu einer einfachen Liste von Zahlen zusammen.

«/»ist der Divisionshyperoperator; Mit der Liste auf der rechten und 1linken Seite wird die Liste der Primpaare in ihre Kehrwerte umgewandelt, die dann durch summiert werden sum.

Sean
quelle
1

Clojure, 147 Bytes

(fn[n](let[p #(if(> % 2)(<(.indexOf(for[a(range 2 %)](mod % a))0)0))](reduce +(for[a(range 2 n)](if(and(p a)(p(- a 2)))(+(/ 1 a)(/ 1(- a 2)))0)))))

Und Clojure stirbt wie immer als letzter.

Ungolfed:

; Returns the primality of a number.
(defn prime? [n]
  (if (> n 2)
    (< (.indexOf (for [a (range 2 n)] (mod n a)) 0) 0)))

; Calculates the actual Brun's Constant. ' (Stupid highlighter)
(defn brunsconst [n]
  ; Adds all of the entries together
  (reduce
    +
    ; For a in range(2, n):
    (for [a (range 2 n)]
      (let [b (- a 2)]
        ; If both a and a-2 are prime:
        (if (and (prime? a) (prime? b))
          ; Place (1/a + 1/a-2) on the array, else 0
          (+ (/ 1 a) (/ 1 b)) 0)))))
Clismique
quelle
0

Bash + GNU-Dienstprogramme, 86-85 Byte

for((k=4;k<$1;k++,j=k-2)){ [ `factor $k $j|wc -w` = 4 ]&&x=$x+1/$k+1/$j;};bc -l<<<0$x

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

Mitchell Spector
quelle
0

APL NARS, 216 Byte, 108 Zeichen

  r←z n;h;i;k;v
  i←0⋄n-←1⋄h←1+⍳n-1⋄→B
A:k←i⊃h⋄h←k∪(0≠k∣h)/h
B:→A×⍳(⍴h)≥i+←1
  r←+/÷(v-2),v←(h=1⌽h+2)/h

dies würde das "Crivello di Eratostene" verwenden, um die Unterliste in 1..arg der Anfrage-Primzahlen zu finden. Prüfung:

  z¨2 6 10 13 100 620
0 0.5333333333 0.8761904762 0.8761904762 1.330990366 1.499970603 
  z 100000
1.672799585
RosLuP
quelle