A293814 - OEIS

%I #13 Dec 26 2017 13:44:47

%S 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 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 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 Number of partitions of n into distinct nontrivial divisors of n.

%H Antti Karttunen, <a href="/A293814/b293814.txt">Table of n, a(n) for n = 0..16384</a>

%H <a href="/index/Par#part">Index entries for sequences related to partitions</a>

%F a(n) = [x^n] Product_{d|n, 1 < d < n} (1 + x^d).

%F a(n) = A211111(n) - 1 for n > 1.

%e 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 with(numtheory):

%p a:= proc(n) local b, l; l:= sort([(divisors(n) minus {1, n})[]]):

%p       b:= proc(m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,

%p              b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i-1))))

%p           end; forget(b):

%p       b(n, nops(l))

%p     end:

%p seq(a(n), n=0..100);  # _Alois P. Heinz_, Oct 16 2017

%t 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 (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 (Scheme)

%o ;; Implements a simple backtracking algorithm:

%o (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 (define (proper-divisors n) (reverse (cdr (reverse (divisors n)))))

%o (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 ;; _Antti Karttunen_, Dec 22 2017

%Y Cf. A027750, A033630, A070824, A065205, A211111, A293813.

%K nonn

%O 0,25

%A _Ilya Gutkovskiy_, Oct 16 2017