# Goldbach's conjecture

Write a program that prompts the user for an even integer greater than 2.

Given Goldbach’s conjecture that every even integer greater than 2 can be expressed as the sum of two primes, print out two prime numbers which, when added together, provide the requested even number. Edit: the program only has to print A PAIR of primes, not all. For example:

4 : 2 + 2

6: 3 + 3

8: 3 + 5

10: 5 + 5 or 3 + 7

• "only has to print a pair of primes" Does that mean we are allowed to print more pairs? – Ayiko Jan 29 '14 at 17:59
• I suppose if it shortens the length of your code, but it should be organized – Rationality Jan 30 '14 at 4:34

# APL, 34 or 44 bytes

The first version is 34 symbol long and is restricted to characters from the original single-byte APL charsets, such as the one still supported in Dyalog APL:

↑c/⍨n=+/¨c←,∘.,⍨v/⍨~v∊v∘.×v←1↓⍳n←⎕


Explanation:

                               n←⎕   ⍝ ask for a number, store as n
v←1↓⍳n     ⍝ generate all integers from 2 to n
v∘.×v          ⍝ compute the product table of any two such integers
v/⍨~v∊               ⍝ select those that don't appear in the product table
c←,∘.,⍨                     ⍝ generate all possible pairs of these primes
n=+/¨c                           ⍝ check which pairs have a sum equal to n
↑c/⍨                                 ⍝ take the first that does


The second version is only 22 symbol long, because it exploits the π function to check for prime numbers, but that's only available in NARS2000 which uses Unicode, so the byte count is 44 in UCS-2:

2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1


Explanation:

                   ⎕    ⍝ ask for a number N
⍳ -1  ⍝ generate all naturals from 1 to N-1
(⍪,⌽)      ⍝ arrange it into a table of all pairs of naturals with sum N
{∧/0π⍵}            ⍝ check which pairs are made of all primes
2⍴(⌿⍨       )           ⍝ return the first pair that does


Examples

(⎕: is the prompt asking for a number)

      2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
4
2 2
2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
6
3 3
2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
8
3 5
2⍴(⌿⍨{∧/0π⍵})(⍪,⌽)⍳⎕-1
⎕:
124
11 113

• Would ¯2π⍳2πn work as a prime generator? – Oberon Jan 28 '14 at 14:43
• @Oberon what does the π operator do exactly? – primo Jan 28 '14 at 15:01
• Dyadic π switches with ⍺: ¯2πx calculates the xth prime, ¯1πx is the first prime less than x, 0πx tests x for primality, 1πx is the first prime greater than x, 2πx is the number of primes less than x, 10πx is the number of divisors of x, 11πx is the sum of all divisors of x, 12πx and 13πx are the Möbius and totient function, respectively. Last but not least, the monadic πx returns the prime factorization of x. – Oberon Jan 28 '14 at 15:10
• @Oberon that's specific to NARS2000, isn't it? Seems to be an interesting interpreter. I'll try it out and revise my answer. – Tobia Jan 28 '14 at 22:51
• @Tobia It is? Sorry then. I saw it referenced somewhere, but they never mentioned NARS2000. Good to know. – Oberon Jan 29 '14 at 14:28

# Python 2, 75 71 bytes

n=input();k=m=1;p={0}
while{n-k,k}-p:m*=k*k;k+=1;p|={m%k*k}
print n-k,k


Test it on Ideone.

### How it works

We use a corollary of Wilson's theorem: At all times, the variable m is equal to the square of the factorial of k - 1; k starts at value 1 and m at value 0!² = 1. The set p will consist of 0 and all prime numbers up to the current value of k.

In each iteration, we first check if both n - k and k belong to p, which is true if and only if the set difference of {n-k, k} and p is empty. If it is, the condition is falsy and the loop continues.

