A329110 Number of integer sequences 1 <= b_1 < b_2 < ... < b_t <= n such that b_i divides b_(i+1) for all 0 < i < t.

1, 3, 5, 9, 11, 17, 19, 27, 31, 37, 39, 55, 57, 63, 69, 85, 87, 103, 105, 121, 127, 133, 135, 175, 179, 185, 193, 209, 211, 237, 239, 271, 277, 283, 289, 341, 343, 349, 355, 395, 397, 423, 425, 441, 457, 463, 465, 561, 565, 581, 587, 603, 605, 645, 651, 691

Offset

1,2

Comments

Cumulative sum of A067824.

Links

Peter Kagey, Table of n, a(n) for n = 1..10000

Mathematics Stack Exchange user Markus Scheuer, Finding the number of subsets of a set such that an element divides the succeeding element.

Formula

From Vaclav Kotesovec, Mar 18 2021: (Start)

a(n) ~ -2*n^r/(r*zeta'(r)), where r=A107311 is the root of the equation zeta(r)=2.

a(n) ~ 2*A247667 * n^A107311 / A107311.

a(n) ~ 2*A217598 * n^A107311. (End)

Example

For n = 4 the a(4) = 9 sequences are 1; 1, 2; 1, 2, 4; 1, 3; 1, 4; 2; 2, 4; 3; and 4.

Prog

(PARI) s=0; for (n=1, #(z=vector(56)), print1 (s += z[n]=1+sumdiv(n, k, if (k<n, z[k], 0)) ", ")) \\ Rémy Sigrist, Nov 08 2019

Crossrefs

Cf. A067824.

Sequence in context: A258165 A076193 A056533 * A114186 A117992 A015614

Adjacent sequences: A329107 A329108 A329109 * A329111 A329112 A329113

Keyword

nonn

Author

Peter Kagey, Nov 04 2019

Status

approved