Find runs of composite numbers (non-primes) in C#

example

I recently had a birthday and my age is a prime number, so like any normal person I was wondering how long a run of consecutive composite numbers comes after my current age. (Doesn’t everyone wonder such things?) This example finds runs of consecutive composite numbers–numbers that are not prime.

The longest possible run of sequential primes is 2 and includes the numbers 2 and 3. Any other prime has a multiple of 2 on either side of it, so all other runs of primes include only a single number. (It’s more interesting to look at pairs of primes–two primes separated by a single multiple of 2. I may write an example that looks at pairs of primes later.)

Composite numbers are another matter and you can find long sequences of consecutive composite numbers. For example, the numbers 24, 25, 26, 27, and 28 form a run of 5 sequential composite numbers.

The following two posts examine prime number distribution visually:

If you look very closely at the images produced by those examples, you’ll see that there are some fairly long black horizontal stripes indicating runs of composite numbers. In fact, if you look at large enough numbers, you can find composite runs of any length.

This example looks for those long runs. Enter the desired run length and click Go to make the program use the following code to search for composite runs.

private void btnGo_Click(object sender, EventArgs e)
{
    btnGo.Enabled = false;
    txtResults.Clear();
    Cursor = Cursors.WaitCursor;
    Refresh();

    int desired_length = int.Parse(txtNumComposites.Text);

    for (int length = 100; length <= 100000000; length *= 10)
    {
        // Make the sieve.
        bool[] is_prime = MakeSieve(length);

        // Look for a run.
        int run_start, run_length;
        run_start = FindRun(is_prime, desired_length,
            out run_length);

        // See if we found the desired run.
        if (run_start >= 0)
        {
            string txt = "Run length " +
                run_length.ToString() + ":\r\n";
            int found = 0;
            for (int i = run_start; i < is_prime.Length; i++)
            {
                if (is_prime[i]) break;
                txt += i.ToString() + " ";
                found++;
            }
            txtResults.Text = txt;
            Debug.Assert(found == run_length);
            break;
        }
    }

    if (txtResults.Text.Length == 0)
        txtResults.Text = "Not found";

    btnGo.Enabled = true;
    Cursor = Cursors.Default;
}

After some preliminaries, this code enters a loop where variable length takes the values 100, 1 thousand, 10 thousand, and so on increasing by a factor of 10 each time up to 100 million. For each value of length, the program calls the MakeSieve method to make an Euler’s sieve with length number of entries. (See the post Use Euler’s Sieve to find prime numbers in C# for information on Euler’s sieve and the code that builds it.)

The program then calls the FindRun method described shortly to search the sieve for a composite run of the desired length. If FindRun finds such a run, the code displays it and breaks out of its loop.

The following code shows the FindRun method.

// Return the index of the beginning of a run
// with the desried length.
private int FindRun(bool[] is_prime, int desired_length,
    out int found_length)
{
    // Make sure there is at least 1 composite number (4).
    Debug.Assert(is_prime.Length > 5);

    // Examine values.
    found_length = 0;
    int run_start = -1;
    bool in_run = false;
    for (int i = 4; i < is_prime.Length; i++)
    {
        // See if this value is prime.
        if (is_prime[i])
        {
            // The previous run is ending. (We know there
            // was a run because every prime is preceded
            // by a multiple of 2.)

            // See if the previous run is long enough.
            if (found_length >= desired_length)
            {
                // Return this run.
                return run_start;
            }

            // We're no longer in a run.
            in_run = false;
            found_length = 0;
        }
        else
        {
            if (!in_run)
            {
                // Start a run.
                in_run = true;
                run_start = i;
            }
            found_length++;     // Continue the run.
        }
    }

    // See if we finished with a run of the desired length.
    if (in_run && (found_length >= desired_length))
    {
        // Return this run.
        return run_start;
    }
    return -1;
}

The FindRun method starts at the value 4 (which is the first composite number) and loops through the is_prime array containing Euler’s sieve.

When the code finds a prime, you know that a composite run is ending, even if it is only a run of a single composite number. The code checks whether the run that’s ending is long enough and, if it is, returns it.

If the ending run isn’t long enough, the code resets is_run and found_length so it can start a new run with the next number (which is a multiple of two and therefore composite).

When the program finds a non-prime, it checks whether it is starting a new run. If it is, the method sets in_run to true an records the run’s starting index. Whether this is a new or old run, the program increments found_length.

If the method finishes checking the is_prime array without finding a run with the desired length, it returns -1 to indicate that it didn’t find the desired run.

If you examine large enough numbers, you’ll eventually find a composite run of any desired length, but you may need to examine some pretty big numbers. For example, if you look closely at the picture above, you’ll see that you won’t find a run of 200 composite numbers until you examine more than 20 million numbers.


Download Example   Follow me on Twitter   RSS feed


About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, mathematics and tagged , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *