Turning Sequences of Numbers into Arithmetic Progressions

I've been thinking quite a bit about arithmetic progressions since I came across a problem named "The Arithmetic Progression Detective" on Codewars. An arithmetic progression is a sequence of integers such that, for any consecutive integers xix_i xi and xi+1x_{i + 1} xi+1 in the sequence, xi+1−xix_{i + 1} - x_i xi+1−xi is always the same value, d,d, d, known as the common difference. Let sns_n sn be an arbitrary sequence of integers. Let dnd_n dn be the common difference of the arithmetic progression from which sns_n sn deviates by no more than one value—the incorrect value—if such a progression exists. I'm going to call sns_n sn fixable if and only if such a progression exists. If sns_n sn cannot be turned into an arithmetic progression through the replacement of just one number in sn,s_n, sn, then sns_n sn is not fixable. Bearing this in mind, what limits can we identify to the range of fixable sequences? Let s1s_1 s1 be the sequence 1,2,4,5.1, 2, 4, 5. 1,2,4,5. Let s2s_2 s2 be the sequence 2,5,6,8.2, 5, 6, 8. 2,5,6,8. s1s_1 s1 is not a fixable sequence. But s2s_2 s2 clearly is, since s2s_2 s2 deviates by just one number from the arithmetic progression 2,4,6,8.2, 4, 6, 8. 2,4,6,8. s1s_1 s1 and s2s_2 s2 have a great deal in common. Each includes four numbers. Each superficially resembles an arithmetic progression. Each contains exactly one deviation, in one sense or another: exactly one step whose size differs from the others' in the case of s1,s_1, s1, and exactly one incorrect value in the case of s2.s_2. s2. So what difference between these two sequences makes s2s_2 s2 fixable and s1s_1 s1 not? One of the first things I noticed is, unlike s2,s_2, s2, s1s_1 s1 consists of steps all but one of which are the same size. To see this, note the following. The step from 22 2 to 44 4 in s1s_1 s1 is of size 2.2. 2. The remaining steps in s1s_1 s1 are of size 1.1. 1. By contrast, in s2,s_2, s2, each step's a different size. Steps one through three, respectively, are of sizes 3,1,3, 1, 3,1, and 2.2. 2. So, the only step of size d2d_2 d2 in s2s_2 s2 is the third and final step, from 66 6 to 8.8. 8. This goes to show you should not take for granted that sns_n sn contains at least two steps of size dn,d_n , dn, even assuming that there are four or more values in sn,s_n, sn, and only one is incorrect. But this difference between s1s_1 s1 and s2s_2 s2 does not fully explain their differing with respect to fixability. Some sequences are just like s1s_1 s1 in that they consist of steps all but one of which are the same size, but they are still fixable. One such sequence is 1,4,6,8.1, 4, 6, 8. 1,4,6,8. All you have to do to fix this is replace 11 1 with 2.2. 2. Really any sequence is fixable whose first or last term is the sole incorrect value. For our purposes the incorrect value in sns_n sn is defined as the one and only term whose replacement can single-handedly turn sns_n sn into an arithmetic progression. What sets s1s_1 s1 apart from a sequence whose first or final term is the only wrong one? Why is s1s_1 s1 not fixable like that kind of sequence? Maybe this is a better explanation. In s1s_1 s1 we have a step of size 1,1, 1, followed by one of size 2,2, 2, followed by one of size 1.1. 1. If we could turn that second step into a step of size 1,1, 1, we'd be able to create an arithmetic progression. But if we try to do that by moving the beginning of the second step closer to that of the first step, we end up narrowing the first step. And if we move the beginning of the second step closer to the end of the second step, we widen the first step. If on the other hand we move the end of the second step closer to that of the third step, we narrow the third step. And if we move the end of the second step closer to the beginning of the second step, we widen the third step. So there are various ways to decrease the size of the second step from 22 2 to 1.1. 1. But they all end up shortening or lengthening one of the other steps, such that it is no longer of size 1.1. 1. (Well, more precisely, all our options have this result if we limit ourselves to replacing just one integer in s1s_1 s1 with just one integer.) So we don't end up with an arithmetic progression. That's where 1,2,4,51, 2, 4, 5 1,2,4,5 differs from 1,4,6,8.1, 4, 6, 8. 1,4,6,8. The latter sequence consists of a step of size 3,3, 3, followed by two steps of size 2.2. 2. Crucially, that first step has an endpoint that no other step has. That is, the first number in the sequence is where the first step begins, and no other ste

