15. Prime tuples

This is a relatively straightforward problem. Simply create an Euler's sieve and then search it for primes that have the right spacing and number. The following method takes this approach:

// Look for groups of primes.
private List<List<int>> FindPrimeGroups(int max,
    int spacing, int number, bool[] isPrime)
{
    List<List<int>> results = new List<List<int>>();

    // Treat 2 specially.
    List<int> group = GroupAt(2, max, spacing, number, isPrime);
    if (group != null) results.Add(group);

    // Check odd primes to see if a group starts there.
    for (int p = 3; p <= max; p += 2)
    {
        group = GroupAt(p, max, spacing, number, isPrime);
        if (group != null) results.Add(group);
    }

    // Return the groups we found.
    return results;
}

This method's final parameter, isPrime, is an Euler's sieve containing primes up to the maximum value, max.

The method calls the GroupAt method, which will be described shortly, to see if there is a group of primes with the desired spacing and number starting with the value 2. Like many programs that deal with primes, this one treats 2 specially because it is the only even prime number, and that lets the code look only at odd values later.

After considering 2, the method loops over odd values up to max and uses the GroupAt method to see if any of them begin the right kind of prime groups.

The following code shows the GroupAt method:

// Determine whether the indicated number begins a group.
// Return the group or null if there is no group here.
private List<int> GroupAt(int startIndex, int max,
    int spacing, int number, bool[] isPrime)
{
    // See if there is room for a group.
    if (startIndex + (number - 1) * spacing > max)
        return null;

    // If there is no group here, return null.
    for (int i = 0; i < number; i++)
        if (!isPrime[startIndex + i * spacing])
            return null;

    // We found a group. Return it.
    List<int> result = new List<int>();
    for (int i = 0; i < number; i++)
        result.Add(startIndex + i * spacing);
    return result;
}

This method first checks to see if there is room before the max value for the desired primes. For example, if max is 100 and we're looking for a group of two primes spaced four apart, then there's no need to check for a group starting at position 97 because 97 + 4 = 101 is greater than max. (This check is important because it prevents the program from trying to access isPrime[101], which would cause an IndexOutOfRangeException.)

The method then loops through the desired number of values with the indicated spacing. For example, if spacing is 6, number is 3, and startIndex is 17, then the program would examine the values 17, 23, and 29.

If the isPrime array shows that any of the values are not prime, the method returns null.

If all of the examined values are prime, the method returns them in a list.

If you experiment with the program for a while, you'll notice something interesting about the values. If you look for two primes with any even spacing (as in {p, p + 2}, {p, p + 4}, {p, p + 6}, and so on), you'll find lots of results. However, if you look for three or four primes (as in {p, p + 2, p + 4} or {p, p + 6, p + 12}), you'll only get interesting results if the spacing is a multiple of three.

To see why, suppose we're looking for three primes and the spacing is 2, so we're looking for a set {p, p + 2, p + 4}. In that case, one of those three values must be a multiple of three, so that value cannot be prime. (Unless the first value is 3, as in {3, 5, 7} or {3, 7, 11}.) This means that you won't find groups of three or more with a spacing of 2.

The same argument works if the spacing is some other value that is not a multiple of three.

In contrast, if the spacing is a multiple of three, then either all of the values are multiples of three, or none of them are. If none of them are multiples of three, then they might all be prime.

Download the PrimeTuples example solution to see additional details.