# Solve Goldbach's Conjecture

Goldbach's Conjecture states that every even whole number greater than 2 is the sum of 2 prime numbers. Your task is to return those 2 prime numbers, given an even whole number as input. There are often multiple solutions - any solution will do.

# Input/Output Examples

These examples only show one of potentially many possible outputs.

```
4 -> 2, 2
6 -> 3, 3
24 -> 5, 19
120 -> 7, 113
1000 -> 3, 997
```

This is code-golf, so shortest answer in each language wins.

P.S. If no one finds a test case that has no solution, I'll consider the problem solved by engineer's induction.

[Husk], 9 bytes ḟo=⁰Σπ2 …

2y ago

[JavaScript (Node.js)], 87 byt …

2y ago

Japt, 13 bytes o ï æ@¶X …

2y ago

[APL (Dyalog Unicode)], 32 byt …

2y ago

J, 46 char ``` ({.(+/m)#a) …

12mo ago

MATL, 19 bytes ``` XH:YqtZ!t …

1y ago

Ruby, 62 bytes require' …

1y ago

[Python 3.8], 112 bytes …

1y ago

Ruby, 69 bytes ```RUBY req …

1y ago

J, 50 bytes ```J {{({[:y&( …

1y ago

## 10 answers

# JavaScript (Node.js), 87 bytes

```
f=(a,b=2,c=a-b,d=(a,b=2)=>b<a?a%b&&d(a,b+1):1,e=a=>d(++a)?a:e(a))=>d(c)?[b,c]:f(a,e(b))
```

#### 0 comment threads

# Husk, 9 bytes

```
ḟo=⁰Σπ2İp
```

## Explanation

```
ḟo=⁰Σπ2İp
İp take the infinite list of primes
π2 cartesian power 2 (all possible pairs)
ḟo first pair which satisfies:
Σ sum
= equals
⁰ input?
```

#### 0 comment threads

# Japt, 13 bytes

```
o ï æ@¶Xx*Xej
```

```
o ï æ@¶Xx*Xej :Implicit input of integer U
o :Range [0,U)
ï :Cartesian product
æ :First pair X that returns true
@ :When passed through the following function
¶ : Test U for equality with
Xx : X Reduced by addition
* : Multiplied by
Xe : Is every element in X
j : Prime?
```

#### 0 comment threads

# APL (Dyalog Unicode), 32 bytes (SBCS)

```
{⊃(⊢(/⍨)⍵=+/¨),∘.,⍨(⊢~∘.×)⍨1↓⍳⍵}
```

```
{⊃(⊢(/⍨)⍵=+/¨),∘.,⍨(⊢~∘.×)⍨1↓⍳⍵}
⍳⍵ ⍝ Range from 1 to n
1↓ ⍝ Drop the 1st number (make 2 to n)
(⊢~∘.×)⍨ ⍝ Filter prime numbers
⍨ ⍝ Use range as both arguments for train
∘.× ⍝ Outer product - multiply all numbers
⍝ in [2..n] by every other number in [2..n],
⍝ giving all composite numbers up to n
~ ⍝ Remove those composite numbers from
⊢ ⍝ that same range (2 to n)
∘.,⍨ ⍝ Cartesian product with itself
, ⍝ Flatten into vector of prime pairs
(⊢(/⍨)⍵=+/¨) ⍝ Filter the ones that sum to n
+/¨ ⍝ Map each pair to its sum
⍵= ⍝ Check if it equals n
(/⍨) ⍝ Keep elements where the pair equals n in
⊢ ⍝ that same vector of prime pairs
⊃ ⍝ Get the first pair that works
```

#### 0 comment threads

# J, 50 bytes

```
{{({~[:y&(i.&1@:=)[:>+/&.>),{@(,&<)~p:i.p:^:_1 y}}
```

A nasty DD solution.

```
{{({~[:y&(i.&1@:=)[:>+/&.>),{@(,&<)~p:i.p:^:_1 y}}
p:i.p:^:_1 NB. primes less than y
{@(,&<) NB. cartesian product, 2d array of boxed pairs
, NB. flatten boxes
({~[:y&(i.&1@:=)[:>+/&.>) NB. monadic hook
[:>+/&.> NB. sum each pair and unbox
[:y&(i.&1@:=) NB. first occurrence of y in list of sums
{~ NB. flip arguments to index boxed pairs
```

#### 0 comment threads

# Ruby, 69 bytes

```
require'prime';->n{Prime.first(n).then{_1.product _1}.find{_1+_2==n}}
```

#### 0 comment threads

# J, 46 char

```
({.(+/m)#a),{:(+/"1 m=:x=+/~a)#a=:p:i._1 p:x=:
```

**Sample runs**

({.(+/m)#a),{:(+/"1 m=:x=+/~a)#a=:p:i._1 p:x=:4

2 2

({.(+/m)#a),{:(+/"1 m=:x=+/~a)#a=:p:i._1 p:x=:6

3 3

({.(+/m)#a),{:(+/"1 m=:x=+/~a)#a=:p:i._1 p:x=:24

5 19

({.(+/m)#a),{:(+/"1 m=:x=+/~a)#a=:p:i._1 p:x=:120

7 113

({.(+/m)#a),{:(+/"1 m=:x=+/~a)#a=:p:i._1 p:x=:1000

3 997

#### 0 comment threads

# MATL, 19 bytes

```
XH:YqtZ*!tsH=f1Z)Z)
```

I'm still a novice at MATL, so I am all ears to any improvements.

```
XH:YqtZ*!tsH=f1Z)Z)
XH - copy implicit input to H clipboard
: - range 1..n
Yq - vectorized n-th prime
t - duplicate
Z* - cartesian product
! - transpose
t - duplicate
s - sum columns
H= - paste from clipboard H and vectorized equal
f - find indices of nonzeros
1Z) - first index returned from f
Z) - use that index to find first pair from Z*!
```

#### 0 comment threads

# Python 3.8, 112 bytes

```
def f(x):y=[i for i in range(2,x)if not[j for j in range(2,i)if i%j<1]];return[(q,x-q)for q in y if x-q in y][0]
```

## 0 comment threads