Feb 18, 2025 - 04:23

Turning Sequences of Numbers into Arithmetic Progressions

I've been thinking quite a bit about arithmetic progressions since I came across a problem named "The Arithmetic Progression Detective" on Codewars. An arithmetic progression is a sequence of integers such that, for any consecutive integers $x_i$ and $x_{i + 1}$ in the sequence, $x_{i + 1} - x_i$ is always the same value, $d,$ known as the common difference.

Let $s_n$ be an arbitrary sequence of integers. Let $d_n$ be the common difference of the arithmetic progression from which $s_n$ deviates by no more than one value—the incorrect value—if such a progression exists. I'm going to call $s_n$ fixable if and only if such a progression exists. If $s_n$ cannot be turned into an arithmetic progression through the replacement of just one number in $s_n,$ then $s_n$ is not fixable. Bearing this in mind, what limits can we identify to the range of fixable sequences?

Let $s_1$ be the sequence $1, 2, 4, 5.$ Let $s_2$ be the sequence $2, 5, 6, 8.$ $s_1$ is not a fixable sequence. But $s_2$ clearly is, since $s_2$ deviates by just one number from the arithmetic progression $2, 4, 6, 8.$

$s_1$ and $s_2$ have a great deal in common. Each includes four numbers. Each superficially resembles an arithmetic progression. Each contains exactly one deviation, in one sense or another: exactly one step whose size differs from the others' in the case of $s_1,$ and exactly one incorrect value in the case of $s_2.$ So what difference between these two sequences makes $s_2$ fixable and $s_1$ not?

One of the first things I noticed is, unlike $s_2,$ $s_1$ consists of steps all but one of which are the same size. To see this, note the following. The step from $2$ to $4$ in $s_1$ is of size $2.$ The remaining steps in $s_1$ are of size $1.$ By contrast, in $s_2,$ each step's a different size. Steps one through three, respectively, are of sizes $3, 1,$ and $2.$ So, the only step of size $d_2$ in $s_2$ is the third and final step, from $6$ to $8.$

This goes to show you should not take for granted that $s_n$ contains at least two steps of size $d_n ,$ even assuming that there are four or more values in $s_n,$ and only one is incorrect.

But this difference between $s_1$ and $s_2$ does not fully explain their differing with respect to fixability. Some sequences are just like $s_1$ in that they consist of steps all but one of which are the same size, but they are still fixable. One such sequence is $1, 4, 6, 8.$ All you have to do to fix this is replace $1$ with $2.$ Really any sequence is fixable whose first or last term is the sole incorrect value. For our purposes the incorrect value in $s_n$ is defined as the one and only term whose replacement can single-handedly turn $s_n$ into an arithmetic progression.

What sets $s_1$ apart from a sequence whose first or final term is the only wrong one? Why is $s_1$ not fixable like that kind of sequence? Maybe this is a better explanation.

In $s_1$ we have a step of size $1,$ followed by one of size $2,$ followed by one of size $1.$ If we could turn that second step into a step of size $1,$ we'd be able to create an arithmetic progression. But if we try to do that by moving the beginning of the second step closer to that of the first step, we end up narrowing the first step. And if we move the beginning of the second step closer to the end of the second step, we widen the first step.

If on the other hand we move the end of the second step closer to that of the third step, we narrow the third step. And if we move the end of the second step closer to the beginning of the second step, we widen the third step.

So there are various ways to decrease the size of the second step from $2$ to $1.$ But they all end up shortening or lengthening one of the other steps, such that it is no longer of size $1.$ (Well, more precisely, all our options have this result if we limit ourselves to replacing just one integer in $s_1$ with just one integer.) So we don't end up with an arithmetic progression.

