La constante de Brun es el valor al que converge la suma de los recíprocos de los pares primos gemelos ( 1/p
y 1/(p+2)
dónde p
y p+2
ambos son primos). Es aproximadamente 1.902160583104
.
Dado un entero positivo N
, aproxima la constante de Brun sumando los recíprocos de los pares primos gemelos donde ambos primos en el par son menores que N
, y genera la aproximación.
Reglas
N
será un número entero positivo dentro del rango representable para su idioma.- La salida debe ser lo más precisa posible al valor verdadero, dentro de los límites de la implementación de punto flotante de su idioma, ignorando cualquier problema potencial debido a imprecisiones aritméticas de punto flotante. Si su lenguaje es capaz de aritmética de precisión arbitraria, debe ser al menos tan precisa como la aritmética de precisión doble IEEE 754.
- Alternativamente, se puede generar una fracción exacta en cualquier formato consistente y sin ambigüedades.
- Si un primo aparece en múltiples pares primos gemelos (por ejemplo
5
, parte de ambos(3, 5)
y(5, 7)
), su recíproco contribuye a la suma cada vez.
Casos de prueba
2 -> 0
6 -> 0.5333333333333333
10 -> 0.8761904761904762
13 -> 0.8761904761904762
100 -> 1.3309903657190867
620 -> 1.4999706034568274
100000 -> 1.67279958482774
Respuestas:
Python 3 ,
787775706862 bytes¡Gracias a @xnor por jugar
24 bytes y allanar el camino para 4 más!Pruébalo en línea!
Fondo
Recordemos que el teorema de Wilson establece que para todos los enteros k> 1 ,
donde a ≡ b (mod d) significa que a - b es divisible por d , es decir, a y b tienen el mismo residuo cuando se divide por d .
En Wilson Theorems for Double-, Hyper-, Sub- and Super-factorials , los autores prueban generalizaciones para factoriales dobles, sobre los que se basa esta respuesta. El factorial doble de un entero k ≥ 0 se define por
El teorema 4 del trabajo antes mencionado establece lo siguiente.
Elevando ambos lados de las congruencias al cuarto poder, deducimos que
para todos los números primos impares p . Desde 1 !! = 1 , la equivalencia se cumple también para p = 2 .
Ahora, hacer lo mismo con el teorema de Wilson revela que
Ya que
resulta que
siempre que p es primo.
Ahora, que k sea un número entero extraño, positivo y compuesto. Por definición, existen enteros a, b> 1 tales que k = ab .
Como k es impar, también lo son a y b . Por lo tanto, ambos ocurren en la secuencia 1, 3, ..., k - 2 y
donde | Indica divisibilidad.
Resumiendo, para todos los enteros impares k> 1
donde p (k) = 1 si k es primo y p (k) = 0 si k es compuesto.
Cómo funciona
Cuando se llama a la función f con un único argumento, k , m y j se inicializan como 3 , 1 y 0 .
Tenga en cuenta que ((k - 2) !!) 4 = 1 !! 4 = 1 = m . De hecho, la igualdad m = ((k - 2) !!) 4 se mantendrá en todo momento. j es flotante y siempre será igual a ((k - 4) !!) 4 % (k - 2) / (k - 2) .
Mientras k <n ,
and
se evaluará el argumento correcto de . Como j = ((k - 4) !!) 4 % (k - 2) / (k - 2) , como se demuestra en el primer párrafo, j = 1 / (k - 2) si k - 2 es primo y j = 0 si no. Del mismo modo, dado que m% k = ((k - 2) !!) 4 es igual a 1 si k es primo y 0 si no, -m% k = k - 1 si k es primo y -m% k = 0 si no. Por lo tanto, se-m%k*j*2/k
evalúa como 2 (k - 1) / (k (k - 2)) = ((k - 2) + k) / (k (k - 2)) = 1 / k + 1 / (k - 2) si el par (k - 2, k)consiste en primos gemelos y en 0 si no.Después de calcular lo anterior, agregamos el resultado al valor de retorno de la llamada recursiva
f(n,k+2,m*k**4,m%k/k)
. k se incrementa en 2, por lo que solo toma valores impares ‡ † , multiplicamos m por k 4 ya que mk 4 = ((k - 2) !!) 4 k 4 = (k !!) 4 y pasamos el valor actual de m% k / k , que es igual a 1 / k si el "viejo" k es primo y 0 si no, como parámetro j para la llamada a la función.Finalmente, una vez que k es igual o mayor que n , f devolverá False y la recursión se detendrá. El valor de retorno de f (n) será la suma de todos 1 / k + 1 / (k - 2) tal que (k - 2, k) es un par primo gemelo yk <n , según se desee.
‡ Los resultados del párrafo Fondo solo se mantienen para enteros impares. Dado que incluso los enteros no pueden ser primos gemelos, podemos omitirlos de manera segura.
fuente
m%k*(j/k+j/(k-2))
.((k-2)!!)^4 = p(k)
módulop
para imparp
. No he trabajado con su argumento, pero aquí hay uno que se me ocurrió (que podría ser lo mismo en esencia). Módulo de trabajop
en el set{1,2,..,p-1}
, las igualaciones son exactamente las negativas de las probabilidades. Por lo tanto,prod(odds) = ± prod(evens)
. El teorema de Wilson nos dice esoprod(all) = - p(k)
. Desde entoncesprod(all) = prod(odds) * prod(evens) = prod(odds) * ± prod(evens)
, tenemosprod(odds)^2 = ±p(k)
y asíprod(odds)^4 = p(k)^2 = p(k)
.Jalea ,
1514 bytesPruébalo en línea!
Cómo funciona
fuente
Gelatina ,
1614 bytes (con un poco de ayuda de @Dennis)Pruébalo en línea!
Mientras intentaba mejorar mi respuesta anterior, pensé en un algoritmo totalmente diferente, y es algo más corto. Estoy usando una publicación diferente, como es el estándar aquí para una respuesta que usa una técnica diferente.
Dennis sugiriendo reemplazar
_/2+$$Ðḟ
conIċ¥Ðf2
; Me había olvidado por completo de la posibilidad de un filtro diádico. Como tal, este algoritmo ahora se vincula con el que utilizó la respuesta de Dennis.Explicación
fuente
2_/2+$$Ðḟ
puede llegar a serIċ¥Ðf2
.Brachylog , 17 bytes
Pruébalo en línea!
¡Esta es la nueva versión de Brachylog, con una página de códigos brillante!
Explicación
fuente
MATL , 16 bytes
Pruébalo en línea!
Considere la entrada
13
como un ejemplo.fuente
Mathematica,
4847 bytes¡Gracias a JungHwan Min por guardar 1 byte!
Función sin nombre que toma un entero positivo como entrada y devuelve una fracción exacta; por ejemplo,
If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&[10]
devuelve92/105
.If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]
prueba si ambosi
yi-2
son primos, devolviendo la suma de sus recíprocos si es así y0
si no.~Sum~{i,#-1}&
luego devuelve la suma de esas contribuciones para todos los valoresi
menores que la entrada.Presentación previa:
fuente
If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&
N@
delante del código.N
devuelve una aproximación decimal a un número real; sin embargo, requiere bytes adicionales para mostrar más de 6 higos sig, y no importa cuántos sig figs se muestren, sigue siendo menos preciso que la fracción misma.Octava, 45 bytes
Explicación:
¡Pruébelo en línea!
fuente
JavaScript (ES6),
6766 bytesGuardado 1 byte gracias a @Arnauld
Salidas
false
para caso de prueba2
, que está permitido por defecto .Fragmento de prueba
Mostrar fragmento de código
fuente
1/n+++1/++n
guarda un byte.+++
no siempre arroja un error ...05AB1E ,
1914 bytes (-5 @Emigna)Pruébalo en línea!
fuente
<LDpÏÍDpÏDÌ«zO
para guardar 5 bytes.Jalea , 19 bytes
Pruébalo en línea!
Tengo la sensación de que esto es mejorable, pero no puedo ver de inmediato cómo.
Explicación
Los
µ
Connect todas estas porciones junto tubería de estilo, con cada uno tomando la salida de la anterior como su entrada.fuente
Pyth -
222117 bytesCreo que la refactorización ayudará.
Test Suite .
fuente
Perl 6 ,
5951 bytes{sum 1 «/»grep((*-(2&0)).is-prime,^$_).flatmap:{$_-2,$_}}
-2..* Z ^$_
comprime la lista infinita-2, -1, 0, 1, ...
con la lista0, 1, ... $_-1
($_
siendo el argumento de la función), produciendo la lista(-2, 0), (-1, 1), (0, 2), ..., ($_-3, $_-1)
. (Obviamente, ninguno de estos números menores que 3 puede estar en un par primo, pero3..* Z 5..^$_
es unos pocos bytes más largo y ninguno de los números adicionales es primo).Los
grep
selecciona sólo aquellas parejas donde todos (es decir, ambos números) son primos, y losflat
ellos se aplana en una lista simple de números.«/»
es el hiperoperador de división; con la lista a la derecha y1
a la izquierda, convierte la lista de pares primos en sus recíprocos, que luego se suma porsum
.fuente
Clojure, 147 bytes
Y Clojure viene último, como siempre.
Sin golf:
fuente
Julia 0.4 ,
4846 bytesPruébalo en línea!
fuente
Bash + utilidades GNU,
8685 bytesPruébalo en línea!
Construye una gran expresión aritmética y luego la alimenta
bc -l
para evaluarla.Editar: se dejó por error en un par $ (...) de una versión anterior con sustitución de comando anidada; cambiado a backticks para guardar un byte.
fuente
NARS APL, 216 bytes, 108 caracteres
esto usaría el "Crivello di Eratostene" para encontrar la sublista en 1..arg de primos de solicitud. Prueba:
fuente