A339890 Number of odd-length factorizations of n into factors > 1.

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 2, 1, 4, 1, 1, 1, 4, 1, 1, 1, 3, 1, 2, 1, 2, 2, 1, 1, 6, 1, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 5, 1, 1, 2, 5, 1, 2, 1, 2, 1, 2, 1, 8, 1, 1, 2, 2, 1, 2, 1, 6, 2, 1, 1, 5, 1, 1, 1

Offset: 1

Author

Gus Wiseman, Dec 28 2020

Keywords

• nonn

Examples

			The a(n) factorizations for n = 24, 48, 60, 72, 96, 120:
  24      48          60       72          96          120
  2*2*6   2*3*8       2*5*6    2*4*9       2*6*8       3*5*8
  2*3*4   2*4*6       3*4*5    2*6*6       3*4*8       4*5*6
          3*4*4       2*2*15   3*3*8       4*4*6       2*2*30
          2*2*12      2*3*10   3*4*6       2*2*24      2*3*20
          2*2*2*2*3            2*2*18      2*3*16      2*4*15
                               2*3*12      2*4*12      2*5*12
                               2*2*2*3*3   2*2*2*2*6   2*6*10
                                           2*2*2*3*4   3*4*10
                                                       2*2*2*3*5
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000

Crossrefs

The case of set partitions (or n squarefree) is A024429.

The case of partitions (or prime powers) is A027193.

The ordered version is A174726 (even: A174725).

The remaining (even-length) factorizations are counted by A339846.

A000009 counts partitions into odd parts, ranked by A066208.

A001055 counts factorizations, with strict case A045778.

A027193 counts partitions of odd length, ranked by A026424.

A058695 counts partitions of odd numbers, ranked by A300063.

A160786 counts odd-length partitions of odd numbers, ranked by A300272.

A316439 counts factorizations by product and length.

A340101 counts factorizations into odd factors.

A340102 counts odd-length factorizations into odd factors.

Cf. A000700, A002033, A027187, A028260, A074206, A078408, A236914, A320732.

Programs

Maple

g:= proc(n, k, t) option remember; `if`(n>k, 0, t)+
      `if`(isprime(n), 0, add(`if`(d>k, 0, g(n/d, d, 1-t)),
          d=numtheory[divisors](n) minus {1, n}))
    end:
a:= n-> `if`(n<2, 0, g(n$2, 1)):
seq(a(n), n=1..100);  # Alois P. Heinz, Dec 30 2020

Mathematica

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],OddQ@Length[#]&]],{n,100}]

Formula

a(n) + A339846(n) = A001055(n).