That's where $1, 2, 4, 5$ differs from $1, 4, 6, 8.$ The latter sequence consists of a step of size $3,$ followed by two steps of size $2.$ Crucially, that first step has an endpoint that no other step has. That is, the first number in the sequence is where the first step begins, and no other step begins or ends with that number. So you can replace that number with any number you want, including a number $x$ such that $4 - x = 2.$ The substitution will affect no step but the first, which is the only one you want to change.

Here is a more formal proof that you cannot turn $1, 2, 4, 5$ into an arithmetic progression by replacing just one integer with just one integer. We can split into two categories the integers in $s_1$ there are to replace: the numbers on the ends and those in between.

Suppose you replace exactly one of the two numbers on the ends $5).(\textrm{i.e., } 1 \textrm{ or } 5).$ Replacing $1$ changes only the size or direction of the first step, whereas replacing $5$ changes only the size or direction of the final step. So after you replace $1,$ the sizes of the second and third steps are still, respectively, $2$ and $1.$ And after you replace $5,$ the sizes of the first and second steps are still, respectively, $1$ and $2.$ But all the steps in the modified sequence must be the same size, if the sequence is to count as an arithmetic progression. So the modified sequence cannot be an arithmetic progression. In other words, you cannot turn $s_1$ into an arithmetic progression by replacing just $1,$ or just $5,$ with just one integer.

Suppose that instead you replace exactly one number strictly between those on the ends $4).(\textrm{i.e., } 2 \textrm{ or } 4).$ Let $x$ and $y$ be arbitrary integers such that $\not= 2$ and $\not= 4.$ Let $s_{1_x}$ be the sequence resulting from replacing $2$ with $x .$ Let $s_{1_y}$ be the sequence resulting from replacing $4$ with $y .$

Recall that $s_1$ is the sequence $1, 2, 4, 5.$ Consequently, $s_{1_x}$ is the sequence $1, x, 4, 5,$ and $s_{1_y}$ is the sequence $1, 2, y, 5.$ The first two steps in $s_{1_x}$ differ from the first two in $s_1;$ no other steps in $s_{1_x}$ differ from those in $s_1.$ The final two steps in $s_{1_y}$ differ from the final two in $s_1;$ no other steps in $s_{1_y}$ differ from those in $s_1.$

Let $b = x - 2, c = y - 4.$ Then $1 + b$ is the signed value representing the size and direction (on the number line) of the step from $1$ to $x$ in $s_{1_x} ,$ and $2 - b$ is that representing the size and direction of the step from $x$ to $4$ in $s_{1_x} .$ Furthermore, $2 + c$ is the signed value representing the size and direction (on the number line) of the step from $2$ to $y$ in $s_{1_y},$ and $1 - c$ is that representing the size and direction of the step from $y$ to $5$ in $s_{1_y} .$

$s_{1_x}$ or $s_{1_y}$ is an arithmetic progression only if all steps within it are of the same size and direction. Thus, $s_{1_x}$ is an arithmetic progression only if

$1 + b = 2 - b = 1.$

And $s_{1_y}$ is an arithmetic progression only if

$1 = 2 + c = 1 - c .$

But it is true neither that

$1 + b = 2 - b = 1$

nor that

$1 = 2 + c = 1 - c .$

I shall show that neither of these is true by giving a proof by contradiction of the falsity of each.

Here is a proof by contradiction that

$1 + b = 2 - b = 1$

is false.

Assume the following arguendo:

$1 + b = 2 - b = 1$

Then:

$1 + b = 2 - b$

$1 + 2 b = 2$ $sides)\tiny (\textrm{added } b \textrm{ to both sides})$

$2 b = 1$ $sides)\tiny (\textrm{subtracted } 1 \textrm{ from both sides})$

$\frac{1}{2}$ $2)\tiny (\textrm{divided both sides by } 2)$

$\frac{1}{2} = \frac{3}{2}$

$\frac{3}{2}$ $of=)\tiny (\textrm{transitivity of} =)$

But our initial assumption entails

$1 = 2 - b .$

So:

