;;
;; 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
  )
)