题目

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。

解答

根据以上分析,我们有以下 Haskell 程序:

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)

这个程序的运行时间是 9 秒。

参考资料

  1. Wikipedia: Euler's totient function