projecteuler.net

Convex path in square

Published on Sunday, 21st May 2017, 04:00 am; Solved by 390;
Difficulty rating: 40%

Problem 604

Let $F(N)$ be the maximum number of lattice points in an axis-aligned $N\times N$ square that the graph of a single strictly convex increasing function can pass through.

You are given that $F(1) = 2$, $F(3) = 3$, $F(9) = 6$, $F(11) = 7$, $F(100) = 30$ and $F(50000) = 1898$.
Below is the graph of a function reaching the maximum 3 for $N=3$:

p604_convex3.png

Find $F(10^{18})$.