cp's OEIS Frontend

From Antti Karttunen, Dec 06 2014: (Start)

For n >= 2, a(n) tells in which column of the sieve of Eratosthenes (see A083140, A083221) n occurs in. A055396 gives the corresponding row index.

(End)

The function in Brocard's Conjecture, which states that for n >= 2, a(n) >= 4.

The lines in the graph correspond to prime gaps of 2, 4, 6, ... . - T. D. Noe, Feb 04 2008

Lengths of blocks of consecutive primes in A000430 (union of primes and squares of primes). - Reinhard Zumkeller, Sep 23 2011

In the n-th step of the sieve of Eratosthenes, all multiples of prime(n) are removed. Then a(n) gives the number of new primes obtained after the n-th step. - Jean-Christophe Hervé, Oct 27 2013

More precisely, after the n-th step, one is sure to have eliminated all composites less than prime(n+1)^2, since any composite N has a prime factor <= sqrt(N). It is in exactly this (restricted) sense that a(n) yields the number of "new primes" (additional numbers known to be prime) after the n-th step. But one knows after the n-th step also that all remaining numbers between prime(n+1)^2 and prime(n+1)*(prime(n+1)+2) are prime: By construction they don't have a factor less than prime(n+1) and they don't have a factor prime(n+1) so the least prime factor could be prime(n+2) >= prime(n+1)+2. For example, after eliminating multiples of 3 in the 2nd step, one has (2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 31, 35, ...) and one knows that all remaining numbers strictly in between 5^2=25 and 5*(5+2)=35 are prime, too. - M. F. Hasler, Dec 31 2014

Numerically, the slope of the lowest "ray" m(n) = min {a(k); k>n}, seems to converge to a value somewhere in the range 1.75 < m(n)/n < 1.8; with m(n)/n > 1.7 for n > 900, m(n)/n > 1.75 for n > 2700. - M. F. Hasler, Dec 31 2014

Legendre's conjecture (see A014085) would imply that a(n) >= 2 for all n and that sequences A054272, A250473 and A250474 were thus strictly increasing (see the Wikipedia article about Brocard's conjecture). - Antti Karttunen, Jan 01 2015

a(n) >= 4 up to at least n = 4*10^5. - Eric W. Weisstein, Jan 13 2025

Position of the first composite number (which is always 4) on row n of A249821. The fourth column of A249822.

Position of the first nonfixed term on row n of arrays of permutations A251721 and A251722.

According to the definition, this is the number of multiples of prime(n) below prime(n)^3 (and thus, the number of numbers below prime(n)^2) which do not have a smaller factor than prime(n). That is, the numbers remaining below prime(n)^2 after deleting all multiples of primes less than prime(n), as is done by applying the first n-1 steps of the sieve of Eratosthenes (when the first step is elimination of multiples of 2). This explains that the first differences are a(n+1)-a(n) = A050216(n)-1 for n>1, and a(n) = A054272(n)+2. - M. F. Hasler, Dec 31 2014

From Antti Karttunen, Dec 17 2014, further edited Jan 01 & 04 2014: (Start)

Semiprimes p*q, p < q, such that the smallest r for which r^k <= p and q < r^(k+1) [for some k >= 0] is q+1, and thus k = 0. In other words, semiprimes whose both prime factors do not fit (simultaneously) between any two consecutive powers of any natural number r less than or equal to the larger prime factor. This condition forces the larger prime factor q to be greater than the square of the smaller prime factor because otherwise the opposite condition given in A251728 would hold.

Assuming that A054272(n), the number of primes in interval [prime(n), prime(n)^2], is nondecreasing (implied for example if Legendre's or Brocard's conjecture is true), these are also "unsettled" semiprimes that occur in a square array A083221 constructed from the sieve of Eratosthenes, "above the line A251719", meaning that if and only if row < A251719(col) then a semiprime occurring at A083221(row, col) is in this sequence, and conversely, all the semiprimes that occur at any position A083221(row, col) where row >= A251719(col) are in the complementary sequence A251728.

(End)

Semiprimes p*q, p < q, such that b = q+1 is the minimal base with the property that p and q have equal length representations in base b. This was the original definition, which is based primarily on A138510: A138510(A174956(a(n))) = A084127(A174956(a(n))) + 1.

Semiprimes p*q for which there exists r <= q such that r^k <= p <= q < r^(k+1), for some k >= 1, i.e., semiprimes whose both prime factors fit inside a semiopen range of two consecutive powers of some natural number r which itself is not greater than the larger prime factor. If such r exists, then it must be <= p (the smaller prime factor of n), which forces q to be less than p^2. On the other hand, when p <= q < p^2, then setting r = p and k = 1 satisfies the equation r^k <= p <= q < r^(k+1).

Assuming that A054272(n), the number of primes in interval [p(n), p(n)^2], is nondecreasing (implied for example if Legendre's or Brocard's conjecture is true), it follows that for any a(n), A003961(a(n)) is also in sequence. In other words, whenever prime(i)*prime(j) is in the sequence, then so is also prime(i+1)*prime(j+1).

From above would follow also that these are all the "settled semiprimes" that occur in a square array A083221 constructed from the sieve of Eratosthenes, from the level A251719 downward. Furthermore, this sequence would then be an infinite disjoint union of sequences of A003961-iterates starting from the initial values given in A251724.

See also the comments in the complementary sequence of semiprimes, A138511.

Composite numbers n with all prime factors greater than the cube root of n. - Doug Bell, Oct 27 2015

If "p <= q" in the definition were changed to "p < q" then the squares of primes (A001248) would be removed, yielding A138109. - Jon E. Schoenfield, Dec 27 2022

a(n) = Length of the initial fixed portion of the permutation at row n of A251721 & A251722.

Also, for n > 1, the length of the maximal increasing prefix on row n of A249821.

For n >= 2: a(n) = the first "settled semiprime" in the column n of the sieve of Eratosthenes: a(n) = A083221(A251719(n), n).

The "settling of semiprimes" here means that from that semiprime onward, all the other terms in the same column n of a square array A083221 (which is constructed from the sieve of Eratosthenes) are also semiprimes, obtained by successive iterations of A003961 starting from the semiprime here given as a(n). Cf. comments in A251728 which contains all such semiprimes. The "unsettled" semiprimes are in its complement A138511.

Here we assume that A054272(n), the number of primes in interval [prime(n), prime(n)^2], is nondecreasing (implied for example if Legendre's or Brocard's conjecture is true).

Haga's conjecture (see link below) is that if the integers from 1 to p^2 (p prime) are put in a p by p square in standard order, then there's a transversal consisting of primes; i.e., a set of p primes containing exactly one number in each row and column. E.g., for p=5 the primes 5, 7, 11, 19, 23 work. Since p is needed for the p-th column, primes less than p can't be used. a(n) is the number of primes available minus the number needed for the transversal.