Goldbach's conjecture

Question

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

Answer 1

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

Answer 2

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.

Answer 3

Ruby 2.0 (65)

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

Answer 4

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

Answer 5

GolfScript 41 33 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.

Answer 6

perl 6: 69

$/=get;for grep &is-prime,^$/ {exit say $_,$_-$/ if ($/-$_).is-prime}

Answer 7

R, 170 112 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: 
Read 1 item
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

Answer 8

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

Answer 9

JavaScript (ES6) (Regex), 105

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

Answer 10

Scala, 286 192 172 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.

Answer 11

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);}

Answer 12

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))))))
(g(int(read-line)))

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

Answer 13

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

Answer 14

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.

Answer 15

Haskell, 97C

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],p`mod`x==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)]

Answer 16

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

Answer 17

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.

Answer 18

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]

Answer 19

GTB, 31

For your TI-84 Calculator

`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

Answer 20

JavaScript, 139 137 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

Answer 21

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

Answer 22

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

Answer 23

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

Answer 24

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

Answer 25

Jelly, 8 bytes (non-competing)

_ÆRfÆR.ị

Try it online! or verify all test cases.

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.

Answer 26

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:])

Answer 27

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)

Answer 28

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!

Answer 29

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.

Answer 30

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;