We consider monic degree-\(7\) polynomials
$$P(t)=t^7+a_1t^6+a_2t^5+a_3t^4+a_4t^3+a_5t^2+a_6t+a_7$$
with integer coefficients, all roots real, and sorted roots \(r_1\le \cdots \le r_7\) satisfying
$$\lfloor r_i\rfloor=i \qquad (1\le i\le 7).$$
For every admissible coefficient vector \(a=(a_1,\dots,a_7)\), define
$$S(a)=\sum_{i=1}^7 |a_i|.$$
The goal is to sum \(S(a)\) over all such polynomials.
Because the roots are real and lie in the positive intervals \([1,2),[2,3),\dots,[7,8)\), we may write
$$P(t)=\prod_{i=1}^7 (t-r_i)=t^7-e_1t^6+e_2t^5-e_3t^4+e_4t^3-e_5t^2+e_6t-e_7,$$
where \(e_m\) is the \(m\)-th elementary symmetric sum of the roots. Therefore
$$a_m=(-1)^m e_m \qquad (1\le m\le 7).$$
Since every root is positive, all \(e_m\) are positive as well, and the objective becomes simply
$$S(a)=e_1+e_2+\cdots+e_7.$$
So the search is really over the positive symmetric sums \(e_1,\dots,e_7\), not over arbitrary signed coefficients.
For the elementary symmetric polynomial
$$E_m(b_1,\dots,b_7)=\sum_{1\le i_1<\cdots<i_m\le 7} b_{i_1}\cdots b_{i_m},$$
monotonicity on positive inputs gives
$$E_m(1,2,\dots,7)\le e_m < E_m(2,3,\dots,8).$$
Evaluating these endpoint sums yields the integer coefficient box
$$\begin{aligned} 28\le e_1\le 34,\qquad &322\le e_2\le 510,\qquad 1960\le e_3\le 4024,\\ 6769\le e_4\le 18423,\qquad &13132\le e_5\le 48859,\\ 13068\le e_6\le 69263,\qquad &5040\le e_7\le 40319. \end{aligned}$$
These bounds already remove the overwhelming majority of impossible tuples.
For an integer \(k\in\{1,\dots,8\}\), the value
$$P(k)=\prod_{i=1}^7 (k-r_i)$$
has a prescribed sign. Indeed, when \(P(k)\neq 0\), exactly \(8-k\) factors are negative, so
$$(-1)^k P(k)\ge 0 \qquad (1\le k\le 8).$$
Written in the symmetric sums, this becomes the affine inequality
$$(-1)^k\left(k^7-e_1k^6+e_2k^5-e_3k^4+e_4k^3-e_5k^2+e_6k-e_7\right)\ge 0.$$
If all eight inequalities are strict, then the sign alternates between consecutive integers, so the intermediate value theorem forces one root in each open interval \((k,k+1)\). Since the degree is \(7\), that already accounts for all roots.
Equality \(P(k)=0\) means a root lies exactly on an integer boundary. The sign test alone is not enough there: the polynomial must cross the axis in the direction compatible with the interval \([k,k+1)\).
Near a simple root at \(k\),
$$P(t)\approx P'(k)(t-k),$$
so the admissible orientation is
$$(-1)^{k+1}P'(k)>0 \qquad (1\le k\le 7).$$
At \(k=8\), equality is impossible for a valid polynomial, because no root may have integer part \(8\). This is exactly why the implementation performs a final endpoint validation after the linear range computation.
We now have two kinds of constraints:
$$\text{box bounds for } e_1,\dots,e_7,$$
and
$$8 \text{ affine sign constraints coming from } P(1),P(2),\dots,P(8).$$
Every one of these conditions is linear in the variables \(e_1,\dots,e_7\). Therefore the feasible set is a polyhedral region inside the coefficient box.
The implementation applies Fourier-Motzkin elimination to project away the later coefficients one by one. After these projections have been precomputed, fixing the first few coefficients immediately produces a much tighter lower and upper bound for the next one.
So the search does not walk through the entire raw box. It chooses coefficients in order, repeatedly intersects the static interval from Step 2 with the projected linear interval coming from the remaining sign conditions, and abandons the branch as soon as the interval becomes empty.
After \(e_1,\dots,e_6\) have been chosen, the remaining valid values of \(e_7\) form a single integer interval \([L,R]\). Because all constraints are linear in \(e_7\), any equality case \(P(k)=0\) can only occur at the ends of that interval, so only the endpoints need the derivative test from Step 4.
Once the valid interval is known, its total contribution to the objective is
$$\sum_{u=L}^{R}(e_1+\cdots+e_6+u)=(R-L+1)(e_1+\cdots+e_6)+\frac{(L+R)(R-L+1)}{2}.$$
This arithmetic-series formula is what lets the implementation aggregate an entire final interval in constant time.
The C++, Python, and Java implementations use the same mathematical pipeline. They enumerate the positive symmetric sums instead of the signed coefficients, start from the interval bounds implied by the root locations, precompute projected linear constraints, and then run a depth-first search whose branches are cut as soon as a coefficient interval is empty. For the final coefficient, they validate only boundary values that make some \(P(k)\) vanish, and then add the whole interval contribution with the closed formula above rather than iterating one integer at a time.
Brute force over the coefficient box would be astronomically large. The implemented method is still exponential in the number of free coefficients in the worst case, because it is fundamentally a search problem, but the projected linear bounds reduce the branching factor dramatically. Memory usage stays small: the algorithm stores only a few projected linear systems, the current recursion stack, and the running total.
Betrachtet werden normierte Polynome siebten Grades
$$P(t)=t^7+a_1t^6+a_2t^5+a_3t^4+a_4t^3+a_5t^2+a_6t+a_7$$
mit ganzzahligen Koeffizienten. Alle Nullstellen seien reell, und die sortierten Nullstellen \(r_1\le \cdots \le r_7\) erfüllen
$$\lfloor r_i\rfloor=i \qquad (1\le i\le 7).$$
Für jeden zulässigen Koeffizientenvektor \(a=(a_1,\dots,a_7)\) ist
$$S(a)=\sum_{i=1}^7 |a_i|$$
definiert. Gesucht ist die Summe von \(S(a)\) über alle zulässigen Polynome.
Da die Nullstellen in den positiven Intervallen \([1,2),[2,3),\dots,[7,8)\) liegen, kann man schreiben
$$P(t)=\prod_{i=1}^7 (t-r_i)=t^7-e_1t^6+e_2t^5-e_3t^4+e_4t^3-e_5t^2+e_6t-e_7,$$
wobei \(e_m\) die \(m\)-te elementarsymmetrische Summe der Nullstellen bezeichnet. Damit gilt
$$a_m=(-1)^m e_m \qquad (1\le m\le 7).$$
Weil alle Nullstellen positiv sind, sind auch alle \(e_m\) positiv. Daher vereinfacht sich die Zielfunktion zu
$$S(a)=e_1+e_2+\cdots+e_7.$$
Die Implementierung durchsucht also nicht beliebige Vorzeichenmuster, sondern direkt die positiven symmetrischen Summen \(e_1,\dots,e_7\).
Für das elementarsymmetrische Polynom
$$E_m(b_1,\dots,b_7)=\sum_{1\le i_1<\cdots<i_m\le 7} b_{i_1}\cdots b_{i_m}$$
liefert Monotonie bei positiven Argumenten
$$E_m(1,2,\dots,7)\le e_m < E_m(2,3,\dots,8).$$
Daraus folgt der ganzzahlige Suchkasten
$$\begin{aligned} 28\le e_1\le 34,\qquad &322\le e_2\le 510,\qquad 1960\le e_3\le 4024,\\ 6769\le e_4\le 18423,\qquad &13132\le e_5\le 48859,\\ 13068\le e_6\le 69263,\qquad &5040\le e_7\le 40319. \end{aligned}$$
Schon diese Grenzen eliminieren den größten Teil aller unmöglichen Koeffiziententupel.
Für eine ganze Zahl \(k\in\{1,\dots,8\}\) gilt
$$P(k)=\prod_{i=1}^7 (k-r_i).$$
Falls \(P(k)\neq 0\), sind genau \(8-k\) Faktoren negativ. Daher muss gelten
$$(-1)^k P(k)\ge 0 \qquad (1\le k\le 8).$$
In den Variablen \(e_1,\dots,e_7\) ist das die affine Ungleichung
$$(-1)^k\left(k^7-e_1k^6+e_2k^5-e_3k^4+e_4k^3-e_5k^2+e_6k-e_7\right)\ge 0.$$
Sind alle diese Ungleichungen strikt, dann wechselt das Vorzeichen an aufeinanderfolgenden ganzen Zahlen, und der Zwischenwertsatz erzwingt genau eine Nullstelle in jedem offenen Intervall \((k,k+1)\). Bei Grad \(7\) sind damit bereits alle Nullstellen erklärt.
Die Gleichheit \(P(k)=0\) bedeutet, dass eine Nullstelle genau auf einer ganzzahligen Grenze liegt. Dann reicht das bloße Vorzeichenkriterium nicht aus: Das Polynom muss die Achse in der richtigen Richtung schneiden.
In der Nähe einer einfachen Nullstelle \(k\) gilt
$$P(t)\approx P'(k)(t-k),$$
also ist die zulässige Orientierung
$$(-1)^{k+1}P'(k)>0 \qquad (1\le k\le 7).$$
Bei \(k=8\) ist Gleichheit für ein gültiges Polynom ausgeschlossen, da keine Nullstelle ganzzahligen Anteil \(8\) haben darf. Genau deshalb prüft die Implementierung am Ende nur noch die Intervallränder gesondert.
Es gibt nun zwei Typen von Bedingungen:
$$\text{Kasten-Schranken für } e_1,\dots,e_7,$$
und
$$8 \text{ affine Vorzeichenbedingungen aus } P(1),P(2),\dots,P(8).$$
Alle diese Relationen sind linear in den Variablen \(e_1,\dots,e_7\). Der zulässige Bereich ist daher ein Polyeder innerhalb des Koeffizientenkastens.
Die Implementierung verwendet Fourier-Motzkin-Elimination, um die späteren Koeffizienten schrittweise wegzuprojezieren. Nach dieser Vorberechnung liefern feste Anfangskoeffizienten sofort deutlich schärfere untere und obere Grenzen für den jeweils nächsten Koeffizienten.
Die Suche läuft also nicht über den gesamten Rohkasten. Stattdessen werden die Koeffizienten nacheinander gewählt; jedes Mal wird das statische Intervall aus Schritt 2 mit einem projizierten linearen Intervall geschnitten, und ein Zweig wird sofort verworfen, sobald das Ergebnis leer ist.
Sind \(e_1,\dots,e_6\) fest, dann bilden die zulässigen Werte von \(e_7\) ein einziges ganzzahliges Intervall \([L,R]\). Weil alle Bedingungen linear in \(e_7\) sind, kann ein Gleichheitsfall \(P(k)=0\) nur an den Endpunkten dieses Intervalls auftreten. Deshalb müssen nur diese Randwerte mit der Ableitungsbedingung aus Schritt 4 geprüft werden.
Ist das Intervall validiert, dann lautet sein Gesamtbeitrag
$$\sum_{u=L}^{R}(e_1+\cdots+e_6+u)=(R-L+1)(e_1+\cdots+e_6)+\frac{(L+R)(R-L+1)}{2}.$$
Damit ersetzt die Implementierung eine punktweise Enumeration durch eine einzige Formel für eine arithmetische Reihe.
Die C++-, Python- und Java-Implementierungen folgen derselben mathematischen Struktur. Sie zählen die positiven symmetrischen Summen statt der vorzeichenbehafteten Koeffizienten, starten mit den durch die Wurzelintervalle erzwungenen Schranken, benutzen vorab projizierte lineare Bedingungen zur Intervallverengung während einer Tiefensuche und schneiden Zweige sofort ab, wenn ein Intervall leer wird. Für den letzten Koeffizienten werden nur noch Randwerte überprüft, bei denen ein \(P(k)\) verschwinden könnte; anschließend wird der Beitrag des gesamten Intervalls mit der obigen Summenformel addiert.
Ein Brute-Force-Verfahren über den gesamten Koeffizientenkasten wäre astronomisch teuer. Das implementierte Verfahren bleibt im Worst Case exponentiell in der Zahl der freien Koeffizienten, weil es letztlich ein Suchproblem ist, aber die projizierten linearen Schranken reduzieren den Verzweigungsgrad massiv. Der Speicherbedarf bleibt klein: einige projizierte lineare Systeme, der aktuelle Rekursionspfad und die laufende Summe genügen.
Derecesi \(7\) olan monik polinomları inceliyoruz:
$$P(t)=t^7+a_1t^6+a_2t^5+a_3t^4+a_4t^3+a_5t^2+a_6t+a_7.$$
Katsayılar tam sayıdır, tüm kökler gerçektir ve sıralı kökler \(r_1\le \cdots \le r_7\) şu koşulu sağlar:
$$\lfloor r_i\rfloor=i \qquad (1\le i\le 7).$$
Her geçerli katsayı vektörü \(a=(a_1,\dots,a_7)\) için
$$S(a)=\sum_{i=1}^7 |a_i|$$
tanımlanır. Amaç, tüm geçerli polinomlar üzerinde \(S(a)\) toplamını bulmaktır.
Kökler \([1,2),[2,3),\dots,[7,8)\) aralıklarında olduğundan
$$P(t)=\prod_{i=1}^7 (t-r_i)=t^7-e_1t^6+e_2t^5-e_3t^4+e_4t^3-e_5t^2+e_6t-e_7$$
şeklinde yazabiliriz. Burada \(e_m\), köklerin \(m\). elemanter simetrik toplamıdır. Dolayısıyla
$$a_m=(-1)^m e_m \qquad (1\le m\le 7).$$
Bütün kökler pozitif olduğu için tüm \(e_m\) değerleri de pozitiftir. Bu yüzden hedef fonksiyon
$$S(a)=e_1+e_2+\cdots+e_7$$
olur. Yani arama, işaretli katsayılarda değil, pozitif simetrik toplamlar \(e_1,\dots,e_7\) üzerinde yapılır.
Elemanter simetrik polinom
$$E_m(b_1,\dots,b_7)=\sum_{1\le i_1<\cdots<i_m\le 7} b_{i_1}\cdots b_{i_m}$$
için, pozitif girdilerde tekdüzelik sayesinde
$$E_m(1,2,\dots,7)\le e_m < E_m(2,3,\dots,8)$$
elde edilir. Sayısal olarak bu, şu tam sayı aralıklarını verir:
$$\begin{aligned} 28\le e_1\le 34,\qquad &322\le e_2\le 510,\qquad 1960\le e_3\le 4024,\\ 6769\le e_4\le 18423,\qquad &13132\le e_5\le 48859,\\ 13068\le e_6\le 69263,\qquad &5040\le e_7\le 40319. \end{aligned}$$
Bu kutu sınırları tek başına bile imkansız adayların büyük kısmını eler.
\(k\in\{1,\dots,8\}\) tam sayısı için
$$P(k)=\prod_{i=1}^7 (k-r_i)$$
değerinin işareti önceden bellidir. \(P(k)\neq 0\) ise tam olarak \(8-k\) tane negatif çarpan vardır; dolayısıyla
$$(-1)^k P(k)\ge 0 \qquad (1\le k\le 8)$$
olmalıdır. Bu koşul, \(e_1,\dots,e_7\) cinsinden şu doğrusal eşitsizliktir:
$$(-1)^k\left(k^7-e_1k^6+e_2k^5-e_3k^4+e_4k^3-e_5k^2+e_6k-e_7\right)\ge 0.$$
Eğer bu sekiz eşitsizliğin hepsi sıkıysa, ardışık tam sayılarda işaret değişimi olur. Ara değer teoremi böylece her \((k,k+1)\) açık aralığında bir kök bulunduğunu söyler. Derece \(7\) olduğu için tüm kökler bundan ibarettir.
\(P(k)=0\) olması, bir kökün tam sayı sınırına tam denk geldiği anlamına gelir. Bu durumda yalnızca işaret koşulu yetmez; polinom ekseni doğru yönde kesmelidir.
Basit bir kökün yakınında
$$P(t)\approx P'(k)(t-k)$$
olduğundan uygun yönelim
$$(-1)^{k+1}P'(k)>0 \qquad (1\le k\le 7)$$
şeklindedir. \(k=8\) için eşitlik geçersizdir; çünkü hiçbir kökün tam sayı kısmı \(8\) olamaz. Uygulamanın son aşamada sadece uç değerleri ayrıca doğrulamasının nedeni tam olarak budur.
Artık iki tür koşulumuz var:
$$\text{\(e_1,\dots,e_7\) için kutu sınırları}$$
ve
$$P(1),P(2),\dots,P(8)\text{ değerlerinden gelen }8\text{ doğrusal işaret koşulu}.$$
Bu koşulların hepsi \(e_1,\dots,e_7\) değişkenlerinde doğrusaldır. Dolayısıyla uygun küme, katsayı kutusunun içinde kalan bir çokyüzlü bölgedir.
Uygulama, daha sonraki katsayıları adım adım yok etmek için Fourier-Motzkin eliminasyonu kullanır. Bu projeksiyonlar önceden çıkarıldıktan sonra, ilk birkaç katsayı sabitlendiğinde bir sonraki katsayı için çok daha dar bir alt ve üst sınır hemen elde edilir.
Böylece arama ham kutunun tamamında dolaşmaz. Katsayılar sırayla seçilir; her adımda Adım 2'deki statik aralık ile geriye kalan işaret koşullarından türetilen projeksiyon aralığı kesiştirilir; sonuç boşsa dal anında budanır.
\(e_1,\dots,e_6\) sabitlenince, \(e_7\) için kalan geçerli değerler tek bir tam sayı aralığı \([L,R]\) oluşturur. Bütün koşullar \(e_7\)'de doğrusal olduğu için \(P(k)=0\) eşitliği ancak bu aralığın uçlarında oluşabilir. Bu yüzden sadece uç noktalar Adım 4'teki türev kuralıyla kontrol edilir.
Geçerli aralık bulunduğunda toplam katkı
$$\sum_{u=L}^{R}(e_1+\cdots+e_6+u)=(R-L+1)(e_1+\cdots+e_6)+\frac{(L+R)(R-L+1)}{2}$$
olur. Bu aritmetik dizi formülü, son aralıktaki değerleri tek tek sayma ihtiyacını ortadan kaldırır.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. İşaretli katsayılar yerine pozitif simetrik toplamlar üzerinde arama yaparlar; kök aralıklarının verdiği ilk sınırlarla başlarlar; önceden projekte edilmiş doğrusal koşullarla derinlik öncelikli arama sırasında her yeni katsayının aralığını daraltırlar; aralık boşaldığı anda dalı keserler. Son katsayıda ise yalnızca \(P(k)=0\) yapabilecek sınır değerleri doğrular, ardından tüm aralık katkısını yukarıdaki kapalı formülle eklerler.
Tüm katsayı kutusu üzerinde kaba kuvvet taraması astronomik büyüklüktedir. Uygulanan yöntem en kötü durumda serbest katsayı sayısında hâlâ üstel davranır; çünkü temelde bu bir arama problemidir. Ancak projekte edilmiş doğrusal sınırlar dallanmayı ciddi biçimde küçültür. Bellek kullanımı da düşüktür: birkaç doğrusal sistem, güncel özyineleme yığını ve kümülatif toplam yeterlidir.
Estudiamos polinomios mónicos de grado \(7\)
$$P(t)=t^7+a_1t^6+a_2t^5+a_3t^4+a_4t^3+a_5t^2+a_6t+a_7$$
con coeficientes enteros, todas las raíces reales y raíces ordenadas \(r_1\le \cdots \le r_7\) que cumplen
$$\lfloor r_i\rfloor=i \qquad (1\le i\le 7).$$
Para cada vector admisible \(a=(a_1,\dots,a_7)\) se define
$$S(a)=\sum_{i=1}^7 |a_i|.$$
Hay que sumar \(S(a)\) sobre todos los polinomios válidos.
Como las raíces están en los intervalos positivos \([1,2),[2,3),\dots,[7,8)\), podemos escribir
$$P(t)=\prod_{i=1}^7 (t-r_i)=t^7-e_1t^6+e_2t^5-e_3t^4+e_4t^3-e_5t^2+e_6t-e_7,$$
donde \(e_m\) es la \(m\)-ésima suma simétrica elemental de las raíces. Por lo tanto,
$$a_m=(-1)^m e_m \qquad (1\le m\le 7).$$
Como todas las raíces son positivas, todos los \(e_m\) también lo son, y la función objetivo se reduce a
$$S(a)=e_1+e_2+\cdots+e_7.$$
Así, la búsqueda real se hace sobre las sumas simétricas positivas \(e_1,\dots,e_7\), no sobre coeficientes con signos arbitrarios.
Para el polinomio simétrico elemental
$$E_m(b_1,\dots,b_7)=\sum_{1\le i_1<\cdots<i_m\le 7} b_{i_1}\cdots b_{i_m},$$
la monotonía en entradas positivas da
$$E_m(1,2,\dots,7)\le e_m < E_m(2,3,\dots,8).$$
Al evaluar esos extremos obtenemos la caja entera
$$\begin{aligned} 28\le e_1\le 34,\qquad &322\le e_2\le 510,\qquad 1960\le e_3\le 4024,\\ 6769\le e_4\le 18423,\qquad &13132\le e_5\le 48859,\\ 13068\le e_6\le 69263,\qquad &5040\le e_7\le 40319. \end{aligned}$$
Estas cotas ya descartan una cantidad enorme de candidatos imposibles.
Para un entero \(k\in\{1,\dots,8\}\),
$$P(k)=\prod_{i=1}^7 (k-r_i).$$
Si \(P(k)\neq 0\), hay exactamente \(8-k\) factores negativos. Por consiguiente, debe cumplirse
$$(-1)^k P(k)\ge 0 \qquad (1\le k\le 8).$$
En términos de \(e_1,\dots,e_7\), esto es
$$(-1)^k\left(k^7-e_1k^6+e_2k^5-e_3k^4+e_4k^3-e_5k^2+e_6k-e_7\right)\ge 0.$$
Si las ocho desigualdades son estrictas, el signo alterna entre enteros consecutivos, y el teorema del valor intermedio obliga a que haya una raíz en cada intervalo abierto \((k,k+1)\). Como el grado es \(7\), eso ya describe todas las raíces.
La igualdad \(P(k)=0\) significa que una raíz cae exactamente en una frontera entera. En ese caso el signo no basta: el polinomio debe cruzar el eje con la orientación correcta para que la raíz pertenezca al intervalo \([k,k+1)\).
Cerca de una raíz simple en \(k\),
$$P(t)\approx P'(k)(t-k),$$
de modo que la orientación válida es
$$(-1)^{k+1}P'(k)>0 \qquad (1\le k\le 7).$$
En \(k=8\) la igualdad es imposible para un polinomio válido, porque ninguna raíz puede tener parte entera \(8\). Por eso la implementación hace una validación adicional solo en los extremos finales.
Ahora tenemos dos familias de restricciones:
$$\text{cotas tipo caja para } e_1,\dots,e_7,$$
y
$$8 \text{ restricciones afines derivadas de } P(1),P(2),\dots,P(8).$$
Todas son lineales en las variables \(e_1,\dots,e_7\). Por eso el conjunto admisible es una región poliédrica dentro de la caja inicial.
La implementación aplica eliminación de Fourier-Motzkin para proyectar sucesivamente los coeficientes finales. Tras esa precomputación, fijar los primeros coeficientes produce enseguida cotas mucho más estrechas para el siguiente coeficiente.
En consecuencia, la búsqueda no recorre toda la caja bruta. Va eligiendo coeficientes en orden, intersecta el intervalo estático del Paso 2 con el intervalo lineal proyectado por las restricciones restantes, y poda la rama en cuanto la intersección queda vacía.
Una vez fijados \(e_1,\dots,e_6\), los valores posibles de \(e_7\) forman un único intervalo entero \([L,R]\). Como todas las restricciones son lineales en \(e_7\), los casos de igualdad \(P(k)=0\) solo pueden aparecer en los extremos de ese intervalo. Por eso basta con verificar esos extremos usando la condición con la derivada del Paso 4.
Si el intervalo final es válido, su contribución total vale
$$\sum_{u=L}^{R}(e_1+\cdots+e_6+u)=(R-L+1)(e_1+\cdots+e_6)+\frac{(L+R)(R-L+1)}{2}.$$
Esta fórmula de progresión aritmética evita enumerar entero por entero el último tramo.
Las implementaciones en C++, Python y Java siguen exactamente esta estructura matemática. Enumeran las sumas simétricas positivas en lugar de los coeficientes con signo, empiezan por las cotas que imponen los intervalos de las raíces, usan restricciones lineales proyectadas para estrechar el siguiente intervalo durante una búsqueda en profundidad y descartan una rama en cuanto un intervalo queda vacío. Para el último coeficiente, solo revisan los valores frontera que podrían hacer \(P(k)=0\), y luego añaden de una vez la contribución de todo el intervalo con la fórmula cerrada.
Un barrido exhaustivo sobre toda la caja de coeficientes sería astronómico. El método implementado sigue siendo exponencial en el peor caso respecto al número de coeficientes libres, porque el problema de fondo sigue siendo de búsqueda, pero las proyecciones lineales reducen muchísimo el factor de ramificación. El uso de memoria es pequeño: solo se conservan unos pocos sistemas lineales proyectados, la pila de recursión actual y la suma acumulada.
我们研究首一七次多项式
$$P(t)=t^7+a_1t^6+a_2t^5+a_3t^4+a_4t^3+a_5t^2+a_6t+a_7$$
其中系数为整数，全部根都是实数，并且按从小到大排列后的根 \(r_1\le \cdots \le r_7\) 满足
$$\lfloor r_i\rfloor=i \qquad (1\le i\le 7).$$
对每个可行系数向量 \(a=(a_1,\dots,a_7)\)，定义
$$S(a)=\sum_{i=1}^7 |a_i|.$$
目标是把所有可行多项式对应的 \(S(a)\) 全部加起来。
由于七个根分别落在正区间 \([1,2),[2,3),\dots,[7,8)\) 中，可以写成
$$P(t)=\prod_{i=1}^7 (t-r_i)=t^7-e_1t^6+e_2t^5-e_3t^4+e_4t^3-e_5t^2+e_6t-e_7,$$
其中 \(e_m\) 是七个根的第 \(m\) 个初等对称和。因此
$$a_m=(-1)^m e_m \qquad (1\le m\le 7).$$
因为所有根都为正，所以所有 \(e_m\) 也都为正，目标函数直接变成
$$S(a)=e_1+e_2+\cdots+e_7.$$
也就是说，真正被枚举的不是带符号的系数，而是正的对称和 \(e_1,\dots,e_7\)。
记初等对称多项式
$$E_m(b_1,\dots,b_7)=\sum_{1\le i_1<\cdots<i_m\le 7} b_{i_1}\cdots b_{i_m}.$$
由于它在正输入上单调递增，所以有
$$E_m(1,2,\dots,7)\le e_m < E_m(2,3,\dots,8).$$
把两端算出来，就得到整数范围
$$\begin{aligned} 28\le e_1\le 34,\qquad &322\le e_2\le 510,\qquad 1960\le e_3\le 4024,\\ 6769\le e_4\le 18423,\qquad &13132\le e_5\le 48859,\\ 13068\le e_6\le 69263,\qquad &5040\le e_7\le 40319. \end{aligned}$$
这一步已经把绝大多数不可能的候选全部排除了。
对任意整数 \(k\in\{1,\dots,8\}\)，有
$$P(k)=\prod_{i=1}^7 (k-r_i).$$
当 \(P(k)\neq 0\) 时，负因子的个数恰好是 \(8-k\)，因此必须满足
$$(-1)^k P(k)\ge 0 \qquad (1\le k\le 8).$$
把它改写成 \(e_1,\dots,e_7\) 的线性不等式，就是
$$(-1)^k\left(k^7-e_1k^6+e_2k^5-e_3k^4+e_4k^3-e_5k^2+e_6k-e_7\right)\ge 0.$$
如果这八个不等式都是严格的，那么相邻整数点的符号就会交替变化。由介值定理可知，每个开区间 \((k,k+1)\) 中都至少有一个根。由于多项式次数正好是 \(7\)，这已经完全确定了根的分布。
若 \(P(k)=0\)，说明某个根正好落在整数边界上。这时单看符号还不够，必须确认多项式穿过横轴的方向与区间 \([k,k+1)\) 一致。
在简单根 \(k\) 的附近，
$$P(t)\approx P'(k)(t-k),$$
因此允许的方向条件是
$$(-1)^{k+1}P'(k)>0 \qquad (1\le k\le 7).$$
而在 \(k=8\) 处，等号绝不允许出现，因为任何根的整数部分都不能是 \(8\)。这也解释了为什么实现只在最后一步单独检查区间端点。
现在我们有两类限制：
$$\text{\(e_1,\dots,e_7\) 的盒状范围}$$
以及
$$P(1),P(2),\dots,P(8)\text{ 给出的 }8\text{ 个仿射符号约束}.$$
这些条件对 \(e_1,\dots,e_7\) 都是线性的，因此整体可行集就是初始系数盒中的一个多面体区域。
实现使用 Fourier-Motzkin 消元，把后面的系数逐步投影出去。这样一来，只要前面若干个系数已经固定，下一项系数就能立刻得到远比原始盒状范围更紧的上下界。
因此搜索不会在整个原始盒子里盲目枚举，而是按顺序选择系数，把步骤 2 的静态区间与投影得到的线性区间相交；一旦交集为空，该分支马上剪掉。
当 \(e_1,\dots,e_6\) 固定后，剩余可行的 \(e_7\) 会组成一个单独的整数区间 \([L,R]\)。由于所有限制对 \(e_7\) 都是线性的，所以只有区间端点才可能出现 \(P(k)=0\) 的等号情形。于是只需要对这些端点应用步骤 4 的导数判定。
一旦区间合法，它对目标函数的总贡献就是
$$\sum_{u=L}^{R}(e_1+\cdots+e_6+u)=(R-L+1)(e_1+\cdots+e_6)+\frac{(L+R)(R-L+1)}{2}.$$
这条等差求和公式使得最后一层无需逐个枚举整数。
C++、Python 和 Java 实现遵循同一条数学路线。它们枚举的是正的对称和，而不是带符号的原始系数；先使用根区间给出的静态范围；再利用预先投影好的线性约束，在深度优先搜索过程中不断收紧下一个系数的区间；一旦区间为空就立即剪枝。对于最后一个系数，只检查会让某个 \(P(k)\) 恰好为零的边界值，然后用上面的闭式公式一次性加入整段区间的贡献。
如果直接在整个系数盒上暴力枚举，规模会大到完全不可行。这个方法在最坏情况下相对于自由系数个数仍然是指数级的，因为它本质上仍是搜索问题；但线性投影和区间剪枝把实际分支数压得很低。内存占用也不大，只需要少量投影后的线性系统、当前递归栈和累计答案。
Рассматриваются унитарные многочлены степени \(7\)
$$P(t)=t^7+a_1t^6+a_2t^5+a_3t^4+a_4t^3+a_5t^2+a_6t+a_7$$
с целыми коэффициентами. Все корни вещественные, а упорядоченные корни \(r_1\le \cdots \le r_7\) удовлетворяют условию
$$\lfloor r_i\rfloor=i \qquad (1\le i\le 7).$$
Для каждого допустимого вектора коэффициентов \(a=(a_1,\dots,a_7)\) определим
$$S(a)=\sum_{i=1}^7 |a_i|.$$
Нужно просуммировать \(S(a)\) по всем допустимым многочленам.
Поскольку корни лежат в положительных интервалах \([1,2),[2,3),\dots,[7,8)\), можно записать
$$P(t)=\prod_{i=1}^7 (t-r_i)=t^7-e_1t^6+e_2t^5-e_3t^4+e_4t^3-e_5t^2+e_6t-e_7,$$
где \(e_m\) обозначает \(m\)-ю элементарную симметрическую сумму корней. Поэтому
$$a_m=(-1)^m e_m \qquad (1\le m\le 7).$$
Так как все корни положительны, все \(e_m\) тоже положительны, и целевая функция упрощается до
$$S(a)=e_1+e_2+\cdots+e_7.$$
Следовательно, поиск идёт не по произвольным знаковым коэффициентам, а по положительным симметрическим суммам \(e_1,\dots,e_7\).
Для элементарного симметрического многочлена
$$E_m(b_1,\dots,b_7)=\sum_{1\le i_1<\cdots<i_m\le 7} b_{i_1}\cdots b_{i_m}$$
монотонность по положительным аргументам даёт
$$E_m(1,2,\dots,7)\le e_m < E_m(2,3,\dots,8).$$
После подстановки получаем целочисленный бокс
$$\begin{aligned} 28\le e_1\le 34,\qquad &322\le e_2\le 510,\qquad 1960\le e_3\le 4024,\\ 6769\le e_4\le 18423,\qquad &13132\le e_5\le 48859,\\ 13068\le e_6\le 69263,\qquad &5040\le e_7\le 40319. \end{aligned}$$
Уже эти границы отсеивают подавляющее большинство невозможных наборов.
Для целого \(k\in\{1,\dots,8\}\)
$$P(k)=\prod_{i=1}^7 (k-r_i).$$
Если \(P(k)\neq 0\), то отрицательных множителей ровно \(8-k\), поэтому необходимо условие
$$(-1)^k P(k)\ge 0 \qquad (1\le k\le 8).$$
В переменных \(e_1,\dots,e_7\) это аффинное неравенство
$$(-1)^k\left(k^7-e_1k^6+e_2k^5-e_3k^4+e_4k^3-e_5k^2+e_6k-e_7\right)\ge 0.$$
Если все восемь неравенств строгие, знаки на соседних целых точках чередуются, и теорема о промежуточном значении гарантирует один корень в каждом открытом интервале \((k,k+1)\). Поскольку степень равна \(7\), это исчерпывает все корни.
Равенство \(P(k)=0\) означает, что корень попал точно на целую границу. Тогда одного лишь знака недостаточно: нужно проверить, что график пересекает ось в правильном направлении, совместимом с интервалом \([k,k+1)\).
В окрестности простого корня \(k\)
$$P(t)\approx P'(k)(t-k),$$
поэтому допустимое направление задаётся условием
$$(-1)^{k+1}P'(k)>0 \qquad (1\le k\le 7).$$
При \(k=8\) равенство недопустимо, так как ни один корень не может иметь целую часть \(8\). Именно поэтому реализация отдельно проверяет только крайние значения итогового интервала.
Теперь имеются два типа ограничений:
$$\text{боксовые границы для } e_1,\dots,e_7,$$
и
$$8 \text{ аффинных знаковых ограничений из } P(1),P(2),\dots,P(8).$$
Все они линейны по переменным \(e_1,\dots,e_7\). Значит, допустимое множество представляет собой многогранную область внутри исходного бокса.
Реализация использует исключение Фурье-Моцкина, чтобы последовательно убрать более поздние коэффициенты. После такой предобработки, как только первые коэффициенты зафиксированы, для следующего коэффициента сразу получается гораздо более узкий целочисленный интервал.
Поэтому поиск не перебирает весь исходный бокс. Коэффициенты выбираются по порядку; на каждом шаге пересекаются статический интервал из шага 2 и проецированный линейный интервал, вытекающий из оставшихся знаковых ограничений; если пересечение пусто, ветвь сразу отсекается.
После фиксации \(e_1,\dots,e_6\) допустимые значения \(e_7\) образуют один целочисленный интервал \([L,R]\). Поскольку все ограничения линейны по \(e_7\), случаи равенства \(P(k)=0\) могут появиться только на концах этого интервала. Значит, проверять производную нужно только на границах.
Когда итоговый интервал признан допустимым, его вклад равен
$$\sum_{u=L}^{R}(e_1+\cdots+e_6+u)=(R-L+1)(e_1+\cdots+e_6)+\frac{(L+R)(R-L+1)}{2}.$$
Эта формула арифметической прогрессии избавляет от поэлементного перебора последнего уровня.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Они перебирают положительные симметрические суммы вместо знаковых коэффициентов, начинают с диапазонов, навязанных интервалами для корней, затем с помощью заранее спроецированных линейных ограничений сужают диапазон следующего коэффициента во время поиска в глубину и немедленно отбрасывают ветви с пустым интервалом. Для последнего коэффициента проверяются только граничные значения, при которых может возникнуть \(P(k)=0\), после чего вклад всего интервала добавляется одной закрытой формулой.
Полный перебор по всему коэффициентному боксу был бы астрономически дорогим. В худшем случае метод остаётся экспоненциальным по числу свободных коэффициентов, потому что это всё ещё задача поиска, но линейная проекция и агрессивное отсечение резко уменьшают фактическое число ветвей. Памяти требуется мало: несколько спроецированных линейных систем, текущий рекурсивный стек и накопленная сумма.
نبحث في كثيرات الحدود الأحادية من الدرجة \(7\)
$$P(t)=t^7+a_1t^6+a_2t^5+a_3t^4+a_4t^3+a_5t^2+a_6t+a_7$$
ذات المعاملات الصحيحة، بحيث تكون جميع الجذور حقيقية، وبعد ترتيبها \(r_1\le \cdots \le r_7\) تحقق
$$\lfloor r_i\rfloor=i \qquad (1\le i\le 7).$$
ولكل متجه معاملات صالح \(a=(a_1,\dots,a_7)\) نعرّف
$$S(a)=\sum_{i=1}^7 |a_i|.$$
والمطلوب هو جمع \(S(a)\) على جميع كثيرات الحدود الصالحة.
بما أن الجذور تقع في المجالات الموجبة \([1,2),[2,3),\dots,[7,8)\)، فيمكن كتابة
$$P(t)=\prod_{i=1}^7 (t-r_i)=t^7-e_1t^6+e_2t^5-e_3t^4+e_4t^3-e_5t^2+e_6t-e_7,$$
حيث يمثّل \(e_m\) المجموع التناظري الابتدائي من الرتبة \(m\) للجذور. لذلك
$$a_m=(-1)^m e_m \qquad (1\le m\le 7).$$
ولأن جميع الجذور موجبة، فإن كل \(e_m\) موجب أيضًا، ومن ثم تصبح الدالة الهدف
$$S(a)=e_1+e_2+\cdots+e_7.$$
إذًا البحث الفعلي ليس على معاملات موقعة اعتباطيًا، بل على المجاميع التناظرية الموجبة \(e_1,\dots,e_7\).
إذا رمزنا إلى كثير الحدود التناظري الابتدائي بـ
$$E_m(b_1,\dots,b_7)=\sum_{1\le i_1<\cdots<i_m\le 7} b_{i_1}\cdots b_{i_m},$$
فإن الرتابة على المدخلات الموجبة تعطي
$$E_m(1,2,\dots,7)\le e_m < E_m(2,3,\dots,8).$$
وبحساب الطرفين نحصل على صندوق البحث الصحيح
$$\begin{aligned} 28\le e_1\le 34,\qquad &322\le e_2\le 510,\qquad 1960\le e_3\le 4024,\\ 6769\le e_4\le 18423,\qquad &13132\le e_5\le 48859,\\ 13068\le e_6\le 69263,\qquad &5040\le e_7\le 40319. \end{aligned}$$
هذه الحدود وحدها تستبعد عددًا هائلًا من المرشحين غير الممكنين.
لكل عدد صحيح \(k\in\{1,\dots,8\}\) يكون
$$P(k)=\prod_{i=1}^7 (k-r_i).$$
وعندما لا يكون \(P(k)=0\)، فإن عدد العوامل السالبة يساوي تمامًا \(8-k\)، ولذلك يجب أن يتحقق
$$(-1)^k P(k)\ge 0 \qquad (1\le k\le 8).$$
وبالكتابة بدلالة \(e_1,\dots,e_7\) نحصل على المتباينة الخطية
$$(-1)^k\left(k^7-e_1k^6+e_2k^5-e_3k^4+e_4k^3-e_5k^2+e_6k-e_7\right)\ge 0.$$
إذا كانت هذه المتباينات الثماني صارمة كلها، فإن الإشارة تتناوب بين الأعداد الصحيحة المتتالية، وعندئذ تضمن مبرهنة القيمة المتوسطة وجود جذر واحد في كل مجال مفتوح \((k,k+1)\). وبما أن الدرجة تساوي \(7\)، فهذا يفسّر جميع الجذور.
المساواة \(P(k)=0\) تعني أن جذرًا يقع تمامًا على حد صحيح. هنا لا تكفي إشارة \(P(k)\) وحدها، بل يجب التأكد من أن المنحنى يقطع المحور بالاتجاه الموافق للمجال \([k,k+1)\).
بالقرب من جذر بسيط عند \(k\) لدينا تقريبًا
$$P(t)\approx P'(k)(t-k),$$
ومن ثم يكون شرط الاتجاه الصحيح هو
$$(-1)^{k+1}P'(k)>0 \qquad (1\le k\le 7).$$
أما عند \(k=8\) فالمساواة مرفوضة تمامًا، لأن أي جذر ذي جزء صحيح \(8\) غير مسموح. وهذا يفسر لماذا يكتفي التنفيذ في المرحلة الأخيرة بفحص أطراف المجال فقط.
لدينا الآن نوعان من القيود: حدود صندوقية للمتغيرات \(e_1,\dots,e_7\)، وثمانية قيود خطية مشتقة من القيم \(P(1),P(2),\dots,P(8)\).
جميع هذه القيود خطية في المتغيرات \(e_1,\dots,e_7\)، ولذلك تكون المجموعة المقبولة منطقة متعددة الوجوه داخل صندوق المعاملات الأصلي.
يستخدم التنفيذ حذف فورييه-موتزكين لإسقاط المعاملات الأخيرة واحدًا بعد واحد. وبعد هذه التهيئة، يصبح تثبيت أول عدة معاملات كافيًا لإنتاج حد أدنى وحد أعلى أضيق بكثير للمعامل التالي.
لذلك لا يسير البحث داخل الصندوق الخام كله. بل يختار المعاملات بالتتابع، ويقاطع المجال الثابت القادم من الخطوة 2 مع المجال الخطي المسقَط من القيود الباقية، ويقصّ الفرع فورًا إذا أصبح التقاطع فارغًا.
بعد تثبيت \(e_1,\dots,e_6\)، تشكل القيم الصالحة لـ \(e_7\) مجالًا صحيحًا واحدًا \([L,R]\). وبما أن جميع القيود خطية في \(e_7\)، فإن حالات المساواة \(P(k)=0\) لا يمكن أن تظهر إلا عند طرفي هذا المجال. لذلك يكفي اختبار الطرفين بشرط المشتقة في الخطوة 4.
وعندما يثبت أن المجال صالح، تكون مساهمته الكلية في الدالة الهدف
$$\sum_{u=L}^{R}(e_1+\cdots+e_6+u)=(R-L+1)(e_1+\cdots+e_6)+\frac{(L+R)(R-L+1)}{2}.$$
هذه صيغة مجموع متتالية حسابية، وهي التي تتيح تجميع المجال الأخير دفعة واحدة بدل تعداد كل قيمة على حدة.
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. فهي تعدّد المجاميع التناظرية الموجبة بدل المعاملات ذات الإشارات، وتبدأ من الحدود التي تفرضها مجالات الجذور، ثم تستخدم قيودًا خطية مسقطة مسبقًا لتضييق مجال المعامل التالي أثناء بحث عمقي، وتلغي الفرع بمجرد أن يصبح المجال فارغًا. أما في المعامل الأخير، فلا تُفحص إلا القيم الحدية التي قد تجعل بعض \(P(k)\) مساويًا للصفر، ثم تُضاف مساهمة المجال كله بالصيغة المغلقة أعلاه.
الفحص الشامل على صندوق المعاملات كله سيكون فلكي الحجم. المنهج المنفذ يبقى أسيًا في أسوأ الأحوال بالنسبة لعدد المعاملات الحرة، لأن المسألة ما تزال مسألة بحث، لكن الإسقاط الخطي وتقليم المجالات يخفضان عامل التفرع بصورة كبيرة جدًا. أما الذاكرة المطلوبة فتبقى صغيرة: بضع منظومات خطية مسقطة، ومكدس الاستدعاء الحالي، والمجموع التراكمي.