A342085 Number of decreasing chains of distinct superior divisors starting with n.

1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 5, 1, 2, 2, 6, 1, 5, 1, 4, 2, 2, 1, 11, 2, 2, 3, 4, 1, 7, 1, 10, 2, 2, 2, 15, 1, 2, 2, 10, 1, 6, 1, 4, 5, 2, 1, 26, 2, 5, 2, 4, 1, 11, 2, 10, 2, 2, 1, 21, 1, 2, 5, 20, 2, 6, 1, 4, 2, 7, 1, 39, 1, 2, 5, 4, 2, 6, 1, 23, 6, 2, 1

Offset

1,4

Comments

We define a divisor d|n to be superior if d >= n/d. Superior divisors are counted by A038548 and listed by A161908.

These chains have first-quotients (in analogy with first-differences) that are term-wise less than or equal to their decapitation (maximum element removed). Equivalently, x <= y^2 for all adjacent x, y. For example, the divisor chain q = 24/8/4/2 has first-quotients (3,2,2), which are less than or equal to (8,4,2), so q is counted under a(24).

Also the number of ordered factorizations of n where each factor is less than or equal to the product of all previous factors.

Links

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

Formula

a(2^n) = A045690(n).

Example

The a(n) chains for n = 2, 4, 8, 12, 16, 20, 24, 30, 32:
  2  4    8      12      16        20       24         30       32
     4/2  8/4    12/4    16/4      20/5     24/6       30/6     32/8
          8/4/2  12/6    16/8      20/10    24/8       30/10    32/16
                 12/4/2  16/4/2    20/10/5  24/12      30/15    32/8/4
                 12/6/3  16/8/4             24/6/3     30/6/3   32/16/4
                         16/8/4/2           24/8/4     30/10/5  32/16/8
                                            24/12/4    30/15/5  32/8/4/2
                                            24/12/6             32/16/4/2
                                            24/8/4/2            32/16/8/4
                                            24/12/4/2           32/16/8/4/2
                                            24/12/6/3
The a(n) ordered factorizations for n = 2, 4, 8, 12, 16, 20, 24, 30, 32:
  2  4    8      12     16       20     24       30     32
     2*2  4*2    4*3    4*4      5*4    6*4      6*5    8*4
          2*2*2  6*2    8*2      10*2   8*3      10*3   16*2
                 2*2*3  2*2*4    5*2*2  12*2     15*2   4*2*4
                 3*2*2  4*2*2           3*2*4    3*2*5  4*4*2
                        2*2*2*2         4*2*3    5*2*3  8*2*2
                                        4*3*2    5*3*2  2*2*2*4
                                        6*2*2           2*2*4*2
                                        2*2*2*3         4*2*2*2
                                        2*2*3*2         2*2*2*2*2
                                        3*2*2*2

Maple

a:= proc(n) option remember; 1+add(`if`(d>=n/d,
      a(d), 0), d=numtheory[divisors](n) minus {n})
    end:
seq(a(n), n=1..128);  # Alois P. Heinz, Jun 24 2021

Mathematica

cmo[n_]:=Prepend[Prepend[#, n]&/@Join@@cmo/@Select[Most[Divisors[n]], #>=n/#&], {n}];
Table[Length[cmo[n]], {n, 100}]

Crossrefs

The restriction to powers of 2 is A045690.

The inferior version is A337135.

The strictly inferior version is A342083.

The strictly superior version is A342084.

The additive version is A342094, with strict case A342095.

The additive version not allowing equality is A342098.

A001055 counts factorizations.

A003238 counts divisibility chains 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.

A074206 counts strict chains of divisors from n to 1 (also ordered factorizations).

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.

- Inferior: A033676, A066839, A072499, A161906.

- Superior: A033677, A070038, A161908, A341676.

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

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

Cf. A000203, A001248, A005117, A006530, A020639, A057567, A057568, A112798, A169594, A337105, A342096, A342097.

Sequence in context: A112970 A112971 A299201 * A050379 A344589 A153024

Adjacent sequences: A342082 A342083 A342084 * A342086 A342087 A342088

Keyword

nonn

Author

Gus Wiseman, Feb 28 2021

Status

approved