Goldbach's comet: Difference between revisions

=={{header|J}}==

Task implementation:

<lang J> 10 10$#/.~4,/:~ 0-.~,(<:/~ * +/~) p:1+i.p:inv 202

1 1 1 2 1 2 2 2 2 3

3 3 2 3 2 4 4 2 3 4

3 4 5 4 3 5 3 4 6 3

5 6 2 5 6 5 5 7 4 5

8 5 4 9 4 5 7 3 6 8

5 6 8 6 7 10 6 6 12 4

5 10 3 7 9 6 5 8 7 8

11 6 5 12 4 8 11 5 8 10

5 6 13 9 6 11 7 7 14 6

8 13 5 8 11 7 9 13 8 9</lang>

And, for G(1e6):

<lang j>

-:+/1 p: 1e6-p:i.p:inv 1e6

5402</lang>

Explanation:

For the first part, the easiest approach seems to be to brute force it. The first 100 numbers starting with 4 end at 202, so we start by finding all primes less than 202.

Also, we can eliminate an odd/even test on the sum of primes by excluding 2 from our list of primes and including 4 as an explicit constant.

Also, since we are only concerned about distinct sums, we eliminate all pairs where the first prime in the sum exceeds the second prime in the sum.

So.. we compute a couple thousand sums, sort them in numeric order (prepending that list with 4), count how many times each unique value appears, and order the first 100 of those frequencies in a 10x10 table.

---

For G(1e6) that brute force approach becomes inefficient -- instead of about 2000 numbers, many of which are relevant, we would need to find over 6e9 sums, most of which would be irrelevant.

Instead, for G(1e6), we find all primes less than a million, subtract each from 1 million and count how many of the differences are prime and cut that in half. We cut that um in half because this approach counts each pair twice (once with the smallest value first, again with the smallest value second). Since 1e6 is not the square of a prime we do not have a prime which appears twice in one of these sums.