%I #37 Jun 30 2024 22:07:14

%S 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,

%T 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,

%U 3,6,11,2,11,6,3,6,3,6,11,2,11,6,3,6,3,6,11,2

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

%C 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.

%C In this sequence, x = 4 and thus a(1) = A079047(4) = 11. - _Michael Somos_, Mar 09 2014

%C 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

%H Michael Somos, <a href="/A236175/b236175.txt">Table of n, a(n) for n = 1..80</a>

%H Christopher J. Hanson, <a href="http://www.codeproject.com/Articles/716180/The-structure-of-prime-numbers-and-twin-prime-gaps">The structure of prime numbers and twin prime gaps</a>

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,0,0,0,0,0,1).

%F a(n + 8) = a(n). - _Michael Somos_, Mar 09 2014

%F a(n) = A359632(n) - 1. - _Peter Munn_, Jan 21 2023

%t PadRight[{}, 100, {11, 6, 3, 6, 3, 6, 11, 2}] (* _Paolo Xausa_, Jun 30 2024 *)

%o (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 */

%o (C#)

%o // p(4) = GeneratePrimePattern( 4 );

%o static void GeneratePrimePattern( int ordinal )

%o {

%o // Contract

%o if( ordinal < 1 )

%o throw new ArgumentOutOfRangeException( "ordinal" );

%o // Local data

%o int size = 1 << 18;

%o int[] numberLine = Enumerable.Range( 2, size ).ToArray();

%o int pointer = 0;

%o // Apply sieve: for each integer greater than 1

%o while( pointer < numberLine.Length )

%o {

%o // Locals

%o int x = numberLine[pointer];

%o int index = pointer;

%o List<int> pattern = new List<int>();

%o int skips = 0;

%o // Find all products

%o for( int n = x + x; n < size; n += x )

%o {

%o // Fast forward through number-line

%o while( numberLine[++index] < n )

%o skips++;

%o // If the number was not already removed

%o if( numberLine[index] == n )

%o {

%o // Mark as not prime

%o numberLine[index] = 0;

%o // Add skip count to pattern

%o pattern.Add( skips );

%o // Reset skips

%o skips = 0;

%o }

%o // Otherwise we've skipped again

%o else skips++;

%o }

%o // Reduce number-line

%o numberLine = numberLine.Where( n => n > 0 ).ToArray();

%o // If we have a pattern we want

%o if( pattern.Any() && pointer == ordinal - 1 )

%o {

%o // Report pattern

%o int previousValue = 3; // > 2

%o System.Console.WriteLine( "Pattern P({0}) = {1} :: p({0}) = {2}", pointer + 1, numberLine[pointer], String.Join( ", ", pattern.TakeWhile( value => previousValue > 2 && ( previousValue = value ) > 0 ) ) );

%o return;

%o }

%o // Move number-line pointer forward

%o pointer++;

%o }

%o }

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

%Y Cf. A079047, A236185-A236190, A359632.

%K nonn,easy

%O 1,1

%A _Christopher J. Hanson_, Jan 19 2014

%E Edited by _Michael Somos_, Mar 09 2014. Made sequence periodic.