5
$\begingroup$

When trying to solve a number theory problem I came across this other problem which sounds interesting. Let $n$ be a positive integer, and consider $n$ consecutive positive integers $a_1, \ldots, a_n$ that are at most $n^2$.

What is an upper bound for the number of integers in this kind of list that have a prime factor greater than $n$?

What's interesting is that for any such prime factor, it appears only once as a factor in the list, and there can only be at most $n$ such primes. I'm guessing that $n$ is too large an upper bound and cannot be reached, i.e. there is always at least one number with prime factors all less than or equal to $n$.

I don't have any results besides checking some lists of numbers, and I don't really know how to approach this. Any ideas?

$\endgroup$
2
$\begingroup$

At least one of the numbers will be divisible by $n$. It cannot have a prime factor greater than $n$ because then it would be at least $n(n+1)$, so at most $n-1$ of them can have a prime factor larger than $n$. An example that meets this is $n=5$ and the numbers $19-23$ where only $20$ does not have a prime factor greater than $5$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Silly me, I should have thought of that. Now I guess the next natural question is whether the bound $n-1$ can be achieved infinitely often. $\endgroup$ – Paul Cusson Jan 18 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.