# 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? Jan 29, 2014 at 17:59
• I suppose if it shortens the length of your code, but it should be organized Jan 30, 2014 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? Jan 28, 2014 at 14:43
• @Oberon what does the π operator do exactly? Jan 28, 2014 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. Jan 28, 2014 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. Jan 28, 2014 at 22:51
• @Tobia It is? Sorry then. I saw it referenced somewhere, but they never mentioned NARS2000. Good to know. Jan 29, 2014 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? May 25, 2016 at 8:18
• @LeakyNun I've added an explanation. May 25, 2016 at 16:52
• Oh... that is genius. May 25, 2016 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[1]>$$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][1];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][1] #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][1];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!! Feb 2, 2014 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? Feb 2, 2014 at 20:22
• The tab could be reduced to a space, and the space before the print could be removed (shaves off 4 bytes). May 25, 2016 at 7:00

a=/^(xx+?)(?!(xx+)\2+$)x*(?=\1$)(?!(xx+)\3+$)/.exec("x".repeat(prompt()));alert(a[1].length+"+"+a[0].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, 2014 at 17:25
• Thanks! Didn't think of that &&. (I'll never get used to argument type silencing...) Jan 27, 2014 at 17:57
• I love your use of the nested ternary.
– Josh
Jan 27, 2014 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. Feb 2, 2014 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
– Moop
Mar 4, 2014 at 17:40
• With this MSE solution we can do it in 47 bytes: Cases[{1,1}~FrobeniusSolve~Input[],{__?PrimeQ}] or even in 42 bytes as a function: Cases[{1,1}~FrobeniusSolve~#,{__?PrimeQ}]&. Jan 26 at 15:58

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

# 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? Jan 27, 2014 at 23:21
• No, didn't notice that. It would add many characters right now julia. g(int(readline(STDIN)))
– gggg
Jan 27, 2014 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  • I think you can shave off 2 more chars by return; instead of return 0; Jan 27, 2014 at 23:16 ## 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) Jan 27, 2014 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. May 25, 2016 at 10:52 • Also using r=range(2,n) and referencing r saves a few more. May 25, 2016 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.


Python3 version of this one -110 bytes

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


and a super golfed version:

exec(bytes('㵰慬扭慤砠愺汬砨椥㴡‰潦⁲⁩湩爠湡敧㈨砬⤩渊椽瑮椨灮瑵⤨਩潦⁲⁩湩爠湡敧㈨測ㄭ㨩 晩瀠椨☩⡰⵮⥩›牰湩⡴Ⱪ⵮⥩','u16')[2:])

• Welcome to Code Golf! Nice first answer. Jan 26 at 22:27
• This program does not run and it is unclear what your actual code is. Also, neither of the two programs you wrote match the bytecount you specified. Please fix your answer and properly format the code. Jan 26 at 23:54
• @Makonede i fixed the issues you found.
– Gabe
Jan 28 at 1:07
• Your code still doesn't work, and the bytecount is still wrong. Also, like I asked, please properly format your code. Jan 28 at 2:48
• @Razetime thanks for noticing when i was making the answer it didn't show the first line.
– Gabe
Jan 28 at 22:31

# 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;
`