6
$\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 Answers 2

Reset to default
3
$\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$.

$\endgroup$
1
  • $\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, 2020 at 4:05
0
$\begingroup$

Denote this upper bound by $u(n)$. Let $l(k)$ be the largest $n$ where $u(n)=n-k$. Then some pairs $k:l(k)$ are as follows: 1:10 2:15 3:16 4:21 5:27 6:30 7:40 8:37 9:42 10:46 11:57 12:58 13:65 14:70 15:72 16:78 17:79 18:81 19:87 20: 96 21:97 22:100 23:102 24:106 25:107 26:108 27:126 28:127 29:129 30:133 31:136 32:147 33:148 34:155 35:156 36:166 37: 167 38:172 39:165 40:174 41:178 42:185 43:190 44:196 45:198 46:202 47:204 48:207 49:209 50:214 51:221 52:222 53:226 54:227 55:233 56:238 57:243 58:247 59:250 60:251 61:256 62:268 63:262 64:270 65:272 66:275 67:280 68:281 69:282 70: 289 71:292 72:296 73:300 74:310 75:311 76:312 77:316 78:328 79:330 80:332 81:338 82:344 83:347 84:348 85:350 86:352 87:355 88:365 89:366 90:369 91:372 92:378 93:379 94:385 95:388 96:395 97:397 98:408 99:411 100:418 101:430 103:432 104:433 105:435 106:438 108:442 and so on.

In particular, to answer Paul Cusson's comment to Ross Millikan's answer, $u(n)=n-1$ last when $n=10$. (Some positive integers, such as 102, appear not to be values of $k=n-u(n)$.)

Though $u$ is not always an increasing function of $n$, and $l$, where defined, is not always an increasing function of $k$, it certainly appears that $\liminf_{n\to\infty} u(n)=\infty$ and $\liminf_{k\to\infty} l(k)=\infty$ (where the latter limit is taken over values of $k$ where $l(k)$ is defined).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .