# [欧拉计划]第12题有什么好的解法

``````(defn solution-12 []
(let [tran-nums (fn [num]
(cons (filterv #(zero? (rem num %)) (range 1 num))
num))]
(loop [n 1
c (count (tran-nums n))]
(if (= c 500)
n
(recur (inc n)
(count (tran-nums (inc n))))))))
``````

http://pe-cn.github.io/12/

1 个赞

1 个赞

28 的因数有 `1 2 4 7 14 28`，注意这里没要求质因数，14 怎會小于 sqrt 28，別被帶偏了

1 个赞

`24: 1 2 3 4 6 8 12 24` 这算不算反例

sqrt 24 = 4.8

1 < 4.8

2 < 4.8

3 < 4.8

4 < 4.8

6 和 4，8 和 3，12 和 2，24 和 1 是一对。

1 个赞

1 个赞

(1) 通过单边的缩放，d(n) >= 2^m，你只能得到一个下限，不可能同时得到下限和上限。不过这里限定了「第一个 d(n) 不少于 500」，所以设这么一个上限，结果数字也在里面了，所以说歪打误着。显然 2^499 正好有 500 个因数，但它远大于这个上限了。

(2) 然而，这个下限也是错的。

2^8 < 500 这个缩放，把任何一个满足 n > 2^8 的 n 替换掉 500 也不会影响得到这个下限。然而，第一个 d(n) >= 256 的正整数 n 是 1081080 = 2^3 * 3^3 * 5 * 7 * 11 * 13；不过 n = 256 不满足 n > 2^8, 可能不太好，那么我们看 n = 257 的情况，第一个 d(n) >= 257 的正整数 n 是 1441440 = 2^5 * 3^2 * 5 * 7 * 11 * 13.

2 个赞

``````module Main where
import Data.List (find)

main = print \$ pair
where pair = find ((500 <) . fst) \$ map (factors `pd` id) \$ (triToStream . tri) initial

pd f g = \n -> (f n, g n)

-- smallest tri num larger than
tri :: Int -> Int
tri p = ceiling \$ (sqrt (fromIntegral \$ p * 8 + 1) - 1) / 2

triToStream :: Int -> [Int]
triToStream n = (a : aux a n)
where a = (n * (n + 1)) `div` 2
aux a n = (a + n + 1 : aux (a + n + 1) (n + 1))

factors :: Int -> Int
factors n =  2 * (aux mid 0) - if n `div` mid == mid then 1 else 0
where mid = ((floor . sqrt) (fromIntegral n))
aux 1 acc = acc + 1
aux a acc = aux (a - 1) (acc + if mod n a == 0 then 1 else 0)

initial :: Int
initial = 9699690
``````

``````(define (factors n)
(let* ([mid (floor (sqrt n))]
[half (let loop ((a mid)
(acc 1))
(if (= a 1)
acc
(loop (1- a) (+ acc (if (= (mod n a) 0)
1
0)))))])
(+ (* 2 half)
(if (= n (* mid mid))
1
0))))

(define (problem12 n)
(let loop ((x (/ (* (+ n 1) n) 2))
(n (1+ n)))
(if (< 500 (factors x))
x
(loop (+ x n) (1+ n)))))
``````
``````> (time (problem12 1393))
(time (problem12 1393))
811 collections
1.646439303s elapsed cpu time, including 0.012281831s collecting
1.647140000s elapsed real time, including 0.013833000s collecting
6842787616 bytes allocated, including 6842210896 bytes reclaimed
``````

Scheme 也用方括号。主要 loop … recur 和 Scheme 的 let loop 结构也差不多，下意识就写出来 Scheme 了