A079047 -id:A079047 - cp's OEIS frontend

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

Christopher J. Hanson, Jan 19 2014

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

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).

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.

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

{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++;
    }
}

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

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

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

A138109 Positive integers k whose smallest prime factor is greater than the cube root of k and strictly less than the square root of k.

Original entry on oeis.org

6, 15, 21, 35, 55, 65, 77, 85, 91, 95, 115, 119, 133, 143, 161, 187, 203, 209, 217, 221, 247, 253, 259, 287, 299, 301, 319, 323, 329, 341, 377, 391, 403, 407, 437, 451, 473, 481, 493, 517, 527, 533, 551, 559, 583, 589, 611, 629, 649, 667, 671, 689, 697, 703

Offset: 1

David S. Newman, May 04 2008

nonn

This sequence was suggested by Moshe Shmuel Newman.
A020639(n)^2 < a(n) < A020639(n)^3. - Reinhard Zumkeller, Dec 17 2014
In other words, k = p*q with primes p, q satisfying p < q < p^2. - Charles R Greathouse IV, Apr 03 2017
If "strictly less than" in the definition were changed to "less than or equal to" then this sequence would also include the squares of primes (A001248), resulting in A251728. - Jon E. Schoenfield, Dec 27 2022

			6 is a term because the smallest prime factor of 6 is 2 and 6^(1/3) = 1.817... < 2 < 2.449... = sqrt(6).
From _Michael De Vlieger_, Apr 27 2024: (Start):
Table of p*q where p = prime(n) and q = prime(n+k):
n\k   1     2     3     4     5     6     7     8     9    10    11
-------------------------------------------------------------------
1:    6;
2:   15,   21;
3:   35,   55,   65,   85,   95,  115;
4:   77,   91,  119,  133,  161,  203,  217,  259,  287,  301,  329;
     ... (End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Subsequence of A251728 and of A006881. A006094 is a proper subset.

Cf. A020639, A010846, A079047, A162306.

a138109 n = a138109_list !! (n-1)
a138109_list = filter f [1..] where
   f x = p ^ 2 < x && x < p ^ 3 where p = a020639 x
-- Reinhard Zumkeller, Dec 17 2014

s = {}; Do[f = FactorInteger[i]; test = f[[1]][[1]]; If [test < N[i^(1/2)] && test > N[i^(1/3)], s = Union[s, {i}]], {i, 2, 2000}]; Print[s]
Select[Range[1000],Surd[#,3]Harvey P. Dale, May 10 2015 *)

is(n)=my(f=factor(n)); f[,2]==[1,1]~ && f[1,1]^3 > n \\ Charles R Greathouse IV, Mar 28 2017

list(lim)=if(lim<6, return([])); my(v=List([6])); forprime(p=3,sqrtint(1+lim\=1)-1, forprime(q=p+2, min(p^2-2,lim\p), listput(v,p*q))); Set(v) \\ Charles R Greathouse IV, Mar 28 2017

from math import isqrt
from sympy import primepi, primerange
def A138109(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n+x+(t:=primepi(s:=isqrt(x)))+(t*(t-1)>>1)-sum(primepi(min(x//p,p**2)) for p in primerange(s+1)))
    return bisection(f,n,n) # Chai Wah Wu, Mar 05 2025

From Michael De Vlieger, Apr 27 2024: (Start)
Let k = a(n); row k of A162306 = {1, p, q, p^2, p*q}, therefore A010846(k) = 5.
A079047(n) = card({ q : p < q < p^2 }), p and q primes. (End)

A273257 Number of twin primes between prime(n) and prime(n)^2.

Original entry on oeis.org

0, 1, 3, 4, 8, 9, 16, 17, 21, 29, 30, 41, 48, 50, 61, 74, 87, 91, 110, 121, 123, 138, 152, 166, 187, 202, 208, 218, 223, 234, 276, 288, 315, 320, 365, 374, 394, 411, 432, 455, 480, 492, 541, 547, 567, 574, 626, 685, 708, 716, 732, 764, 772, 818, 851

Offset: 1

Jesse H. Crotts, Aug 28 2016

nonn

Both p and p+2 must appear in the indicated range, and a prime can only be used once (so (3, 5) and (5, 7) can't both be used).
It appears that there should be more twin primes between prime(n) and prime(n)^2 as n increases. Specifically this sequence should be strictly increasing.
Indeed even the number of twin primes between prime(n)^2 and prime(n+1)^2 (A057767) seems to have a lower bound of about n/11. - M. F. Hasler, Jun 27 2019

			For n=3, prime(3)=5 because it is the 5th prime. There are 3 twin prime subsets on the set {5,6,7,...,24,25} so the 3rd term is 3.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A001097, A079047, A143738.

Table[Function[w, Length@ Select[Prime[Range @@ w], Function[p, And[# - p == 2, # < Prime@ Last@ w] &@ NextPrime@ p]]]@ {n, PrimePi[Prime[n]^2]}, {n, 55}] (* Michael De Vlieger, Aug 30 2016 *)
ntp[n_]:=Count[Partition[Select[Range[Prime[n],Prime[n]^2],PrimeQ],2,1], ?(#[[2]]-#[[1]]==2&)]; Join[{0,1},Array[ntp,60,3]] (* _Harvey P. Dale, Nov 01 2016 *)

a(n)=if(n<3,return(n-1)); my(p=prime(n),q=p,s); forprime(r=q+1,p^2, if(r-q==2, s++); q=r); s \\ Charles R Greathouse IV, Aug 28 2016

More terms from Charles R Greathouse IV, Aug 28 2016

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A138109 Positive integers k whose smallest prime factor is greater than the cube root of k and strictly less than the square root of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

A273257 Number of twin primes between prime(n) and prime(n)^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions