Let the three fruit quantities be positive integers \(a,b,c\). In the published statement, the second and third fractions share the same denominator \(a+c\), so the condition is
$$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+c}=4,$$
which immediately simplifies to
$$\frac{a}{b+c}+\frac{b+c}{a+c}=4.$$
For every solution with perimeter \(p=a+b+c\le 10^7\), we must add \(p\) to the final total. A direct search over all triples would be hopeless, so the real task is to classify the integer solutions in a structured way.
The implementations work by identifying primitive solutions, turning them into explicit parameter families, and then summing all multiples of each primitive perimeter at once.
Multiplying by \((a+c)(b+c)\) removes the denominators:
$$a(a+c)+(b+c)^2=4(a+c)(b+c).$$
After expansion this becomes the quadratic Diophantine equation
$$a^2-4ab-3ac+b^2-2bc-3c^2=0.$$
Now treat it as a quadratic in \(b\):
$$b^2-(4a+2c)b+(a^2-3ac-3c^2)=0.$$
Its discriminant is
$$\Delta=(4a+2c)^2-4(a^2-3ac-3c^2)=4(a+c)(3a+4c).$$
Therefore any integer solution must satisfy
$$b=2a+c\pm \sqrt{(a+c)(3a+4c)},$$
so \((a+c)(3a+4c)\) has to be a perfect square.
After clearing denominators, the equation is homogeneous of degree 2. If \((a,b,c)\) is a solution, then so is \(k(a,b,c)\) for every positive integer \(k\). That means every solution is a multiple of a primitive one with \(\gcd(a,b,c)=1\).
For a primitive triple we only need one coprimality statement: \(\gcd(a,c)=1\). Indeed, if some \(d\) divides both \(a\) and \(c\), then in
$$a^2-4ab-3ac+b^2-2bc-3c^2=0$$
every term except \(b^2\) is divisible by \(d\), hence \(d\mid b^2\), so \(d\mid b\). That would force \(d\mid \gcd(a,b,c)\), contradicting primitiveness.
Now compute
$$\gcd(a+c,3a+4c)=\gcd(a+c,\;3a+4c-3(a+c))=\gcd(a+c,c)=\gcd(a,c)=1.$$
So the two factors in \((a+c)(3a+4c)\) are coprime.
We already know that \((a+c)(3a+4c)\) is a square, and the previous step shows the two factors are coprime. By unique factorization, each factor must therefore be a square on its own:
$$a+c=u^2,\qquad 3a+4c=v^2,\qquad \gcd(u,v)=1.$$
Solving this linear system gives
$$a=4u^2-v^2,\qquad c=v^2-3u^2.$$
Substituting back into the quadratic formula for \(b\) yields
$$b=5u^2-v^2\pm uv.$$
Thus every primitive solution has the form
$$\bigl(a,b,c\bigr)=\bigl(4u^2-v^2,\;5u^2-v^2\pm uv,\;v^2-3u^2\bigr),\qquad \gcd(u,v)=1.$$
Since \(a\gt 0\) and \(c\gt 0\), we obtain
$$v^2\lt 4u^2,\qquad v^2\gt 3u^2,$$
so the valid region is the narrow strip
$$\sqrt{3}\,u \lt v \lt 2u.$$
The primitive perimeter is
$$p_\pm=a+b+c=6u^2-v^2\pm uv.$$
These expressions factor neatly:
$$p_-=(2u-v)(3u+v),\qquad p_+=(2u+v)(3u-v).$$
Those two factorizations are the bridge from the theoretical parametrization to the compact formulas used in the implementations.
Because \(\gcd(u,v)=1\), the pair cannot be both even. The first implemented family covers the case where \(u\) and \(v\) have opposite parity.
For the perimeter \(p_-\), set
$$m=u,\qquad n=2u-v,$$
so \(v=2m-n\). Then
$$a=4mn-n^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
and
$$p_-=n(5m-n).$$
For the perimeter \(p_+\), set
$$m=2u+v,\qquad n=u,$$
so \(v=m-2n\). This gives
$$a=4mn-m^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
and
$$p_+=m(5n-m).$$
In both branches we get \(\gcd(m,n)=1\) and \(m-n\) odd. The positivity conditions on \(b\) and \(c\) imply
$$2+\sqrt{3}\lt \frac{m}{n}\lt \frac{5+\sqrt{21}}{2}\lt 5,$$
which explains why the implementations can safely scan only up to \(m\le 5n\) in this family.
The only remaining primitive possibility is that both \(u\) and \(v\) are odd.
For the perimeter \(p_-\), define
$$m=\frac{3u-v}{2},\qquad n=\frac{v-u}{2},$$
so equivalently
$$u=m+n,\qquad v=m+3n.$$
Then
$$a=3m^2+2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
and
$$p_-=4m^2+2mn-6n^2.$$
For the perimeter \(p_+\), define
$$m=\frac{3u+v}{2},\qquad n=\frac{u+v}{2},$$
so equivalently
$$u=m-n,\qquad v=3n-m.$$
This yields
$$a=3m^2-2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
and
$$p_+=4m^2-2mn-6n^2.$$
Again \(\gcd(m,n)=1\) and \(m-n\) is odd. Here the common positivity conditions on \(b\) and \(c\) give
$$\sqrt{\frac{7}{3}}\lt \frac{m}{n}\lt \sqrt{3}\lt 2,$$
so the scan only needs \(m\le 2n\) in this second family.
Take the smallest primitive pair that works: \(u=4\), \(v=7\). Then
$$a=4\cdot 4^2-7^2=15,\qquad c=7^2-3\cdot 4^2=1.$$
For \(b\) we obtain
$$b=5\cdot 4^2-7^2\pm 4\cdot 7=31\pm 28\in\{3,59\}.$$
So the two primitive solutions are \((15,3,1)\) with perimeter \(19\), and \((15,59,1)\) with perimeter \(75\). If the search bound were \(N=50\), only the first triple and its double \((30,6,2)\) would contribute, producing
$$19+38=57.$$
This is exactly the small checkpoint reproduced by the implementations.
For any primitive solution, \(u^2=a+c\lt a+b+c=p\le N\). So the fundamental parameters are only \(O(\sqrt{N})\), and the linear substitutions above keep the implementation parameters \(m,n\) in the same range.
The C++, Python, and Java implementations loop over positive \(n\), then scan \(m\) over the two ranges implied by the derivation: up to \(5n\) for the opposite-parity family and up to \(2n\) for the odd-odd family. They enforce \(\gcd(m,n)=1\) and opposite parity, compute the corresponding formulas for \(a\), \(b\), \(c\), and discard any candidate with a nonpositive component.
If a primitive triple has perimeter \(p\), then every multiple \(kp\) is also valid as long as \(kp\le N\). With
$$q=\left\lfloor\frac{N}{p}\right\rfloor,$$
the total contribution of that primitive triple is
$$p+2p+\cdots+qp=p\frac{q(q+1)}{2}.$$
That closed form is why the implementations never need to generate each multiple explicitly. They also include a small brute-force verifier for low bounds, and the C++ implementation can optionally split the outer parameter range across several threads.
Let \(N\) be the perimeter limit. The outer parameter only grows like \(\sqrt{N}\). Across all \(n\), the first family examines \(O\!\left(\sum n\right)=O(N)\) candidate pairs \((m,n)\), and the second family does the same. Each candidate uses only fixed-width integer arithmetic plus one gcd test, so in ordinary RAM-model terms the running time is \(O(N)\).
Memory usage is \(O(1)\) aside from a few counters and, in the multithreaded C++ version, a small array of partial sums. For \(N=10^7\) this leaves only a few million arithmetic checks, which is easily manageable.
Bezeichne die drei Fruchtmengen mit positiven ganzen Zahlen \(a,b,c\). In der veröffentlichten Fassung besitzen der zweite und der dritte Bruch denselben Nenner \(a+c\), also lautet die Bedingung
$$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+c}=4,$$
und damit sofort
$$\frac{a}{b+c}+\frac{b+c}{a+c}=4.$$
Für jede Lösung mit Umfang \(p=a+b+c\le 10^7\) soll \(p\) zur Endsumme addiert werden. Ein direkter Durchlauf über alle Tripel wäre viel zu groß; deshalb muss man die ganzzahligen Lösungen parametrisieren.
Die Implementierungen bestimmen zuerst die primitiven Lösungen, schreiben diese als explizite Familien und summieren dann die Vielfachen jedes primitiven Umfangs in geschlossener Form.
Durch Multiplikation mit \((a+c)(b+c)\) verschwinden die Nenner:
$$a(a+c)+(b+c)^2=4(a+c)(b+c).$$
Ausmultipliziert ergibt das die quadratische diophantische Gleichung
$$a^2-4ab-3ac+b^2-2bc-3c^2=0.$$
Betrachtet man sie als quadratische Gleichung in \(b\), so erhält man
$$b^2-(4a+2c)b+(a^2-3ac-3c^2)=0.$$
Die Diskriminante ist
$$\Delta=(4a+2c)^2-4(a^2-3ac-3c^2)=4(a+c)(3a+4c).$$
Also muss jede ganzzahlige Lösung die Form
$$b=2a+c\pm \sqrt{(a+c)(3a+4c)}$$
haben, und damit ist \((a+c)(3a+4c)\) ein Quadrat.
Nach dem Beseitigen der Nenner ist die Gleichung homogen vom Grad 2. Wenn \((a,b,c)\) eine Lösung ist, dann ist auch \(k(a,b,c)\) für jedes positive \(k\) eine Lösung. Daher genügt es, die primitiven Tripel mit \(\gcd(a,b,c)=1\) zu klassifizieren.
Für ein primitives Tripel brauchen wir nur \(\gcd(a,c)=1\). Denn falls ein \(d\) sowohl \(a\) als auch \(c\) teilt, dann sind in
$$a^2-4ab-3ac+b^2-2bc-3c^2=0$$
alle Terme außer \(b^2\) durch \(d\) teilbar, also gilt \(d\mid b^2\) und damit \(d\mid b\). Das widerspricht der Primitivität.
Nun folgt
$$\gcd(a+c,3a+4c)=\gcd(a+c,\;3a+4c-3(a+c))=\gcd(a+c,c)=\gcd(a,c)=1.$$
Die beiden Faktoren von \((a+c)(3a+4c)\) sind also teilerfremd.
Wir wissen bereits, dass \((a+c)(3a+4c)\) ein Quadrat ist. Weil die beiden Faktoren teilerfremd sind, muss wegen der eindeutigen Primfaktorzerlegung jeder Faktor selbst ein Quadrat sein:
$$a+c=u^2,\qquad 3a+4c=v^2,\qquad \gcd(u,v)=1.$$
Das lineare Gleichungssystem liefert
$$a=4u^2-v^2,\qquad c=v^2-3u^2.$$
Zurück in der quadratischen Formel für \(b\) folgt
$$b=5u^2-v^2\pm uv.$$
Damit besitzt jedes primitive Tripel die Gestalt
$$\bigl(a,b,c\bigr)=\bigl(4u^2-v^2,\;5u^2-v^2\pm uv,\;v^2-3u^2\bigr),\qquad \gcd(u,v)=1.$$
Aus \(a\gt 0\) und \(c\gt 0\) folgt
$$v^2\lt 4u^2,\qquad v^2\gt 3u^2,$$
also der schmale Bereich
$$\sqrt{3}\,u \lt v \lt 2u.$$
Der primitive Umfang ist
$$p_\pm=a+b+c=6u^2-v^2\pm uv.$$
Diese beiden Ausdrücke zerfallen in lineare Faktoren:
$$p_-=(2u-v)(3u+v),\qquad p_+=(2u+v)(3u-v).$$
Genau diese Faktorisierungen führen zu den kompakten Parametrisierungen, die der Code später durchsucht.
Da \(\gcd(u,v)=1\) gilt, können \(u\) und \(v\) nicht beide gerade sein. Die erste implementierte Familie behandelt den Fall entgegengesetzter Parität.
Für den Umfang \(p_-\) setzen wir
$$m=u,\qquad n=2u-v,$$
also \(v=2m-n\). Dann erhält man
$$a=4mn-n^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
sowie
$$p_-=n(5m-n).$$
Für den Umfang \(p_+\) setzen wir
$$m=2u+v,\qquad n=u,$$
also \(v=m-2n\). Damit folgt
$$a=4mn-m^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
und
$$p_+=m(5n-m).$$
In beiden Zweigen gilt \(\gcd(m,n)=1\) und \(m-n\) ist ungerade. Aus den Positivitätsbedingungen für \(b\) und \(c\) folgt
$$2+\sqrt{3}\lt \frac{m}{n}\lt \frac{5+\sqrt{21}}{2}\lt 5,$$
weshalb der Suchbereich \(m\le 5n\) vollständig ausreicht.
Die einzige verbleibende primitive Möglichkeit ist, dass \(u\) und \(v\) beide ungerade sind.
Für den Umfang \(p_-\) definieren wir
$$m=\frac{3u-v}{2},\qquad n=\frac{v-u}{2},$$
also äquivalent
$$u=m+n,\qquad v=m+3n.$$
Dann ergibt sich
$$a=3m^2+2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
und
$$p_-=4m^2+2mn-6n^2.$$
Für den Umfang \(p_+\) definieren wir
$$m=\frac{3u+v}{2},\qquad n=\frac{u+v}{2},$$
also äquivalent
$$u=m-n,\qquad v=3n-m.$$
Damit erhält man
$$a=3m^2-2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
sowie
$$p_+=4m^2-2mn-6n^2.$$
Wieder gilt \(\gcd(m,n)=1\) und \(m-n\) ist ungerade. Die gemeinsamen Positivitätsbedingungen für \(b\) und \(c\) liefern
$$\sqrt{\frac{7}{3}}\lt \frac{m}{n}\lt \sqrt{3}\lt 2,$$
also genügt hier der Bereich \(m\le 2n\).
Nimm das kleinste funktionierende primitive Paar \(u=4\), \(v=7\). Dann gilt
$$a=4\cdot 4^2-7^2=15,\qquad c=7^2-3\cdot 4^2=1.$$
Für \(b\) erhält man
$$b=5\cdot 4^2-7^2\pm 4\cdot 7=31\pm 28\in\{3,59\}.$$
Die beiden primitiven Lösungen sind also \((15,3,1)\) mit Umfang \(19\) und \((15,59,1)\) mit Umfang \(75\). Bei einer Schranke \(N=50\) tragen nur das erste Tripel und sein Doppel \((30,6,2)\) bei, also insgesamt
$$19+38=57.$$
Genau dieser kleine Kontrollwert wird von den Implementierungen reproduziert.
Für jede primitive Lösung gilt \(u^2=a+c\lt a+b+c=p\le N\). Daher liegen die fundamentalen Parameter nur in der Größenordnung \(\sqrt{N}\), und die linearen Transformationen oben halten auch die Implementierungsparameter \(m,n\) in demselben Bereich.
Die C++-, Python- und Java-Implementierungen laufen über positive \(n\) und durchsuchen dann \(m\) genau in den beiden aus der Herleitung kommenden Bereichen: bis \(5n\) für die Familie mit entgegengesetzter Parität und bis \(2n\) für die ungerade Familie. Dabei werden \(\gcd(m,n)=1\) und entgegengesetzte Parität erzwungen, die Formeln für \(a,b,c\) ausgewertet und alle Kandidaten mit einer nichtpositiven Komponente verworfen.
Hat ein primitives Tripel den Umfang \(p\), dann ist auch jedes Vielfache \(kp\) gültig, solange \(kp\le N\). Mit
$$q=\left\lfloor\frac{N}{p}\right\rfloor$$
ist der Gesamtbeitrag dieses primitiven Tripels
$$p+2p+\cdots+qp=p\frac{q(q+1)}{2}.$$
Deshalb muss keine Implementierung die einzelnen Vielfachen explizit erzeugen. Zusätzlich gibt es einen kleinen Brute-Force-Abgleich für niedrige Schranken; die C++-Implementierung kann den äußeren Parameterbereich außerdem optional auf mehrere Threads aufteilen.
Sei \(N\) die Umfangsschranke. Der äußere Parameter wächst nur wie \(\sqrt{N}\). Über alle \(n\) hinweg untersucht die erste Familie \(O\!\left(\sum n\right)=O(N)\) Kandidatenpaare \((m,n)\), und die zweite Familie ebenfalls. Jeder Kandidat benötigt nur Ganzzahlarithmetik fester Breite plus einen ggT-Test, also ist die Laufzeit im üblichen RAM-Modell \(O(N)\).
Der Speicherbedarf ist \(O(1)\), abgesehen von wenigen Zählern und im mehrfädigen C++-Fall einem kleinen Feld partieller Summen. Für \(N=10^7\) bleiben damit nur einige Millionen arithmetische Prüfungen.
Üç meyve miktarını pozitif tamsayılar \(a,b,c\) ile gösterelim. Yayınlanan metinde ikinci ve üçüncü kesrin paydası aynıdır; ikisi de \(a+c\) gelir. Dolayısıyla koşul
$$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+c}=4$$
olur ve bu da hemen
$$\frac{a}{b+c}+\frac{b+c}{a+c}=4$$
şeklinde sadeleşir. \(p=a+b+c\le 10^7\) olan her çözüm için çevre \(p\) sonuca eklenmelidir. Bütün üçlüleri doğrudan taramak imkansız olduğu için asıl iş, çözümleri yapısal olarak sınıflandırmaktır.
Uygulamalar önce primitive çözümleri ayıklar, sonra bunları açık parametre ailelerine dönüştürür ve her primitive çevrenin tüm katlarını tek formülle toplar.
\((a+c)(b+c)\) ile çarpınca paydalar kaybolur:
$$a(a+c)+(b+c)^2=4(a+c)(b+c).$$
Açınca şu ikinci dereceden Diophantine denklem elde edilir:
$$a^2-4ab-3ac+b^2-2bc-3c^2=0.$$
Bunu \(b\) açısından ikinci dereceden denklem olarak okursak
$$b^2-(4a+2c)b+(a^2-3ac-3c^2)=0$$
olur. Diskriminant
$$\Delta=(4a+2c)^2-4(a^2-3ac-3c^2)=4(a+c)(3a+4c)$$
olduğundan, her tam sayı çözüm için
$$b=2a+c\pm \sqrt{(a+c)(3a+4c)}$$
yazılabilmelidir. Yani \((a+c)(3a+4c)\) mutlaka tam kare olmalıdır.
Paydalar kaldırıldıktan sonra denklem derece 2 homojendir. \((a,b,c)\) bir çözümse, her pozitif \(k\) için \(k(a,b,c)\) de çözümdür. Bu yüzden her çözüm, \(\gcd(a,b,c)=1\) olan bir primitive çözümün katıdır.
Primitive üçlü için gereken ana gözlem \(\gcd(a,c)=1\) olmasıdır. Gerçekten bir \(d\), hem \(a\)'yı hem \(c\)'yi bölüyorsa
$$a^2-4ab-3ac+b^2-2bc-3c^2=0$$
denkleminde \(b^2\) dışındaki her terim \(d\)'ye bölünür; dolayısıyla \(d\mid b^2\), yani \(d\mid b\). Bu da \(\gcd(a,b,c)=1\) ile çelişir.
Böylece
$$\gcd(a+c,3a+4c)=\gcd(a+c,\;3a+4c-3(a+c))=\gcd(a+c,c)=\gcd(a,c)=1$$
elde edilir. Demek ki \((a+c)(3a+4c)\) çarpımındaki iki çarpan aralarında asaldır.
\((a+c)(3a+4c)\)'nin tam kare olduğunu biliyoruz. Çarpanlar aralarında asal olduğundan, tekil asal çarpanlara ayırma gereği her biri ayrı ayrı tam kare olmalıdır:
$$a+c=u^2,\qquad 3a+4c=v^2,\qquad \gcd(u,v)=1.$$
Bu lineer sistemi çözersek
$$a=4u^2-v^2,\qquad c=v^2-3u^2$$
bulunur. Sonra \(b\) için
$$b=5u^2-v^2\pm uv$$
elde edilir. Yani her primitive çözüm
$$\bigl(a,b,c\bigr)=\bigl(4u^2-v^2,\;5u^2-v^2\pm uv,\;v^2-3u^2\bigr),\qquad \gcd(u,v)=1$$
biçimindedir.
\(a\gt 0\) ve \(c\gt 0\) koşullarından
$$v^2\lt 4u^2,\qquad v^2\gt 3u^2$$
çıkar; yani geçerli bölge
$$\sqrt{3}\,u \lt v \lt 2u$$
şerididir. Primitive çevre ise
$$p_\pm=a+b+c=6u^2-v^2\pm uv$$
olur ve şu şekilde çarpanlara ayrılır:
$$p_-=(2u-v)(3u+v),\qquad p_+=(2u+v)(3u-v).$$
Uygulamalardaki kompakt tarama formülleri tam olarak bu iki çarpanlaşmadan doğar.
\(\gcd(u,v)=1\) olduğu için \(u\) ve \(v\) aynı anda çift olamaz. Uygulamanın ilk ailesi, pariteleri farklı olan durumu kapsar.
\(p_-\) için
$$m=u,\qquad n=2u-v$$
seçelim; böylece \(v=2m-n\) olur. O zaman
$$a=4mn-n^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
ve
$$p_-=n(5m-n)$$
elde edilir. \(p_+\) için bu kez
$$m=2u+v,\qquad n=u$$
alınır; yani \(v=m-2n\). Bu da
$$a=4mn-m^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
ile
$$p_+=m(5n-m)$$
sonucunu verir. Her iki kolda da \(\gcd(m,n)=1\) ve \(m-n\) tektir. Ayrıca \(b\gt 0\) ve \(c\gt 0\) koşulları
$$2+\sqrt{3}\lt \frac{m}{n}\lt \frac{5+\sqrt{21}}{2}\lt 5$$
eşitsizliğini verdiği için taramanın \(m\le 5n\) ile sınırlandırılması yeterlidir.
Kalan tek primitive olasılık, \(u\) ve \(v\)'nin ikisinin de tek olmasıdır.
\(p_-\) için
$$m=\frac{3u-v}{2},\qquad n=\frac{v-u}{2}$$
tanımlayalım; eşdeğer olarak
$$u=m+n,\qquad v=m+3n.$$
Buradan
$$a=3m^2+2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
ve
$$p_-=4m^2+2mn-6n^2$$
gelir. \(p_+\) için ise
$$m=\frac{3u+v}{2},\qquad n=\frac{u+v}{2}$$
tanımıyla
$$u=m-n,\qquad v=3n-m$$
yazılır ve
$$a=3m^2-2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
ile
$$p_+=4m^2-2mn-6n^2$$
bulunur. Yine \(\gcd(m,n)=1\) ve \(m-n\) tektir. Bu ailede \(b\gt 0\) ile \(c\gt 0\) birlikte
$$\sqrt{\frac{7}{3}}\lt \frac{m}{n}\lt \sqrt{3}\lt 2$$
verdiğinden tarama için \(m\le 2n\) yeterlidir.
En küçük uygun primitive çift \(u=4\), \(v=7\)'dir. O zaman
$$a=4\cdot 4^2-7^2=15,\qquad c=7^2-3\cdot 4^2=1$$
olur. \(b\) için
$$b=5\cdot 4^2-7^2\pm 4\cdot 7=31\pm 28\in\{3,59\}$$
çıkar. Böylece iki primitive çözüm \((15,3,1)\) ve \((15,59,1)\) olur; çevreleri sırasıyla \(19\) ve \(75\)'tir. \(N=50\) olsaydı yalnızca ilk çözüm ve onun iki katı \((30,6,2)\) katkı verirdi:
$$19+38=57.$$
Uygulamaların küçük doğrulama noktasında ürettiği değer tam olarak budur.
Her primitive çözüm için \(u^2=a+c\lt a+b+c=p\le N\) olduğundan temel parametreler yalnızca \(\sqrt{N}\) mertebesindedir. Yukarıdaki lineer dönüşümler de uygulamadaki \(m,n\) parametrelerini aynı ölçek içinde tutar.
C++, Python ve Java uygulamaları pozitif \(n\) üzerinden gider; ardından \(m\)'yi türetimde çıkan iki aralıkta tarar: farklı pariteli aile için \(5n\)'e kadar, tek-tek aile için \(2n\)'ye kadar. Her adayda \(\gcd(m,n)=1\) ve ters parite şartı kontrol edilir, ilgili \(a,b,c\) formülleri hesaplanır ve herhangi bir bileşeni pozitif olmayan adaylar atılır.
Primitive bir üçlünün çevresi \(p\) ise, \(kp\le N\) olduğu sürece her \(kp\) de geçerlidir. Bu durumda
$$q=\left\lfloor\frac{N}{p}\right\rfloor$$
olmak üzere toplam katkı
$$p+2p+\cdots+qp=p\frac{q(q+1)}{2}$$
şeklindedir. Böylece uygulamalar her katı tek tek üretmez. Düşük sınırlar için küçük bir brute-force doğrulaması da bulunur; C++ uygulaması isterse dış parametre aralığını birkaç iş parçacığına da bölebilir.
Çevre sınırı \(N\) olsun. Dış parametre yalnızca \(\sqrt{N}\) gibi büyür. Tüm \(n\) değerleri boyunca ilk aile \(O\!\left(\sum n\right)=O(N)\) aday çifti \((m,n)\) inceler; ikinci aile de aynı mertebededir. Her adayda sabit genişlikte tamsayı aritmetiği ve bir EBOB testi vardır, dolayısıyla alışılmış RAM modelinde toplam süre \(O(N)\) olur.
Bellek kullanımı birkaç sayaç dışında \(O(1)\)'dir; çok iş parçacıklı C++ sürümünde buna küçük bir kısmi toplamlar dizisi eklenir. \(N=10^7\) için bu, yalnızca birkaç milyon aritmetik denetim anlamına gelir.
Denotemos las tres cantidades de fruta por enteros positivos \(a,b,c\). En la version publicada, la segunda y la tercera fraccion comparten el mismo denominador \(a+c\), de modo que la condicion es
$$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+c}=4,$$
y por tanto se simplifica a
$$\frac{a}{b+c}+\frac{b+c}{a+c}=4.$$
Para cada solucion con perimetro \(p=a+b+c\le 10^7\), hay que sumar \(p\) al total final. Recorrer todas las ternas directamente seria inviable; la clave es describir las soluciones enteras mediante una parametrizacion.
Las implementaciones identifican primero las soluciones primitivas, las convierten en familias explicitas y luego suman de una sola vez todos los multiplos de cada perimetro primitivo.
Multiplicando por \((a+c)(b+c)\) desaparecen los denominadores:
$$a(a+c)+(b+c)^2=4(a+c)(b+c).$$
Al expandir se obtiene la ecuacion diofantica cuadratica
$$a^2-4ab-3ac+b^2-2bc-3c^2=0.$$
Vista como ecuacion cuadratica en \(b\), queda
$$b^2-(4a+2c)b+(a^2-3ac-3c^2)=0.$$
Su discriminante es
$$\Delta=(4a+2c)^2-4(a^2-3ac-3c^2)=4(a+c)(3a+4c).$$
Por lo tanto, toda solucion entera debe satisfacer
$$b=2a+c\pm \sqrt{(a+c)(3a+4c)},$$
de donde se deduce que \((a+c)(3a+4c)\) tiene que ser un cuadrado perfecto.
Tras eliminar denominadores, la ecuacion es homogenea de grado 2. Si \((a,b,c)\) es una solucion, entonces \(k(a,b,c)\) tambien lo es para cualquier entero positivo \(k\). Asi, toda solucion es un multiplo de una terna primitiva con \(\gcd(a,b,c)=1\).
Para una terna primitiva basta demostrar \(\gcd(a,c)=1\). En efecto, si un \(d\) divide a la vez a \(a\) y a \(c\), entonces en
$$a^2-4ab-3ac+b^2-2bc-3c^2=0$$
todos los terminos salvo \(b^2\) son divisibles por \(d\), luego \(d\mid b^2\) y por tanto \(d\mid b\). Eso contradice la primitividad.
Ahora
$$\gcd(a+c,3a+4c)=\gcd(a+c,\;3a+4c-3(a+c))=\gcd(a+c,c)=\gcd(a,c)=1,$$
asi que los dos factores de \((a+c)(3a+4c)\) son coprimos.
Ya sabemos que \((a+c)(3a+4c)\) es un cuadrado perfecto. Como los dos factores son coprimos, la factorizacion unica obliga a que cada uno sea cuadrado por separado:
$$a+c=u^2,\qquad 3a+4c=v^2,\qquad \gcd(u,v)=1.$$
Al resolver el sistema lineal se obtiene
$$a=4u^2-v^2,\qquad c=v^2-3u^2.$$
Al sustituir de nuevo en la formula cuadratica para \(b\), resulta
$$b=5u^2-v^2\pm uv.$$
Por tanto, toda solucion primitiva tiene la forma
$$\bigl(a,b,c\bigr)=\bigl(4u^2-v^2,\;5u^2-v^2\pm uv,\;v^2-3u^2\bigr),\qquad \gcd(u,v)=1.$$
Las condiciones \(a\gt 0\) y \(c\gt 0\) implican
$$v^2\lt 4u^2,\qquad v^2\gt 3u^2,$$
es decir, la franja
$$\sqrt{3}\,u \lt v \lt 2u.$$
El perimetro primitivo vale
$$p_\pm=a+b+c=6u^2-v^2\pm uv,$$
y se factoriza como
$$p_-=(2u-v)(3u+v),\qquad p_+=(2u+v)(3u-v).$$
Esas dos factorizaciones son exactamente las que producen las formulas compactas que luego recorre la implementacion.
Como \(\gcd(u,v)=1\), no pueden ser ambos pares. La primera familia implementada cubre el caso en que tienen paridad opuesta.
Para el perimetro \(p_-\), tomamos
$$m=u,\qquad n=2u-v,$$
de modo que \(v=2m-n\). Entonces
$$a=4mn-n^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
y
$$p_-=n(5m-n).$$
Para el perimetro \(p_+\), tomamos
$$m=2u+v,\qquad n=u,$$
de manera que \(v=m-2n\). Esto produce
$$a=4mn-m^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
y
$$p_+=m(5n-m).$$
En ambas ramas se cumple \(\gcd(m,n)=1\) y \(m-n\) es impar. Ademas, las desigualdades \(b\gt 0\) y \(c\gt 0\) implican
$$2+\sqrt{3}\lt \frac{m}{n}\lt \frac{5+\sqrt{21}}{2}\lt 5,$$
lo que explica por que basta con explorar \(m\le 5n\) en esta familia.
La unica posibilidad primitiva restante es que \(u\) y \(v\) sean ambos impares.
Para el perimetro \(p_-\), definimos
$$m=\frac{3u-v}{2},\qquad n=\frac{v-u}{2},$$
equivalentemente
$$u=m+n,\qquad v=m+3n.$$
Con ello se obtiene
$$a=3m^2+2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
y
$$p_-=4m^2+2mn-6n^2.$$
Para el perimetro \(p_+\), definimos
$$m=\frac{3u+v}{2},\qquad n=\frac{u+v}{2},$$
equivalentemente
$$u=m-n,\qquad v=3n-m.$$
Entonces
$$a=3m^2-2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
y
$$p_+=4m^2-2mn-6n^2.$$
De nuevo \(\gcd(m,n)=1\) y \(m-n\) es impar. Aqui las condiciones comunes \(b\gt 0\) y \(c\gt 0\) dan
$$\sqrt{\frac{7}{3}}\lt \frac{m}{n}\lt \sqrt{3}\lt 2,$$
de modo que basta el limite \(m\le 2n\).
Tomemos el menor par primitivo que funciona: \(u=4\), \(v=7\). Entonces
$$a=4\cdot 4^2-7^2=15,\qquad c=7^2-3\cdot 4^2=1.$$
Para \(b\) obtenemos
$$b=5\cdot 4^2-7^2\pm 4\cdot 7=31\pm 28\in\{3,59\}.$$
Las dos soluciones primitivas son \((15,3,1)\), con perimetro \(19\), y \((15,59,1)\), con perimetro \(75\). Si el limite fuera \(N=50\), solo contribuirian la primera y su doble \((30,6,2)\), con total
$$19+38=57.$$
Ese es exactamente el pequeno punto de control que reproducen las implementaciones.
Para cualquier solucion primitiva se tiene \(u^2=a+c\lt a+b+c=p\le N\). Por eso los parametros fundamentales solo llegan a escala \(\sqrt{N}\), y las sustituciones lineales anteriores mantienen tambien a \(m\) y \(n\) en ese mismo orden.
Las implementaciones en C++, Python y Java recorren \(n\) positivo y luego examinan \(m\) en los dos intervalos deducidos de la teoria: hasta \(5n\) para la familia de paridad opuesta y hasta \(2n\) para la familia impar-impar. Imponen \(\gcd(m,n)=1\) y paridad opuesta, evaluan las formulas de \(a\), \(b\), \(c\) y descartan cualquier candidato con algun componente no positivo.
Si una terna primitiva tiene perimetro \(p\), entonces todo multiplo \(kp\) tambien es valido mientras \(kp\le N\). Con
$$q=\left\lfloor\frac{N}{p}\right\rfloor,$$
la contribucion total de esa terna primitiva es
$$p+2p+\cdots+qp=p\frac{q(q+1)}{2}.$$
Por eso la implementacion no genera cada multiplo de manera explicita. Tambien hay una verificacion por fuerza bruta para limites pequenos, y la version en C++ puede repartir el barrido exterior entre varios hilos.
Sea \(N\) el limite del perimetro. El parametro exterior crece solo como \(\sqrt{N}\). Sumando sobre todos los valores de \(n\), la primera familia revisa \(O\!\left(\sum n\right)=O(N)\) pares candidatos \((m,n)\), y la segunda familia hace lo mismo. Cada candidato usa aritmetica entera de ancho fijo y una prueba de gcd, asi que en el modelo RAM habitual el tiempo total es \(O(N)\).
La memoria es \(O(1)\), salvo unos pocos acumuladores y, en la version paralela de C++, un pequeno arreglo de sumas parciales. Para \(N=10^7\), eso deja solo unos pocos millones de comprobaciones aritmeticas.
把三种水果的数量记为正整数 \(a,b,c\)。按照当前发布的题面，第二个分数和第三个分数的分母都是 \(a+c\)，因此 条件实际上是
$$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+c}=4,$$
也就是
$$\frac{a}{b+c}+\frac{b+c}{a+c}=4.$$
对于每一个满足 \(p=a+b+c\le 10^7\) 的正整数解，都要把周长 \(p\) 加入总和。直接枚举所有三元组完全不可行， 所以关键不是暴力搜索，而是把整数解按结构分类。
三份实现的核心思路一致：先刻画本原解，再把本原解改写成两个可枚举的参数族，最后把每个本原周长的全部倍数一次性加入答案。
先乘上 \((a+c)(b+c)\) 消去分母：
$$a(a+c)+(b+c)^2=4(a+c)(b+c).$$
展开后得到二次丢番图方程
$$a^2-4ab-3ac+b^2-2bc-3c^2=0.$$
把它看成关于 \(b\) 的二次方程：
$$b^2-(4a+2c)b+(a^2-3ac-3c^2)=0.$$
它的判别式为
$$\Delta=(4a+2c)^2-4(a^2-3ac-3c^2)=4(a+c)(3a+4c).$$
因此任何整数解都必须满足
$$b=2a+c\pm \sqrt{(a+c)(3a+4c)},$$
这说明 \((a+c)(3a+4c)\) 一定是完全平方数。
消去分母以后，方程是二次齐次的。如果 \((a,b,c)\) 是一个解，那么对任意正整数 \(k\)，\(k(a,b,c)\) 仍然是解。 所以所有解都来自某个本原解，也就是 \(\gcd(a,b,c)=1\) 的解。
对本原解，最关键的结论是 \(\gcd(a,c)=1\)。理由很简单：如果某个 \(d\) 同时整除 \(a\) 和 \(c\)，那么在
$$a^2-4ab-3ac+b^2-2bc-3c^2=0$$
里，除了 \(b^2\) 之外的每一项都被 \(d\) 整除，于是 \(d\mid b^2\)，从而 \(d\mid b\)。这就推出 \(d\mid \gcd(a,b,c)\)，与本原性矛盾。
于是
$$\gcd(a+c,3a+4c)=\gcd(a+c,\;3a+4c-3(a+c))=\gcd(a+c,c)=\gcd(a,c)=1,$$
也就是说，\((a+c)(3a+4c)\) 这两个因子本身互素。
既然 \((a+c)(3a+4c)\) 是平方数，而这两个因子互素，那么由唯一分解定理可知，每个因子都必须单独是平方：
$$a+c=u^2,\qquad 3a+4c=v^2,\qquad \gcd(u,v)=1.$$
解这个线性方程组得到
$$a=4u^2-v^2,\qquad c=v^2-3u^2.$$
再代回 \(b\) 的二次公式，可得
$$b=5u^2-v^2\pm uv.$$
因此每一个本原解都可以写成
$$\bigl(a,b,c\bigr)=\bigl(4u^2-v^2,\;5u^2-v^2\pm uv,\;v^2-3u^2\bigr),\qquad \gcd(u,v)=1.$$
由 \(a\gt 0\) 与 \(c\gt 0\) 可知
$$v^2\lt 4u^2,\qquad v^2\gt 3u^2,$$
所以可行区域是
$$\sqrt{3}\,u \lt v \lt 2u.$$
本原周长为
$$p_\pm=a+b+c=6u^2-v^2\pm uv.$$
它恰好还能分解成
$$p_-=(2u-v)(3u+v),\qquad p_+=(2u+v)(3u-v).$$
这一步非常重要，因为实现里真正枚举的紧凑公式正是从这两个分解式变形出来的。
由于 \(\gcd(u,v)=1\)，\(u\) 和 \(v\) 不可能同时为偶数。第一类实现对应的是两者奇偶性相反的情况。
对于周长 \(p_-\)，令
$$m=u,\qquad n=2u-v,$$
于是 \(v=2m-n\)。代入后得到
$$a=4mn-n^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
并且
$$p_-=n(5m-n).$$
对于周长 \(p_+\)，令
$$m=2u+v,\qquad n=u,$$
于是 \(v=m-2n\)。这时有
$$a=4mn-m^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
并且
$$p_+=m(5n-m).$$
这两条分支都满足 \(\gcd(m,n)=1\)，而且 \(m-n\) 为奇数。再结合 \(b\gt 0\) 与 \(c\gt 0\)，可以推出
$$2+\sqrt{3}\lt \frac{m}{n}\lt \frac{5+\sqrt{21}}{2}\lt 5,$$
这就解释了为什么实现里只需要把这一类扫描到 \(m\le 5n\) 即可。
剩下的本原情形只有 \(u\) 和 \(v\) 都是奇数。
对于周长 \(p_-\)，定义
$$m=\frac{3u-v}{2},\qquad n=\frac{v-u}{2},$$
等价地写成
$$u=m+n,\qquad v=m+3n.$$
于是得到
$$a=3m^2+2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
以及
$$p_-=4m^2+2mn-6n^2.$$
对于周长 \(p_+\)，定义
$$m=\frac{3u+v}{2},\qquad n=\frac{u+v}{2},$$
等价地写成
$$u=m-n,\qquad v=3n-m.$$
这时有
$$a=3m^2-2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
以及
$$p_+=4m^2-2mn-6n^2.$$
同样地，\(\gcd(m,n)=1\) 且 \(m-n\) 为奇数。由共同的正性条件 \(b\gt 0\) 与 \(c\gt 0\) 可得
$$\sqrt{\frac{7}{3}}\lt \frac{m}{n}\lt \sqrt{3}\lt 2,$$
因此这一类只需扫描到 \(m\le 2n\)。
取最小的有效本原参数对 \(u=4\), \(v=7\)。那么
$$a=4\cdot 4^2-7^2=15,\qquad c=7^2-3\cdot 4^2=1.$$
对 \(b\) 则有
$$b=5\cdot 4^2-7^2\pm 4\cdot 7=31\pm 28\in\{3,59\}.$$
所以两个本原解分别是 \((15,3,1)\) 和 \((15,59,1)\)，周长分别为 \(19\) 与 \(75\)。如果上界是 \(N=50\)， 那么只有第一个三元组及其倍数 \((30,6,2)\) 会被计入，总和为
$$19+38=57.$$
这正好对应实现里使用的小规模校验值。
任何本原解都满足 \(u^2=a+c\lt a+b+c=p\le N\)，因此基础参数只需要到 \(\sqrt{N}\) 量级。上面的线性换元不会改变 这个量级，所以实现中的 \(m,n\) 也都只落在 \(O(\sqrt{N})\) 的范围内。
C++、Python 和 Java 实现都会先遍历正整数 \(n\)，再根据推导出的两个范围枚举 \(m\)：第一类扫到 \(5n\)， 第二类扫到 \(2n\)。它们统一要求 \(\gcd(m,n)=1\) 且奇偶性相反，然后用相应公式计算 \(a,b,c\)，只保留三个 分量都为正的候选。
如果某个本原三元组的周长是 \(p\)，那么只要 \(kp\le N\)，所有倍数 \(kp\) 都仍然有效。设
$$q=\left\lfloor\frac{N}{p}\right\rfloor,$$
则这个本原三元组的总贡献为
$$p+2p+\cdots+qp=p\frac{q(q+1)}{2}.$$
这就是实现不需要逐个生成倍数的原因。代码还包含一个小范围暴力校验器；其中 C++ 版本还可以把外层参数区间拆给多个线程并行求和。
设周长上界为 \(N\)。外层参数只增长到 \(\sqrt{N}\)。对所有 \(n\) 累加后，第一类检查的候选对 \((m,n)\) 数量是 \(O\!\left(\sum n\right)=O(N)\)，第二类同样如此。每个候选只做定宽整数运算和一次 gcd 检查，因此在通常的 RAM 模型下，总时间复杂度可以视为 \(O(N)\)。
空间复杂度是 \(O(1)\)：除少数计数器外几乎不需要额外存储；只有多线程的 C++ 版本会多保存一小组部分和。 对 \(N=10^7\) 而言，这只意味着几百万次算术检查。
Обозначим три количества фруктов через положительные целые числа \(a,b,c\). В опубликованной формулировке у второй и третьей дробей одинаковый знаменатель \(a+c\), поэтому условие имеет вид
$$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+c}=4,$$
то есть сразу упрощается до
$$\frac{a}{b+c}+\frac{b+c}{a+c}=4.$$
Для каждого решения с периметром \(p=a+b+c\le 10^7\) нужно добавить \(p\) к общей сумме. Перебирать все тройки напрямую бессмысленно; нужно описать все целочисленные решения в параметрической форме.
Все три реализации сначала классифицируют примитивные решения, затем переводят их в две явные параметрические семьи и после этого добавляют все кратные каждого примитивного периметра одной формулой.
Умножим на \((a+c)(b+c)\), чтобы убрать знаменатели:
$$a(a+c)+(b+c)^2=4(a+c)(b+c).$$
После раскрытия скобок получаем квадратное диофантово уравнение
$$a^2-4ab-3ac+b^2-2bc-3c^2=0.$$
Если рассматривать его как квадратное уравнение по \(b\), то
$$b^2-(4a+2c)b+(a^2-3ac-3c^2)=0.$$
Его дискриминант равен
$$\Delta=(4a+2c)^2-4(a^2-3ac-3c^2)=4(a+c)(3a+4c).$$
Следовательно, для любого целочисленного решения должно выполняться
$$b=2a+c\pm \sqrt{(a+c)(3a+4c)},$$
то есть \((a+c)(3a+4c)\) обязано быть полным квадратом.
После устранения знаменателей уравнение однородно степени 2. Если \((a,b,c)\) является решением, то и \(k(a,b,c)\) тоже является решением для любого положительного \(k\). Значит, достаточно описать примитивные тройки с \(\gcd(a,b,c)=1\).
Для примитивной тройки нужен только один важный факт: \(\gcd(a,c)=1\). Действительно, если некоторое \(d\) делит и \(a\), и \(c\), то в равенстве
$$a^2-4ab-3ac+b^2-2bc-3c^2=0$$
все члены, кроме \(b^2\), кратны \(d\). Значит, \(d\mid b^2\), откуда \(d\mid b\), а это противоречит примитивности.
Теперь получаем
$$\gcd(a+c,3a+4c)=\gcd(a+c,\;3a+4c-3(a+c))=\gcd(a+c,c)=\gcd(a,c)=1.$$
Итак, множители в \((a+c)(3a+4c)\) взаимно просты.
Мы уже знаем, что произведение \((a+c)(3a+4c)\) является квадратом. Поскольку множители взаимно просты, из единственности разложения на простые следует, что каждый из них сам квадрат:
$$a+c=u^2,\qquad 3a+4c=v^2,\qquad \gcd(u,v)=1.$$
Решая линейную систему, находим
$$a=4u^2-v^2,\qquad c=v^2-3u^2.$$
Подстановка обратно в квадратную формулу для \(b\) дает
$$b=5u^2-v^2\pm uv.$$
Значит, каждое примитивное решение имеет вид
$$\bigl(a,b,c\bigr)=\bigl(4u^2-v^2,\;5u^2-v^2\pm uv,\;v^2-3u^2\bigr),\qquad \gcd(u,v)=1.$$
Из условий \(a\gt 0\) и \(c\gt 0\) следует
$$v^2\lt 4u^2,\qquad v^2\gt 3u^2,$$
то есть допустимая область задается неравенством
$$\sqrt{3}\,u \lt v \lt 2u.$$
Примитивный периметр равен
$$p_\pm=a+b+c=6u^2-v^2\pm uv.$$
Он красиво раскладывается на линейные множители:
$$p_-=(2u-v)(3u+v),\qquad p_+=(2u+v)(3u-v).$$
Именно эти разложения приводят к компактным формулам, которые затем перебирает программа.
Так как \(\gcd(u,v)=1\), числа \(u\) и \(v\) не могут быть одновременно четными. Первое семейство в реализации соответствует случаю разной четности.
Для периметра \(p_-\) положим
$$m=u,\qquad n=2u-v,$$
тогда \(v=2m-n\). После подстановки получаем
$$a=4mn-n^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
и
$$p_-=n(5m-n).$$
Для периметра \(p_+\) положим
$$m=2u+v,\qquad n=u,$$
тогда \(v=m-2n\). Это дает
$$a=4mn-m^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
и
$$p_+=m(5n-m).$$
В обеих ветвях выполняется \(\gcd(m,n)=1\), а \(m-n\) нечетно. Из условий \(b\gt 0\) и \(c\gt 0\) следует
$$2+\sqrt{3}\lt \frac{m}{n}\lt \frac{5+\sqrt{21}}{2}\lt 5,$$
поэтому в этой семье достаточно проверять только \(m\le 5n\).
Остается единственная примитивная возможность: оба числа \(u\) и \(v\) нечетные.
Для периметра \(p_-\) определим
$$m=\frac{3u-v}{2},\qquad n=\frac{v-u}{2},$$
или, что то же самое,
$$u=m+n,\qquad v=m+3n.$$
Тогда получаем
$$a=3m^2+2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
и
$$p_-=4m^2+2mn-6n^2.$$
Для периметра \(p_+\) определим
$$m=\frac{3u+v}{2},\qquad n=\frac{u+v}{2},$$
или эквивалентно
$$u=m-n,\qquad v=3n-m.$$
Это дает
$$a=3m^2-2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
и
$$p_+=4m^2-2mn-6n^2.$$
Снова \(\gcd(m,n)=1\), а \(m-n\) нечетно. Общие условия положительности \(b\gt 0\) и \(c\gt 0\) приводят к оценке
$$\sqrt{\frac{7}{3}}\lt \frac{m}{n}\lt \sqrt{3}\lt 2,$$
поэтому здесь хватает перебора \(m\le 2n\).
Возьмем наименьшую подходящую примитивную пару \(u=4\), \(v=7\). Тогда
$$a=4\cdot 4^2-7^2=15,\qquad c=7^2-3\cdot 4^2=1.$$
Для \(b\) получаем
$$b=5\cdot 4^2-7^2\pm 4\cdot 7=31\pm 28\in\{3,59\}.$$
Следовательно, две примитивные тройки таковы: \((15,3,1)\) с периметром \(19\) и \((15,59,1)\) с периметром \(75\). Если бы предел был \(N=50\), то вклад дали бы только первая тройка и ее удвоение \((30,6,2)\):
$$19+38=57.$$
Именно это малое контрольное значение воспроизводят реализации.
Для любой примитивной тройки выполняется \(u^2=a+c\lt a+b+c=p\le N\). Значит, базовые параметры имеют порядок только \(\sqrt{N}\), а описанные выше линейные замены сохраняют тот же масштаб и для параметров \(m,n\).
Реализации на C++, Python и Java перебирают положительные \(n\), а затем рассматривают \(m\) в двух интервалах, выведенных из формул: до \(5n\) для семейства разной четности и до \(2n\) для семейства нечетных \(u,v\). Они требуют \(\gcd(m,n)=1\) и разную четность, вычисляют соответствующие значения \(a,b,c\) и отбрасывают все случаи, где хотя бы одна компонента неположительна.
Если примитивная тройка имеет периметр \(p\), то любой кратный периметр \(kp\) тоже допустим, пока \(kp\le N\). При
$$q=\left\lfloor\frac{N}{p}\right\rfloor$$
общий вклад этой примитивной тройки равен
$$p+2p+\cdots+qp=p\frac{q(q+1)}{2}.$$
Поэтому код не генерирует каждое кратное отдельно. Кроме того, в нем есть небольшая проверка полным перебором для малых границ, а реализация на C++ может при желании разделить внешний диапазон параметров между несколькими потоками.
Пусть \(N\) обозначает ограничение на периметр. Внешний параметр растет только как \(\sqrt{N}\). Если суммировать по всем \(n\), то первое семейство проверяет \(O\!\left(\sum n\right)=O(N)\) кандидатных пар \((m,n)\), и второе семейство делает то же самое. Для каждого кандидата нужны только целочисленные операции фиксированной ширины и один тест gcd, так что в стандартной RAM-модели время работы равно \(O(N)\).
Память имеет порядок \(O(1)\): кроме нескольких счетчиков почти ничего не хранится; только многопоточная версия на C++ использует небольшой массив частичных сумм. Для \(N=10^7\) это означает лишь несколько миллионов арифметических проверок.
لنرمز إلى كميات الفاكهة الثلاثة بالأعداد الصحيحة الموجبة \(a,b,c\). في الصيغة المنشورة من المسألة، يملك الكسران الثاني والثالث المقام نفسه \(a+c\)، ولذلك يصبح الشرط
$$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+c}=4,$$
أي مباشرة
$$\frac{a}{b+c}+\frac{b+c}{a+c}=4.$$
لكل حل يحقق \(p=a+b+c\le 10^7\) يجب أن نضيف المحيط \(p\) إلى المجموع النهائي. ومن الواضح أن الفحص المباشر لكل الثلاثيات غير ممكن عمليا، لذلك لا بد من تصنيف الحلول الصحيحة بطريقة بنيوية.
تعتمد جميع التطبيقات على الفكرة نفسها: إيجاد الحلول الأولية، ثم تحويلها إلى عائلتين واضحتين من المعاملات، ثم جمع جميع مضاعفات كل محيط أولي دفعة واحدة.
نضرب أولا في \((a+c)(b+c)\) للتخلص من المقامات:
$$a(a+c)+(b+c)^2=4(a+c)(b+c).$$
وبعد التوسيع نحصل على المعادلة الديوفانتية التربيعية
$$a^2-4ab-3ac+b^2-2bc-3c^2=0.$$
وإذا اعتبرناها معادلة تربيعية في \(b\)، فإنها تصبح
$$b^2-(4a+2c)b+(a^2-3ac-3c^2)=0.$$
ومميزها هو
$$\Delta=(4a+2c)^2-4(a^2-3ac-3c^2)=4(a+c)(3a+4c).$$
لذلك لا بد أن يحقق كل حل صحيح
$$b=2a+c\pm \sqrt{(a+c)(3a+4c)},$$
وهذا يعني أن \((a+c)(3a+4c)\) يجب أن يكون مربعا كاملا.
بعد إزالة المقامات تصبح المعادلة متجانسة من الدرجة الثانية. فإذا كانت \((a,b,c)\) حلا، فإن \(k(a,b,c)\) يبقى حلا لكل عدد صحيح موجب \(k\). ومن ثم فإن كل حل هو مضاعف لحل أولي يحقق \(\gcd(a,b,c)=1\).
في الحالة الأولية نحتاج إلى حقيقة أساسية واحدة فقط، وهي \(\gcd(a,c)=1\). فإذا كان هناك \(d\) يقسم كلا من \(a\) و\(c\)، فإن جميع الحدود في
$$a^2-4ab-3ac+b^2-2bc-3c^2=0$$
عدا \(b^2\) تكون قابلة للقسمة على \(d\)، وبالتالي \(d\mid b^2\)، ومنه \(d\mid b\). وهذا يناقض أولية الثلاثية.
وعندئذ نحصل على
$$\gcd(a+c,3a+4c)=\gcd(a+c,\;3a+4c-3(a+c))=\gcd(a+c,c)=\gcd(a,c)=1.$$
أي إن العاملين في \((a+c)(3a+4c)\) متباينان أوليا.
بما أن \((a+c)(3a+4c)\) مربع كامل، وبما أن العاملين متباينان أوليا، فإن التحليل الأولي الفريد يفرض أن يكون كل عامل منهما مربعا كاملا على حدة:
$$a+c=u^2,\qquad 3a+4c=v^2,\qquad \gcd(u,v)=1.$$
بحل هذا النظام الخطي نحصل على
$$a=4u^2-v^2,\qquad c=v^2-3u^2.$$
ثم بالتعويض في صيغة \(b\) التربيعية نجد
$$b=5u^2-v^2\pm uv.$$
إذن كل حل أولي يكتب على الصورة
$$\bigl(a,b,c\bigr)=\bigl(4u^2-v^2,\;5u^2-v^2\pm uv,\;v^2-3u^2\bigr),\qquad \gcd(u,v)=1.$$
من الشرطين \(a\gt 0\) و\(c\gt 0\) نحصل على
$$v^2\lt 4u^2,\qquad v^2\gt 3u^2,$$
أي إن المجال المسموح هو
$$\sqrt{3}\,u \lt v \lt 2u.$$
أما المحيط الأولي فهو
$$p_\pm=a+b+c=6u^2-v^2\pm uv.$$
وهذا يتفكك إلى
$$p_-=(2u-v)(3u+v),\qquad p_+=(2u+v)(3u-v).$$
وهذان التحليلان هما الجسر المباشر بين البرهان النظري والصيغ المضغوطة التي تستعملها التطبيقات.
بما أن \(\gcd(u,v)=1\)، فلا يمكن أن يكونا زوجيين معا. العائلة الأولى في التطبيق تغطي حالة اختلاف الفردية.
بالنسبة إلى المحيط \(p_-\)، نضع
$$m=u,\qquad n=2u-v,$$
وعندها \(v=2m-n\). فنحصل على
$$a=4mn-n^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
وكذلك
$$p_-=n(5m-n).$$
وبالنسبة إلى المحيط \(p_+\)، نضع
$$m=2u+v,\qquad n=u,$$
وعندها \(v=m-2n\). وهذا يعطي
$$a=4mn-m^2,\qquad b=5mn-m^2-n^2,\qquad c=m^2-4mn+n^2,$$
مع
$$p_+=m(5n-m).$$
وفي كلا الفرعين لدينا \(\gcd(m,n)=1\) و\(m-n\) عدد فردي. كما أن الشرطين \(b\gt 0\) و\(c\gt 0\) يؤديان إلى
$$2+\sqrt{3}\lt \frac{m}{n}\lt \frac{5+\sqrt{21}}{2}\lt 5,$$
ولهذا يكفي أن تمسح الخوارزمية هذه العائلة حتى \(m\le 5n\).
لا يبقى من الحالات الأولية إلا أن يكون \(u\) و\(v\) فرديين معا.
للمحيط \(p_-\)، نعرف
$$m=\frac{3u-v}{2},\qquad n=\frac{v-u}{2},$$
أي بصورة مكافئة
$$u=m+n,\qquad v=m+3n.$$
وبالتعويض نحصل على
$$a=3m^2+2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
وكذلك
$$p_-=4m^2+2mn-6n^2.$$
أما للمحيط \(p_+\)، فنأخذ
$$m=\frac{3u+v}{2},\qquad n=\frac{u+v}{2},$$
أي بصورة مكافئة
$$u=m-n,\qquad v=3n-m.$$
فنحصل على
$$a=3m^2-2mn-5n^2,\qquad b=3m^2-7n^2,\qquad c=2(3n^2-m^2),$$
ومعها
$$p_+=4m^2-2mn-6n^2.$$
ومرة أخرى يكون \(\gcd(m,n)=1\) و\(m-n\) فرديا. ومن الشرطين المشتركين \(b\gt 0\) و\(c\gt 0\) نحصل على
$$\sqrt{\frac{7}{3}}\lt \frac{m}{n}\lt \sqrt{3}\lt 2,$$
ولذلك يكفي هنا المسح حتى \(m\le 2n\).
لنأخذ أصغر زوج أولي صالح وهو \(u=4\)، \(v=7\). عندئذ
$$a=4\cdot 4^2-7^2=15,\qquad c=7^2-3\cdot 4^2=1.$$
أما \(b\) فيساوي
$$b=5\cdot 4^2-7^2\pm 4\cdot 7=31\pm 28\in\{3,59\}.$$
إذن الحلان الأوليان هما \((15,3,1)\) بمحيط \(19\)، و\((15,59,1)\) بمحيط \(75\). ولو كان الحد \(N=50\)، فلن يدخل في المجموع إلا الحل الأول ومضاعفه \((30,6,2)\)، فتكون الحصيلة
$$19+38=57.$$
وهذا بالضبط هو التحقق الصغير الذي تعيده التطبيقات.
لكل حل أولي لدينا \(u^2=a+c\lt a+b+c=p\le N\). ولهذا فإن المعاملات الأساسية لا تصل إلا إلى رتبة \(\sqrt{N}\)، كما أن التحويلات الخطية السابقة تُبقي معاملي التنفيذ \(m,n\) ضمن الرتبة نفسها.
تقوم تطبيقات C++ وPython وJava بالمرور على \(n\) الموجب، ثم تفحص \(m\) في المجالين المستنتجين من الاشتقاق: حتى \(5n\) للعائلة ذات الفردية المختلفة، وحتى \(2n\) للعائلة التي يكون فيها \(u\) و\(v\) فرديين. وهي تفرض الشرطين \(\gcd(m,n)=1\) واختلاف الفردية، ثم تحسب صيغ \(a,b,c\) المناسبة، وتستبعد كل مرشح يحتوي عنصرا غير موجب.
إذا كان للمثلث الأولي محيط \(p\)، فإن كل مضاعف \(kp\) يبقى صالحا ما دام \(kp\le N\). ومع
$$q=\left\lfloor\frac{N}{p}\right\rfloor$$
تكون مساهمة هذا الحل الأولي
$$p+2p+\cdots+qp=p\frac{q(q+1)}{2}.$$
ولهذا لا تحتاج التطبيقات إلى توليد كل مضاعف على حدة. كما يوجد فاحص brute-force صغير للحدود المنخفضة، وتستطيع نسخة C++ عند الرغبة تقسيم المجال الخارجي على عدة خيوط.
ليكن \(N\) حد المحيط. إن المعامل الخارجي ينمو فقط مثل \(\sqrt{N}\). وعند الجمع على جميع قيم \(n\)، فإن العائلة الأولى تفحص \(O\!\left(\sum n\right)=O(N)\) من الأزواج المرشحة \((m,n)\)، والعائلة الثانية تفعل الشيء نفسه. وكل مرشح يحتاج فقط إلى حسابات صحيحة ثابتة العرض واختبار gcd واحد، لذا يكون الزمن الكلي \(O(N)\) في نموذج RAM المعتاد.
أما الذاكرة فهي \(O(1)\) باستثناء بضعة مجاميع وعدادات، ومع النسخة متعددة الخيوط في C++ توجد أيضا مصفوفة صغيرة للمجاميع الجزئية. وعند \(N=10^7\) يعني هذا بضع ملايين فقط من الفحوص الحسابية.