Note that k > 0, and {n - k, k} will satisfy the condition for some positive value of n - k (assuming that Goldbach's conjecture is true), so the 0 in p won't lead to false positives.

In the loop, we update k and m. The new value of m is m × k² = (k - 1)!² × k² = k!², and the new value of k is k + 1, so m = (k - 1)!² still holds before and after the update.

Then, we perform set union to add the value of m % k × k to p. By the corollary of Wilson's theorem, this will add 1 × k = k if k is prime and 0 × k = 0 if not.

When the loop ends, we print the last values of n - k and k, which will be primes with sum n.

• How on earth does that prime generating algorithm work? – Leaky Nun May 25 '16 at 8:18
• @LeakyNun I've added an explanation. – Dennis May 25 '16 at 16:52
• Oh... that is genius. – Leaky Nun May 25 '16 at 19:11

# Ruby 2.0 (65)

require'prime'
n=gets.to_i
Prime.find{|i|p [i,n-i]if(n-i).prime?}


## PHP - 73 bytes

<?for(;@($n%--$$n?:o=&argv>$$n=++$n)||${++$b}^${--$o};);echo"$b+$o";


Input is taken as a command line argument.

Sample usage:

$php goldbach.php 7098 19+7079  ## GolfScript 4133 32 ~(,2>.-1%]zip{{.,2>\{\%!}+,},!}?  Accepts command line argument e.g. echo "14" | ruby golfscript.rb goldbach.gs -> [2 12]  Finds all relevant partitions of the input number with: (,2>.-1%]zip #If only zip were a one-character command! It is so often useful.  and then finds the first partition where no numbers are NOT prime with: {np,!}? #For each partition, filter down to elements that are not prime, and only accept if there are no such results (since [] is falsey).  where the composite-checking block np is: {.,2>\{\%!}+,}  this block filters down to all numbers that evenly divide a given number. If there are no such numbers (so the number is prime), the result is [], which is falsey in GolfScript. ## perl 6: 69 $/=get;for grep &is-prime,^$/ {exit say$_,$_-$/ if ($/-$_).is-prime}


### R, 170112 83 characters

a=scan();b=2:a;p=b[rowSums(!outer(b,b,%%))<2];q=p[(a-p)%in%p];cat(a,":",q,a-q)


Indented:

a=scan() #Take user input as a numeric
b=2:a
p=b[rowSums(!outer(b,b,%%))<2] #Find all primes from 2 to user input
q=p[(a-p)%in%p] #Check which a-p also belong to p and takes the first one
cat(a,":",q,a-q)


Usage:

> a=scan();b=2:a;p=b[rowSums(!outer(b,b,%%))<2];q=p[(a-p)%in%p];cat(a,":",q,a-q)
1: 72
2:
72 : 5 67


Old solution at 112 characters, for posterity

a=scan();b=2:a;p=b[rowSums(!outer(b,b,%%))<2];w=which(outer(p,p,+)==a,T);cat(a,":",p[w[1,1]],p[w[1,2]])


Indented:

a=scan()
b=2:a
p=b[rowSums(!outer(b,b,%%))<2]
w=which(outer(p,p,+)==a,T) #Find the index of valid combinations
cat(a,":",p[w[1,1]],p[w[1,2]]) #Prints the first valid combination

• This is both crazy and genial!! – Tomas Feb 2 '14 at 20:08

# Python - 107

Basically an improvement on the second part of nutria's answer (I ran this on 2.7 but I think it should also work for 3.x)

p=lambda x:all(x%i!=0 for i in range(2,x))
n=input()
for i in range(2,n-1):
if p(i)&p(n-i): print i,n-i

• Are the newlines, and spaces after : mandatory? – mniip Feb 2 '14 at 20:22
• The tab could be reduced to a space, and the space before the print could be removed (shaves off 4 bytes). – clismique May 25 '16 at 7:00

a=/^(xx+?)(?!(xx+)\2+$)x*(?=\1$)(?!(xx+)\3+$)/.exec("x".repeat(prompt()));alert(a.length+"+"+a.length)  Now you have a regex that tests the Goldbach conjecture, which has low requirement on special features (basic back-reference support, positive and negative look-ahead). This uses String.prototype.repeat(), which is part of EcmaScript 6th edition proposal. Currently, this code only works on Firefox. I really need a better language that has terse command when working with regex... ## Scala, 286192172 148 chars Not the fastest but it works. Call g(10) to obtain the list of goldbach pairs for 10. def g(n:Int)={def p(n:Int,f:Int=2):Boolean=f>n/2||n%f!=0&&p(n,f+1) s"$n : "+(for(i<-2 to n/2;j=n-i if p(i)&&p(j))yield s"$i +$j").mkString(" or ")}


Conversion to C++ is straightforward.

# C - 139 129 characters

a,b;i(x,y){return x>y?x%y?i(x,y+1):0:x>1;}main(){scanf("%i",&a);for(b=a/2;b-->1;)i(b,2)&&i(a-
b,2)&&printf("%i:%i+%i\n",a,b,a-b);}

• You can shave 8 characters by removing the int declarations in your function i. You can save another 2 characters by removing the if and adding in another double ampersand: i(b,2)&&i(a-b,2)&&printf(...) – Josh Jan 27 '14 at 17:25
• Thanks! Didn't think of that &&. (I'll never get used to argument type silencing...) – Oberon Jan 27 '14 at 17:57
• I love your use of the nested ternary. – Josh Jan 27 '14 at 20:37

