4
$\begingroup$

Let $f:\Bbb N\setminus\{0,1\}\to\Bbb N$ be a function defined by $$f(n)=\operatorname{lcm}[1,2,\ldots,n]$$ Prove that for all $n\ge2$ there exis $n$ consecutive numbers for which $f$ is constant.

Find the greatest number of elements of a set of consecutive integers on which $f$ is strictly increasing and determine all sets for which this maximum is realized.

I tried with $n!$ but the idea didn't work.

Any help will be truly appreciated.

$\endgroup$
  • $\begingroup$ It has something to do with factorials. $\endgroup$ – TheRandomGuy Mar 23 '16 at 6:50
3
$\begingroup$

Hint :

The function $f(n)$ strictly increases at $n$ if and only if $n$ is a prime power $p^k$ with $p$ prime and $k\ge 1$.

$\endgroup$
0
$\begingroup$

(a) let $n$ be given. Let the first $n$ primes be $p_1$ to $p_n$.

By Chinese remainder theorem, there exist some $x$ such that \begin{eqnarray} x &=& 0 \pmod {p_1} \\ x &=& -1 \pmod {p_2} \\ ... \\ x &=& -(n-1) \pmod{p_n} \end{eqnarray}

Then $\{x, x+1,..., x+(n-1)\}$ are $n$ consecutive numbers which are multiples of the primes $p_1$ to $p_n$.

So $LCM[1,2,...,x] = LCM[1,2,...,x,x+1] = ... = LCM[1,2,...,x+(n-1)]$

$\implies f(x) = f(x+1) = ... = f(x+n-1)$

(b) suppose $f(n) = x$. Consider $f(n+1)$.

if $n+1$ is prime, $f(n+1) > f(n)$

if $n+1$ is a prime power, then also $f(n+1) > f(n)$

if $n+1$ is not either, then it is composite, and $n+1 = ab$ where $a,b \in S_n$. In this case, $f(n+1) = f(n)$

So we have that $f(n+1) > f(n) \iff n+1$ is a prime or prime power.

Now the longest strictly increasing sequence. We have: $f(2) = 2, f(3) = 6, f(4) = 12, f(5) = 60$ is a strictly increasing sequence of $4$ numbers.

Any other consecutive sequence of $4$ or more numbers will have $2$ even numbers. It is not possible for both to be powers of $2$ (since only $1$ of them can be a multiple of $4$). So $f(n)$ cannot be strictly increasing on that sequence of numbers.

$\endgroup$
  • $\begingroup$ what about $f(6) = 60, f(7)=420, f(8)=840, f(9)=2520$? $\endgroup$ – Merk Zockerborg Oct 6 '18 at 15:24

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.