A284466 Number of compositions (ordered partitions) of n into odd divisors of n.

1, 1, 1, 2, 1, 2, 6, 2, 1, 20, 8, 2, 60, 2, 10, 450, 1, 2, 726, 2, 140, 3321, 14, 2, 5896, 572, 16, 26426, 264, 2, 394406, 2, 1, 226020, 20, 51886, 961584, 2, 22, 2044895, 38740, 2, 20959503, 2, 676, 478164163, 26, 2, 56849086, 31201, 652968, 184947044, 980, 2, 1273706934, 6620376, 153366, 1803937344

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2000

Index entries for sequences related to compositions

Formula

a(n) = [x^n] 1/(1 - Sum_{d|n, d positive odd} x^d).

a(n) = 1 if n is a power of 2.

a(n) = 2 if n is an odd prime.

Example

a(10) = 8 because 10 has 4 divisors {1, 2, 5, 10} among which 2 are odd {1, 5} therefore we have [5, 5], [5, 1, 1, 1, 1, 1], [1, 5, 1, 1, 1, 1], [1, 1, 5, 1, 1, 1], [1, 1, 1, 5, 1, 1], [1, 1, 1, 1, 5, 1], [1, 1, 1, 1, 1, 5] and [1, 1, 1, 1, 1, 1, 1, 1, 1, 1].

Maple

with(numtheory):
a:= proc(n) option remember; local b, l;
      l, b:= select(x-> is(x:: odd), divisors(n)),
      proc(m) option remember; `if`(m=0, 1,
         add(`if`(j>m, 0, b(m-j)), j=l))
      end; b(n)
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Mar 30 2017

Mathematica

Table[d = Divisors[n]; Coefficient[Series[1/(1 - Sum[Boole[Mod[d[[k]], 2] == 1] x^d[[k]], {k, Length[d]}]), {x, 0, n}], x, n], {n, 0, 57}]

Prog

(Python)
from sympy import divisors
from sympy.core.cache import cacheit
@cacheit
def a(n):
    l=[x for x in divisors(n) if x%2]
    @cacheit
    def b(m): return 1 if m==0 else sum(b(m - j) for j in l if j <= m)
    return b(n)
print([a(n) for n in range(61)]) # Indranil Ghosh, Aug 01 2017, after Maple code

Crossrefs

Cf. A000045, A005408, A032021, A100346, A171565.

Sequence in context: A133644 A265870 A341409 * A258615 A152431 A143965

Adjacent sequences: A284463 A284464 A284465 * A284467 A284468 A284469

Keyword

nonn

Author

Ilya Gutkovskiy, Mar 27 2017

Status

approved