Detailed mathematical approach

Problem Summary

Let \(F(N)\) be the maximum number of lattice points inside an \(N \times N\) square that can lie on the graph of one strictly convex increasing function. If the graph passes through \(k+1\) lattice points, then those points determine \(k\) consecutive step vectors. The task is to evaluate \(F(10^{18})\), but the derivation below works for general \(N\).

Mathematical Approach

Write the selected lattice points in increasing \(x\)-order as \(P_0,P_1,\dots,P_k\). For each consecutive pair define the step vector

$P_i-P_{i-1}=(a_i,b_i).$

Because the graph is increasing, every step satisfies \(a_i\gt 0\) and \(b_i\gt 0\). The entire problem becomes: how many such steps can we choose while preserving strict convexity and staying inside the square?

Step 1: Convert the curve into step vectors

Strict convexity means the slopes of consecutive chords are strictly increasing:

$\frac{b_1}{a_1} \lt \frac{b_2}{a_2} \lt \cdots \lt \frac{b_k}{a_k}.$

The horizontal and vertical spans must both fit into the square, so

$\sum_{i=1}^{k} a_i \le N,\qquad \sum_{i=1}^{k} b_i \le N.$

Adding the two inequalities gives the global \(L_1\) budget

$\sum_{i=1}^{k}(a_i+b_i)\le 2N.$

Each extra segment increases the number of lattice points by exactly \(1\), so maximizing points is equivalent to maximizing the number of admissible step vectors.

Step 2: Keep only primitive directions

If a step \((a,b)\) has \(d=\gcd(a,b)\gt 1\), then the reduced vector \((a/d,b/d)\) has the same slope but strictly smaller cost \((a+b)/d\). Since equal slopes cannot repeat on a strictly convex chain, a non-primitive step is never preferable to its primitive version. Therefore an optimal construction may be assumed to use only primitive vectors:

$\gcd(a_i,b_i)=1.$

Now fix

$s=a+b.$

Every primitive vector in that layer has the form \((a,s-a)\) with \(1\le a\le s-1\) and

$\gcd(a,s)=1.$

The number of such choices is exactly Euler's totient:

$\#\{a:1\le a\le s-1,\ \gcd(a,s)=1\}=\varphi(s).$

Step 3: Full layers are balanced

All primitive vectors with the same value of \(a+b=s\) form one layer. Every vector in that layer contributes one segment and costs \(s\) units of \(L_1\) budget.

The layer is symmetric because \((a,s-a)\) is primitive if and only if \((s-a,a)\) is primitive. Pairing those two vectors gives equal total contribution in the \(x\)- and \(y\)-directions, so

$\sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} a = \sum_{\substack{1\le a\lt s\\ \gcd(a,s)=1}} (s-a) = \frac{s\varphi(s)}{2}.$

Therefore taking the whole layer uses total cost

$s\varphi(s),$

and that cost is split evenly between horizontal and vertical motion. This is the key reason the two-dimensional square constraint collapses to an \(L_1\)-budget problem for complete layers.

Step 4: Greedy by increasing \(a+b\)

Each available segment is worth one more lattice point, but a segment from layer \(s\) costs \(s\). Hence the cheapest segments always come from the smallest remaining \(s\), so the optimal count is obtained by taking layers in increasing order.

Define the prefix segment count and prefix cost by

$\Phi(m)=\sum_{s=2}^{m}\varphi(s),\qquad C(m)=\sum_{s=2}^{m}s\varphi(s).$

Let \(m\) be the largest integer such that

$C(m)\le 2N.$

Then all layers \(2,3,\dots,m\) are taken completely, contributing \(\Phi(m)\) segments. The next candidate layer is

$s=m+1.$

With remaining budget

$R=2N-C(m),$

the raw number of extra segments available from that next layer is

$t=\left\lfloor\frac{R}{s}\right\rfloor,\qquad r=R\bmod s.$

So the default segment count is \(\Phi(m)+t\), and the default point count is \(\Phi(m)+t+1\).

Step 5: Exact saturation is the only delicate case

When \(r\gt 0\), there is still slack after choosing \(t\) vectors from the final layer, and the implementations treat that situation as feasible. The only time a correction is needed is

$r=0,\qquad t\equiv 1\pmod{2}.$

In that case the lower complete layers are already perfectly balanced, and the last layer must balance itself exactly:

$\sum a=\sum b=\frac{ts}{2}.$

If \(t\) is even, we can use complementary pairs \((a,s-a)\) and \((s-a,a)\), so balancing is automatic.

If \(t=1\), balancing is impossible.

If \(s\equiv 0\pmod{4}\), balancing is also impossible. Every admissible \(a\) is odd, so the sum of an odd number of such terms is odd, while \(ts/2\) is even.

The remaining case is \(s\equiv 2\pmod{4}\), so \(s=2n\) with \(n\) odd. Any larger odd balanced subset can then be written as one balanced triple together with complementary pairs. So the question reduces to whether there exist three integers coprime to \(s\) whose sum is \(3s/2\). The implementation checks exactly that condition and subtracts one segment if it fails.

Worked Example: \(N=100\)

Here the total budget is

$2N=200.$

The prefix costs of the early layers are

$\begin{aligned} C(2)&=2,\\ C(3)&=8,\\ C(4)&=16,\\ C(5)&=36,\\ C(6)&=48,\\ C(7)&=90,\\ C(8)&=122,\\ C(9)&=176. \end{aligned}$

But \(C(10)=216\gt 200\), so the last complete layer is \(m=9\). The complete layers contribute

$\Phi(9)=\varphi(2)+\varphi(3)+\cdots+\varphi(9)=1+2+2+4+2+6+4+6=27$

segments. The remaining budget is

$R=200-176=24.$

The next layer is \(s=10\), hence

$t=\left\lfloor\frac{24}{10}\right\rfloor=2,\qquad r=4.$

No correction is needed because \(r\ne 0\). Therefore

$F(100)=27+2+1=30,$

matching the checkpoint used by the C++, Python, and Java implementations.

How the Code Works

The implementation first sieves Euler's totient function up to a cutoff large enough that the prefix cost \(C(m)\) exceeds \(2\times 10^{18}\). From those totients it builds two prefix arrays: one for \(\Phi(m)\) and one for \(C(m)\).

For a given \(N\), it binary-searches the largest \(m\) with \(C(m)\le 2N\). That immediately gives the number of complete layers and the remaining budget \(R\).

Next it computes \(t=\lfloor R/(m+1)\rfloor\) and \(r=R\bmod (m+1)\). The default answer is the number of complete-layer segments plus \(t\), followed by one extra point for the starting lattice point.

Finally, if the remainder is zero and the last-layer count is odd, the implementation runs the balancing test from Step 5. In the impossible subcases it decreases the segment count by \(1\), then returns the number of lattice points.

Complexity Analysis

If the sieve stops at \(L\), computing all totients up to \(L\) costs \(O(L\log\log L)\) time and \(O(L)\) memory. Building the prefix arrays is \(O(L)\). A query for \(F(N)\) then needs one binary search, a few arithmetic operations, and only a tiny extra check in the rare exact-saturation case.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=604
2. Convex function: Wikipedia - Convex function
3. Euler's totient function: Wikipedia - Euler's totient function
4. Farey sequence: Wikipedia - Farey sequence
5. Coprime integers: Wikipedia - Coprime integers