A337135 a(1) = 1; for n > 1, a(n) = Sum_{d|n, d <= sqrt(n)} a(d).

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

Offset: 1

Author

Ilya Gutkovskiy, Nov 21 2020

Keywords

• nonn

Comments

From Gus Wiseman, Mar 05 2021: (Start)

This sequence counts all of the following essentially equivalent things:

1. Chains of distinct inferior divisors from n to 1, where a divisor d|n is inferior if d <= n/d. Inferior divisors are counted by A038548 and listed by A161906.

2. Chains of divisors from n to 1 whose first-quotients (in analogy with first-differences) are term-wise greater than or equal to their decapitation (maximum element removed). For example, the divisor chain q = 60/4/2/1 has first-quotients (15,2,2), which are >= (4,2,1), so q is counted under a(60).

3. Chains of divisors from n to 1 such that x >= y^2 for all adjacent x, y.

4. Factorizations of n where each factor is greater than or equal to the product of all previous factors.

(End)

Examples

			From _Gus Wiseman_, Mar 05 2021: (Start)
The a(n) chains for n = 1, 2, 4, 12, 16, 24, 36, 60:
  1  2/1  4/1    12/1    16/1      24/1      36/1      60/1
          4/2/1  12/2/1  16/2/1    24/2/1    36/2/1    60/2/1
                 12/3/1  16/4/1    24/3/1    36/3/1    60/3/1
                         16/4/2/1  24/4/1    36/4/1    60/4/1
                                   24/4/2/1  36/6/1    60/5/1
                                             36/4/2/1  60/6/1
                                             36/6/2/1  60/4/2/1
                                                       60/6/2/1
The a(n) factorizations for n = 2, 4, 12, 16, 24, 36, 60:
    2  4    12   16     24     36     60
       2*2  2*6  2*8    3*8    4*9    2*30
            3*4  4*4    4*6    6*6    3*20
                 2*2*4  2*12   2*18   4*15
                        2*2*6  3*12   5*12
                               2*2*9  6*10
                               2*3*6  2*2*15
                                      2*3*10
(End)
		

Links

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

Crossrefs

Cf. A002033, A008578 (positions of 1's), A068108.

The restriction to powers of 2 is A018819.

Not requiring inferiority gives A074206 (ordered factorizations).

The strictly inferior version is A342083.

The strictly superior version is A342084.

The weakly superior version is A342085.

The additive version is A000929, or A342098 forbidding equality.

A000005 counts divisors, with sum A000203.

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 strict factorizations of divisors.

- Inferior: A033676, A066839, A072499, A161906.

- Superior: A033677, A070038, A161908.

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

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

Cf. A001248, A006530, A020639, A040039, A045690, A337105, A342087, A342094, A342095, A342096, A342097.

Programs

Maple

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

Mathematica

a[1] = 1; a[n_] := a[n] = DivisorSum[n, a[#] &, # <= Sqrt[n] &]; Table[a[n], {n, 95}]
(* second program *)
asc[n_]:=Prepend[#,n]&/@Prepend[Join@@Table[asc[d],{d,Select[Divisors[n],#Gus Wiseman, Mar 05 2021 *)

Formula

G.f.: Sum_{k>=1} a(k) * x^(k^2) / (1 - x^k).

a(2^n) = A018819(n). - Gus Wiseman, Mar 08 2021