#lang racket



;;; Задача 1. Да се напише функция mygcd a b, която връща НОД(a, b).

(define (mygcd a b)
  ;; Euclidean algorithm
  (cond
    [(> a b) (mygcd b a)]
    [(= a 0) b]
    [else (mygcd (remainder b a) a)]))



;;; Задача 2. Да се напише функция mymaxdivisor x, която намира най-големия делител d на цялото число x > 1, за който d < x.

(define (mymaxdivisor x)
  ;; We find the smallest divisor, and x divided by it will bring the biggest divisor
  (define (helper s)
    (if (= (remainder x s) 0)
      s
      (helper (+ s 1))))
  (quotient x (helper 2)))



;;; Задача 3. Да се дефинира функция sum-odds a b, която намира сумата на нечетните числа в затворения интервал [a, b].

(define (sum-odds a b)
  (cond
    [(= a b) a]
    [(= (remainder a 2) 0) (sum-odds (+ 1 a) b)]
    [(= (remainder b 2) 0) (sum-odds a (- 1 b))]
    ;; Formula for sum of arithmetic progression, where a_1 = a, a_n = b, n = (b - a) / 2 + 1
    ;; (n = count of odd numbers between a and b)
    [else (* (/ (+ a b) 2) (+ (/ (- b a) 2) 1))]))



;;; Задача 4. Да се дефинира предикат prime? n, който проверява дали естественото число n е просто.

(define (prime? n)
  ;; Finding primes is done with a plethora of optimizations. Here, we check until we reach (sqrt n)
  ;; and we check the value above and below every six numbers. Wikipedia explains these methods in
  ;; further detail: https://en.wikipedia.org/wiki/Primality_test#Simple_methods
  ;; Implementation of my C code: https://gitlab.com/Syndamia/algorithms/-/blob/master/C/IsPrime.c
  (define (helper i maxi)
    (cond
      [(> (- i 1) maxi) #t]
      [(or (= (remainder n (- i 1)) 0) (= (remainder n (+ i 1)) 0)) #f]
      [else (helper (+ i 6) maxi)]))
  ;; Another optimization is to do a couple simple checks which will rule out a lot of numbers
  (cond
    [(<= n 1) #f]
    [(<= n 3) #t]
    [(or (= (remainder n 2) 0) (= (remainder n 3) 0)) #f]
    [else (helper 6 (sqrt n))]))



;;; Задача 5. Да се дефинира функция count-palindromes a b, която намира броя на палиндромите в интервала [a, b], където a и b са цели неотрицателни числа и a<b.

(define (palindrome? n)
  ;; i stores the left side of the digits, and j stores the right side
  (define (helper i j)
    (cond
      [(= i 0) #f]
      [(or (= i j) (= (quotient i 10) j)) #t]
      [else (helper (quotient i 10) (+ (remainder i 10) (* j 10)))]))
  (cond
    [(= n 0) #t]
    [(or (< n 0) (= (remainder n 10) 0)) #f]
    [else (helper n 0)]))

(define (count-palindromes a b)
  (if (> a b)
    0
    (+ (count-palindromes (+ 1 a) b) (if (palindrome? a) 1 0))))



;;; Задача 6. Да се дефинира функция count-divisors n, която чрез линейно итеративен процес намира броя на естествените делители на едно естествено число n.

(define (count-divisors n)
  (define (helper d)
    (cond
      [(< (quotient n 2) d) 0]
      [(= (remainder n d) 0) (+ (helper (add1 d)) 1)]
      [else (helper (add1 d))]))
  (+ (helper 2) 2)) ; We don't need to have checks for 1 and n itself