Minimum steps to create all numbers under fixed math operations cycle
Making Every Number from 1 to N Under a Fixed Cycle of $+$, $\times$, $-$, $÷$
Discrete Mathematics
Summary
This paper looks at a puzzle where you start with the number 2 and try to make every number from 1 to N by combining previous numbers, but you must use addition, multiplication, subtraction, and division in a repeating order. The authors find the smallest number of steps needed to do this is always N - 1 for any N greater or equal to 9. They can't use usual methods to prove this, so they find a clever way to jump from a range of numbers to a bigger range all at once. They also provide exact sequences of steps for numbers up to 33, found by computer search.
What this means in practice
- •For algorithm designers: Identify limits on sequence construction under fixed operation cycles to optimize numerical algorithms involving restricted operations.
- •For mathematics educators: Provide structured exercises on operation sequences and number construction to teach properties of arithmetic operations and induction techniques.
A theory result. No direct application yet.
Authors
Sean Lesmana, Theodore Tjugiarto
Abstract
Start with the number $2$. At each move, combine two numbers already made, but the operations must be used in the fixed repeating order $+,\times,-,÷$. We ask for the fewest moves needed to make every integer from $1$ to $N$. Since $2$ is already one of the numbers we want and each move makes at most one new number, at least $N-1$ moves are needed. We show that $N-1$ moves are also enough for every $N\ge 9$. Conventional induction cannot work, because a division that comes right after a completed interval $\{1,\dots,P\}$ produces numbers already made. Instead we extend a completed interval $\{1,\dots,P\}$ to $\{1,\dots,3P\}$ all at once, which counting shows is the smallest multiplicative extension $P\to kP$ that can work, and then adjust the last few moves to reach every other $N$. For $9\le N\le 33$ we give explicit sequences, found by computer search.