112 lines
2.5 KiB
Common Lisp
112 lines
2.5 KiB
Common Lisp
|
(defun binomial (n k)
|
||
|
|
(cond
|
||
|
|
((= k 0) 1)
|
||
|
|
((= n k) 1)
|
||
|
|
(t (+ (binomial (- n 1) k) (binomial (- n 1) (- k 1))))))
|
||
|
|
|
||
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
||
|
|
|
||
|
|
|
||
|
|
(defun next_row (row)
|
||
|
|
(mapcar #'+ (append '(0) row) (append row '(0))))
|
||
|
|
|
||
|
|
(defun generate_pascal_row (n current_row)
|
||
|
|
(if (= n 0)
|
||
|
|
current_row
|
||
|
|
(generate_pascal_row (- n 1) (next_row current_row))))
|
||
|
|
|
||
|
|
(defun generate_pascal (n)
|
||
|
|
(generate_pascal_row n '(1)))
|
||
|
|
|
||
|
|
(defun binomial2 (n k)
|
||
|
|
(nth k (generate_pascal n)))
|
||
|
|
|
||
|
|
|
||
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
||
|
|
|
||
|
|
(defun empty_or_singleton (list)
|
||
|
|
(or (null list) (null (cdr list))))
|
||
|
|
|
||
|
|
(defun right_half (list)
|
||
|
|
(last list (ceiling (/ (length list) 2))))
|
||
|
|
(defun left_half (list)
|
||
|
|
(ldiff list (right_half list)))
|
||
|
|
|
||
|
|
(defun mergelists (list1 list2)
|
||
|
|
(merge 'list list1 list2 #'<))
|
||
|
|
(defun mergesort (list)
|
||
|
|
(if (empty_or_singleton list) list
|
||
|
|
(mergelists
|
||
|
|
(mergesort (left_half list))
|
||
|
|
(mergesort (right_half list)))))
|
||
|
|
|
||
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
||
|
|
|
||
|
|
(defun gcde (a b)
|
||
|
|
(if (= a 0)
|
||
|
|
(values b 0 1)
|
||
|
|
(multiple-value-bind (g x y)
|
||
|
|
(gcde (mod b a) a)
|
||
|
|
(values g (- y (* (floor b a) x)) x))))
|
||
|
|
|
||
|
|
(defun de (a b)
|
||
|
|
(multiple-value-bind (x y g)
|
||
|
|
(gcde a b)
|
||
|
|
(values x y g)))
|
||
|
|
|
||
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
||
|
|
|
||
|
|
(defun factorize (n factor)
|
||
|
|
(cond
|
||
|
|
((= 1 n) nil)
|
||
|
|
((= 0 (mod n factor)) (cons factor (factorize (/ n factor) factor)))
|
||
|
|
(t (factorize n (+ factor 1)))))
|
||
|
|
|
||
|
|
|
||
|
|
(defun prime_factors (n)
|
||
|
|
(factorize n 2))
|
||
|
|
|
||
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
||
|
|
|
||
|
|
(defun _gcd (a b)
|
||
|
|
(if (= a 0) b
|
||
|
|
(_gcd (mod b a) a)))
|
||
|
|
|
||
|
|
(defun is_coprime (a b)
|
||
|
|
(= (_gcd a b) 1))
|
||
|
|
|
||
|
|
(defun totient_helper (n i)
|
||
|
|
(cond ((= i n) (if (is_coprime n i) 1 0))
|
||
|
|
((is_coprime n i) (1+ (totient_helper n (1+ i))))
|
||
|
|
(t (totient_helper n (1+ i)))))
|
||
|
|
|
||
|
|
(defun totient (n)
|
||
|
|
(totient_helper n 1))
|
||
|
|
|
||
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
||
|
|
|
||
|
|
(defun totient2 (n)
|
||
|
|
(let ((unique_factors (remove-duplicates (prime_factors n))))
|
||
|
|
(reduce #'(lambda (acc p) (floor (/ (* acc (- p 1)) p))) unique_factors :initial-value n)))
|
||
|
|
|
||
|
|
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
||
|
|
|
||
|
|
|
||
|
|
(defun prime? (n &optional (divisor 2))
|
||
|
|
(cond ((<= n 1) nil)
|
||
|
|
((= n 2) t)
|
||
|
|
((evenp n) nil)
|
||
|
|
((> divisor (isqrt n)) t)
|
||
|
|
((zerop (mod n divisor)) nil)
|
||
|
|
(t (prime? n (+ divisor 1)))))
|
||
|
|
|
||
|
|
(defun primes_helper (n result)
|
||
|
|
(if (zerop n)
|
||
|
|
result
|
||
|
|
(if (prime? n)
|
||
|
|
(primes_helper (- n 1) (cons n result))
|
||
|
|
(primes_helper (- n 1) result))))
|
||
|
|
|
||
|
|
(defun primes (n)
|
||
|
|
(primes_helper n '()))
|