A347050 Number of factorizations of n that are a twin (x*x) or have an alternating permutation.

1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 4, 1, 2, 2, 4, 1, 4, 1, 4, 2, 2, 1, 6, 2, 2, 2, 4, 1, 5, 1, 5, 2, 2, 2, 9, 1, 2, 2, 6, 1, 5, 1, 4, 4, 2, 1, 10, 2, 4, 2, 4, 1, 6, 2, 6, 2, 2, 1, 11, 1, 2, 4, 7, 2, 5, 1, 4, 2, 5, 1, 15, 1, 2, 4, 4, 2, 5, 1, 10, 4, 2, 1, 11, 2

Offset: 1

Author

Gus Wiseman, Oct 15 2021

Keywords

• nonn

Comments

First differs from A348383 at a(216) = 27, A348383(216) = 28.

A factorization of n is a weakly increasing sequence of positive integers > 1 with product n.

These permutations are ordered factorizations of n with no adjacent triples (..., x, y, z, ...) where x <= y <= z or x >= y >= z.

The version without twins for n > 0 is a(n) + 1 if n is a perfect square; otherwise a(n).

Examples

			The factorizations for n = 4, 12, 24, 30, 36, 48, 60, 64, 72:
  4    12     24     30     36       48       60       64       72
  2*2  2*6    3*8    5*6    4*9      6*8      2*30     8*8      8*9
       3*4    4*6    2*15   6*6      2*24     3*20     2*32     2*36
       2*2*3  2*12   3*10   2*18     3*16     4*15     4*16     3*24
              2*2*6  2*3*5  3*12     4*12     5*12     2*4*8    4*18
              2*3*4         2*2*9    2*3*8    6*10     2*2*16   6*12
                            2*3*6    2*4*6    2*5*6    2*2*4*4  2*4*9
                            3*3*4    3*4*4    3*4*5             2*6*6
                            2*2*3*3  2*2*12   2*2*15            3*3*8
                                     2*2*3*4  2*3*10            3*4*6
                                              2*2*3*5           2*2*18
                                                                2*3*12
                                                                2*2*3*6
                                                                2*3*3*4
                                                                2*2*2*3*3
The a(270) = 19 factorizations:
  (2*3*5*9)   (5*6*9)   (3*90)   (270)
  (3*3*5*6)   (2*3*45)  (5*54)
  (2*3*3*15)  (2*5*27)  (6*45)
              (2*9*15)  (9*30)
              (3*3*30)  (10*27)
              (3*5*18)  (15*18)
              (3*6*15)  (2*135)
              (3*9*10)
Note that (2*3*3*3*5) is separable but has no alternating permutations.
		

Crossrefs

Partitions not of this type are counted by A344654, ranked by A344653.

Partitions of this type are counted by A344740, ranked by A344742.

The complement is counted by A347706, without twins A348380.

The case without twins is A348379.

Dominates A348383, the separable case.

A001055 counts factorizations, strict A045778, ordered A074206.

A001250 counts alternating permutations.

A008480 counts permutations of prime indices, strict A335489.

A025047 counts alternating or wiggly compositions, ranked by A345167.

A056239 adds up prime indices, row sums of A112798.

A325534 counts separable partitions, ranked by A335433.

A325535 counts inseparable partitions, ranked by A335448.

A335452 counts anti-run permutations of prime indices, complement A336107.

A339846 counts even-length factorizations.

A339890 counts odd-length factorizations.

Cf. A038548, A049774, A102726, A119620, A128761, A344614, A347437, A347438, A347458, A348381.

Programs

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],Function[f,Select[Permutations[f],!MatchQ[#,{_,x_,y_,z_,_}/;x<=y<=z||x>=y>=z]&]!={}]]],{n,100}]

Formula

For n > 1, a(n) = A335434(n) + A010052(n).