A286851 Number of compositions (ordered partitions) of n into unitary divisors of n.

1, 1, 2, 2, 2, 2, 25, 2, 2, 2, 129, 2, 170, 2, 742, 450, 2, 2, 4603, 2, 1503, 3321, 29967, 2, 9278, 2, 200390, 2, 13460, 2, 154004511, 2, 2, 226020, 9262157, 51886, 127654, 2, 63346598, 2044895, 170354, 2, 185493291001, 2, 1304512, 567124, 2972038875, 2, 59489916, 2, 20367343494, 184947044, 14324735, 2

Offset

0,3

Links

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

Eric Weisstein's World of Mathematics, Unitary Divisor

Index entries for sequences related to compositions

Formula

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

a(n) = 2 if n is a prime power (A246655).

Example

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

Maple

a:= proc(n) option remember; local b, l; l, b:=
      select(x-> igcd(x, n/x)=1, numtheory[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, Aug 01 2017

Mathematica

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

Prog

(Python)
from sympy import divisors, gcd
from sympy.core.cache import cacheit
@cacheit
def a(n):
    l=[x for x in divisors(n) if gcd(x, n//x)==1]
    @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. A066874, A100346, A246655, A284463, A284464, A284465, A284466.

Sequence in context: A029627 A075182 A292023 * A320017 A289087 A378134

Adjacent sequences: A286848 A286849 A286850 * A286852 A286853 A286854

Keyword

nonn

Author

Ilya Gutkovskiy, Aug 01 2017

Status

approved