Particiones Goldbach

18

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 + qdónde py qson 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!

DJMcMayhem
fuente
1
Siempre se te ocurren desafíos tan agradables :-)
Luis Mendo

Respuestas:

6

Jalea , 8 bytes

_ÆRÆPSHĊ

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

_ÆRÆPSHĊ  Main link. Argument: n (positive integer)

 ÆR       Prime range; yield [2, 3, 5, ..., n].
_         Subtract all primes in this range from n.
   ÆP     Compute the primality of the resulting differences.
          This returns 1 for each prime p such that n - p is also prime.
     S    Compute the sum of the resulting Booleans.
      H   Divide it by 2, since [p, n - p] and [n - p, p] have both been counted.
       Ċ  Ceil; round the resulting quotient up (needed if n = 2p).
Dennis
fuente
Oh, mucho mejor: D
Jonathan Allan
5

Python 2, 76 bytes

g=lambda n,k=2:n/k/2and all(x%i for x in[k,n-k]for i in range(2,x))+g(n,k+1)

Recursiva se arrastra desde k=2que n/2, sumando los valores en tanto ky n-kson primos. Sería bueno para contar nhacia abajo al mismo tiempo en lugar, pero esto tiene un problema que k=0y k=1son falsamente llamada Prime:

g=lambda n,k=0:n/k and all(x%i for x in[k,n]for i in range(2,x))+g(n-1,k+1)

La verificación de primalidad es la división de prueba, acortada al verificar ambas ky n-kjuntas. Encontré que esto es más corto que usar un generador de teoremas de Wilson (79 bytes):

f=lambda n,k=1,P=1,l=[]:n/k and P%k*(n-k in l+P%k*[k])+f(n,k+1,P*k*k,l+P%k*[k])

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 agregar n-ka la lista cuando llegamos a k. Una versión iterativa evita esto, pero tiene 82 bytes:

n=input()
s=P=k=1;l=[]
while k<n:l+=P%k*[k];s+=P%k*(n-k in l);P*=k*k;k+=1
print~-s
xnor
fuente
5

MATL , 8 bytes

tZq&+=Rz

Pruébalo en línea!

Explicación

Considere la entrada 8como un ejemplo

      % Take input implicitly
t     % Duplicate
      % STACK: 8, 8
Zq    % All primes up to that number
      % STACK: 8, [2 3 5 7]
&+    % Matrix with all pairwise additions
      % STACK: 8, [4  5  7  9
                   5  6  8 10
                   7  8 10 12
                   9 10 12 14]
=     % True for entries that equal the input
      % STACK: [0 0 0 0
                0 0 1 0
                0 1 0 0
                0 0 0 0]
R     % Extract upper triangular part (including diagonal). 
      % This removes pairs that are equal up to order
      % STACK: [0 0 0 0
                0 0 1 0
                0 0 0 0
                0 0 0 0]
z     % Number of nonzero entries
      % STACK: 1
      % Display implicitly

Es interesante observar el gráfico de la secuencia , utilizando una versión ligeramente modificada del código:

:"@       % Input n implicitly. For each k from 1 to n, push k
tZq&+=Rz  % Same code as above. Pushes the result for each k
]v'.'&XG  % End. Concatenate all results into a vector. Plot as dots

Para la entrada 10000el resultado es

ingrese la descripción de la imagen aquí

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

Luis Mendo
fuente
1
¡Ese Upper triangular parttruco es realmente genial!
DJMcMayhem
3

JavaScript (ES6), 77 73 70 bytes

Guardado 3 bytes gracias a @Arnauld

f=(n,x=n)=>--x<2||n%x&&f(n,x)
g=(a,b=a>>1)=>b>1?f(b)*f(a-b)+g(a,b-1):0

fes una función de prueba de primalidad; La función relevante es g.

ffunciona 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; regresar n%x.
  • f(n,x-1)De lo contrario, el número puede o no ser primo; decremento x e inténtelo de nuevo.

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

ETHproducciones
fuente
Como aes positivo, b=a>>1debería ahorrarte un byte.
Arnauld
@Arnauld ¡Gracias! Debería haber recordado al >>operador ...
ETHproductions
Con respecto a la función de prueba de primalidad, ¿podría hacer f=(n,x=n)=>--x<2||n%x&&f(n,x)?
Arnauld
@Arnauld Eso es genial, gracias :)
ETHproductions
2

05AB1E , 10 8 bytes

Extremadamente ineficiente.

D!f-pO;î

Pruébalo en línea! o Pruebe una forma menos eficiente de generar primos

Explicación

n = 10 usado como ejemplo.

D          # duplicate
           # STACK: 10, 10 
 !         # factorial
           # STACK: 10, 3628800
  f        # unique prime factors
           # STACK: 10, [2,3,5,7]
   -       # subtract
           # STACK: [8,7,5,3]
    p      # is prime
           # STACK: [0,1,1,1]
     O     # sum
           # STACK: 3
      ;    # divide by 2
           # STACK: 1.5
       î   # round up
           # STACK: 2
           # implicit output
