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
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).
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
KEYWORD
nonn,easy
AUTHOR
Christopher J. Hanson, Jan 19 2014
EXTENSIONS
Edited by Michael Somos, Mar 09 2014. Made sequence periodic.
STATUS
approved