For every positive integer $x$, let $k(x)$ denote the number of composite numbers that do not exceed $x$. Find all positive integers $n$ for which $(k (n))! $ lcm $(1, 2,..., n)> (n - 1) !$ .
Problem
Source: 2020 Estonia TST 2.1
Tags: number theory, least common multiple, factorial
27.11.2020 15:56
The only solutions are $2,3,4,5,7,9$ $(k (n))! $ lcm $(1, 2,..., n)> (n - 1) !$ can be rewritten as $p_1^{e_1} \times p_2^{e_2} ... p_k^{e_k}>(n-1)(n-2)...(n-k)$ where $p_1^{e_1} \times p_2^{e_2} ... p_k^{e_k}$ is the prime factorization of $lcm(1,2,3,...n)$ If $n$ is not of the form $p^k$, it is clear that there is no value of n which would satisfy $p_1^{e_1} \times p_2^{e_2} ... p_k^{e_k}>(n-1)(n-2)...(n-k)$, as the RHS is the largest number that is the product of $k$ distinct numbers less than $n$. So we have to consider the case for when n is of the form $p^k$ We rearrange $p_i^{e_i}$ in descending order of magnitude and we call this sequence $a_i$ (i.e $a_1=n$) $\prod {\frac{a_i}{n-i}}<1$ is equivalent to $p_1^{e_1} \times p_2^{e_2} ... p_k^{e_k}<(n-1)(n-2)...(n-k)$ Here we must notice that the $max(\frac{a_i}{n-i})=\frac{n-i+1}{n-i}$ and there can only exist a maximum of three of such fractions (This is because excluding $2^t$, all the other $a_i$ are odd) There also must exist at least $k-4$ fractions $\frac{a_i}{n-i}$ such that $\frac{a_i}{n-i}<1$ (we have excluded the 3 fractions mentioned above and only one can be the same because $a_i$ are all odd) so if $k-4>3$, then $\prod {\frac{a_i}{n-i}}<1$, as $\frac{x+1}{x} \times \frac{x-y-1}{x-y}<1$ for all positive integer $x$ and $y$ where $x>y+1$ and so we only have to consider the cases where $k\le 7$. The 7th prime number is $17$ so checking all the numbers of the form $p^k$ which are less than or equal to $17$, we find that the only solutions are $2,3,4,5,7,9$
03.02.2021 10:13
anthonyshinex wrote: there can only exist a maximum of three of such fractions (This is because excluding $2^t$, all the other $a_i$ are odd) Why is three? Please explain this.