Goldbach's comet: Difference between revisions

=={{header|J}}==

Task implementation:

<syntaxhighlight 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</syntaxhighlight>

And, for G(1e6):

<syntaxhighlight lang="j">

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

5402</syntaxhighlight>

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 (and sum all pairs of these primes).

Also, we can eliminate an odd/even test on these sums 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 sums, almost 600 of which are relevant, we would need to find over 6e9 sums, and about 6e9 of them 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 sum 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).