Archive for the ‘hayashi’ Tag

projecteuler27

projecteuler27

 projecteuler問題27は、二次方程式

n^2 + an + b, where |a| < 1000 and |b| < 1000

において、n = 0 から素数が続く数が最大となる係数を探し出し、その積を求めるもの。
 何も考えずに力ずくで求めるスクリプトは、

(define (func n a b)
  (+ b (* a n) (* n n)))
(setq lst '() len 1)
(for (i -999 999)
  (for (j -999 999)
    (let (k 0 res '() flag true)
       (while flag
         (let (ans (func k i j))
            (if(and (> ans 0) (= 1 (length (factor ans)))) (push (list k i j) res -1)
                (setq flag nil)))
           (++ k))
    (when (> (length res) len) (setq len (length res)) (push res lst -1)))))
(lst -1 -1)
(apply * (1 (lst -1 -1)))

 これを実行すると

(lambda (n a b) (+ b (* a n) (* n n)))
1
nil
(70 -61 971)
-59231
> 

 こんな感じで答え -59231 が求まります。
 この時の二次方程式は

n^2 - 61n + 971

 で n = 0 ~ 70 で 71 個の素数が作られます。
 実際に計算してみると、

> (map (hayashi func -61 971) (sequence 0 70))
(971 911 853 797 743 691 641 593 547 503 461 421 383 347 313 281 251 223 197 173 
 151 131 113 97 83 71 61 53 47 43 41 41 43 47 53 61 71 83 97 113 131 151 173 197 
 223 251 281 313 347 383 421 461 503 547 593 641 691 743 797 853 911 971 1033 1097 
 1163 1231 1301 1373 1447 1523 1601)
> 

 こんな感じ。
 ここで関数 hayashi は拙作で、(newlisp-utility.lsp にあります)

(hayashi func -61 971)

 は以下の式等価です。

(fn (x) (func x -61 971))

 以上、如何でしょうか?

広告

projecteuler24

 projecteuler問題24は、辞書的順列問題。0 から 9 までの数字を組み合わせた10桁の数値を辞書的に並べ、百万番目を求めるもの。
 当然一番目は 0123456789 。先頭が 0 である数は

 9! = 362880 個。

 とすれば、

1000000 - 2*362880 = 274240

 となり、解答は先頭が 2 の 274240 番目。
 こんな風に各桁を求めれば、解答に行く着くはず。
 これを関数にすれば

(define (make-ans cnt lst, (res '()))
  (-- cnt)
  (while (> cnt 0)
    (let (cm (apply * (sequence 1 (-- (length lst)))))
      (push (pop lst (/ cnt cm)) res -1)
      (setq cnt (% cnt cm))))
  (apply string (if lst (append res lst) res)))

 実際に試すと、

> (make-ans 1 (sequence 0 9))
"0123456789"
> (make-ans 362880 (sequence 0 9))
"0987654321"
> (make-ans 362881 (sequence 0 9))
"1023456789"
> (make-ans 1000000 (sequence 0 9))
"2783915460"
> 

 こんな感じ。
 ちなみ、例題にある 0 から 2 の三桁も

> (map (hayashi make-ans (sequence 0 2)) '(1 2 3 4 5 6))
("012" "021" "102" "120" "201" "210")
> (map (fn (x) (make-ans x (sequence 0 2))) '(1 2 3 4 5 6))
("012" "021" "102" "120" "201" "210")
> 

 この通り。
 hayashi は拙作の関数で二番目以降の引数を curry のように扱える関数で、newlisp-utility.lsp に置いてあります。
 以上、如何でしょうか?