# 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