### newLISP - 169 148 chars

(define(p n)(=(length(factor n))1))
(define(g n)(when(even? n)(for(i 3 n 2)
(and(p i)(p(- n i))(println n {: } i { }(- n i))))))


includes the code to run it. The results are over-generous...

72: 5 67
72: 11 61
72: 13 59
72: 19 53
72: 29 43
72: 31 41
72: 41 31
72: 43 29
72: 53 19
72: 59 13
72: 61 11
72: 67 5


## Sage, 60

Similar in score and feel to r.e.s.'s solution, but I think it's different enough to post.

i=n=input()
while not{i,n-i}<set(primes(n)):i-=1
print i,n-i


## Sage, 65 62

n=input()
i=0
p=is_prime
while p(i)*p(n-i)==0:i+=1
print i,n-i


With the above in file goldbach.sage, execute it with Sage running in a terminal:

sage: %runfile goldbach.sage


Thanks to @boothby for the p=is_prime idea.

• You can get this down to 62 by setting p=is_prime. – boothby Feb 2 '14 at 17:13

g n=head[(a,b)|let q=p n,a<-q,b<-q,a+b==n]
p n=filter c[2..n]
c p=null[x|x<-[2..p-1],pmodx==0]


Explanation:

• g is the "goldbach" function. Calling g n gives you the pair of primes that add up to n.
• p is a function that generates a list of primes less than n.
• c is the prime checker function used to define p.

Example runs:

*Main> g 4
(2,2)
*Main> g 6
(3,3)
*Main> g 8
(3,5)
*Main> g 10
(3,7)
*Main> g 12
(5,7)
*Main> map g [4,6..100]
[(2,2),(3,3),(3,5),(3,7),(5,7),(3,11),(3,13),(5,13),(3,17),(3,19),(5,19),(3,23),(5,23),(7,23),(3,29),(3,31),(5,31),(7,31),(3,37),(5,37),(3,41),(3,43),(5,43),(3,47),(5,47),(7,47),(3,53),(5,53),(7,53),(3,59),(3,61),(5,61),(7,61),(3,67),(5,67),(3,71),(3,73),(5,73),(7,73),(3,79),(5,79),(3,83),(5,83),(7,83),(3,89),(5,89),(7,89),(19,79),(3,97)]


# Mathematica 56

This returns all of the solutions for the input integer.

