P38 - 高欧拉函数数

2026-09-07 00:00    #Haskell   #99题   #数论  

P38 - 高欧拉函数数

Construct the list of highly totient numbers

官方模块：Problems.P38　核心函数：highlyTotientNumbers

← P37 欧拉乘积公式 | P39 素数列表 →

题目描述

可能有多个 xx 满足 φ(x)=n\varphi(x)=n。若 nn 的原像数量严格大于所有更小整数的原像数量，就称 nn 为高欧拉函数数（highly totient number）。要求构造它们的无限列表。

函数签名

1highlyTotientNumbers :: [Integer]

实现

方法一：无限惰性列表（标准解）

 1highlyTotientNumbers :: [Integer]
 2highlyTotientNumbers = records 1 0
 3  where
 4    records n best
 5      | count > best = n : records (n + 1) count
 6      | otherwise    = records (n + 1) best
 7      where count = tally n
 8
 9tally :: Integer -> Int
10tally n = length [x | x <- [1..upperBound n], totient' x == n]
11
12upperBound :: Integer -> Integer
13upperBound n = product (map (+ 1) (1 : primeFactors n))

困难在于不能无限枚举 xx。若 n=φ(x)n=\varphi(x)，可由 nn 的质因数构造一个安全上界 x≤∏q∈{1}∪factors⁡(n)(q+1)x\le \prod_{q\in\{1\}\cup\operatorname{factors}(n)}(q+1)。因此 tally n 只需检查有限区间。

方法二：流式记录值筛选

1highlyTotientNumbers :: [Integer]
2highlyTotientNumbers =
3  [n
4  | (n, count, previousBest) <- zip3 [1..] counts bestsBefore
5  , count > previousBest
6  ]
7  where
8    counts = map tally [1..]
9    bestsBefore = scanl max 0 counts

把每个 nn 的原像数量组成惰性流，scanl max 0 counts 在同一位置给出此前最大值。当前数量严格超过此前记录时，nn 就是新的高欧拉函数数。它把“计算计数”和“寻找记录”拆成两个独立步骤。

方法三：有限前缀一次性统计

 1import qualified Data.Map.Strict as Map
 2
 3highlyTotientNumbersUpTo :: Integer -> [Integer]
 4highlyTotientNumbersUpTo limit
 5  | limit < 1 = []
 6  | otherwise = records 0 [(n, count n) | n <- [1..limit]]
 7  where
 8    searchLimit = maximum (map upperBound [1..limit])
 9    histogram = Map.fromListWith (+)
10      [(totient' x, 1 :: Int) | x <- [1..searchLimit]]
11    count n = Map.findWithDefault 0 n histogram
12
13    records _ [] = []
14    records best ((n, occurrences):rest)
15      | occurrences > best = n : records occurrences rest
16      | otherwise = records best rest

若只需要不超过 limit 的前缀，可以先取这些目标值所需安全上界的最大值，再把每个 xx 的欧拉函数值一次性加入直方图。与前两种方法对每个 nn 重新扫描不同，这里每个候选 xx 只计算一次。

方法对比

方法特点
递归记录逐个计算并立即输出，控制流直接
流式筛选scanl 维护此前最大值，组合性好
有限直方图一次统计整个前缀，适合已知上限

测试

1>>> take 10 highlyTotientNumbers
2[1,2,4,8,12,24,48,72,144,240]
3>>> highlyTotientNumbersUpTo 12
4[1,2,4,8,12]

参考