Constante aproximada de Brun

25

A constante de Brun é o valor para o qual a soma dos recíprocos dos pares primos gêmeos ( 1/pe 1/(p+2)onde pe p+2são ambos primos) converge. É aproximadamente 1.902160583104.

Dado um número inteiro positivo N, aproxime a constante de Brun somando os recíprocos dos pares primos gêmeos, em que ambos os números primos no par são menores que Ne produzam a aproximação.

Regras

  • N será um número inteiro positivo dentro do intervalo representável para o seu idioma.
  • A saída deve ser a mais precisa possível do valor real, dentro dos limites da implementação de ponto flutuante do seu idioma, ignorando quaisquer problemas em potencial devido a imprecisões aritméticas de ponto flutuante. Se seu idioma é capaz de aritmética de precisão arbitrária, deve ser pelo menos tão preciso quanto a aritmética de precisão dupla IEEE 754.
  • Como alternativa, uma fração exata pode ser impressa em qualquer formato consistente e inequívoco.
  • Se um primo aparecer em vários pares primos gêmeos (por exemplo 5, parte de ambos (3, 5)e (5, 7)), seu recíproco contribuirá para a soma de cada vez.

Casos de teste

2 -> 0
6 -> 0.5333333333333333
10 -> 0.8761904761904762
13 -> 0.8761904761904762
100 -> 1.3309903657190867
620 -> 1.4999706034568274
100000 -> 1.67279958482774
Mego
fonte
Uma fração exata pode ser produzida?
precisa saber é o seguinte
@ LegionMammal978 Sim, eu vou esclarecer.
Mego 22/01
Nota lateral: o valor 1.902160583104 ... para a constante de Brun é apenas conjecturado; nem mesmo o primeiro número significativo foi calculado rigorosamente (ou seja, nem se sabe se é maior ou menor que 2).
Greg Martin
@GregMartin Embora isso seja verdade, também é a melhor aproximação que temos atualmente.
Mego 22/01
5 é o único nobre que aparece em dois pares de primeira linha
Christian Sievers

Respostas:

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)

Obrigado ao @xnor por jogar 2 4 bytes e abrir caminho para mais 4!

Experimente online!

fundo

Lembre-se de que o teorema de Wilson afirma que, para todos os números inteiros k> 1 ,

onde um ≡ b (d mod) meios que a - b é divisível por d , isto é, um e b têm o mesmo resíduo, quando dividido por d .

Nos teoremas de Wilson para duplo , hiper, sub e super fatorial , os autores provam generalizações para fatoriais duplos, nos quais essa resposta se baseia. O fatorial duplo de um número inteiro k ≥ 0 é definido por

O teorema 4 do artigo mencionado acima afirma o seguinte.

Elevando ambos os lados das congruências para a quarta potência, deduzimos que

para todos os números primos ímpares p . Desde 1 !! = 1 , a equivalência também vale para p = 2 .

Agora, fazer o mesmo com o teorema de Wilson revela que

Desde a

segue que

sempre que p é primo.

Agora, seja k um número inteiro ímpar, positivo e composto. Por definição, existem inteiros a, b> 1 tais que k = ab .

Como k é ímpar, também são a e b . Assim, ambos ocorrem na sequência 1, 3,…, k - 2 e

onde | indica divisibilidade.

Resumindo, para todos os números ímpares k> 1

onde p (k) = 1 se k é primo ep (k) = 0 se k é composto.

Como funciona

Quando a função f é chamado com um único argumento, k , m , e j são inicializados como 3 , 1 e 0 .

Observe que ((k - 2) !!) 4 = 1 !! 4 = 1 = m . De fato, a igualdade m = ((k - 2) !!) 4 será mantida o tempo todo. j é um ponto flutuante e sempre será igual a ((k - 4) !!) 4 % (k - 2) / (k - 2) .

Enquanto k <n , o argumento correto de andserá avaliado. Como j = ((k - 4) !!) 4 % (k - 2) / (k - 2) , como comprovado no primeiro parágrafo, j = 1 / (k - 2) se k - 2 for primo e j = 0 se não. Da mesma forma, como m% k = ((k - 2) !!) 4 é igual a 1 se k for primo e 0 se não for, -m% k = k - 1 se k for primo e -m% k = 0 se não for. Portanto, -m%k*j*2/kavalia para 2 (k - 1) / (k (k - 2)) = ((k - 2) + k) / (k (k - 2)) = 1 / k + 1 / (k - 2) se o par (k - 2, k)consiste em primos gêmeos e a 0, se não.

Após calcular o acima, adicionamos o resultado ao valor de retorno da chamada recursiva f(n,k+2,m*k**4,m%k/k). k é incrementado por 2, portanto, leva apenas valores ímpares ‡ † , multiplicamos m por k 4, pois mk 4 = ((k - 2) !!) 4 k 4 = (k !!) 4 e passamos o valor atual de m% k / k - que é igual a 1 / k se o "antigo" k for primo e 0 se não - como parâmetro j para a chamada de função.

Finalmente, quando k for igual ou maior que n , f retornará Falso e a recursão será interrompida. O valor de retorno de f (n) será a soma de todos 1 / k + 1 / (k - 2), como (k - 2, k) é um par primo duplo e k <n , conforme desejado.


Os resultados do parágrafo Segundo plano são válidos apenas para números inteiros ímpares. Como mesmo números inteiros não podem ser primos gêmeos, podemos ignorá-los com segurança.

