La conjetura de Goldbach establece que cada número par mayor que dos puede expresarse como la suma de dos números primos. Por ejemplo,
4 = 2 + 2
6 = 3 + 3
8 = 5 + 3
Sin embargo, una vez que llegamos a 10, sucede algo interesante. No solo se puede escribir 10 como
5 + 5
pero también se puede escribir como
7 + 3
Como 10 puede expresarse como la suma de dos primos de dos maneras , decimos que la "partición Goldbach" de 10 es 2
. O más generalmente,
La partición Goldbach de un número es el número total de formas distintas de escribir
n = p + q
dóndep
yq
son primos yp >= q
Su desafío es escribir un programa o función que encuentre la partición Goldbach de un número. Ahora, técnicamente el término "partición Goldbach" se usa solo para referirse a números pares. Sin embargo, puesto que el entero impar p + 2 puede también ser expresada como la suma de dos números primos si p> 2 es primo, que se ampliará a todos los números enteros positivos ( A061358 ).
Puede suponer con seguridad que su entrada siempre será un número entero positivo, y puede tomar entrada y salida en cualquiera de nuestros métodos permitidos por defecto , por ejemplo, argumentos de función y valor de retorno, STDIN y STDOUT, leer y escribir en un archivo, etc.
Las particiones de Goldbach de los enteros positivos hasta 100 son:
0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 1, 2, 1, 3, 0, 3, 1,
3, 0, 2, 0, 3, 1, 2, 1, 4, 0, 4, 0, 2, 1, 3, 0, 4, 1, 3, 1, 4, 0, 5, 1, 4,
0, 3, 0, 5, 1, 3, 0, 4, 0, 6, 1, 3, 1, 5, 0, 6, 0, 2, 1, 5, 0, 6, 1, 5, 1,
5, 0, 7, 0, 4, 1, 5, 0, 8, 1, 5, 0, 4, 0, 9, 1, 4, 0, 5, 0, 7, 0, 3, 1, 6
Como de costumbre, se aplican las lagunas estándar, ¡y gana la respuesta más corta en bytes!
Respuestas:
Jalea , 8 bytes
Pruébalo en línea! o verificar todos los casos de prueba .
Cómo funciona
fuente
Python 2, 76 bytes
Recursiva se arrastra desde
k=2
quen/2
, sumando los valores en tantok
yn-k
son primos. Sería bueno para contarn
hacia abajo al mismo tiempo en lugar, pero esto tiene un problema quek=0
yk=1
son falsamente llamada Prime:La verificación de primalidad es la división de prueba, acortada al verificar ambas
k
yn-k
juntas. Encontré que esto es más corto que usar un generador de teoremas de Wilson (79 bytes):La idea de este es mantener una lista de todos los números primos en la mitad inferior para que se verifique cuando lleguemos a la mitad superior, pero para el punto medio
k=n/2
, no hemos tenido tiempo de agregarn-k
a la lista cuando llegamos ak
. Una versión iterativa evita esto, pero tiene 82 bytes:fuente
MATL , 8 bytes
Pruébalo en línea!
Explicación
Considere la entrada
8
como un ejemploEs interesante observar el gráfico de la secuencia , utilizando una versión ligeramente modificada del código:
Para la entrada
10000
el resultado esPuede probarlo en MATL Online (Actualice la página si el botón "Ejecutar" no cambia a "Matar" cuando se presiona). Se necesitan varios 25 segundos para producir el gráfico para la entrada
3000
; las entradas superiores a unos pocos miles se agotarán.fuente
Upper triangular part
truco es realmente genial!JavaScript (ES6),
777370 bytesGuardado 3 bytes gracias a @Arnauld
f
es una función de prueba de primalidad; La función relevante esg
.f
funciona contando recursivamente desde n-1 ; El flujo de control en cada etapa es así:x<2||
Si x <2 , el número es primo; volver 1 .n%x&&
De lo contrario, si n mod x = 0 , el número no es primo; regresarn%x
.f(n,x-1)
De lo contrario, el número puede o no ser primo; decremento x e inténtelo de nuevo.g
funciona de manera similar, aunque no con tanto flujo de control. Funciona multiplicando f (b) por f (ab) para cada entero b en el rango [2, piso (a / 2)] , y luego sumando los resultados. Esto nos da el número de pares que se suma a una donde ambos números en la pareja son primos, que es exactamente lo que queremos.fuente
a
es positivo,b=a>>1
debería ahorrarte un byte.>>
operador ...f=(n,x=n)=>--x<2||n%x&&f(n,x)
?05AB1E ,
108 bytesExtremadamente ineficiente.
Pruébalo en línea! o Pruebe una forma menos eficiente de generar primos
Explicación
n = 10
usado como ejemplo.fuente
ü
en su lugar? Al igual queD!fü+r¢
?n=10
que sería count (10, [5,8,12]) que es 0 en lugar de 2.ü
se aplica entre cada par de elementos solamente. Sinã
embargo, me dio la idea de intentarlo , pero desafortunadamente resultó 1 byte más.GAP , 57 bytes
No creo que GAP tenga un camino más corto que este obvio.
Number
cuenta cuántos elementos de una lista satisfacen un predicado.Usándolo para calcular los primeros 100 valores:
fuente
Brachylog , 22 bytes
Pruébalo en línea!
Explicación
Una transcripción directa del problema.
fuente
Mathematica, 52 bytes
El resultado se proporciona como una función anónima. Intenta trazar un gráfico sobre él:
Por cierto, el código tiene la misma longitud con la versión de función del código de demostración en OEIS.
fuente
PrimeQ[#~IntegerPartitions~{2}]~Count~{a=True,a}&
Jalea , 12 bytes
TryItOnline
1-100
¿Cómo?
fuente
Raqueta 219 bytes
Sin golf:
Pruebas:
Salida:
fuente
En realidad , 11 bytes
Pruébalo en línea!
Explicación:
fuente
05AB1E , 6 bytes
Pruébalo en línea!
Explicación:
fuente
Haskell, 73 bytes
Ejemplo de uso:
map f [1..25]
->[0,0,0,1,1,1,1,1,1,2,0,1,1,2,1,2,0,2,1,2,1,3,0,3,1]
.La ejecución directa de la definición: en primer lugar se unen
r
a todos los números primos hasta el número de entradan
, a continuación, tomar una1
para todosp
yq
desder
dondeq<=p
yp+q==n
y sumarlos.fuente