$\frac{3}{2}$

$\frac{3}{2}$ $of=)\tiny (\textrm{transitivity of} =)$

But obviously:

$\not= \frac{3}{2}$

Therefore,

$\frac{3}{2} \land 1 \not= \frac{3}{2}.$

Contradiction! We derived this from our initial assumption. A contradiction cannot be true, so neither can anything that entails a contradiction. Thus, our initial assumption must be false. Since this conclusion follows given an arbitrary integer $x,$ the proof just given demonstrates that $1 + b = 2 - b = 1$ is false regardless of what integer you substitute for $2$ in $s_{1}.$

Now let us prove by contradiction that

$1 = 2 + c = 1 - c$

is false.

Assume the following, arguendo:

$1 = 2 + c = 1 - c$

Then:

$2 + c = 1 - c$

$2 + 2 c = 1$ $sides)\tiny (\textrm{added } c \textrm{ to both sides})$

$2 c = - 1$ $sides)\tiny (\textrm{subtracted } 2 \textrm{ from both sides})$

$-\frac{1}{2}$ $2)\tiny (\textrm{divided both sides by } 2)$

$\frac{1}{2} = \frac{3}{2}$

$\frac{3}{2}$ $of=)\tiny (\textrm{transitivity of} =)$

But our initial assumption entails:

$1 = 2 + c$

So:

$\frac{3}{2}$

$\frac{3}{2}$ $of=)\tiny (\textrm{transitivity of} =)$

But obviously:

$\not= \frac{3}{2}$

Therefore,

$\frac{3}{2} \land 1 \not= \frac{3}{2}.$

Another contradiction! Since this conclusion follows given an arbitrary integer $y,$ the proof just given demonstrates that $1 = 2 + c = 1 - c$ is false regardless of what integer you substitute for $4$ in $s_{1}.$

Recall that $s_{1_x}$ is an arithmetic progression only if

$1 + b = 2 - b = 1.$

And $s_{1_y}$ is an arithmetic progression only if

$1 = 2 + c = 1 - c .$

But as the foregoing proofs by contradiction show, it is true neither that

$1 + b = 2 - b = 1$

nor that

$1 = 2 + c = 1 - c .$

Therefore, neither $s_{1_x}$ nor $s_{1_y}$ is an arithmetic progression. But if you replace only $2$ or $4$ in $s$ with exactly one integer, unequal to the one it replaces, the result is either $s_{1_x}$ or $s_{1_y}.$ So you cannot turn $s_1$ into an arithmetic progression by replacing just $2,$ or just $4,$ with just one integer.

But if you can't get an arithmetic progression by thus replacing just $2$ or $4,$ and you can't do so by thus replacing just $1$ or $5,$ then you can't do so by thus replacing just $1, 2, 4,$ or $5.$ But that means you can't do so by replacing just one integer with just one integer, since $1, 2, 4,$ and $5$ are all the integers there are to replace in $s_1.$

Therefore, you cannot turn $s_1$ into an arithmetic progression by replacing just one integer with just one integer.

From the above proof, what lesson should we draw concerning sequences other than $s_1?$ This is my takeaway.

Let $s_3$ be some sequence of integers $x1,x2,…,xℓ−1,xℓx_1, x_2, \dots , x_{\ell-1}, x_\ell$ of length $ℓ≥4.\ell \geq 4.$ (To be clear, we know $s_3$ includes the four values $x1,x2,xℓ−1,x_1, x_2, x_{\ell-1},$ and $xℓ.x_\ell.$ We don't know if $s_3$ includes other values.) Let $\leq i \leq \ell.$ Let $x_i$ be the $ithi^{\textrm{th}}$ number in $s_3.$ Let $d_i = x_{i + 1} - x_i.$ Let step $i$ be the step in $s_3$ from $x_i$ to $x_{i + 1}.$

Let $s_{3_z}$ be the sequence resulting from replacing $x_i$ with an arbitrary integer $z .$ Let $\leq i_z \leq \ell.$ Let $x_{i_z}$ be the $izthi_z^{\textrm{th}}$ number in $s_{3_z}.$ Let $d_{i_z} = x_{i + 1_z} - x_{i_z}.$ Let step $i_z$ be the step in $s_{3_z}$ from $x_{i_z}$ to $x_{i + 1_z}.$ The subscript of $x$ in this last expression should be read as $i + 1)_z,$ not as the expression $i + 1_z$ with which $1_z + i$ is interchangeable.

