login
A293814
Number of partitions of n into distinct nontrivial divisors of n.
5
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 5, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 18, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 1, 0, 3, 0, 0, 0, 13, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 10, 0, 0, 0, 1
OFFSET
0,25
FORMULA
a(n) = [x^n] Product_{d|n, 1 < d < n} (1 + x^d).
a(n) = A211111(n) - 1 for n > 1.
EXAMPLE
a(24) = 2 because 24 has 8 divisors {1, 2, 3, 4, 6, 8, 12, 24} among which 6 are nontrivial divisors {2, 3, 4, 6, 8, 12} therefore we have [12, 8, 4] and [12, 6, 4, 2].
MAPLE
with(numtheory):
a:= proc(n) local b, l; l:= sort([(divisors(n) minus {1, n})[]]):
b:= proc(m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i-1))))
end; forget(b):
b(n, nops(l))
end:
seq(a(n), n=0..100); # Alois P. Heinz, Oct 16 2017
MATHEMATICA
Table[d = Divisors[n]; Coefficient[Series[Product[1 + Boole[d[[k]] != 1 && d[[k]] != n] x^d[[k]], {k, Length[d]}], {x, 0, n}], x, n], {n, 0, 100}]
PROG
(PARI) A293814(n) = { if(!n, return(1)); my(p=1); fordiv(n, d, if(d>1&&d<n, p *= (1 + 'x^d))); polcoeff(p, n); }; \\ Antti Karttunen, Dec 22 2017
(Scheme)
;; Implements a simple backtracking algorithm:
(define (A293814 n) (if (<= n 1) (- 1 n) (let ((s (list 0))) (let fork ((r n) (divs (cdr (proper-divisors n)))) (cond ((zero? r) (set-car! s (+ 1 (car s)))) ((or (null? divs) (> (car divs) r)) #f) (else (begin (fork (- r (car divs)) (cdr divs)) (fork r (cdr divs)))))) (car s))))
(define (proper-divisors n) (reverse (cdr (reverse (divisors n)))))
(define (divisors n) (let loop ((k n) (divs (list))) (cond ((zero? k) divs) ((zero? (modulo n k)) (loop (- k 1) (cons k divs))) (else (loop (- k 1) divs)))))
;; Antti Karttunen, Dec 22 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, Oct 16 2017
STATUS
approved