# 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? – Jack M May 20 '18 at 9:33
• @JackM The dot means multiplication. – N. F. Taussig May 20 '18 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. – Old Peter May 20 '18 at 11:08
• @JackM Yes, the dots separate powers of 1000 and should make the numbers easier to read. – user495573 May 20 '18 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$. – Adam Bailey May 21 '18 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{\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. – user495573 May 22 '18 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. – Old Peter May 22 '18 at 9:29
• The second link of the question gutefrage.net/frage/… gives the answer shown above. LOL! – Old Peter May 22 '18 at 17:59
• @Old Peter: now I feel myself like "expert from math.stackexchange" ;) – Oleg567 May 23 '18 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. – Mr Pie May 21 '18 at 11:56
• Okay, I'll elaborate it in a short while. Thanks for your comment. – User1234 May 21 '18 at 11:56
• No problem. I would not recommend deletion. $(+1)$ :) – Mr Pie May 21 '18 at 11:57
• Thanks! I've more or less shown how to go about with the question, could you have a look please? – User1234 May 21 '18 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. – user495573 May 22 '18 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.