Essays/Goldbach Conjecture

The Goldbach conjecture states that every even number > 2 can be expressed as the sum of two primes.

g1=: 3 : 0
 n=. y
 assert. (2<n) > 2|n
 i=. i.10>.>.(^.n)*^.^.n
 while. 1 do.
  c=. p: i
  j=. (1&p: i. 1:) 1>.n-c
  if. j<#c do. n (],-) j{c return. end.
  i=. i+#i
 end.
)

   g1 100
3 97
   g1 1e6
17 999983
   g1 10^50x
383 99999999999999999999999999999999999999999999999617

g1 n finds the smallest prime p (and hence the largest prime q ) such that n=p+q . The list of smallest primes p in the sums is OEIS A020481 while the list of largest primes q is OEIS A020482.

The phrase g1"0 ]4+2*i.<:-:n expresses each even number between 4 and n as a sum of of two primes, but there is a more efficient method: Let p be all the primes less than *:^.n , and q be all the primes less than n . Compute all possible sums of p against q ,  and only apply g1 to those numbers not among the sums.

plt=: i.&.(p:^:_1)  NB. all primes less than x

gv=: 3 : 0
 n=. y
 assert. (2<n) > 2|n
 v=. 4+2*i.<:-:n
 q=. plt n
 p=. q {.~ q (>i.1:) >.*:^.n
 c=. , p +/ q
 t=. (<.(c i. v)%#q) { p,0
 v (],.-) t i}~ {.@g1"0 i{v [ i=. I.0=t
)

   gv 20
2  2
3  3
3  5
3  7
5  7
3 11
5 11
7 11
3 17

   load 'plot'
   plot {."1 gv 4e5

---

See also

MathWorld
On-line Encyclopedia of Integer Sequences

---

Contributed by Roger Hui.