## On x^3 - x + y^3 - y = z^3 - z

```Suppose we wish to find an infinite set of solutions of the equation

x^3 - x  +  y^3 - y  =  z^3 - z                 (1)

where x, y, z are integers greater than 1.  If z and x are both odd
or both even, we can define integers u and v such that z=u+v and
x=u-v.  Substituting into equation (1) gives

y^3 - y  =  2v(3u^2 + v^2 - 1)

Since v divides the right-hand side, it would be nice if it also
divides the left-hand side, which can be written as (y)(y^2 - 1).
By setting y = kv for some integer k we can divide through the
entire equation by v, leaving just an equation of degree 2 in the
variables u and v.  Making this substitution and dividing through
by v, we have

k(k^2 v^2 - 1)  =  6u^2 + 2v^2 - 2

Re-arranging terms, this can be written in the form of a Pell equation
in the variables u and v for any given k

(k^3 - 2)v^2  -  6u^2  =  (k - 2)

With k equal to 1 or 2, this equation has either no solutions or else
trivial solutions.  However, with k = 3 we have

(5v)^2 - 6u^2  =  1

This Pell equation has the infinite family of solutions

u        5v
-------  -------
2        5
20       49
198      485
1960     4801
19402    47525
192060   470449
1901198  4656965

etc.

Each of these sequences satisfies the recurrence

s[n]  =  10s[n-1] - s[n-2]

The sequence for 5v has the initial values s[0]=5 and s[1]=49, and
we can combine successive recurrences to give a single recurrence
for just the even-indexed terms

s[2n] = 98s[2(n-1)] - s[2(n-2)]

with the initial values 5 and 485.  Hence all subsequent even-
indexed terms of the 5v sequence are divisible by 5.  Thus we have
the infinite sequence of solutions

u        v        x=u-v    y=3v    z=u+v
-------  -------    -------  -------  -------
2        1          1        3        3
198       97        101      291      295
19402     9505       9897    28515    28907
1901198   931393     969805  2794179  2832591

etc.

Other infinite sequences of solutions can be constructed based
on other values of k.  However, as is characteristic of the solutions
of Pell equations, these are exponentially increasing sequences, so
they do not account for a very large fraction of all the solutions
of equation (1).

To find an efficient way of searching for more solutions, we can
change the sign of z (without loss of generality) and write equation
(1) in the equivalent form

x^3 + y^3 + z^3  =  x + y + z

Making use of the algebraic identity

x^3 + y^3 + z^3  =  (x+y+z)^3 - 3(x+y)(x+z)(y+z)

we have

(x+y+z-1)(x+y+z)(x+y+z+1)  =  3(x+y)(x+z)(y+z)          (2)

Letting S denote the sum x+y+z, the left side is S^3 - S, which is
automatically divisible by 3 (due to Fermat's Little Theorem).  So,
we can search form solutions by considering each possible value of S
in turn, and all the factorizations of (S^3 - S)/3 into three factors,
which we can call a=x+y, b=x+z, and c=y+z.  Then, for any such
factorization, we can check to see if a+b+c = 2S.  If it does, then
we have the solution

a+b-c            a-b+c           -a+b+c
x = -----        y = -----       z = ------
2                2                2

Of course, the signs of a,b,c ambiguous, because we can negate any
two of them and leave the product abc unchanged.  However, it's clear
that (for all sufficiently large solutions) the two smaller factors
(in magnitude) must have the same sign, and the larger factor must
have the opposite sign, so we can simply take the smaller factors b,c
as negative and a as positive.

Aside from the degenerate "S=1" solutions of the form |x|=1,y=-z, the
smallest solutions are shown in the table below.

S         c       b       a         x       y       z
-----     -----   -----   -----     -----   -----   -----
1         1       1       0         0       0       1
2         1       1       2         1       1       0
2         1       2       1         1       0       1
3        -1      -1       8         4       4      -5
3         2       2       2         1       1       1
8        -1      -7      24         9      15     -16
20        -1     -35      76        21      55     -56
28        -3     -28      87        31      56     -59
34        -1     -85     154        35     119    -120
36        -4     -35     111        40      71     -75
47        -2     -92     188        49     139    -141
55        -7     -48     165        62     103    -110
65       -20     -26     176        85      91    -111
97        -4    -194     392       101     291    -295
99       -21     -56     275       120     155    -176
134        -3    -399     670       137     533    -536
144        -6    -286     580       150     430    -436
144       -44     -58     390       188     202    -246
207       -13    -309     736       220     516    -529
225       -24    -226     700       249     451    -475
225       -28    -200     678       253     425    -453
226        -5    -678    1135       231     904    -909
246       -82     -91     665       328     337    -419
259       -14    -430     962       273     689    -703
280       -35    -248     843       315     528    -563
286       -19    -410    1001       305     696    -715
286       -77    -130     779       363     416    -493
287        -4   -1144    1722       291    1431   -1435
300       -25    -364     989       325     664    -689
323       -27    -391    1064       350     714    -741
323      -102    -126     874       425     449    -551
342       -93    -154     931       435     496    -589
344       -56    -245     989       400     589    -645
351       -28    -440    1170       379     791    -819
360        -8   -1077    1805       368    1437   -1445
377       -48    -329    1131       425     706    -754
429      -104    -215    1177       533     644    -748
433        -6   -1732    2604       439    2165   -2171
441       -49    -429    1360       490     870    -919
489       -16   -1141    2135       505    1630   -1646
495      -114    -260    1364       609     755    -869
524        -5   -2615    3668       529    3139   -3144
610       -94    -455    1769       704    1065   -1159
628      -148    -323    1727       776     951   -1099
703       -48    -988    2442       751    1691   -1739
703      -176    -342    1924       879    1045   -1221
720       -10   -2876    4326       730    3596   -3606
729      -240    -273    1971       969    1002   -1242
736        -7   -3680    5159       743    4416   -4423
749       -50   -1070    2618       799    1819   -1869
749      -107    -595    2200       856    1344   -1451
781      -142    -506    2210       923    1287   -1429
811       -87    -811    2520       898    1622   -1709
813       -22   -2146    3794       835    2959   -2981
819       -35   -1599    3272       854    2418   -2453
863        -6   -5172    6904       869    6035   -6041
1024       -82   -1280    3410      1106    2304   -2386
1035       -55   -1739    3864      1090    2774   -2829
1035       -69   -1480    3619      1104    2515   -2584
1035      -105   -1081    3256      1140    2116   -2221
1036      -111   -1037    3220      1147    2073   -2184
1044      -308    -435    2831      1352    1479   -1787
1153        -8   -6918    9232      1161    8071   -8079

There are two distinct solutions for each of the S-values

3  =  (3)
144  =  (2^4)(3^2)
225  =  (3^2)(5^2)
286  =  (2)(11)(13)
323  =  (17)(19)
703  =  (19)(37)
749  =  (7)(107)

and there are three distinct solutions for the S-value

1035  =  (3^2)(5)(23)

It's also interesting to note the odd fact that, beginning with the
7th entry on this list, every 7th entry has a single-digit value of
c, with the exception of the 21st entry.  However, even in this case
it is a near miss, because the 22nd entry has a single-digit c.
Another item of interest is that in three of the cases where there
are multiple solutions for a single S, there is also a solution for
S+1.  This is not too suprising, since the numbers to be factored
consist of three consecutive integers S-1, S, and S+1, which implies
that the candidates for consecutive S values share two factors.

Noting that exactly one of the factors on the left side of (2) is
divisible by 3, we can consider the most general factorization of
the two sides.  There are three cases to consider, depending on
whether 3 divides S-1, S, or S+1.  If 3 divides S, then we have
integers A,B,..,I such that

/ x+y+z \
(x+y+z-1)(  -----  )(x+y+z+1)  =  (x+y)(x+z)(y+z)
\   3   /

Therefore, we have

ABC = x+y+z-1      3DEF = x+y+z      GHI = x+y+z+1

ADG = x+y           BEH = x+z        CFI = y+z

This immediately gives many relations between the factors A,B,I, such
as
6DEF = ADG + BEH + CFI

3DEF  =  ABC + 1  =  GHI - 1

These are necessary and sufficient conditions for a solution.  Thus
for any S divisible by 3 we need only check the 3-part factorizations

S-1 = ABC     S/3 = DEF     S+1 = GHI

to see if the integers A,B,...,I satisfy 6DEF=ADG+BEH+CFI.  Of course,
the orderings of the factors can be changed, so we can hold one of
the orderings (say, ABC) fixed and apply all the permutations of the
other two orderings.  This gives 36 possible arrangements.  Also,
two of the numbers D,E,F could be negative, so if we are dealing with
only positive numbers we must allow for the three possibilities

6DEF =  ADG - BEH - CFI
6DEF = -ADG + BEH - CFI
6DEF = -ADG - BEH + CFI

There is a solution for S if and only if one of the 36 permutations
of the 3-part factorizations of S-1, S/3, S+1 satisfies one of these
three relations.  For example, with S = 99 we have

98 = (1)(14)(7)      99/3 = (11)(-1)(-3)     100 = (25)(4)(1)

corresponding to the assignments

A =  1   B = 14   C =  7
D = 11   E = -1   F = -3
G = 25   H =  4   I =  1