The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A051336 Number of arithmetic progressions in {1,2,3,...,n}, including trivial arithmetic progressions of lengths 1 and 2. 4
 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 (list; graph; refs; listen; history; text; internal format)
 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): ; a(2): ,,[1,2]; a(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]]}, 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, p == 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 22 17:14 EDT 2023. Contains 365531 sequences. (Running on oeis4.)