Goldbach partitions

Question

The Goldbach conjecture states that every even number greater than two can be expressed as the sum of two primes. For example,

4 = 2 + 2
6 = 3 + 3
8 = 5 + 3

However, once we get to 10 something interesting happens. Not only can 10 be written as

5 + 5

but it can also be written as

7 + 3

Since 10 can be expressed as the sum of two primes two ways, we say that the "Goldbach partition" of 10 is 2. Or more generally,

The Goldbach partition of a number is the total number of distinct ways of writing n = p + q where p and q are primes and p >= q

Your challenge is to write a program or function that finds the Goldbach partition of a number. Now, technically the term "Goldbach partition" is used only to refer to even numbers. However, since the odd integer p + 2 can also be expressed as the sum of two primes if p > 2 is prime, we will extend this to all positive integers (A061358).

You may safely assume that your input will always be a positive integer, and you may take input and output in any of our default allowed methods, for example function arguments and return value, STDIN and STDOUT, reading and writing to a file, etc.

The Goldbach partitions of the positive integers up to 100 are:

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

As usual, standard loopholes apply, and the shortest answer in bytes wins!

Answer 1

Jelly, 8 bytes

_ÆRÆPSHĊ

Try it online! or verify all test cases.

How it works

_Æ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).

Answer 2

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)

Recursively crawls up from k=2 to n/2, adding up values where both k and n-k are prime. It would be nice to count n down at the same time instead, but this has a problem that k=0 and k=1 are falsely called 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)

The primality check is trial-division, shortened by checking both k and n-k together. I found this to be shorter than using a Wilson's Theorem generator (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])

The idea for this one is to keep a list of all primes in the bottom half to be checked by the time we get to the top half, but for the midpoint k=n/2, we haven't had time to add n-k to out list when we get to k. An iterative version gets around this, but is 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

Answer 3

MATL, 8 bytes

tZq&+=Rz

Try it online!

Explanation

Consider input 8 as an example

      % 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

---

It's interesting to observe the graph of the sequence, using a slightly modified version of the code:

:"@       % 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

For input 10000 the result is

You can try it at MATL Online (Refresh the page if the "Run" button doesn't change to "Kill" when pressed). It takes several about 25 seconds to produce the graph for input 3000; inputs above a few thousands will time out.

Answer 4

05AB1E, 6 bytes

;ÅP-pO

Try it online!

Explanation:

                  # 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

Answer 5

Regex 🐇 (ECMAScript^RME / Perl / PCRE), 38 33 32 bytes

^(xx+)(?=\1(x*))(?!\2?(xx+)\3+$)

Try it on replit.com! - ECMAScript (RegexMathEngine)
Try it online! - Perl
Try it online! - PCRE2

Takes its input in unary, as a string of x characters whose length represents the number. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)

^                     # tail = N = input number
(xx+)                 # \1 = conjectured first prime, automatically asserted
                      #      to be ≥ 2;
                      # tail = N-\1 == conjectured second prime
(?=
    \1                # tail -= \1; assert that second prime ≥ first prime;
                      # since the first prime is ≥ 2, this automatically
                      # asserts the second also to be so.
    (x*)              # \2 = tail == N-2*\1 == tool to make tail = \1
)
(?!                   # Assert there is no way to make the following match:
    \2?               # either leave tail unchanged, or tail = \1
    (xx+)\3+$         # Assert that tail is composite (which is only the same
                      # as being not prime for numbers ≥ 2)
)

Regex 🐝 (ECMAScript 2018 or better), 36 bytes

(?<=(x+x))(?=\1(x*))(?!\2?(xx+)\3+$)

Returns its output as the number of matches.

Try it online! - ECMAScript 2018
Try it online! - Python (import regex)
Try it online! - .NET

Regex 🐝 (_{^{ECMAScript 2018 or better /}} Java), 37 bytes

(?<=^(xx+))(?=\1(x*))(?!\2?(xx+)\3+$)

Try it online! - ECMAScript 2018
Try it online! - Java
Try it online! - Python (import regex)
Try it online! - .NET

Answer 6

JavaScript (ES6), 77 73 70 bytes

Saved 3 bytes thanks to @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

f is a primality-test function; the relevant function is g.

f works by recursively counting down from n-1; the control flow at each stage goes like this:

• x<2|| If x < 2, the number is prime; return 1.
• n%x&& Otherwise if n mod x = 0, the number is not prime; return n%x.
• f(n,x-1) Otherwise, the number may or may not be prime; decrement x and try again.

g works in a similar fashion, though with not so much control flow. It works by multiplying f(b) by f(a-b) for each integer b in the range [2, floor(a/2)], then summing the results. This gives us the number of pairs that sum to a where both numbers in the pair are prime, which is exactly what we want.

Answer 7

GAP, 57 bytes

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

I don't think GAP has a shorter way than this obvious one. Number counts how many elements of a list satisfy a predicate.

Using it to compute the first 100 values:

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 ]

Answer 8

Brachylog, 22 bytes

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

Try it online!

Explanation

A straight up transcription of the problem.

:{                }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

Answer 9

Mathematica, 52 bytes

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

The result is provided as an anonymous function. Try to plot a graph over it:

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

By the way, the code has the same length with function version of demo code on OEIS.

Answer 10

05AB1E, 10 8 bytes

Extremely inefficient.

D!f-pO;î

Try it online! or Try a less efficient way of generating primes

Explanation

n = 10 used as example.

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

Answer 11

Vyxal, 6 bytes

½~æ-æ∑

Try it Online! Includes header and footer to produce first 100 results.

Answer 12

Jelly, 12 bytes

HRð,_@ÆPð×/S

TryItOnline
1-100

How?

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

Answer 13

Racket 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))

Ungolfed:

(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

Testing:

(f 10)
(f 100)

Output:

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

Answer 14

Actually, 11 bytes

;R`p`░@-♂bΣ

Try it online!

Explanation:

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

Answer 15

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]

Usage example: 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].

Direct implementation of the definition: first bind r to all primes up to the input number n, then take a 1 for all p and q from r where q<=p and p+q==n and sum them.