|
(Scheme)
; returns all but the last element of a list
(define rdc(lambda(x)(if(null? (cdr x))'()(cons (car x) (rdc (cdr x))))))
; gets the two's complement of a given bit
(define twosComplement (lambda (x)(if (eq? x #\0) "1" "0" )))
; gets the two's complement of a string
(define complementOfCurrent (lambda (x y z)(if (eq? (string-length y) z) y (complementOfCurrent (list->string (cdr (string->list x))) (string-append y (twosComplement (string-ref x 0))) z))))
; concatenates the two's complement of a string onto the current string, giving the next element in the TM sequence
(define concatenateComplement (lambda (x i)(if(zero? i) x (concatenateComplement(string-append x (complementOfCurrent x "" (string-length x)))(- i 1)))))
; generates the TM sequence of length 2^x
(define generateThue (lambda (x)(concatenateComplement "0" x)))
; if a bit is 1, get 2^i, where i is the index of that bit from right-left
(define F (lambda (c i)(if (eq? c #\1) (expt 2 i) 0)))
; gathers the sum of 2^index for all indices corresponding to a 1
(define fn (lambda (x sum i stop)(if (eq? i stop) sum (fn (list->string (rdc (string->list x))) (+ sum (F (string-ref x (-(string-length x) 1)) i)) (+ i 1)stop))))
(define f (lambda (x)(fn (generateThue x) 0 0 (string-length (generateThue x)))))
; format: (f x)
; example: (f 10)
| 