;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; ;; Scheme-program for computing Leroy Quet's A163820. ;; ;; See https://oeis.org/A163820 ;; ;; ;; ;; A163820 Number of permutations of the divisors of n that are greater ;; ;; than 1, in which consecutive elements are not coprime. ;; ;; ;; ;; Written by Antti Karttunen, 2017-10-21. (cleaned Oct 22) ;; ;; ;; ;; The OEIS-sequence data (also defs & programs) has been submitted as per ;; ;; http://oeis.org/wiki/The_OEIS_Contributor's_License_Agreement ;; ;; and it is made available with ;; ;; http://oeis.org/wiki/The_OEIS_End-User_License_Agreement ;; ;; which uses the Creative Commons Attribution Non-Commercial 3.0 license ;; ;; http://creativecommons.org/licenses/by-nc/3.0/ ;; ;; ;; ;; Thus, this source file uses the same CC BY-NC 3.0 license. ;; ;; ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; Because the values of sequence depends only on the prime-signature of n, it is enough ;; to actually compute it only for values of A025487 (least integer of each prime signature). ;; To do that, change the following definition of A163820 to use definec (instead of define) ;; (see http://oeis.org/wiki/Memoization#Scheme for its implementation) ;; and uncomment the lines beginning with ;; in it. ;; An implementation of A046523 can be found under https://github.com/karttu/IntSeq ;; (define (A163820 n) ;; (let ((fr (A046523 n))) ;; (if (< fr n) ;; If the first representative of this prime signature is < n, ;; (A163820 fr) ;; then dig the result from the memoized cache. (use definec!) (let ((pds (proper-divisors n))) ;; Otherwise, actually do some heavy work. (fold-left (lambda (s d) (+ s (A163820apu d (delete d pds)))) 0 pds ) ) ;; ) ;; ) ) ;; Gives the number of possible ways to construct a list that begins with d ;; and which is then followed by some other divisor e found from rest-of-divs ;; such that gcd(d,e) > 1, and that gcd(e,f) > 1, gcd(f,g) > 1, etc. where ;; f, g, etc. are the rest of divisors in the arrangement. ;; This is still very straightforward. ;; (How about a more intelligent algorithm, by traversing in the divisor-lattice of n? ;; Also any possibilities (other than the one mentioned above about prime-signatures) for ;; more clever divide-and-conquer/dynamic programming ?) ;; (define (A163820apu d rest-of-divs) (if (null? rest-of-divs) ;; If no more divisors, then we have found one way to arrange divisors. 1 (let ((pnos (remove (lambda (e) (= 1 (gcd d e))) rest-of-divs))) ;; pnos = possible next-ones (successors) ;; (if (null? (cdr rest-of-divs)) ;; (length pnos) ;; An optimization for cases where only one divisor left. (Hardly an optimization at all?) (let loop ((possible-next-ones pnos) (s 0) ) (cond ((null? possible-next-ones) s) ;; Finished the list of possible-next-ones, return the sum. (else (loop (cdr possible-next-ones) (+ s (A163820apu (car possible-next-ones) (delete (car possible-next-ones) rest-of-divs) ) ) ) ) ) ) ;; ) ) ) ) (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 (divisors n) (cons 1 (proper-divisors n)))