login
A051336
Number of increasing arithmetic progressions in {1,2,3,...,n}, including trivial arithmetic progressions of lengths 1 and 2.
8
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 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
LINKS
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 *)
PROG
(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
CROSSREFS
Cf. A078567.
See A078651 and A366471 for GPs.
Sequence in context: A155354 A136219 A078582 * A253896 A002623 A173196
KEYWORD
nonn,easy,nice
AUTHOR
John W. Layman, Nov 02 1999
STATUS
approved