Thought Process

Not too difficult problem. The idea to find S(n) is simple

1. First, I create a function search(i, j) which goes through all the neighbours of the i-th element of row j and it returns the position of the neighbours which are prime

   • For example search(8, 0) = [(7, 0), (9, 1)] since the prime neighbours of 37 are 29 and 47.

2. Then for every prime number on the n-th row, call the search function

   • Now there are 3 cases:

     1. If it returns 2 or more values, then this prime is part of a prime triplet

     2. If it returns 0 values, then this is not part of a prime triplet

     3. If it returns exactly 1 value, then we apply search on that value

        1. If this element has at least 2 prime neighbours (note that we will find the original prime we started with, so we need 2 neighbours not 1) then our original prime was part of a prime triplet

Now all we need to do is generate the 5 rows we care about (That is 2 rows below and above the row we care about) and find which elements are prime.

Finding the rows is trivial, and to find the primes I implemented a prime_sieve_in_range function, which I'm honestly very surprised I hadn't done yet! It is based on the Sieve of Eratosthenes.