Solution

Answer: 1398582231101

Let the graph pass through lattice points

$$P_0,P_1,\dots,P_m$$

with strictly increasing $x$-coordinates and $y$-coordinates.

Define the step vectors

$$v_i=P_i-P_{i-1}=(a_i,b_i),\qquad a_i,b_i\in \mathbb Z_{>0}.$$

For a strictly convex increasing function, the slopes must satisfy

$$\frac{b_1}{a_1}<\frac{b_2}{a_2}<\cdots<\frac{b_m}{a_m}.$$

Thus every slope can occur at most once, so every vector may be taken primitive:

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

Also,

$$\sum a_i\le N,\qquad \sum b_i\le N.$$

Hence the problem becomes:

Choose as many primitive positive lattice vectors as possible, with strictly increasing slopes, subject to

$$\sum a_i\le N,\qquad \sum b_i\le N.$$

1. Ordering by $a+b$

For a primitive vector $(a,b)$, define its “cost”

$$c=a+b.$$

To maximize the number of vectors, we clearly take vectors with the smallest possible values of $a+b$.

For a fixed $s$, the primitive vectors with $a+b=s$ are

$$(a,s-a),\qquad 1\le a<s,\quad \gcd(a,s)=1.$$

There are exactly

$$\varphi(s)$$

such vectors.

2. Cost of a complete shell

Consider taking all primitive vectors with $a+b=s$.

Because the set is symmetric under $a\leftrightarrow b$,

$$\sum a=\sum b=\frac{s\varphi(s)}2$$

(for $s=2$, this equals $1$).

Therefore, if we take all shells $2,3,\dots,m$, then

$$X(m)=Y(m)=\frac12\sum_{s=2}^m s\varphi(s).$$

The number of vectors used is

$$V(m)=\sum_{s=2}^m \varphi(s).$$

Hence the number of lattice points is

$$F=V(m)+1.$$

3. Partial final shell

Let $m$ be maximal such that

$$X(m)\le N.$$

Define the remaining capacity

$$R=N-X(m).$$

Now we may additionally take vectors from the next shell $s=m+1$.

Each such vector has total cost $s$, so every added vector consumes exactly $s$ units from the combined budget

$$(\sum a_i)+(\sum b_i)\le 2N.$$

The remaining combined budget is $2R$, hence the maximum extra vectors is

$$\left\lfloor \frac{2R}{s}\right\rfloor .$$

Therefore

$$\boxed{ F(N)=1+\sum_{k=2}^m\varphi(k) +\left\lfloor \frac{2\left(N-\frac12\sum_{k=2}^m k\varphi(k)\right)} {m+1} \right\rfloor }$$

where $m$ is maximal with

$$\frac12\sum_{k=2}^m k\varphi(k)\le N.$$

This reproduces all given values:

$F(3)=3$
$F(9)=6$
$F(11)=7$
$F(100)=30$
$F(50000)=1898$

4. Python implementation

from array import array

N = 10**18

# ---------------------------------------------------------
# Compute Euler phi up to a sufficient limit.
# The required m is about (pi^2 N)^(1/3) ~ 2.15e6.
# ---------------------------------------------------------

LIMIT = 3_000_000

phi = array('Q', range(LIMIT + 1))

for p in range(2, LIMIT + 1):
    if phi[p] == p:                 # p is prime
        for k in range(p, LIMIT + 1, p):
            phi[k] -= phi[k] // p

# ---------------------------------------------------------
# Accumulate complete shells
# ---------------------------------------------------------

used = 0          # X(m)
count = 1         # initial lattice point
s = 2

while True:

    # contribution of the complete shell a+b=s
    add = (s * phi[s]) // 2

    if used + add > N:
        break

    used += add
    count += phi[s]
    s += 1

# ---------------------------------------------------------
# Partial next shell
# ---------------------------------------------------------

remaining = N - used
extra = (2 * remaining) // s

answer = count + extra

print(answer)

5. Code walkthrough

Totient sieve

phi = array('Q', range(LIMIT + 1))

Initializes $\phi(n)=n$.

For every prime $p$,

phi[k] -= phi[k] // p

implements Euler’s product formula

$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right).$$

Building complete shells

For shell $s$,

add = (s * phi[s]) // 2

is the amount added to both the $x$- and $y$-totals.

We keep taking whole shells while the budget allows.

The number of vectors added is

count += phi[s]

because shell $s$ contains exactly $\varphi(s)$ primitive vectors.

Partial final shell

After the last complete shell:

remaining = N - used
extra = (2 * remaining) // s

adds as many vectors as possible from the next shell.

Finally,

answer = count + extra

gives the total number of lattice points.

6. Verification for the examples

The program gives:

$$\begin{aligned} F(1)&=2\ F(3)&=3\ F(9)&=6\ F(11)&=7\ F(100)&=30\ F(50000)&=1898 \end{aligned}$$

matching the statement exactly.

For $N=10^{18}$, the computation yields

$$\boxed{1398582231101}.$$

Answer: 1398582231101

Project Euler Problem 604