;; ;; https://oeis.org/A077565/a077565.txt ;; ;; Scheme-program for computing Amarnath Murthy's A077565 in https://oeis.org/A077565 ;; A077565 [Murthy] o=1: Number of factorizations of n where each factor has a different prime signature. ;; ;; Written by Antti Karttunen, 2017-10-24. ;; ;; ;; This code is for demonstration. ;; You need also implementations of A000040, A008966, A046523 to run it. ;; See e.g. under https://github.com/karttu/IntSeq ;; ;; For n = 30 the solutions are 30, 2*15, 3*10, 5*6, thus a(30) = 4. ;; For n = 36 the solutions are 36, 2*18, 3*12, thus a(36) = 3. ;; For n = 60 the solutions are 60, 2*30, 3*20, 4*15, 5*12, thus a(60) = 5. ;; For n = 72 the solutions are 72, 2*36, 3*24, 4*18, 6*12, 8*9, 3*4*6, thus a(72) = 7. (definec (A077565 n) (if (< (A046523 n) n) (A077565 (A046523 n)) ;; Use the cached value. (let ((allsigs (list 0))) (let fork ((sigmult 1) (m 1) (divs (proper-divisors n))) (cond ((= m n) (attach! sigmult allsigs)) ;; We found a valid factorization, add sigmult mask to allsigs ((or (null? divs) (> (* (car divs) m) n)) #f) ;; Bum, we didn't find a valid partition, return (else (begin (let ((pm (A000040 (A046523 (car divs))))) (fork (* pm sigmult) (* m (car divs)) (cdr divs)) (fork sigmult m (cdr divs)) ;; And/or just skip this divisor without using it. ) ) ) ) ) (length (remove (lambda (sig) (or (zero? sig) (zero? (A008966 sig)))) allsigs)) ;; Only squarefree sigs are counted. ) ) ) (define (proper-divisors n) (let loop ((k n) (divs (list))) (cond ((= 1 k) divs) ((zero? (modulo n k)) (loop (- k 1) (cons k divs))) (else (loop (- k 1) divs)) ) ) ) (define attach! ;; The name is borrowed from old Franz lisp, is like destructive cons. (lambda (elem lista) (set-cdr! lista (cons (car lista) (cdr lista))) (set-car! lista elem) lista ) )