login
A236185
Differences between terms of compacting Eratosthenes sieve for prime(4) = 7.
12
4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2
OFFSET
1,1
COMMENTS
P(x) is a function which represents a prime number at a ordinal x.
This pattern, dp(x) is a sequence of the differences between consecutive prime numbers as described by p(x).
For P(4), dp(4)is the relative offsets of the next 7 primes: 7, +4 = 11, +2 = 13, +4 = 17, +2 = 19, +4 = 23, +6 = 29, +2 = 31
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 this sequence. - Michael Somos, Mar 12 2014
FORMULA
a(n + 8) = a(n). - Michael Somos, Mar 10 2014
a(n) = 4*((n+2) mod 2) + 2*((n+1) mod 2) + 4*(f(8,n+2)+f(8,n)) - 2*f(8,n+1), where f(x,n)= floor(n/x)-floor((n-1)/x). - Gary Detlefs, Nov 16 2020
PROG
(PARI) {a(n) = my(A); if( n<1, 0, A = vector( n*28 + 48, k, k+1); for( i = 1, 3, A = select( k -> k%prime(i), A) ); polcoeff( (1 - x) * Ser( select( k -> k>7 && (k%7) == 0, A) / 7), n)) }; /* Michael Somos, Mar 10 2014 */
(C#)
// dp(4) = GeneratePrimeDifferencialPattern( 4 );
static void GeneratePrimeDifferencialPattern( 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;
int count = 0;
bool counting = true;
// 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 )
{
// Add skip count to pattern
pattern.Add( numberLine[index] );
// Mark as not prime
numberLine[index] = 0;
// Reset skips
if( counting )
{
count++;
if( skips <= 2 )
counting = false;
}
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 prime = numberLine[ordinal-1];
var d = pattern.Take( count ).ToArray();
List<int> dp = new List<int>();
for( int y = 1; y < count; y++ )
dp.Add( ( d[y] - d[y - 1] ) / prime );
System.Console.WriteLine( "Pattern P({0}) = {1} :: dp({0}) = {2}", pointer + 1, numberLine[pointer], String.Join( ", ", dp ) );
return;
}
// Move number-line pointer forward
pointer++;
}
}
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
Edited by Michael Somos, Mar 12 2014. (Added code and comments, refined description.)
STATUS
approved