A342083 Number of chains of strictly inferior divisors from n to 1.

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

Offset

1,6

Comments

We define a divisor d|n to be strictly inferior if d < n/d. Strictly inferior divisors are counted by A056924 and listed by A341674.

These chains have first-quotients (in analogy with first-differences) that are term-wise > their decapitation (maximum element removed). Equivalently, x > y^2 for all adjacent x, y. For example, the divisor chain q = 60/6/2/1 has first-quotients (10,3,2), which are > (6,2,1), so q is counted under a(60).

Also the number of factorizations of n where each factor is greater than the product of all previous factors.

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000

Formula

G.f.: x + Sum_{k>=1} a(k) * x^(k*(k + 1)) / (1 - x^k). - Ilya Gutkovskiy, Nov 03 2021

Example

The a(n) chains for n = 2, 6, 12, 24, 42, 48, 60, 72:
  2/1  6/1    12/1    24/1    42/1      48/1      60/1      72/1
       6/2/1  12/2/1  24/2/1  42/2/1    48/2/1    60/2/1    72/2/1
              12/3/1  24/3/1  42/3/1    48/3/1    60/3/1    72/3/1
                      24/4/1  42/6/1    48/4/1    60/4/1    72/4/1
                              42/6/2/1  48/6/1    60/5/1    72/6/1
                                        48/6/2/1  60/6/1    72/8/1
                                                  60/6/2/1  72/6/2/1
                                                            72/8/2/1
The a(n) factorizations for n = 2, 6, 12, 24, 42, 48, 60, 72:
  2  6    12   24    42     48     60      72
     2*3  2*6  3*8   6*7    6*8    2*30    8*9
          3*4  4*6   2*21   2*24   3*20    2*36
               2*12  3*14   3*16   4*15    3*24
                     2*3*7  4*12   5*12    4*18
                            2*3*8  6*10    6*12
                                   2*3*10  2*4*9
                                           2*3*12

Mathematica

cen[n_]:=If[n==1, {{1}}, Prepend[#, n]&/@Join@@cen/@Select[Divisors[n], #<n/#&]];
Table[Length[cen[n]], {n, 100}]

Crossrefs

The restriction to powers of 2 is A040039.

Not requiring strict inferiority gives A074206 (ordered factorizations).

The weakly inferior version is A337135.

The strictly superior version is A342084.

The weakly superior version is A342085.

The additive version is A342098, or A000929 allowing equality.

A000005 counts divisors.

A001055 counts factorizations.

A003238 counts chains of divisors summing to n-1, with strict case A122651.

A038548 counts inferior (or superior) divisors.

A056924 counts strictly inferior (or strictly superior) divisors.

A067824 counts strict chains of divisors starting with n.

A167865 counts strict chains of divisors > 1 summing to n.

A207375 lists central divisors.

A253249 counts strict chains of divisors.

A334996 counts ordered factorizations by product and length.

A334997 counts chains of divisors of n by length.

A342086 counts chains of divisors with strictly increasing quotients > 1.

- Inferior: A033676, A066839, A072499, A161906.

- Superior: A033677, A070038, A161908.

- Strictly Inferior: A060775, A070039, A333806, A341674.

- Strictly Superior: A048098, A064052, A140271, A238535, A341673.

Cf. A000203, A001248, A002033, A006530, A018819, A020639, A045690, A337105, A342087, A342094, A342095, A342096, A342097.

Sequence in context: A140774 A345345 A056924 * A381452 A316364 A318357

Adjacent sequences: A342080 A342081 A342082 * A342084 A342085 A342086

Keyword

nonn

Author

Gus Wiseman, Feb 28 2021

Status

approved