;; Copyright 2019 Edward L. Platt <elplatt@alum.mit.edu>

#lang racket

;; This module implements a mixed radix number system using Sylvester's sequence.
;;
;; Examples:
;; 0  -> '()
;; 1  -> '(1)
;; 2  -> '(0 1)
;; 3  -> '(1 1)
;; 4  -> '(0 2)
;; 41 -> '(1 2 6)
;; 42 -> '(0 0 0 1)
;;
;; Numbers are represented as a list of digits. The place value for the ith digit is s_i - 1, where s_i is the ith element
;; of Sylvester's sequence. The first few place values are 1, 2, 6, 42.
;;
;; The ith digit is an integer in [0, s_i).

(provide
 
 ;; Find a given element in Sylvester's sequence
 ;;
 ;; Example:
 ;; > (sylvester 4)
 ;; 1807
 sylvester
 
 ;; Represent an integer as a sylvester-radix number
 ;;
 ;; Example:
 ;; > (make-sylvester-radix 1337)
 ;; '(1 2 5 31)
 make-sylvester-radix
 
 ;; Find the integer value of a sylvester-radix number
 ;;
 ;; Example:
 ;; > (sylvester-radix-value '(1 2 5 31))
 ;; 1337
 sylvester-radix-value
 
 ;; Add two sylvester-radix numbers
 ;;
 ;; Example:
 ;; > (add-sylvester-radix '(1 0 1) '(1 0 2))
 ;; '(0 1 3)
 add-sylvester-radix

 ;; Extend length of sylvester-radix number with zero elements.
 ;;
 ;; Example:
 ;; > ((extend-sylvester-radix 4) '(1 2))
 ;; '(1 2 0 0)
 extend-sylvester-radix)

;; —————————————————————————————————
;; Implementation Section

;; Find the nth element of Sylvester's sequence
;; https://oeis.org/A000058
(define (sylvester n)
  (if (= n 0)
      2
      (let ([last (sylvester (- n 1))])
        (+ (* last last)
           (* -1 last)
           1))))

;; Find the sylvester-radix representation of an integer
(define (make-sylvester-radix n)
  (normalize-sylvester-helper '() 0 n))

;; Find the integer representation of a sylvester-radix number
(define (sylvester-radix-value v)
  (sylvester-radix-value-helper v 0 0))

;; Add two sylvester-radix numbers
(define (add-sylvester-radix v w)
  (normalize-sylvester-radix (add-components v w)))

;; Create procedure to extend list to length n
(define (extend-sylvester-radix n)
  (lambda (v)
    (if (>= (length v) n)
        v
        (append v
                (build-list
                 (- n (length v))
                 (lambda (x) 0))))))

;; Ensure digits are in the required range by carrying surplus value.
(define (normalize-sylvester-radix v)
  (normalize-sylvester-helper v 0 0))

;; Recursively normalize a sylvester-radix number.
;; 
;; remaining: Remaining digits. The first is removed on each recursion.
;; index: The index of the first remaining digit.
;; carry: The total integer value carried from lower places.
(define (normalize-sylvester-helper remaining index carry)
  (let* ([digit (if (empty? remaining) 0 (car remaining))]
        [place-value (- (sylvester index) 1)]
        [value (+ (* place-value digit) carry)]
        [next-place-value (- (sylvester (+ index 1)) 1)]
        [remainder (modulo value next-place-value)])
    (if (and (= carry 0) (empty? remaining))
        null
        (cons (/ remainder place-value)
              (normalize-sylvester-helper
               (if (empty? remaining) '() (cdr remaining))
               (+ index 1)
               (- value remainder))))))

;; Recursively find the value of a sylvester-radix number
;;
;; remaining: The remaining digits. The first is removed on each recursion.
;; index: The index of the first remaining digit.
;; total: The total integer value of non-remaining digits.
(define (sylvester-radix-value-helper remaining index total)
  (if (empty? remaining)
      total
      (let ([digit (car remaining)]
            [place-value (- (sylvester index) 1)])
        (sylvester-radix-value-helper
         (cdr remaining)
         (+ index 1)
         (+ total (* digit place-value))))))

;; Add two lists componentwise
(define (add-components a b)
  (if (and (> (length a) 0) (> (length b) 0))
      (cons (+ (car a) (car b))
            (add-components (cdr a) (cdr b)))
      (if (= 0 (length a))
          b
          a)))