Dennis
fonte
Eu acho que sua expressão é a mesma que m%k*(j/k+j/(k-2)).
Xnor
Sim, isso funciona. Obrigado!
Dennis
Boa observação que ((k-2)!!)^4 = p(k)módulo ppara ímpar p. Eu não trabalhei com seu argumento, mas eis um que eu criei (que pode ser o mesmo em essência). Módulo de trabalho pno conjunto {1,2,..,p-1}, os pares são exatamente os negativos das probabilidades. Então prod(odds) = ± prod(evens),. O Teorema de Wilson nos diz isso prod(all) = - p(k). Desde então prod(all) = prod(odds) * prod(evens) = prod(odds) * ± prod(evens), temos prod(odds)^2 = ±p(k)e assim prod(odds)^4 = p(k)^2 = p(k).
Xnor
Agradável! Tentei expressar a soma como uma fração única, mas calcular parte dela em j não me ocorreu. Obrigado novamente! Sua prova é muito mais simples que a do jornal.
Dennis
7

Geléia , 15 14 bytes

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

Experimente online!

Como funciona

’Æ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
fonte
5

Jelly , 16 14 bytes (com uma pequena ajuda de @Dennis)

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

Experimente online!

Ao tentar melhorar minha resposta anterior, pensei em um algoritmo totalmente diferente, e ele é um pouco mais curto. Estou usando um post diferente para isso, como é o padrão aqui para uma resposta que usa uma técnica diferente.

Dennis sugerindo substituir _/2+$$Ðḟpor Iċ¥Ðf2; Eu tinha me esquecido completamente da possibilidade de um filtro diádico. Como tal, esse algoritmo agora está vinculado ao usado pela resposta de Dennis.

Explicação

’Æ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.

fonte
2_/2+$$Ðḟpode se tornar Iċ¥Ðf2.
Dennis
4

Braquilog , 17 bytes

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

Experimente online!

Esta é a nova versão do Brachylog, com uma página de código brilhante!

Explicação

{            }ᶠ        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
Fatalizar
fonte
3

MATL , 16 bytes

liqZqtd2=)t2+h/s

Experimente online!

Considere a entrada 13como um exemplo.

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

Mathematica, 48 47 bytes

Agradecemos a JungHwan Min por economizar 1 byte!

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

Função sem nome, recebendo um número inteiro positivo como entrada e retornando uma fração exata; por exemplo, If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&[10]retorna 92/105.

If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]testa se ambos ie i-2são primos, retornando a soma de seus recíprocos, se sim e 0se não. ~Sum~{i,#-1}&em seguida, retorna a soma dessas contribuições para todos os valores imenores que a entrada.

Submissão anterior:

If[And@@PrimeQ@{i,g=i-2},1/i+1/g,0]~Sum~{i,#-1}&
Greg Martin
fonte
Agora isso é assustador. Desisto. Leg
LegionMammal978
Eu me perguntava se "Fracção Exacta" significava Mathematica :)
Greg Martin
-1 byte:If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&
JungHwan Min
Pode-se obter um número de precisão arbitrária adicionando dois bytes N@, na frente do código.
JungHwan Min
Bom golfe da condição! É verdade que Nretorna uma aproximação decimal para um número real; no entanto, requer bytes extras para exibir mais de 6 sig figs, aproximadamente, e não importa quantos sig figs sejam exibidos, ainda é menos preciso que a própria fração.
Greg Martin
2

Oitava, 45 bytes

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

Explicação:

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  

Experimente Online!

rahnema1
fonte
2

JavaScript (ES6), 67 66 bytes

Guardado 1 byte graças a @Arnauld

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

Saídas falsepara caso de teste 2, que são permitidas por padrão .

Snippet de teste

ETHproductions
fonte
Eu acho que 1/n+++1/++nsalva um byte.
Arnauld
@ Arnauld Obrigado. Por alguma razão, eu nem sabia que +++isso nem sempre
gera
2

05AB1E , 19 14 bytes (-5 @Emigna)

<LDpÏÍDpÏDÌ«zO

Experimente online!

Urna de polvo mágico
fonte
<LDpÏÍDpÏDÌ«zOpara salvar 5 bytes.
Emigna
1

Geléia , 19 bytes

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

Experimente online!

Sinto que isso é improvável, mas não consigo ver imediatamente como.

Explicação

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

Eles µconectam todas essas partes ao estilo de pipeline, cada uma tendo como entrada a saída da anterior.


fonte
1

Pitão - 22 21 17 bytes

Eu acho que a refatoração vai ajudar.

scL1sf.APM_MTm,tt

Conjunto de Teste .

Maltysen
fonte
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 ^$_fecha a lista infinita -2, -1, 0, 1, ...com a lista 0, 1, ... $_-1( $_sendo o argumento para a função), produzindo a lista (-2, 0), (-1, 1), (0, 2), ..., ($_-3, $_-1). (Obviamente, nenhum desses números menores que 3 pode estar em um par primo, mas3..* Z 5..^$_ possui alguns bytes a mais e nenhum dos números extras é primo.)

Ele grepseleciona apenas os pares em que todos os números (ou seja, ambos) são primos e os flatnivela em uma lista simples de números.

«/»é o hiperoperador da divisão; com a lista à direita e 1à esquerda, transforma a lista de pares primos em seus recíprocos, que são então somados por sum.

Sean
fonte
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)))))

E Clojure morre por último, como sempre.

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

Utilitários Bash + GNU, 86 85 bytes

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

Experimente online!

Constrói uma grande expressão aritmética e a alimenta bc -lpara avaliá-la.

Editar: deixado erradamente em um par $ (...) de uma versão antiga com substituição de comando aninhada; alterado para backticks para salvar um byte.

Mitchell Spector
fonte
0

NARS APL, 216 bytes, 108 caracteres

  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

isso usaria o "Crivello di Eratostene" para encontrar a sub-lista em 1..arg de primos de solicitação. Teste:

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