Project Euler Problem 713

Project Euler Problem 713

Solution

Answer: 788626351539895

Let $k=m-1$. To guarantee success, the set of tried fuse-pairs must have the property that every set of $m$ working fuses contains at least one tried pair (otherwise all tried pairs could fail).

This is exactly a graph problem:

• Vertices = fuses.
• Edges = tested pairs.
• We want every set of $m$ vertices to contain an edge.

Equivalently, the complement graph must contain no independent set of size $m$, i.e. no $K_m$. By the Pál Turán theorem, the complement graph with the maximum number of edges is the Turán graph with $m-1$ parts.

If $k=m-1$, write

$$N = kq + r,\qquad 0 \le r < k.$$

The Turán partition has $r$ parts of size $q+1$ and $k-r$ parts of size $q$. Hence

$$T(N,m) = \frac{1}{2} \left( (k-r)q^2+r(q+1)^2-N \right).$$

This simplifies to

$$T(N,m) = qN-\frac{kq(q+1)}{2}, \qquad q=\left\lfloor\frac{N}{k}\right\rfloor.$$

So

$$L(N) = \sum_{k=1}^{N-1} \left( qN-\frac{kq(q+1)}{2} \right), \qquad q=\left\lfloor\frac{N}{k}\right\rfloor.$$

Grouping equal values of $q=\lfloor N/k\rfloor$ gives an $O(\sqrt N)$ computation. Verifying:

• $T(3,2)=3$
• $T(8,4)=7$
• $L(1000)=3281346$ ✓

Evaluating for $N=10^7$:

Answer: 788626351539895