A051336 Number of increasing 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

Author

John W. Layman, Nov 02 1999

Keywords

• nonn
• easy
• nice

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 algorithm known for generating a(n) from scratch has order O(sqrt(n)) (see below). If a(n-1) is known, it reduces to O(n^(1/3)). - Daniel Hoying, May 20 2020

Examples

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

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.

Crossrefs

Cf. A078567.

Cf. A006218, A143127.

See A078651 and A366471 for GPs.

Programs

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 *)

Python

from math import isqrt
def A051336(n): return (((s:=isqrt(n-1))*(s+1))**2>>2)+(1-s**2)*n+sum((q:=(n-1)//k)*(2*n-k*(1+q)) for k in range(1, s+1)) # Chai Wah Wu, Oct 21 2023

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)