nを1から初めてその2乗を足していき、和が2000を初めて超えたとき和はいくつになるか

与えられた木から・・・の回答例を巡ってたら、「nを1から初めてその2乗を足していき、和が2000を初めて超えたとき和はいくつになるかという問題」をScalaで解いてみた - Onion開発停滞日記 > Achiral に Scan とか Pairwise とか条件変化可能な TakeWhile を入れてみた - NyaRuRuの日記 > プログラミング言語が与える影響 (GrayRecord)

と、辿っていって、


nを1から初めてその2乗を足していき、和が2000を初めて超えたとき和はいくつになるかを考えます。


1からnまでのn^2の和の公式は、

Σn^2 = n(n + 1)(2n + 1)/6

なので、nについて解けば、O(1)で回答が出そうなんですが、面倒なので二分探索でいきます。


探査フェーズは2つ。

  • 1から2,4,8,16...と2乗しながらn(n + 1)(2n + 1)/6 >= 2000として、大体の範囲(2000の場合17〜32)を求めます。
  • そしたら、二分探索開始
    • (17 + 32)/2をして17と32の真ん中を求める。真ん中と比較して、
    • 2000以上ならば、17〜真ん中にターゲットあり。
    • 2000より少なければ、(真ん中 + 1)〜32にターゲットあり。
    • 探索できなくなるまで繰り返す。

するっと、

(define (problem x)
  (define (search1 n f cont)
    (if (f n)
        (cont (+ (/ n 2) 1) n)
        (search1 (* n 2) f cont)))

  (define (search2 a b f)
    (if (= a b)
        a
        (let ((center (quotient (+ a b) 2)))
          (if (f center)
              (search2 a center f)
              (search2 (+ center 1) b f)))))
  (define (sum n)
    (/ (* n (+ n 1) (+ (* n 2) 1)) 6))
  (define (cmp n)
    (>= (sum n) x))
  (sum (search1 1 cmp
                (lambda (a b)
                  (search2 a b cmp)))))

(problem 2000) ; 2109
(problem 20000000000000000) ; 20000112783013600
(problem 2000000000000000000000000000000000) ; 2000000000009444638248241095719654

二分探索はえぇぇ。


(二分探索が優勢らしい)