A337135 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

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)

LINKS

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

FORMULA

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

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

EXAMPLE

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)

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], #<n&&#<=n/#&]}], {}]; Table[Length[Select[asc[n], MemberQ[#, 1]&]], {n, 100}] (* Gus Wiseman, Mar 05 2021 *)

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.