# 题目

Problem 604. Convex path in square

Let F(N) be the maximum number of lattice points in an axis-aligned N × 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:

Find F(1018).

# 分析

kabφ(k)items
21011/1
32121/2, 2/1
44421/3, 3/1
56841/4, 2/3, 3/2, 4/1
6101821/5, 5/1
7122461/6, 2/5, 3/4, 4/3, 5/2, 6/1
8184541/7, 3/5, 5/3, 7/1
9226161/8, 2/7, 4/5, 5/4, 7/2, 8/1
10288841/9, 3/7, 7/3, 9/1
1132108101/10, 2/9, 3/8, 4/7, 5/6, 6/5, 7/4, 8/3, 9/2, 10/1

• items 中各项都是形如 i / (k-i) 的既约分数，其分子分母之和等于 k
• items 中的项的数目等于 φ(k)，其中 φ 是欧拉 φ 函数。这是因为 gcd(k-i, i) = gcd(k, i)。
• an+1 = an + φ(kn)。
• bn+1 = bn + knφ(kn) / 2。
• F(b) = a，而对于间隙中的值，a 每增加 2，b 就增加 k
• 例如：F(88) = 28, F(98) = 30, F(108) = 32。所以 F(100) = 30。

# 解答

import Math.NumberTheory.ArithmeticFunctions ( totient )
main = let n = 10^18 :: Int in print \$ (\(k,a,b) -> div (2*(n-b)) k
+ a) \$ last \$ takeWhile (\(_,_,b) -> b <= n) \$ iterate (\(k,a,b)
-> let c = totient(k) in (k+1, a+c, b + div (c*k) 2)) (2,1,0)