A236175 Prime gap pattern of compacting Eratosthenes sieve for prime(4) = 7.

11, 6, 3, 6, 3, 6, 11, 2, 11, 6, 3, 6, 3, 6, 11, 2, 11, 6, 3, 6, 3, 6, 11, 2, 11, 6, 3, 6, 3, 6, 11, 2, 11, 6, 3, 6, 3, 6, 11, 2, 11, 6, 3, 6, 3, 6, 11, 2, 11, 6, 3, 6, 3, 6, 11, 2, 11, 6, 3, 6, 3, 6, 11, 2, 11, 6, 3, 6, 3, 6, 11, 2, 11, 6, 3, 6, 3, 6, 11, 2

Offset: 1

Author

Christopher J. Hanson, Jan 19 2014

Keywords

• nonn
• easy

Comments

P(x) is a function which produces a prime number at a particular ordinal x (A000040). This pattern, p(x), describes the number of values emitted as potentially prime by a reductive sieve before a value is marked "not prime" when processing the prime at ordinal x. p(x) represents only the unique portion of the pattern and terminates when the pattern repeats. The first digit of p(x) corresponds to A079047 for index x.

In this sequence, x = 4 and thus a(1) = A079047(4) = 11. - Michael Somos, Mar 09 2014

The Eratosthenes sieve can be expressed as follows. Start with S1 = [2, 3, 4, 5, ...] the list of numbers bigger than 1. Removing all multiples of the first element 2 yields the list S2 = [3, 5, 7, 9, ...]. Removing all multiples of the first element 3 yields S3 = [5, 7, 11, 13, 17, 19, ...], Removing all multiples of the first element 5 yields S4 = [7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, ...], and so on. The list of first differences of S4 is [4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, ...] which is A236185. The list of indices of all multiples of S4(1) = 7 is [1, 13, 20, 24, 31, 35, 42, 54, 57, 69, 76, 80, ...]. The list of first differences of this list is [12, 7, 4, 7, 4, 7, 12, 3, 12, 7, 4, ...]. Subtract one from each element yields [11, 6, 3, 6, 3, 6, 11, 2, 11, 6, 3, ...] which is this sequence. - Michael Somos, Mar 12 2014

Links

• Michael Somos, Table of n, a(n) for n = 1..80
• Christopher J. Hanson, The structure of prime numbers and twin prime gaps
• Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,1).

Crossrefs

Equivalent sequences for prime(k): A236176 (k=5), A236177 (k=6), A236178 (k=7), A236179 (k=8), A236180 (k=9).

Cf. A079047, A236185-A236190, A359632.

Programs

Mathematica

PadRight[{}, 100, {11, 6, 3, 6, 3, 6, 11, 2}] (* Paolo Xausa, Jun 30 2024 *)

PARI

{a(n) = my(A); if( n<1, 0, A = vector( (n+1) * 1024 \ 37, k, k+1); for( i = 1, 3, A = select( k -> k%prime(i), A) ); polcoeff( (1 - x) * Ser( select( k -> (k%7) == 0, A, 1)), n) - 1) }; /* Michael Somos, Mar 09 2014 */
(C#)
// p(4) = GeneratePrimePattern( 4 );
static void GeneratePrimePattern( int ordinal )
{
    // Contract
    if( ordinal < 1 )
        throw new ArgumentOutOfRangeException( "ordinal" );
    // Local data
    int size = 1 << 18;
    int[] numberLine = Enumerable.Range( 2, size ).ToArray();
    int pointer = 0;
    // Apply sieve: for each integer greater than 1
    while( pointer < numberLine.Length )
    {
        // Locals
        int x = numberLine[pointer];
        int index = pointer;
        List pattern = new List();
        int skips = 0;
        // Find all products
        for( int n = x + x; n < size; n += x )
        {
            // Fast forward through number-line
            while( numberLine[++index] < n )
                skips++;
            // If the number was not already removed
            if( numberLine[index] == n )
            {
                // Mark as not prime
                numberLine[index] = 0;
                // Add skip count to pattern
                pattern.Add( skips );
                // Reset skips
                skips = 0;
            }
            // Otherwise we've skipped again
            else skips++;
        }
        // Reduce number-line
        numberLine = numberLine.Where( n => n > 0 ).ToArray();
        // If we have a pattern we want
        if( pattern.Any() && pointer == ordinal - 1 )
        {
            // Report pattern
            int previousValue = 3; // > 2
            System.Console.WriteLine( "Pattern P({0}) = {1} :: p({0}) = {2}", pointer + 1, numberLine[pointer], String.Join( ", ", pattern.TakeWhile( value => previousValue > 2 && ( previousValue = value ) > 0 ) ) );
            return;
        }
        // Move number-line pointer forward
        pointer++;
    }
}

Formula

a(n + 8) = a(n). - Michael Somos, Mar 09 2014

a(n) = A359632(n) - 1. - Peter Munn, Jan 21 2023

Extensions

Edited by Michael Somos, Mar 09 2014. Made sequence periodic.