A339846 Number of even-length factorizations of n into factors > 1.

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

Offset

1,12

Links

Antti Karttunen, Table of n, a(n) for n = 1..65537

Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

Index entries for sequences computed from exponents in factorization of n

Formula

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

Example

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

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=1, 1, g(n$2, 0)):
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], EvenQ@Length[#]&]], {n, 100}]

Prog

(PARI) A339846(n, m=n, e=1) = if(1==n, e, sumdiv(n, d, if((d>1)&&(d<=m), A339846(n/d, d, 1-e)))); \\ Antti Karttunen, Oct 22 2023

Crossrefs

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

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

The ordered version is A174725, odd: A174726.

The odd-length factorizations are counted by A339890.

A001055 counts factorizations, with strict case A045778.

A001358 lists semiprimes, with squarefree case A006881.

A027187 counts partitions of even length, ranked by A028260.

A058696 counts partitions of even numbers, ranked by A300061.

A316439 counts factorizations by product and length.

A340102 counts odd-length factorizations into odd factors.

Cf. A002033, A007716, A027193, A050320, A058695, A074206, A236913, A320655, A320656, A320732.

Sequence in context: A083537 A231353 A135830 * A029353 A064922 A303337

Adjacent sequences: A339843 A339844 A339845 * A339847 A339848 A339849

Keyword

nonn

Author

Gus Wiseman, Dec 28 2020

Extensions

Data section extended up to a(105) by Antti Karttunen, Oct 22 2023

Status

approved