A294907 a(n) is the smallest number k such that exactly half of the prime(n+1)-rough numbers in the interval [prime(n)^2 + 1, k] are prime.

87, 925, 4757, 17699, 43357, 97703, 187813, 350321, 595871, 920081, 1405609, 2024047, 2827861, 3931217, 5348053, 7053941, 9058607, 11637667, 14631209, 18251339, 22657429, 27786589, 33829567, 40651799, 48209237, 56928409, 67107197, 78713287, 92233283, 107643667

Offset: 1

Author

Jon E. Schoenfield, Nov 10 2017

Keywords

• nonn

Comments

Students who are first learning about prime and composite numbers and factorization learn that trial division is a simple way to determine whether a given number N is prime, and that only those divisors up through the square root of N need to be tried, since trial division by each prime up through a given prime p is sufficient to completely factor every composite number up through at least p^2.

Given a four-function calculator and a set of randomly-selected integers of manageable size to either factor or identify as prime, one can observe fairly quickly that as trial division is attempted using the primes in increasing order as divisors, many numbers that aren't divisible by any of the first several primes turn out to be prime.

Given some positive integer j > prime(n)^2, if we consider the set of integers that exceed prime(n)^2 but do not exceed j, and we exclude each number that is divisible by any of the first n primes, then the numbers that remain will include exactly as many primes as composites if j = a(n), but if j < a(n), then most of the numbers that remain will be prime.

Examples

			The 1st prime is 2, and exactly half of the 42 3-rough numbers (i.e., odd numbers) in the interval [2^2 + 1, 87] are prime, and more than half of the 3-rough numbers in [5, k] are prime for all k < 87, so a(1)=87.
The 2nd prime is 3, and exactly half of the 306 5-rough numbers (i.e., numbers that are not divisible by 2 or 3) in the interval [3^2 + 1, 925] are prime, and more than half of the 5-rough numbers in [10, k] are prime for all k < 925, so a(2) = 925.
		

Crossrefs

Cf. A005408 (3-rough numbers, i.e., the odd numbers), A007310 (5-rough numbers), A007775 (7-rough numbers), A008364 (11-rough numbers).