Emigna
fuente
¿No podrías usar üen su lugar? Al igual que D!fü+r¢?
Urna de pulpo mágico
1
@carusocomputing: no veo cómo funcionaría eso. Para el ejemplo n=10que 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.
Emigna
2

GAP , 57 bytes

n->Number([2..QuoInt(n,2)],k->IsPrime(k)and IsPrime(n-k))

No creo que GAP tenga un camino más corto que este obvio. Numbercuenta cuántos elementos de una lista satisfacen un predicado.

Usándolo para calcular los primeros 100 valores:

gap> List([1..100],n->Number([2..QuoInt(n,2)],k->IsPrime(k)and IsPrime(n-k)));
[ 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 ]
Christian Sievers
fuente
2

Brachylog , 22 bytes

:{,A:B>=.:#pa+?,.=}fl

Pruébalo en línea!

Explicación

Una transcripción directa del problema.

:{                }f       Find all valid outputs of the predicate in brackets for the Input
                    l      Output is the number of valid outputs found

  ,A:B>=.                  Output = [A, B] with A >= B
         :#pa              Both A and B must be prime numbers
             +?,           The sum of A and B is the Input
                .=         Label A and B as integers that verify those constraints
Fatalizar
fuente
2

Mathematica, 52 bytes

Count[IntegerPartitions[#,{2}]//PrimeQ,{True,True}]&

El resultado se proporciona como una función anónima. Intenta trazar un gráfico sobre él:

DiscretePlot[
 Count[IntegerPartitions[#, {2}] // PrimeQ, {True, True}] &[i], {i, 1,
   1000}]

trama de la secuencia

Por cierto, el código tiene la misma longitud con la versión de función del código de demostración en OEIS.

Keyu Gan
fuente
2
49 bytes:PrimeQ[#~IntegerPartitions~{2}]~Count~{a=True,a}&
LegionMammal978
1

Jalea , 12 bytes

HRð,_@ÆPð×/S

TryItOnline
1-100

¿Cómo?

HRð,_@ÆPð×/S - Main link: n    e.g. 22
H            - halve
 R           - range          [1,2,3,4,5,6,7,8,9,10,11] (note this will be 1 to n//2)
  ð          - dyadic chain separation
   ,         - pair with
    _@       - n -           [[1,2,3,4,5,6,7,8,9,10,11],[21,20,19,18,17,16,15,14,13,12,11]]
      ÆP     - is prime? (1 if prime 0 if not)
                            [[0,1,1,0,1,0,1,0,0,0,1],[0,0,1,0,1,0,0,0,1,0,1]]
        ð    - dyadic chain separation
         ×/  - reduce with multiplication
                             [0,0,1,0,1,0,0,0,0,0,1]
           S - sum           3
Jonathan Allan
fuente
1

Raqueta 219 bytes

(let*((pl(for/list((i n) #:when(prime? i))i))(ll(combinations(append pl pl)2))(ol'()))(for/list((i ll))(define tl(sort i >))
(when(and(= n(apply + i))(not(ormap(λ(x)(equal? x tl))ol)))(set! ol(cons tl ol))))(length ol))

Sin golf:

(define(f n)
 (let* ((pl                                   ; create a list of primes till n
          (for/list ((i n) #:when (prime? i))
            i))
         (ll (combinations (append pl pl) 2)) ; get a list of combinations of 2 primes
         (ol '()))                            ; initialize output list
    (for/list ((i ll))                        ; test each combination
      (define tl (sort i >))
      (when (and (= n (apply + i))            ; sum is n
                 (not(ormap (lambda(x)(equal? x tl)) ol))) ; not already in list
        (set! ol (cons tl ol))))              ; if ok, add to list
    (println ol)                              ; print list
    (length ol)))                             ; print length of list

Pruebas:

(f 10)
(f 100)

Salida:

'((5 5) (7 3))
2
'((97 3) (89 11) (83 17) (71 29) (59 41) (53 47))
6
rnso
fuente
1

En realidad , 11 bytes

;R`p`░@-♂bΣ

Pruébalo en línea!

Explicación:

;R`p`░@-♂bΣ
 R`p`░       prime values in [1, n]
;     @-     subtract each value from n
        ♂b   convert each value to boolean
          Σ  sum
Mego
fuente
1

05AB1E , 6 bytes

;ÅP-pO

Pruébalo en línea!

Explicación:

                  # implicit input (example: 10)
;                 # divide input by 2 (5)
 ÅP               # primes up to that ([2, 3, 5])
   -              # subtract from the implict input ([8, 7, 5])
    p             # isPrime? ([0, 1, 1])
     O            # sum (2), implicit output
Mugriento
fuente
0

Haskell, 73 bytes

f n|r<-[a|a<-[2..n],all((<2).gcd a)[2..a-1]]=sum[1|p<-r,q<-r,q<=p,p+q==n]

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 ra todos los números primos hasta el número de entrada n, a continuación, tomar una 1para todos py qdesde rdonde q<=py p+q==ny sumarlos.

nimi
fuente