Select[Tuples[Prime@Range@PrimePi[n = Input[]], 2], Tr@# == n &]


For example, when 1298 is input…

{{7, 1291}, {19, 1279}, {61, 1237}, {67, 1231}, {97, 1201}, {127, 1171}, {181, 1117}, {211, 1087}, {229, 1069}, {277, 1021}, {307, 991}, {331, 967}, {379, 919}, {421, 877}, {439, 859}, {487, 811}, {541, 757}, {547, 751}, {571, 727}, {607, 691}, {691, 607}, {727, 571}, {751, 547}, {757, 541}, {811, 487}, {859, 439}, {877, 421}, {919, 379}, {967, 331}, {991, 307}, {1021, 277}, {1069, 229}, {1087, 211}, {1117, 181}, {1171, 127}, {1201, 97}, {1231, 67}, {1237, 61}, {1279, 19}, {1291, 7}}

As written, it returns each solution twice.

Union[Sort/@ %]


{{7, 1291}, {19, 1279}, {61, 1237}, {67, 1231}, {97, 1201}, {127, 1171}, {181, 1117}, {211, 1087}, {229, 1069}, {277, 1021}, {307, 991}, {331, 967}, {379, 919}, {421, 877}, {439, 859}, {487, 811}, {541, 757}, {547, 751}, {571, 727}, {607, 691}}

• Input 2, ask an oracle if it halts, prove/disprove the twin primes conjecture, win – Filipq Mar 4 '14 at 17:40

# Julia, 62 Chars (85 with prompt)

julia> g(n)=collect(filter((x)->sum(x)==n,combinations(primes(n),2)))
g (generic function with 1 method)

julia> g(88)
4-element Array{Array{Int64,1},1}:
[5,83]
[17,71]
[29,59]
[41,47]

• This doesn't prompt the user (as required), does it? – r.e.s. Jan 27 '14 at 23:21
• No, didn't notice that. It would add many characters right now julia. g(int(readline(STDIN))) – gggg Jan 27 '14 at 23:27

A:.5A→B@%;A,4)4$~B+1,B-1#~B,B&  No prime built-ins. Example runs ?4 2 2 ?6 3 3 ?8 3 5 ?10 5 5  # JavaScript, 139137 136 a=prompt();function b(n){for(i=2;i<n;i++)if(n%i<1)return;return 1}for(c=2,r=1;c<a&&r;c++)if(b(c)&&b(a-c))alert(a+": "+c+" + "+(a-c)),r=0  ## Python 3 - 150 143 characters Old version (150 characters): p=lambda n:0 in[n % i for i in range(2,n)] n=int(input()) [print('%d+%d'%(a, b))for b in range(2,n)for a in range(2,n)if not(a+b!=n or p(a) or p(b))]  New version (thanks to ProgramFOX): p=lambda n:0 in[n%i for i in range(2,n)] n=int(input()) [print('%d+%d'%(a,b))for b in range(2,n)for a in range(2,n)if not((a+b!=n)|p(a)|p(b))]  It prints every combination, for example: 4 2+2 10 7+3 5+5 3+7 • | can safely be used with boolean type, so (a+b!=n)|p(a)|p(b) – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jan 27 '14 at 21:09 • Even shorter by using: print([(a,b)for b in range(2,n)for a in range(2,n)if not((a+b!=n)|p(a)|p(b))]) (prints a list of tuples, whose sum is n). Saves 8 bytes. – agtoever May 25 '16 at 10:52 • Also using r=range(2,n) and referencing r saves a few more. – agtoever May 25 '16 at 10:53 # q [116 chars] y where all each{{2=count where 0=(x mod)each til x+1}each x}each y:{a where x=sum each a:a cross a:til x}"I"$read0 0


No inbuilt function to find prime number.

Input

72


Output

5  67
11 61
13 59
19 53
29 43
31 41
41 31
43 29
53 19
59 13
61 11
67 5


## Python - 206

A little late to the party but I am practicing my golfing skills.

I actually coded this before I found this question! So mine doesn't include the beautiful lambda that the other Python solutions use.

import math
def p(n):
if n%2==0&n>2:return False
for i in range(3,n):
if n%i==0:return False
return True
X=int(input())
for i in range(2,X):
if p(i)&p(X-i):print i,X-i;break


# J - 35 32 char

"Prompt the user" is the bane of every J golfer. There go all my hard-earned characters!

p:(n,n)#:i.&n,+/~p:i.n=:".1!:1]1


Explained:

• ".1!:1]1 - Read in a string (1!:1) from input (file handle 1) and convert it to a number (".).
• p:i.n=: - Assign this number to the variable n, and then take the first n primes.
• +/~ - Make an addition table, n wide and n high.
• i.&n, - Turn the table into a single list, and then find the index of the first occurrence of n, which exists if Goldbach's conjecture is true.
• p:(n,n)#: - Retrieve the row and column from the index, and take the corresponding primes.

Usage:

   p:(n,n)#:i.&n,+/~p:i.n=:".1!:1]1
666
5 661
p:(n,n)#:i.&n,+/~p:i.n=:".1!:1]1
1024
3 1021


Had the prompt not been a requirement, here's a 25 character verb:

