Is it possible to find such sequence of consecutive numbers [n,m], which LCM=k?

Question

You are given number k, which is LCM of consecutive sequence of numbers from n to m. Is it possible to find smallest n with that knowledge, where length of sequence must be >=2? I've already figured out that all odd numbers don't have such representation and that we can figure out what multiplicities of numbers we have in our sequence. E.g. k=42 will definitely have 7 in its sequence.

Answer 1

As $$k=n\cdot(n+1)\cdots m=\frac{m!}{(n-1)!} =(m-n+1)!\cdot{m\choose n-1}=(m-n+1)!\cdot{m\choose m-n+1},$$ we see that $(m-n+1)!$ must divide $k$. So let $r$ be maximal with $r!\mid k$. For $i=2,3,\ldots, r$, we may try to find $m$ with $\frac{k}{i!}={m\choose i}$. Note that $m\mapsto{m\choose i}$ is a strictly increasing polynomial of degree $i$ in $m$ so that for each $i$, at most one $m$ may work. In fact, by the arithmetic-geometric inequality, $$n^i<n\cdot (n+1)\cdots(n+i-1)<\left (n+\frac{i-1}2\right)^i$$ we need only check all $n$ with $$\sqrt[i]k-\frac{i-1}2<n<\sqrt[i]k $$ (where additionally, $n$ must be a divisor of $k$) whether $k=\frac{(n+i-1)!}{(n-1)!}$.

Answer 2

As the question comment says, $n$ must be one of the relatively few divisors of $k$. Actually, all integers between $n$ and $m$, inclusive, must be divisors of $k$. Using this concept, here's a procedure to find the smallest $n$ for a given $k$.

Find the prime factorization of $k$, i.e.,

$$k = \prod_{i=1}^{j} p_i^{e_i} \tag{1}\label{eq1A}$$

for some integer $j \ge 1$, distinct primes $p_i$, and positive integers $e_i$. Using this, determine all of the factors of $k$ and sort them into increasing order. There should be at least one sequence of $2$ or more consecutive integers (if not, then the length of the sequence cannot be $\ge 2$). Assuming there are any such sequences, start with the smallest one.

Assume this sequence starts at $q$ and goes to $r$, with a length of $s = q - r + 1$. Let $t$ be the lcm of all of the integers from $q$ to $r$, inclusive. As $q$ to $r$ are all factors of $k$, this means that $t \mid k$. For each $1 \le i \le j$, determine the remainder $u$ when $q$ is divided by $p_i^{e_i}$. If $u = 0$ or $u + s \gt p_i^{e_i}$, this means $p_i^{e_i} \mid t$. If this is true for all $i$, then $k \mid t$ which, combined with $t \mid k$, means $t = k$, so $n = q$ is the smallest such $n$, with $m = r$. Otherwise, $t \lt k$, so this $q$ doesn't work. If there are no larger sequences of length at least $2$, then there is no $n$ available. Otherwise, repeat the start of this paragraph with the next larger sequence of consecutive factors of length of at least $2$.

Note the above procedure will find the smallest $n$, if any, but the value of $n$ for a given $k$ is not necessarily unique. For example, with $k = 420$, you'll find that $n = 1$ (with $m = 7$) is the smallest $n$. However, any $1 \le n \le 4$, with $m = 7$, gives the same lcm value of $420$.

Answer 3

This is just a few very elementary observations about how to quickly find solutions (or prove they don't exist) for small $k$.

First check on oeis.org/A003418 if one can use the LCM of the numbers in $k!$.

Otherwise, sequences starting with $n>1$ are surprisingly restricted. Consider, for example $n=4$. If $m\ge 6$ then we could reduce $n$ to $3$ without altering the LCM. So, applying this idea for $n>1$ we only need consider

$4\times 5\equiv 20$

$5\times 6\equiv30$, $5\times 6\times 7\equiv210$

$6\times 7\equiv42$, $6\times 7\times 8\equiv168$, $6\times 7\times 8\times 9\equiv504$

$7\times 8\equiv56$

$8\times...$

Examples

1. For your example of $k=42$, one needs only to go to the third row to find $6\times 7$.
2. $k=96$ is not given in A003418 and can easily be seen not to be an LCM for one of the above sequences.

N.B. Note that the LCM is always divisible by $n(n+1)$ which greatly limits the size of $n$. Furthermore, if the sequence has more than two terms then the LCM has to be divisible by $\frac{n(n+1)(n+2)}{2}$ and so on.

It may also be of interest that LCM $=\frac{n(n+1)...m}{D(n,m)}$, where $D(n,m)$ can be easily found for small $m-n$.

$D(n,n+1)=1$

$D(n,n+2)=2$ if $2|n$ and is $1$ otherwise

$D(n,n+3)=6$ if $3|n$ and is $2$ otherwise

...