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

Question

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?

Links to the original problem:
https://www.geocaching.com/geocache/GC69JE0_lotto-mal-anders https://www.gutefrage.net/frage/matherechenart-gesucht-mehrere-variablen-mit-festen-ergebnis?foundIn=unknown_listing

Answer 1

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.

Answer 2

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$

Answer 3

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.