The successor of $x_i$ or $x_{i_z}$ is, respectively, $x_{i + 1}$ or $x_{i + 1_z}.$ The predecessor of $x_i$ or $x_{i_z}$ is, respectively, $x_{i - 1}$ or $x_{i - 1_z}.$ Note that replacing $x_i$ with a different integer changes only step $i - 1$ and step $i .$ The predecessors of step $i - 1)_z$ are indistinguishable from those of step $i - 1.$ The successors of step $i_z$ are indistinguishable from those of step $i .$

Replacing exactly one integer $x_i$ in $s_3$ can only turn $s_3$ into an arithmetic progression on the following condition:

$∃y∃c(y−xi=c∧d1=⋯=di−1+c=di−c=⋯=dℓ−1).\text{\small F}\text{\tiny IXABLE}\text{\small : } \small \exists y \exists c (y - x_i = c \land d_1 = \dots = d_{i - 1} + c = d_i - c = \dots = d_{\ell - 1}).$

Here is an informal, rough English translation of the logical notation above. There are integers $y$ and $c$ such that

(I) $c$ is the difference between $y$ and $x_i,$ and

(II) lengthening step $i - 1$ (if there is one), and shortening step $i$ (if there is one), by $c$ units ensures all steps have the same size and direction.

Allow me, now, to prove that $s_{3_z}$ is not an arithmetic progression if $¬FIXABLE.\neg\text{\small F}\text{\tiny IXABLE}.$

Assume the following, arguendo:

$s_{3_z}$ is an arithmetic progression, and $¬FIXABLE.\neg\text{\small F}\text{\tiny IXABLE}.$

You know what we have to do. Derive a contradiction! From the fact that $s_{3_z}$ is an arithmetic progression, it follows that

$d1z=d2z=⋯=di−1z=diz=di+1z=⋯=dℓ−2z=dℓ−1z.d_{1_z} = d_{2_z} = \dots = d_{i - 1_z} = d_{i_z} = d_{i + 1_z} = \dots = d_{\ell - 2_z} = d_{\ell - 1_z} .$

By the definitions of $x_i$ and $s_{3_z},$ $x_i$ is the $ithi^{\textrm{th}}$ number in $s_3,$ and $s_{3_z}$ is the sequence resulting from substituting $z$ for $x_i$ in $s_3.$ Thus, the $ithi^{\textrm{th}}$ number in $s_{3_z}$ is $z$ rather than $x_i.$ By definition, $x_{i_z}$ is the $ithi^{\textrm{th}}$ number in $s_{3_z}.$ So, given that $x_{i_z}$ and $z$ are each the $ithi^{\textrm{th}}$ number in $s_{3_z},$ it must be that $x_{i_z} = z.$

Since $x_{i_z}$ is the only number in $s_{3_z}$ that differs from the number at the corresponding position in $s_3,$

$∀j≠i(xj=xjz).\forall j \neq i (x_j = x_{j_z}).$

So, $x_{i + 1_z} = x_{i + 1}.$

So, by the definition of $d_{i_z},$

$d_{i_z} = x_{i + 1} - z.$

Solving for $x_{i + 1},$

$x_{i + 1} = d_{i_z} + z.$

Then, from the definition of $d_{i_z},$ we get

$d_{i - 1_z} = x_{i_z} - x_{i - 1_z}.$

So, seeing as $x_{i_z} = z$ and $x_{i - 1_z} = x_{i - 1},$ we may conclude that

$d_{i - 1_z} = z - x_{i - 1}.$

Then we solve for $x_{i - 1}$ as follows:

$x_{i - 1} = z - d_{i - 1_z}.$

