# Non-linear system of equations over the positive integers — more unknowns than equations

This exercise appeared on a german online tutoring board and caught my attention but stumbled me for hours. The task is to find 6 distinct positive three digit integers satisfying:

$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=4.198$
$x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}+x_{5}^{2}+x_{6}^{2}=3.215.224$
$x_{1}^{3}+x_{2}^{3}+x_{3}^{3}+x_{4}^{3}+x_{5}^{3}+x_{6}^{3}=2.600.350.972$

According to the power mean inequality or Cauchy-Schwarz the numbers must lie relatively closely together. However a brief search lead nowhere. For simplicity I set $4.198=A$, $3.215.224=B$ and $2.600.350.972=C$ and then my approach was to manipulate the three equations and perhaps use that no square is negative. For example
$6B-A^{2}=\sum_{i<j}(x_i-x_j)^{2}=(x_{1}-x_{2})^2+(x_{1}-x_{3})^2+...+(x_{2}-x_{3})^2+...+(x_{5}-x_{6})^2$ where every distinct pair appears exactly once.
If now $6B-A^{2}$ would result in something like
$5*1^{2}+4*2^{2}+3*3^{2}+2*4^{2}+1*5^{2}=105$ we could tell exactly what our $x$ were. Unfortunately it gives $1.668.140$ and we cannot conclude much.
Similar reasoning with factoring to $\sum_{i<j}(x_i-x_j)^{4}$ didn't help.
If there exists such a factorization, my intuition says it would only make sense if the $x$ form an arithmetic sequence, otherwise we would get different factors on the right side that can't appear on the left side. (does this sound reasonable?) But substituting gives no solution. Also, I don't know what other, more sophisticated factorization would lead me to the solution.
I'm running out of ideas, how can this problem be solved?

• I believe by $4.198$ you mean $4198$, ie four thousand one hundred and ninety eight? Commented May 20, 2018 at 9:33
• @JackM The dot means multiplication. Commented May 20, 2018 at 9:40
• IMHO, the dots are just readability separators, as used in much of mainland Europe. I assume a manual method is wanted, as a program would be trivial. Commented May 20, 2018 at 11:08
• @JackM Yes, the dots separate powers of 1000 and should make the numbers easier to read. Commented May 20, 2018 at 11:36
• The possibilities can be narrowed down by considering congruence properties mod 8. Note that if $n$ is odd, $n^2 \equiv 1$ and $n^3 \equiv n$, while if $n$ is even, $n^2 \equiv 0,4$ and $n^3 \equiv 0$. The sums are respectively $\equiv 2,0,4$. Commented May 21, 2018 at 9:27

Assume that $x_1<x_2<\cdots < x_6$.

1st step.

Then $$6x_1<A<6x_6; \\ 6x_1^2<B<6x_6^2; \\ 6x_1^3<C<6x_6^3;$$

or (when note that $\dfrac{A}{6}\approx 699.66$, $\sqrt{\dfrac{B}{6}}\approx 732.03$, $\sqrt[3]{\dfrac{C}{6}}\approx 756.76$):

$$x_1\le 699; x_6\ge 700;$$ $$x_1\le 732; x_6\ge 733;$$ $$x_1\le 756; x_6\ge 757;$$

So, we have restrictions for the smallest and the largest numbers: $$x_1\le 700, x_6 \ge 757.$$

2nd step.

We can bruteforce values $x_1,x_2,x_3,x_4, x_5$, and then calculate $x_6 = A - (x_1+x_2+x_3+x_4+x_5)$, and then check whether other sums are correct.
But it takes $5$ loops through roughly almost $900$ possible values.

To reduce $1$ loop:

bruteforce values $x_1,x_2,x_3,x_4$;

denote $s_1 = x_1+x_2+x_3+x_4$, $s_2 = x_1^2+x_2^2+x_3^2+x_4^2$; and then derive $x_5$ and $x_6$: $$x_5+x_6 = A - s_1; \\ x_5^2+x_6^2 = B - s_2;$$ so $$x_5 x_6 = \dfrac{(x_5+x_6)^2-(x_5^2+x_6^2)}{2} = \dfrac{(A-s_1)^2 - (B-s_2)}{2}.$$

And $x_5,x_6$ are roots of polynomial $$w^2 - (x_5+x_6)w + x_5x_6;$$

then the discriminant $$D = 2(B-s_2)-(A-s_1)^2$$ should be a square number.

Using this approach, one can find (in reasonable time) that ...
(please skip this spoiled box if you'll try to solve this problem personally)

$$(x_1,\ldots,x_6) = (365, 438, 789, 821, 877, 908).$$

And maybe this is not the unique solution.

• Thanks for the answer. Apparently there's no way around bruteforcing. Commented May 22, 2018 at 6:46
• Clearly, programming a solution is not as easy as I originally thought. I’ll give it a go, if I can find a spare hour or two. Commented May 22, 2018 at 9:29
• The second link of the question gutefrage.net/frage/… gives the answer shown above. LOL! Commented May 22, 2018 at 17:59
• @Old Peter: now I feel myself like "expert from math.stackexchange" ;) Commented May 23, 2018 at 9:54

