2
$\begingroup$

Given L = LCM(1,2,.....,n) We need to find the largest 'm' such that m<=n and LCM(m,m+1,.....,n) = L

Any process to do so?

eg. LCM (1,2,3,4,5) = 60 and LCM (3,4,5) = 60 So, for n=5 the answer is m=3

$\endgroup$
6
  • $\begingroup$ Do you need an algorithm , or what? $\endgroup$
    – openspace
    Commented May 14, 2016 at 10:46
  • $\begingroup$ Easy to see that $m$ is at least $\lfloor n/2\rfloor$. $\endgroup$ Commented May 14, 2016 at 10:48
  • $\begingroup$ @openspace obviously I need an algorithm. $\endgroup$ Commented May 14, 2016 at 12:06
  • $\begingroup$ @Batominovski I know that but I need a definite value of 'm' given any 'n' $\endgroup$ Commented May 14, 2016 at 12:07
  • $\begingroup$ I know what you need. Is it wrong for me to state a bound on $m$? Should I remove everything I posted here because it didn't answer your question? $\endgroup$ Commented May 14, 2016 at 12:08

1 Answer 1

3
$\begingroup$

Let $X_n$ be the set of $p^k$ where $p$ is a prime natural number not greater than $n$ and $k$ is the largest positive integer such that $p^k\leq n$. (Observe that $\text{lcm}(1,2,\ldots,n)=\prod_{q\in X_n}\,q$.) For each $q\in X_n$, let $t_n(q)$ denote the largest multiple of $q$ that is less than or equal to $n$. Take $Y_n$ for the set of $t_n(q)$ for $q\in X_n$. Set $a_n:=\min\left(Y_n\right)$ and $b_n:=\max\left(Y_n\right)$. Then, $$\text{lcm}\left(1,2,\ldots,n\right)=\text{lcm}\left(a_n,a_n+1,\ldots,b_n-1,b_n\right)\,.$$ To answer the OP's question, $m:=a_n$ is the largest such $m$. I also believe that $\left\{a_n,a_n+1,\ldots,b_n-1,b_n\right\}$ is the smallest interval in $\{1,2,\ldots,n\}$ whose lcm is equal to $\text{lcm}(1,2,\ldots,n)$.

$\endgroup$
0

You must log in to answer this question.

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