Steps that produce a sum of 2017

Question

The numbers $1,2, \ldots, n$ are written in a board, with $n \in \mathbb{N}$. In every move, we can choose two numbers of the board, find their $\rm lcm$, and replace the two numbers with it. After $k$ moves, we find the sum of the numbers in the board, and we name it $S$. Find the minimum and the maximum value of $n$, such that there is $k$ such that $S=2017$.

This is an exercise I show at a Mathematical Forum, posted on 2017, and I have been trying this for a long time actually, and the things I have proven aren't something important, so I would prefer full answers.

As far as I now, it isn't from an exam or a Math Olympiad.

Answer 1

Some hints (all numbers are $\in \Bbb N$).

• for any $k$, ${\rm lcm}(k,1)=k$.
• for any $j,k,$ ${\rm lcm}(j,jk)=jk$.
• the $\rm lcm$ of a prime number $p$ and any other distinct number $k$ is never less than the prime number. If $k>1,$ ${\rm lcm}(p,k)>p$.
• if we have a set of powers of distinct prime numbers, their least common multiple $({\rm lcm})$ is the product of those numbers.
• the product of a set of prime powers is greater than their sum.

Implications for the puzzle, to achieve $S=2017$:

• the sum of the maximum powers of prime numbers less than $n$ must be less than $2017$
• numbers that have multiples in the set can be removed (or retained) (including $1$).

A couple of example solutions, just for checking:

• For $n=63, $ the initial $S_0= 2016$. We can take $2,3$ as our first $\rm lcm$ pair, which are replaced with $6$ to give $S_1=2017$

• For $n=64,$ initial $S_0 = 2080$ and for a target of $2017$ we need to lose $63$. We can feed the powers of $2$ into the $\rm lcm$ calculation to replace all of $\{1,2,4,8,16,32,64\}$ with $64,$ achieving the target sum at $k=6$. Or we could use $\rm lcm$ pairs $(32,64)$ and $(31,62)$ to achieve it at $k=2$.

---

The highest value of $n$ is likely determined by the case where none of the remaining values is a multiple of any other; that is, the last set where $\lfloor n/2 \rfloor {+}1$ to $n$ sums to less that $2017$. This happens for $\fbox{$n=72$}$, when taking $(k,2k)\to 2k$ for every $k$ up to $36$ except for $k=19$ will give the required sum.

The lowest value of $n$ is at least $9$, since below that ${\rm lcm}(1..n)$ is too far below $2017$ - in particular ${\rm lcm}(1..8) = 840$. It's relatively easy to solve this, for example, for $n=24$ by assembling ${\rm lcm}$s from the original numbers in sequential pairs $\{(1,2),(3,4),(5,6),\ldots\}$ for a total of $2444$ and then disassembling some pairs and creating others appropriately to get the target value: $\{1, (2,5),$ $(3,4), 6,$ $(7,8),$ $9, 10,$ $(11,12),$ $(13,14),$ $(15,16),$ $(17,18),$ $19, 20,$ $(21,22),$ $(23,24)\}$. There will be solutions for smaller values of $n$ which use more than two numbers in ${\rm lcm}$ calculations - my smallest is $\fbox{$n=12$}$ which is achieved with $(9,10,11,12)\to 1980,$ $(1,4,6)\to 12,$ and $\{2,3,5,7,8\}$ adding in unchanged.

Answer 2

It is possible to make $S=2017$ starting from $n=11$. Merge $4, 5, 9, 11$ in any order to make the sequence $1, 2, 3, 6, 7, 8, 10, 1980$ which achieves the sum $2017$.

Now what is left is to prove that it is impossible to achieve the sum of $2017$ with $n=10$. Since $\gcd(1, \cdots, 10)=2520>2017$, there should be at least $2$ numbers after the process. Let them $a, b$.

It is obvious that only one of them can be multiple of $7$. WLOG, let $7|a$. Then $a\le1260$, $b\le360$. Since their sum is too small ($1260+360+360<2017$), there need to be at least $4$ numbers to make sum $2017$. Let them $a, b, c, d$.

At most $2$ of $a, b, c, d$ is multiple of $5$ and only one of them is multiple of $7$. WLOG, $a$ is multiple of $7$. If $a$ is not multiple of $5$, WLOG $b, c$ is multiple of $5$. So $a\le504$, $b\le360$, $c\le360$ and $a+b+c\le1224$. If $a$ is multiple of $5$ either, then WLOG $a, b$ is multiple of $5$ thus $a\le1260$, $b\le360$, $c\le72$ and $a+b+c\le1692$. Note that in any cases, $a+b+c\le1692$.

In all cases $d$ is not multiple of $5$ nor $7$, which means $d\le72$. Since $1692+72\times4<2017$, at least $7$ numbers at the end of process is required to make $S=2017$.

Since $k$, the number of replacements, is at most $3$ now, there are only $2$ possible cases for replacement.

• Four numbers were merged, remaining six are not touched: In this case, replaced numbers' lcm is either $2520$ or at most $1260$ and remaining numbers are too small to sum from $1260$ to $2017$.

• Three numbers merged into one, other two numbers merged, and remaining five not touched: The sum is at most $10\times9\times8+10\times9+10+\cdots+1=865<2017$.

Therefore, one cannot achieve $S=2017$ from $n=10$ and $n=11$ is the smallest possible $n$.