Essays/Goldbach Conjecture
< Essays
Jump to navigation
Jump to search
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.