Question: For $k,n\in \mathbb{N}$, what is the smallest $b$ such that there is an interval $N=(b-k,b]\subset \mathbb{N}$ of length $k$ with at least $n$ distinct prime factors dividing the integers $x\in (b-k,b]$?
I am particularly interested when $k$ is large (e.g. $k=n$). Any references in the literature to this type of question would also be appreciated.
Examples: When $k=1$, $n=3$ we have that $b=2\cdot 3\cdot 5=30$ is the smallest such $b$. When $k=2$, $n=3$ we have that $b=6$ is the smallest such $b$ with $N=(4,6]=[5,6]$.
Motivation: When $k=1$ (see below), we naively have something like $b=n\log(n)\#<4^{n\log n}$, which is also basically optimal up to better bounds on the prime counting function (e.g. with RH) and primorial function. Although the complexity of this problem seems to increase with small $k>1$, for large enough $k$, e.g. $k=n$, it seems like this bound should be able to be made much smaller quite easily.
k=1:
When $k=1$ (the interval is just one integer $b$), we have something like $b=n\log(n)\#<4^{n\log n}$. Specifically, we can find an integer with $n$ distinct prime factors simply by noting that $2^x<x\#<4^x$ and that the prime counting function has a nice asymptotic $\pi(x)\sim x/\log(x)$. In particular the explicit bound is enough to conclude something close to this:
${\displaystyle {\big |}\pi (x)-\operatorname {li} (x){\big |}\leq 0.2795{\frac {x}{(\log x)^{3/4}}}\exp \left(-{\sqrt {\frac {\log x}{6.455}}}\right)}$
You are looking for ranges of k consecutive integers with at least n distinct prime factors.
Every prime p <= k is prime factor of at least one element in the range. Every prime p > k is a prime factor of at most one element of the range (but it can be a multiple factor of one number), so we only need to count large prime factors, not keep track of which they are - prime factors > k are distinct. Let $n_0$ be the number of primes <= k. If $n <= n_0$ then the solution is the numbers 1 to k. We assume n is larger.
How large are the numbers? The product of the k numbers is divisible by all primes <= k and by at least $n - n_0$ primes > k. So it is at least the product of the first n primes. In addition it is also divisible by $2^{k/2 - 1}$, $3^{k/3 - 1}$, $5^{k/5 - 1}$, and so on. So you get a lower bound for the product of the k numbers and that gives a lower bound for the largest of the k numbers. That bound will not be very large unless n is large compared to k. For example 100 numbers with 1000 distinct prime factors would have to be very large, 1000 numbers with 1000 distinct prime factors wouldn't.
Given the lower bound for the numbers, how to find a solution? Let's say X is the lower bound for the smallest number. Then we store the numbers from X to X + 1,000,000 + k - 1 in an array. Like in Eratosthenes' sieve, we remove all factors 2, 3, 5, 7, 11 etc. for all primes <= k. We need $n - n_0$ additional prime factors.
If after these divisions a number is 1, then it has no additional prime factors. If it is less than the product of the first two primes > k then it has one additional prime factor. (For example k = 100, a remaining factor less than 101 * 103 means exactly one additional prime factor). If it is less than the product of the next three primes, it has one or two additional factors, and so on.
So we count the additional factors for each range of k consecutive numbers starting with the number X to X + 999,999. This is done very quickly: We add the numbers for the first k numbers. For the next range we just drop the count for the first and add the count for the last number.
Since factoring large numbers is expensive, we first do an "optimistic" count: For numbers that might have one or more factors, we assume they have the larger number of factors. If the total is less than $n - n_0$ then we have no solution. If the total is $n - n_0$ or more then we need to calculate the exact number of divisors for numbers where we were optimistic. If we don't find a range starting with X to X + 999,999 then we increase X by 1,000,000 and try again.
I would think that for example finding 1000 numbers with 1000 distinct prime factors or with 1500 distinct prime factors is no problem at all (for your computer). 100 consecutive numbers with 1000 distinct prime factors - that will be a problem. If the number of distinct prime factors that you are looking for is optimistically large enough, then you might remove not only primes up to k, but also larger primes so that your optimistic guesses for number of distinct factors are lower. And unless you actually have a solution, you will often not need the exact number of divisors, but an upper bound. Say you have a number around $10^{18}$ left, and checked for divisors up to 1,000, so this number might optimistically have 5 factors. As you start testing divisibility by primes from 1000, your optimistic guess will go down - once you divided by primes up to 4,000 it can have only 4 factors, for example. You only need to check up to the point where you prove that the number of additional factors is not enough.
Another improvement that you need to work out: You start with X close to the lower bound, so you cannot have very large prime factors or the product of k numbers will be too large. So when you find an additional prime factor much larger than the n-th prime (say 9,000 when the n-th prime would be 450), you know the product of your numbers would be 20 times larger than the lower bound, and you ignore this solution if X is too small.