login
A236175
Prime gap pattern of compacting Eratosthenes sieve for prime(4) = 7.
13
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,1
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
FORMULA
a(n + 8) = a(n). - Michael Somos, Mar 09 2014
a(n) = A359632(n) - 1. - Peter Munn, Jan 21 2023
MATHEMATICA
PadRight[{}, 100, {11, 6, 3, 6, 3, 6, 11, 2}] (* Paolo Xausa, Jun 30 2024 *)
PROG
(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<int> pattern = new List<int>();
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++;
}
}
CROSSREFS
Equivalent sequences for prime(k): A236176 (k=5), A236177 (k=6), A236178 (k=7), A236179 (k=8), A236180 (k=9).
Sequence in context: A359492 A347357 A288069 * A193813 A338920 A080501
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Edited by Michael Somos, Mar 09 2014. Made sequence periodic.
STATUS
approved