Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

The implementations work by identifying primitive solutions, turning them into explicit parameter families, and then summing all multiples of each primitive perimeter at once.

From the Rational Identity to a Discriminant

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.

Primitive Reduction and the Key Coprimality Fact

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.

Replacing One Square by Two Squares

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.$

Positivity and Perimeter Factorization

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.

Family I: \(u\) and \(v\) of Opposite Parity

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.

Family II: \(u\) and \(v\) Both Odd

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.

Worked Example

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.

How the Code Works

Bounding the Search

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.

Enumerating the Two Families

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.

Adding Every Multiple in One Step

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=991
2. Diophantine equation: Wikipedia - Diophantine equation
3. Coprime integers: Wikipedia - Coprime integers
4. Fundamental theorem of arithmetic: Wikipedia - Fundamental theorem of arithmetic
5. Quadratic equation and discriminant: Wikipedia - Quadratic equation
6. Arithmetic progression: Wikipedia - Arithmetic progression