I was given a programming riddle recently. It was eluded to that there is an equation, but I was told that finding the equation was not the goal, and that writing a simple program was the goal. I solved the riddle and wrote a program, so have not included that all here.
However, I've spent a lot of time trying to figure out if there is an equation or not, and the source of this question wouldn't tell me. So I'd like to propose the issue here in hopes for help (or just the answer). It's killing me.
Solve for x so that x = Lowest Number Possible.
Given i = Variable Whole Number > 1
Constraints are as follows:
- No. of Iterations = i + 1
- The equation for each iteration is: x = ((x-1)/i)*(i-1)
- Every iteration must end in a
non-zeroWHOLE Number
So for i=2, (The answer is 15 7) this would occur:
x = ((7-1)/2)*(2-1) = 3
x = ((3-1)/2)*(2-1) = 1
x = ((1-1)/2)*(2-1) = 0
For i=3, (x starts as 79, so the answer is 79)
x = ((79-1)/3)*(3-1) = 52
x = ((52-1)/3)*(3-1) = 34
x = ((34-1)/3)*(3-1) = 22
x = ((22-1)/3)*(3-1) = 14
- For i=4, x=1021
- For i=5, x=15621
- For i=6, x=279931
- For i=9, x=3486784393
Second Version
The OP has correctly indicated that the first version of the argument (still present, below this second version) is somewhat difficult to follow. Also, the argument leads to the last (smallest) iterate while the question requests the first (largest) iterate. So, trying again to make the argument more clear and get the desired result...
The forward iteration is $x \mapsto \frac{i-1}{i}(x-1)$. So the sequence of iterations is: \begin{align*} 0 &: x \\ 1 &: \frac{i-1}{i}(x-1) \\ 2 &: \frac{i-1}{i}(\frac{i-1}{i}(x-1)-1) \\ 3 &: \frac{i-1}{i}(\frac{i-1}{i}(\frac{i-1}{i}(x-1)-1)-1) \\ \vdots \\ n &: \left(\frac{i-1}{i}\right)^n x - \left(\frac{i-1}{i}\right)^n - \left(\frac{i-1}{i}\right)^{n-1} - \cdots - \left(\frac{i-1}{i}\right) \\ &= \frac{(i-1)^n x - i^0(i-1)^n - i^1(i-1)^{n-1} - \cdots - i^{n-1}(i-1)}{i^n} \end{align*}
The problem is nonsense for $i=0$, since then we would need $\frac{-1}{0}$ in the first iterate. The problem is nonsense for $i=1$ for then all the numerators are zero and all the iterates are zero. The first nontrivial case is $i=2$,where $x$, $\frac{1}{2}(x-1) = \frac{x-1}{2}$, $\frac{1}{4}x - \frac{1}{4} - \frac{1}{2} = \frac{x-3}{4}$, and $\frac{x-1-2-4}{8} =\frac{x-7}{8}$ are all integers. The last of these requires that $x \cong 7 \mod 8$ but this makes the other iterates integers automatically. (The OP has also correctly observed that this solution violates the nonzero requirement for the last iterate -- which is correctable by using the next residue in this equivalence class: $15 \rightarrow 7 \rightarrow 3 \rightarrow 1$.) This happens generically -- notice that on each step we add to the numerator exactly what is needed to turn a multiple of $i^{n-1}$ into a multiple of $i^n$. (This is why my prior version of this answer starts with the last (smallest) iterate -- once it's an integer, the rest of the problem just falls like dominoes.) Although we have just demonstrated that for $i=2$ the least positive residue $\mathrm{mod} i^{i+1}$ is not a solution, this is a coincidence for $i=2$ and this coincidence does not recur for $i \geq 3$.
Before we go much further, let's try to simplify the long string of subtractions in the numerator. We factor out a $-(i-1)$ to make the rest symmetric, substitute binomial sums for the binomials, and rearranging (sorting by $k$s and recognizing the sum of binomials), then a geometric series ... \begin{align*} &- i^0(i-1)^n - i^1(i-1)^{n-1} - \cdots - i^{n-1}(i-1) \\ &= -(i-1)\left( i^0(i-1)^{n-1} + i^1(i-1)^{n-2} + \cdots + i^{n-1}(i-1)^0 \right) \\ &= -(i-1)\left( i^0 \sum_{k=0}^{n-1} \binom{n-1}{k}i^{n-k-1}(-1)^k + i^1 \sum_{k=0}^{n-2} \binom{n-2}{k}i^{n-k-2}(-1)^k + \cdots + {} \right. \\ &\quad\quad\quad \left. {} + i^{n-1}\sum_{k=0}^{0} \binom{0}{k}i^{0-k}(-1)^k \right) \\ &= -(i-1)\left( \sum_{k=0}^{n-1} \binom{n-1}{k}i^{n-k-1}(-1)^k + \sum_{k=0}^{n-2} \binom{n-2}{k}i^{n-k-1}(-1)^k + \cdots + {} \right. \\ &\quad\quad\quad \left. {} + \sum_{k=0}^{0} \binom{0}{k}i^{n-k-1}(-1)^k \right) \\ &= -(i-1) \sum_{j=0}^{n-1}\sum_{k=0}^{j} \binom{j}{k} i^{n-k-1}(-1)^k \\ &= -(i-1) \sum_{j=0}^{n-1} i^{n-1}\left( \frac{i-1}{i} \right)^j \\ &= -(i-1) i^{n-1} \frac{1-\left( \frac{i-1}{i} \right)^n}{1-\frac{i-1}{i}} \\ &= -(i-1)(i^n - (i-1)^n) \end{align*} After all that we can finally write our general iterate as $$ \frac{(i-1)^n x - (i-1)(i^n - (i-1)^n)}{i^n} $$ and the last (smallest) iterate is $$ \frac{(i-1)^{i+1} x - (i-1)(i^{i+1} - (i-1)^{i+1})}{i^{i+1}} $$ For this to be an integer (and thus, for all the prior iterates to be integers), we must have $$ (i-1)^{i+1} x - (i-1)(i^{i+1} - (i-1)^{i+1}) \cong 0 \mod i^{i+1} $$ or, equivalently either of \begin{align*} (i-1)^{i+1} x &\cong (i-1)(i^{i+1} - (i-1)^{i+1}) \mod i^{i+1} x &\cong (i-1)^{-i}(i^{i+1} - (i-1)^{i+1}) \mod i^{i+1} \end{align*}This is roughly analogous to where version 1 stops... but we can do better. Since $i^{i+1} \cong 0 \mod i^{i+1}$, \begin{align*} x &\cong (i-1)^{-i}(0 - (i-1)^{i+1}) \mod i^{i+1} \\ &\cong -1 \cdot (i-1)^{-i}(i-1)^{i+1} \mod i^{i+1} \\ &\cong -1 \cdot (i-1) \mod i^{i+1} \\ &\cong -i+1 \mod i^{i+1} \\ \end{align*}
The smallest positive representative from those equivalence classes is, and the sequence of (or at least, last (smallest) iterate) is \begin{align*} 3 &: 3^4-3+1=79 \rightarrow 52 \rightarrow 34 \rightarrow 22 \rightarrow 14 \\ 4 &: 4^5-4+1=1021 \rightarrow \cdots \rightarrow 240 \\ 5 &: 5^6-5+1=15621 \rightarrow \cdots \rightarrow 4092 \\ 6 &: 6^7-6+1=279931 \rightarrow \cdots \rightarrow 78120 \\ 7 &: 7^8-7+1=5764795 \rightarrow \cdots \rightarrow 1679610 \\ 8 &: 8^9-8+1=134217721 \rightarrow \cdots \rightarrow 40353600 \\ 9 &: 9^{10}-9+1=3486784393 \rightarrow \cdots \rightarrow 1073741816 \\ 10 &: 10^{11}-10+1=99999999991 \rightarrow \cdots \rightarrow 31381059600 \\ &\vdots \\ i &: i^{i+1}-i+1 \rightarrow \cdots \rightarrow (i-1)^{i+1}-i+1 \end{align*} All the other solutions are found from the other members of the equivalence class for a given $i$, and can be computed by adding or subtracting some multiple of $i^{i+1}$ to the numbers in the table. (So, for instance, there are negative numbers, closer to zero than those given, which satisfy the given problem.)
The sequence of smallest iterates, and the general formula for them comes from the first version of this answer. The simplifications to get the form $(i-1)^{i+1}-i+1$ for the smallest iterate are analogous to the simplifications above for the largest iterate.
First version
Instead of focusing on the first (largest) iterate in the given process, let's focus on the last (smallest) iterate. The inverse iteration is $x \rightarrow \frac{i}{i-1} x + 1$. Under iteration, the (reversed) sequence of iterates is \begin{align*} x \\ \frac{i}{i-1} x + 1 \\ \frac{i}{i-1} \left( \frac{i}{i-1} x + 1 \right) + 1 \\ \vdots \end{align*}
It's not hard to see that the sequence of iterates is $\left\{ \left(\frac{i}{i-1}\right)^n x + \sum_{j=0}^{n-1} \left(\frac{i}{i-1}\right)^j \right\}_n$ (where we take $\sum_{j=0}^{-1} \dots = 0$). Putting these over a common denominator, we have $$ (i-1)^{-n} \left[ i^n x + \sum_{j=0}^{n-1} i^j(i-1)^{n-j} \right] $$ For all the iterates to be integers, it is sufficient that $x$ be such that the expression in brackets is an integer when $n=i+1$ $$ i^{i+1} x + \sum_{j=0}^{i} i^j(i-1)^{i-j+1} \cong 0 \mod (i-1)^{i+1} $$ Therefore, $x \cong - i^{-i-1} \sum_{j=0}^{i-1} i^j(i-1)^{i-j+1} \mod (i-1)^{i+1} $ where we can use the Extended Euclidean Algorithm to find $i^{-i-1}$ and the smallest positive representative from that equivalence class is the solution to the problem. Using this, we find the solutions (smallest iterates): \begin{align*} 3 &: 14 \mod 16 \\ 4 &: 240 \mod 243 \\ 5 &: 4092 \mod 4096 \\ 6 &: 78120 \mod 78125 \\ 7 &: 1679610 \mod 1679616 \\ 8 &: 40353600 \mod 40353607 \\ 9 &: 1073741816 \mod 1073741824 \\ 10 &: 31381059600 \mod 31381059609 \end{align*} Running the reverse iterations on these smallest positive members of their equivalence classes gives the initial (largest) iterates that you list. These equivalence classes are the complete sets of final (smallest) iterates under the condition that all the iterates are nonzero integers.
The exceptionally interesting thing to notice is that each of these is $1-i \mod (i-1)^{i+1}$. We can find this from our sum by realizing it's a binomial.