Now let's take our solutions for $x_{i + 1}$ and $x_{i - 1},$ and combine them with the following information. The definition of $d_i$ implies that $x_{i + 1} = d_i + x_i$ and $x_{i - 1} = x_i - d_{i - 1}.$ Taking all these facts into account, we see both that

$d_i + x_i = x_{i + 1} = d_{i_z} + z$

and that

$x_i - d_{i - 1} = x_{i - 1} = z - d_{i - 1_z}.$

Of course, that means $d_i + x_i = d_{i_z} + z$ and $x_i - d_{i - 1} = z - d_{i - 1_z}.$ Solving both these equations for $z,$ we get

$z = x_i + d_i - d_{i_z}$

as well as

$z = x_i - d_{i - 1} - d_{i - 1_z}.$

From those two equations, we derive

$x_i + d_i - d_{i_z} = x_i - d_{i - 1} - d_{i - 1_z},$

which we simplify to

$d_i - d_{i_z} = d_{i - 1_z} - d_{i - 1}.$

From our assumption arguendo that $s_{3_z}$ is an arithmetic progression, it follows that $d_{i - 1_z} = d_{i_z}.$ Given the conjunction of this equation with $d_i - d_{i_z} = d_{i - 1_z} - d_{i - 1},$ it is provable that

$diz=di+di−12d_{i_z} = \frac{d_i + d_{i - 1}}{2}$

which can be rewritten as

$d_{i - 1} = 2d_{i_z} - d_i.$

Because $s_{3_z}$ is an arithmetic progression, indiscernible from $s_3$ apart from $z’sz\textrm{'s}$ having been substituted for $x_i,$ we know the following:

$∀j((j≠i−1∧j≠i)→dj=djz).\forall j ((j \neq i - 1 \land j \neq i) \to d_j = d_{j_z}).$

Time for another proof by contradiction! We want to establish the truth of

$d_{i - 1} + (z - x_i) = d_i - (z - x_i),$

so we assume the negation of that for the sake of argument:

$di−1+(z−xi)≠di−(z−xi).d_{i - 1} + (z - x_i) \neq d_i - (z - x_i).$

From this we derive

$di−1≠2diz−did_{i - 1} \neq 2d_{i_z} - d_i$

which contradicts our previous conclusion that

$d_{i - 1} = 2d_{i_z} - d_i.$

Therefore,

$d_{i - 1} + (z - x_i) = d_i - (z - x_i)$

which completes our subproof!

It goes without saying that both the integer $z$ and the difference $z - x_i$ exist. So, we have found a $y$ and a $c$ such that

$x_i = c \land d_1 = \dots = d_{i - 1} + c = d_i - c = \dots = d_{\ell - 1}.$

If you're curious, $z$ is our $y,$ and $z - x_i$ is our $c .$ That is, we can go from

$z−xi=z−xi∧d1=⋯=di−1+(z−xi)=di−(z−xi)=⋯=dℓ−1\small z - x_i = z - x_i \land d_1 = \dots = d_{i - 1} + (z - x_i) = d_i - (z - x_i) = \dots = d_{\ell - 1}$

$∃y∃c(y−xi=c∧d1=⋯=di−1+c=di−c=⋯=dℓ−1).\exists y \exists c (y - x_i = c \land d_1 = \dots = d_{i - 1} + c = d_i - c = \dots = d_{\ell - 1}).$

And then we've established $FIXABLE.\text{\small F}\text{\tiny IXABLE}.$ So we have finally derived a contradiction from our initial assumptions. Recall what those assumptions were: $s_{3_z}$ is an arithmetic progression, and $¬FIXABLE.\neg\text{\small F}\text{\tiny IXABLE}.$ From these we ultimately concluded $FIXABLE,\text{\small F}\text{\tiny IXABLE},$ which contradicts the second of our two initial assumptions.

So, either $s_{3_z}$ is not an arithmetic progression, or $FIXABLE.\text{\small F}\text{\tiny IXABLE}.$ But this disjunction is just another way of saying $s_{3_z}$ is not an arithmetic progression if $¬FIXABLE.\neg\text{\small F}\text{\tiny IXABLE}.$

And that's what we set out to prove!