2013-11-10

級数と再帰

LISP

順列・組み合わせ・重複組み合わせの通りの数は $_nP_r = n\times _{n-1}P_{r-1}, _nC_r = _{n-1}C_{r-1} + _{n-1}C_r,_rH_n = _nH_{r-1} + _{n-1}H_r$ なので

(define perm
 (lambda (n r)
  (cond ((= r 0) 1)
        ((= r 1) n)
        (else (* n (perm (- n 1) (- r 1)))) )))
(define comb
 (lambda (n r)
  (cond ((= r 0) 1)
        ((= r n) 1)
        (else (+ (comb (- n 1) (- r 1)) (comb (- n 1) r))))))
(define rept
 (lambda (n r)
  (cond ((= r 0) 1)
        ((= n 1) 1)
        (else (+ (rept n (- r 1)) (rept (- n 1) r))))))
(define n! (lambda (n) (perm n n)))

> (perm 5 3)
60
> (comb 5 3)
10
> (rept 5 3)
35
> (n! 5)
120

ゼータ関数 $\zeta(k) = \sum_{n=1}^{\infty} \frac{1}{n^k}$

> (define nums (iota 6))
(apply + (map / (map * nums nums)))
(exact->inexact (apply + (map / (map * nums nums))))

1 1769/3600
1.4913888888888889
> (define nums (iota 100))
(apply + (map / (map * nums nums)))

1 617322549698656842522639951844930715540407914547963618106712480098300144925121901/972186144434381030589657976672623144161975583995746241782720354705517986165248000
> (exact->inexact (apply + (map / (map * nums nums))))

1.6349839001848927

$\zeta(2)=\frac{\pi^2}{6},\zeta(4)=\frac{\pi^4}{90},\zeta{6}=\frac{\pi^6}{945}$

> (define nums (iota 100))

(exact->inexact (apply + (map / (map * nums nums))))
(exact->inexact (apply + (map / (map * nums nums nums nums))))
(exact->inexact (apply + (map / (map * nums nums nums nums nums nums))))
(define pi (* 4 (atan 1)))
(/ (** pi 2) 6)
(/ (** pi 4) 90)
(/ (** pi 6) 945)

1.6349839001848927
1.0823229053444732
1.0173430619649442
1.6449340668482264
1.082323233711138
1.017343061984449

交代級数 $1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}=\sum_{i=1}^{\infty}(-1)^{i+1}\times \frac{1}{i}$

(begin
 (define num-x (iota 1000))
 (define parity-of (lambda (p) (if (odd? p) -1 1)))
 (define parity-x (map parity-of num-x))
 (define terms (map / (map * (map - parity-x) num-x)))
 (* 1.0 (apply + terms)))
(log 2)
(define prototype
 (lambda (n k)
  (if (> n k)
   0
   (+ (/ 1.0 (* (** -1 (- n 1)) n))
    (prototype (++ n) k)) )))

0.6926474305598204
0.6931471805599453

> (prototype 1 1000)
0.6926474305598203

$\sum$ 記号処理が表す総和とは

(define sum
 (lambda (initial final body)
  (if (> initial final)
   0
   (+ (body initial)
      (sum (++ initial) final body) ))))
(define log2
 (lambda (n) ( / (** -1 (- n 1)) n)))
(* 1.0 (sum 1 1000 log2))
(exact->inexact (sum 1 1000 log2))
(log 2)

$\sum_{i=0}^{\infty} \frac{(-1)^n}{2n+1}=\frac{\pi}{4}$

(define leibniz
 (lambda (n) (/ (** -1 n) (+ (* 2 n) 1) )))
(sum 0 1000 leibniz)
(exact->inexact (sum 0 1000 leibniz))
(/ pi 4)

115942754151379749817711499381045829538776769987994283426499174405197859288323135015330300912135070917816946458268092800852360239620177277413429787387349551255003615589569573379800196665329506848656083889369709177405427782467224427236659450935894659229706538420713135430149967239530040710861446951911777821474393129612397845507403965163361525407992992632094863429705101531309515395981444782245447089519458224628701225883500761695065661112790727759938282092270127334705631552774809895098881487984328201218643687326889146827085154438452729289541791425462272951568049058813743132462586534037658186884976579734076397974087562265189907855568091436223915148765419793957077042562861450986938251183985051264149570092106286182764399032728528708672749045573389234562924779885205262978316936978847078635153915075455692080484634049862051993120512957807952166632232781452985693/147575971560004214167515926110910959154039364114823574124246000461914527658542221342892735221356393498040967787373958507841987262911496051590667501531330247838135978840974443799253538292640926269840668436150204200349824875106342825692216080195797882561278687544853408492239067897668276741020722024722920647043361291050258670152054452602340630932745172382890465777119545919256355735334085680330696670323581795898987569556701349947230648600924724829339703465619153667400785835767829015255912124437120483654244048802954353182627323647253464533187610294513012889059213560214079942586690820627448621251921400116373405117084193399206770968054536747884759653724084204389207798419572074824626227112973906822764943279686533643894351344307463662830610651081788025023698731546719066865315845423963070220368816149003349877146224784348331677667520210577535211126744546685023125
0.7856479135848857
0.7853981633974483

ゼータ関数 $\frac{i=1}^{\infty} \frac{1}{i^k}$

(define zeta2
 (lambda (n) (/ (** n 2))))
(exact->inexact (sum 1 1000 zeta2))
(define zeta-k
 (lambda (k) (lambda (n) (/ (** n k)))))
(exact->inexact (sum 1 1000 (zeta-k 2)))
(exact->inexact (sum 1 1000 (zeta-k 6)))

が表す乗積を
- それを使って $\prod_{i=1}^{\infty} \frac{2i}{2i+1}\frac{2i+2}{2i+2}=\frac{\pi}{4}$

(define product
 (lambda (initial final body)
  (if (> initial final)
   1
   (* (body initial)
      (product (++ initial) final body) ))))
(define pi/4
 (lambda (n)
  (* (/ (* 2 n) (+ (* 2 n) 1)) (/ (+ (* 2 n) 2) (+ (* 2 n) 1)))))
(* 4.0 (product 1 1000 pi/4))

- 階乗 $n!$

(define fact
 (lambda (i) (if (= i 0) 1 i)))
(product 0 10 fact)

累積処理として統一化する

(define accumulate
 (lambda (op ini seqs)
  (if (null? seqs)
   ini
   (op (car seqs)
       (accumulate op ini (cdr seqs))))))
(define sum
 (lambda (ini fin body)
  (accumulate + 0 (map body (iota ini fin)))))
(define product
 (lambda (ini fin body)
  (accumulate * 1 (map body (iota ini fin)))))
(define num (lambda (i) i))
(sum 0 100 num)
(product 1 10 num)

ネイピア数 $e=\sum_{i=0}^{\infty} \frac{1}{i!}$ は

(define napier
 (lambda (n)
  (/ (product 0 n fact))))
(exact->inexact (sum 0 10 napier))
(exp 1)

十分近いことをもって正しいと判断して抜き出す

(define pow2?
 (lambda (x)
  (let ((y (inexact->exact (round (** x 1/2)))))
   (if (= x (** y 2)) #t #f) )))
(pow2? 121)

(define pow3?
 (lambda (x)
  (let ((y (inexact->exact (round (** x 1/3)))))
   (if (= x (** y 3)) #t #f))))
(filter pow3? (iota 1000))