A326334 Number of sortable factorizations of n.

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, 1, 4, 1, 4, 2, 2, 1, 7, 2, 2, 3, 4, 1, 4, 1, 7, 2, 2, 2, 8, 1, 2, 2, 7, 1, 4, 1, 4, 4, 2, 1, 12, 2, 4, 2, 4, 1, 7, 2, 7, 2, 2, 1, 8, 1, 2, 4, 11, 2, 4, 1, 4, 2, 4, 1, 14, 1, 2, 4, 4, 2, 4, 1, 12, 5, 2, 1, 8, 2, 2

Offset

1,4

Comments

A factorization into factors > 1 is sortable if there is a permutation (c_1,...,c_k) of the factors such that the maximum prime factor (in the standard factorization of an integer into prime numbers) of c_i is at most the minimum prime factor of c_{i+1}. For example, the factorization (6*8*27) is sortable because the permutation (8,6,27) satisfies the condition.

Links

Table of n, a(n) for n=1..86.

Formula

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

Example

The a(180) = 16 sortable factorizations:
  (2*2*3*3*5)  (2*2*5*9)   (4*5*9)   (2*90)   (180)
               (2*3*5*6)   (2*2*45)  (4*45)
               (3*3*4*5)   (2*5*18)  (5*36)
               (2*2*3*15)  (2*6*15)  (12*15)
                           (3*4*15)
                           (3*5*12)
Missing from this list are the following unsortable factorizations:
  (2*3*3*10)  (5*6*6)   (3*60)
              (2*3*30)  (6*30)
              (2*9*10)  (9*20)
              (3*3*20)  (10*18)
              (3*6*10)

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], OrderedQ[Join@@Sort[First/@FactorInteger[#]&/@#, OrderedQ[PadRight[{#1, #2}]]&]]&]], {n, 100}]

Crossrefs

Factorizations are A001055.

Unsortable factorizations are A326291.

Sortable integer partitions are A326333.

Cf. A058681, A326211, A326212, A326237, A326258, A326332.

Sequence in context: A317141 A317791 A318559 * A218320 A355030 A305254

Adjacent sequences: A326331 A326332 A326333 * A326335 A326336 A326337

Keyword

nonn

Author

Gus Wiseman, Jun 27 2019

Status

approved