(,~p:@#:]i.~&,+/~@:p:@i.)


# Jelly, 8 bytes (non-competing)

_ÆRfÆR.ị


### How it works

_ÆRfÆR.ị  Main link. Argument: n (integer)

ÆR       Prime range; yield all primes in [1, ..., n].
_         Subtract all primes from n.
fÆR    Filter; intersect the list of differences with the prime range.
.ị  At-index 0.5; yield the last and first element.


# Julia, 50 49 bytes

~=primes;n=ARGS[]|>int
(n-~n)∩~n|>extrema|>show


Try it online!

If a function were acceptable, the code could be shortened to 32 bytes:

~=primes
!n=(n-~n)∩~n|>extrema


### How it works

~=primes creates an alias for the built-in primes function which returns a list of all prime numbers up to its argument. n=ARGS[]|>int parses the first command-line argument as saves it in n.

To find a suitable pair of primes, we first compute the aforementioned prime range with ~n. Then, n-~n yields all differences of these primes and n.

By intersecting (∩) the result with the prime range itself, we make sure that the remaining primes p are such that n - p is also a prime.

Finally, extrema takes the lowest and highest prime in the intersection, so their sum must be n.

# SQL, 295 284

In postgresql:

create function c(c int) returns table (n int, m int) as $$with recursive i(n) as (select 2 union all select n+1 from i where n<c), p as (select * from i a where not exists (select * from i b where a.n!=b.n and mod(a.n,b.n)=0)) select * from p a, p b where a.n+b.n=c$$ language sql;


Should be able to do it in half the space though, if it weren't for things like "no left outer join in recursion", "no subquery in recursion"...

Here's the output:

postgres=# select c(10);
c
-------
(3,7)
(5,5)
(7,3)
(3 rows)

postgres=# select c(88);
c
---------
(5,83)
(17,71)
(29,59)
(41,47)
(47,41)
(59,29)
(71,17)
(83,5)
(8 rows)


## Batch - 266

@echo off&setLocal enableDelayedExpansion&for /L %%a in (2,1,%1)do (set/aa=%%a-1&set c=&for /L %%b in (2,1,!a!)do set/ab=%%a%%%%b&if !b!==0 set c=1
if !c! NEQ 1 set l=!l!%%a,)&for %%c in (!l!)do for %%d in (!l!)do set/ad=%%c+%%d&if !d!==%1 set o=%%c + %%d
echo !o!


Set out neatly -

@echo off
setLocal enableDelayedExpansion
for /L %%a in (2,1,%1) do (
set /a a=%%a-1
set c=
for /L %%b in (2,1,!a!) do (
set /a b=%%a%%%%b
if !b!==0 set c=1
)
if !c! NEQ 1 set l=!l!%%a,
)
for %%c in (!l!) do for %%d in (!l!) do (
set /a d=%%c+%%d
if !d!==%1 set o=%%c + %%d
)
echo !o!


## Perl 5, 58 bytes

57, plus 1 for -nE

/^(11+?)(?!(11+)\2+$)1*(?=\1$)(?!(11+)\3+$)/;say for$1,$&  Input and output are in unary. Example: $ perl -nE'/^(11+?)(?!(11+)\2+$)1*(?=\1$)(?!(11+)\3+$)/;say for$1,\$&'
1111111111
111
1111111


Hat-tip.

# Oracle SQL 11.2, 202 bytes

WITH v(x,y,s)AS(SELECT LEVEL,LEVEL,0 FROM DUAL CONNECT BY LEVEL<=:1 UNION ALL SELECT x,y-1,s+SIGN(MOD(x,y))FROM v WHERE y>1),p AS(SELECT x FROM v WHERE x-s=2)SELECT a.x,b.x FROM p a,p b WHERE:1=a.x+b.x;


Un-golfed

WITH v(x,y,s) AS
(
SELECT LEVEL,LEVEL,0 FROM DUAL CONNECT BY LEVEL<=:1
UNION ALL
SELECT x,y-1,s+SIGN(MOD(x,y))FROM v WHERE y>1
)
,p AS (SELECT x FROM v WHERE x-s=2)
SELECT a.x,b.x
FROM p a,p b
WHERE :1=a.x+b.x;


## Python 3, 107 bytes

b=lambda x:all(x%y for y in range(2,x))
g=lambda x,i=2:((i,x-i)if b(i)&b(x-i)else g(x,i+1))if(i<x)else 0
`

b(x) is a primality test for x, and g(x) recurses through numbers to find two primes that fit.