A051336 Number of arithmetic progressions in {1,2,3,...,n}, including trivial arithmetic progressions of lengths 1 and 2.

1, 3, 7, 13, 22, 33, 48, 65, 86, 110, 138, 168, 204, 242, 284, 330, 381, 434, 493, 554, 621, 692, 767, 844, 929, 1017, 1109, 1205, 1307, 1411, 1523, 1637, 1757, 1881, 2009, 2141, 2282, 2425, 2572, 2723, 2882, 3043, 3212, 3383, 3560, 3743, 3930, 4119

Offset

1,2

Comments

The number of arithmetic subsequences of [1, ..., n] with successive-term increment i and length k is (n-i*(k-1))(i > 0, k > 0, n > i*(k-1)). - Robert E. Sawyer (rs.1(AT)mindspring.com)

The best known algorithm to generate a(n) from scratch is O(sqrt(n)) (see below). If a(n-1) is known, it reduces to O(n^(1/3)). - Daniel Hoying, May 20 2020

Links

T. D. Noe, Table of n, a(n) for n = 1..1000

Marcel K. Goh, Jad Hamdan, and Jonah Saks, The lattice of arithmetic progressions, arXiv:2106.05949 [math.CO], 2021.

Daniel Hoying, Proof of recurrence relation, May 19 2020.

Formula

Theorem: the second differences give tau(n+1), the number of divisors of n+1 (A000005).

a(n) = n + A078567(n).

a(n) = n + Sum_{ i=1..n-1, j=1..floor(n/i) } (n - i*j). - Robert E. Sawyer (rs.1(AT)mindspring.com)

From Daniel Hoying, May 15 2020: (Start)

a(n+1) = a(n) + 1 + Sum_{i=1..n} tau(i).

= a(n) + 1 + A006218(n+1).

a(n+1) = (n + 1)*(1 + Sum_{i=1..n} floor(n/i)) - Sum_{i=1..n} i*tau(i).

= (n + 1)*(1 + A006218(n)) - A143127(n). (End)

Example

a(1): [1];
a(2): [1],[2],[1,2];
a(3): [1],[2],[3],[1,2],[1,3],[2,3],[1,2,3].

Mathematica

nmax = 48; t = Table[ DivisorSigma[0, n], {n, 1, nmax}]; Accumulate[ Accumulate[t]+1] - Accumulate[t] (* Jean-François Alcover, Nov 08 2011 *)
With[{c=Accumulate[DivisorSigma[0, Range[50]]]}, Accumulate[c+1]-c] (* Harvey P. Dale, Dec 23 2015 *)
nmax = 50; RecurrenceTable[{a[n] == a[n-1]+1+p[n], p[n] == p[n-1]+DivisorSigma[0, n-1], a[1] == 1, p[1] == 0}, {a, p}, {n, 1, nmax}][[All, 1]] (* Daniel Hoying, May 16 2020 *)

Crossrefs

Cf. A078567.

Cf. A006218, A143127.

Sequence in context: A155354 A136219 A078582 * A253896 A002623 A173196

Adjacent sequences: A051333 A051334 A051335 * A051337 A051338 A051339

Keyword

nonn,easy,nice

Author

John W. Layman, Nov 02 1999

Status

approved