p31.ss

;; P31 (**) Determine whether a given integer number is prime.
;; Example:
;; * (is-prime 7)
;; T

#lang racket

(provide is-prime?)

(define (is-prime? n)
  (and (> n 1)
       (or (= n 2)
           (and (not (zero? (modulo n 2)))
                (let loop ((i 3))
                  (or (> (* i i) n)
                      (and (not (zero? (modulo n i)))
                           (loop (+ i 2)))))))))

p32.ss

;; P32 (**) Determine the greatest common divisor of two positive integer numbers.
;; Use Euclid's algorithm.
;; Example:
;; * (gcd 36 63)
;; 9

(define (gcd a b)
  (let loop ((x a) (y b) (z 1) (w 0))
    (let ((q (quotient x y)) (r (modulo x y)))
      (if (zero? r)
          y
          (loop y r w (- z (* q w)))))))

p33.ss

;; P33 (*) Determine whether two positive integer numbers are coprime.
;; Two numbers are coprime if their greatest common divisor equals 1.
;; Example:
;; * (coprime 35 64)
;; T

#lang racket

(provide coprime?)

(define (coprime? a b)
  (= 1 (gcd a b)))

p34.ss

;; P34 (**) Calculate Euler's totient function phi(m).
;; Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m.
;; Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.

;; * (totient-phi 10)
;; 4

;; Find out what the value of phi(m) is if m is a prime number. Euler's totient function plays an important role in one of the most widely used public key cryptography methods (RSA). In this exercise you should use the most primitive method to calculate this function (there are smarter ways that we shall discuss later).

(require "p33.ss")

(define (totient-phi m)
  (let loop ((r 1) (acc '()))
    (if (> r m)
        (length acc)
        (loop (+ 1 r)
              (if (coprime? r m)
                  (cons r acc)
                  acc)))))

p35.ss

;; P35 (**) Determine the prime factors of a given positive integer.
;; Construct a flat list containing the prime factors in ascending order.
;; Example:
;; * (prime-factors 315)
;; (3 3 5 7)

#lang racket

(provide prime-factors)

(require "p31.ss")

(define (prime-factors n)
  (let loop ((x n) (y 2) (acc '()))
    (cond
     ((= x 1)
      (reverse acc))
     ((and (is-prime? y) (zero? (modulo x y)))
      (loop (/ x y) 2 (cons y acc)))
     (else
      (loop x (+ y 1) acc)))))

p36.ss

;; P36 (**) Determine the prime factors of a given positive integer (2).
;; Construct a list containing the prime factors and their multiplicity.
;; Example:
;; * (prime-factors-mult 315)
;; ((3 2) (5 1) (7 1))
;; Hint: The problem is similar to problem P13.

#lang racket

(provide prime-factors-mult)

(require "p10.ss")
(require "p35.ss")

(define (prime-factors-mult n)
  (map reverse (encode (prime-factors n))))

p37.ss

;; P37 (**) Calculate Euler's totient function phi(m) (improved).
;; See problem P34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem P36 then the function phi(m) can be efficiently calculated as follows: Let ((p1 m1) (p2 m2) (p3 m3) ...) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:
;; phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2 ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ...

;; Note that a ** b stands for the b'th power of a.

(require "p36.ss")

(define (phi m)
  (let loop ((lst (prime-factors-mult m))
             (acc 1))
    (if (null? lst)
        acc
        (let ((p (caar lst))
              (m (- (cadar lst) 1)))
          (loop (cdr lst)
                (* (- p 1) (expt p m) acc))))))

p38.ss

;; P38 (*) Compare the two methods of calculating Euler's totient function.
;; Use the solutions of problems P34 and P37 to compare the algorithms. Take the number of logical inferences as a measure for efficiency. Try to calculate phi(10090) as an example.

> (time (phi 10090))
cpu time: 0 real time: 1 gc time: 0
4032
> (time (totient-phi 10090))
cpu time: 4 real time: 4 gc time: 0
4032
> 

p39.ss

;; P39 (*) A list of prime numbers.
;; Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.

#lang racket

(provide (all-defined-out))

(require srfi/1)

(define (eratosthenes n)
  (let loop ((lst (iota n 3)) (acc '(2)))
    (let ((i (car acc)))
      (if (< (apply max lst) (expt i 2))
          (append (reverse acc) lst)
          (let ((lst (remove (lambda (x)
                               (zero? (modulo x i)))
                             lst)))
            (loop (cdr lst) (cons (car lst) acc)))))))

(define (p39 m n)
  (remove (lambda (x)
            (< x m))
          (eratosthenes n)))

p40.ss

;; P40 (**) Goldbach's conjecture.
;; Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers (much larger than we can go with our Prolog system). Write a predicate to find the two prime numbers that sum up to a given even integer.
;; Example:
;; * (goldbach 28)
;; (5 23)

#lang racket

(provide goldbach)

(require "p39.ss")

(define (goldbach n)
  (and (> n 2) (even? n)
       (let loop ((lst (eratosthenes n)))
         (let ((i (car lst)))
           (let ((j (- n i)))
             (if (member j lst)
                 `(,i ,j)
                 (loop (cdr lst))))))))