cp's OEIS Frontend

A293814 Number of partitions of n into distinct nontrivial divisors of n.

%I A293814 #13 Dec 26 2017 13:44:47
%S A293814 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,
%T A293814 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,
%U A293814 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
%N A293814 Number of partitions of n into distinct nontrivial divisors of n.
%H A293814 Antti Karttunen, <a href="/A293814/b293814.txt">Table of n, a(n) for n = 0..16384</a>
%H A293814 <a href="/index/Par#part">Index entries for sequences related to partitions</a>
%F A293814 a(n) = [x^n] Product_{d|n, 1 < d < n} (1 + x^d).
%F A293814 a(n) = A211111(n) - 1 for n > 1.
%e A293814 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].
%p A293814 with(numtheory):
%p A293814 a:= proc(n) local b, l; l:= sort([(divisors(n) minus {1, n})[]]):
%p A293814       b:= proc(m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
%p A293814              b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i-1))))
%p A293814           end; forget(b):
%p A293814       b(n, nops(l))
%p A293814     end:
%p A293814 seq(a(n), n=0..100);  # _Alois P. Heinz_, Oct 16 2017
%t A293814 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}]
%o A293814 (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
%o A293814 (Scheme)
%o A293814 ;; Implements a simple backtracking algorithm:
%o A293814 (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))))
%o A293814 (define (proper-divisors n) (reverse (cdr (reverse (divisors n)))))
%o A293814 (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)))))
%o A293814 ;; _Antti Karttunen_, Dec 22 2017
%Y A293814 Cf. A027750, A033630, A070824, A065205, A211111, A293813.
%K A293814 nonn
%O A293814 0,25
%A A293814 _Ilya Gutkovskiy_, Oct 16 2017