Try the method of Newton's Sums. Let $$P_i=x_1^i+x_2^i+x_3^i+x_4^i+x_5^i+x_6^i$$ Let $f(x)=ax^6+bx^5+cx^4+dx^3+ex^2+fx+g=0$ have roots $x_1,x_2,x_3,...,x_6$ We want to find the values of $a,b,c,...,g$ so as to find the roots of $f(x)$. This will furnish us with the values of $x_1,x_2,x_3,...,x_6$.  Also, $$\begin{array} { l l l } e_1 & = \sum x_i & = - \frac{b}{a} \\ e_2 & = \sum x_i x_j & = \frac{ c } { a} \\ e_3 & = \sum x_i x_j x_k & = - \frac{ d } { a} \\ & \vdots & \vdots \\ e_6 & = \sum \prod x_i & = \frac{g} { a}. \end{array}$$  Lastly, the recurrence relation for $P_i$ for a polynomial of degree $k$ is as follows:

For $i \leq k - 1$, we have the formulas

$\begin{array} { l l l l } P_0 & = k \\ P_1 & = e_1 \times 1 \\ P_2 & = e_1 P_1 - e_2 \times 2 \\ P_3 & = e_1 P_2 - e_2 P_1 + e_3 \times 3 \\ & \vdots \\ P_{k-1} & = e_1 P_{k-2} - e_2 P_{k-3} + \cdots + (-1)^{k-3} e_{k-2} P_1 + (-1)^{k-2} e_{k-1} \times (k-1). \end{array}$ 

For $i \geq k$, we have the formula

$$P_i = \sum_{j=1}^k (-1)^{j+1} e_j P_{i-j} = e_1 P_{i-1} - e_2 P_{i-2} + \cdots + (-1)^{k+1} e_k P_{i-k}. \ _\square$$  Hence $P_1=4198, P_2=3215224,P_3=2600350972$  But, $$P_1=e_1$$ $$P_2=e_1P_1-2e_2$$$$P_3=e_1P_2-e_2P_1-3e_3$$

Now, $$4198=e_1$$ $$3215224=(4198)(4198)-2e_2\Rightarrow e_2=7203990$$ $$2600350972=(4198)(3215224)-(7203990)(4198)-3e_3\Rightarrow e_3=-868113246$$ In this way, "recreate" $f(x)$ by evaluating $e_4,e_5,e_6$ (hence determining the values of the coefficients $a$, $b$,...,$g$), and the roots of the 'recreated' $f(x)$ will be the values of $x_1,x_2,...,x_6$

• This is an OK answer; it is link-only and is lacking context and other detail. Please elaborate further in order to write a good answer. Commented May 21, 2018 at 11:56
• Okay, I'll elaborate it in a short while. Thanks for your comment. Commented May 21, 2018 at 11:56
• No problem. I would not recommend deletion. $(+1)$ :) Commented May 21, 2018 at 11:57
• Thanks! I've more or less shown how to go about with the question, could you have a look please? Commented May 21, 2018 at 13:19
• I like this approach, also Newton's identities seem to be a powerful tool in this context. But if I'm not mistaken we can only find $e_{1}, e_{2}$ and $e_{3}$ this way for we don't have sufficient information because it doesn't take into account that we're dealing with integers only. Commented May 22, 2018 at 6:15

Find 6 distinct positive three digit integers satisfying

$$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=A=4198\tag1$$ $$x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}+x_{5}^{2}+x_{6}^{2}=B=3215224\tag2$$ $$x_{1}^{3}+x_{2}^{3}+x_{3}^{3}+x_{4}^{3}+x_{5}^{3}+x_{6}^{3}=C=2600350972\tag3$$

As $B\equiv 0{\pmod{8}}$, the square residues$\pmod{8}$ are $(0,4,1,1,1,1)$, $(4,4,4,4,4,4)$ or $(0,0,0,0,0,0,0)$

However, $C\equiv 4{\pmod{8}}$, so $(4,4,4,4,4,4)$ and $(0,0,0,0,0,0,0)$ are rejected.

WLOG, $x_{1}> x_{2}$ and $x_{3}> x_{4}>x_{5}>x_{6}$,

Hence, we have

$x_{1}$ even and in the range $(102,998)$

$x_{2}$ even and in the range $(100,x_{1}-2)$

$x_{1}+x_{2}\equiv 2{\pmod{4}}$

$x_{3}$ odd and in the range $(107,999)$

$x_{4}$ odd and in the range $(105,x_{3}-2)$

$x_{5}$ odd and in the range $(103,x_{4}-2)$

$x_{6}$ is easily calculated from the other $x$, but must be odd and in the range $(101,x_{5}-2)$

Now we can consider a program. I started using equation $(1)$, but the gargantuan volume of solutions was overwhelming.

Equation $(3)$ was much faster, although there was still a massive number of results, so I just reported cases where $(1)$ or $2$, or both, were also satisfied.

The program is essentially as above, with a few tuning tweaks.

I precalculated the squares and cubes of $100$ to $999$.

For $x_{3}$ to $x_{5}$, I calculated the minimum and maximum values, reducing the search-range when possible.

My results

The solution found by @Oleg567 is unique.

There is just one other solution that satisfies equations $(2)$ and $(3)$, but not $(1)$

$$(746,120,939,815,751,731)$$

There are $1107$ solutions that satisfy equations $(1)$ and $(3)$, but not $(2)$

The program used under $22$ minutes CPU.