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
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).
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
KEYWORD
nonn,easy,nice
AUTHOR
John W. Layman, Nov 02 1999
STATUS
approved