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 …
4y ago
[JavaScript (Node.js)], 87 byt …
4y ago
Japt, 13 bytes o ï æ@¶X …
3y ago
[APL (Dyalog Unicode)], 32 byt …
3y ago
J, 46 char ``` ({.(+/m)#a) …
2y ago
MATL, 19 bytes ``` XH:YqtZ!t …
3y ago
Ruby, 62 bytes require' …
3y ago
[Python 3.8], 112 bytes …
3y ago
Ruby, 69 bytes ```RUBY req …
3y ago
J, 50 bytes ```J {{({[:y&( …
3y ago
10 answers
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
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
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
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
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
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
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
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
0 comment threads