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

%I #73 Oct 24 2023 12:56:36

%S 1,3,7,13,22,33,48,65,86,110,138,168,204,242,284,330,381,434,493,554,

%T 621,692,767,844,929,1017,1109,1205,1307,1411,1523,1637,1757,1881,

%U 2009,2141,2282,2425,2572,2723,2882,3043,3212,3383,3560,3743,3930,4119

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

%C 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)

%C 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

%H T. D. Noe, <a href="/A051336/b051336.txt">Table of n, a(n) for n = 1..1000</a>

%H Marcel K. Goh, Jad Hamdan, and Jonah Saks, <a href="https://arxiv.org/abs/2106.05949">The lattice of arithmetic progressions</a>, arXiv:2106.05949 [math.CO], 2021.

%H Daniel Hoying, <a href="/A051336/a051336.txt">Proof of recurrence relation</a>, May 19 2020.

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

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

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

%F From _Daniel Hoying_, May 15 2020: (Start)

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

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

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

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

%e a(1): [1];

%e a(2): [1],[2],[1,2];

%e a(3): [1],[2],[3],[1,2],[1,3],[2,3],[1,2,3].

%t nmax = 48; t = Table[ DivisorSigma[0, n], {n, 1, nmax}]; Accumulate[ Accumulate[t]+1] - Accumulate[t] (* _Jean-François Alcover_, Nov 08 2011 *)

%t With[{c=Accumulate[DivisorSigma[0,Range[50]]]},Accumulate[c+1]-c] (* _Harvey P. Dale_, Dec 23 2015 *)

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

%o (Python)

%o from math import isqrt

%o 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

%Y Cf. A078567.

%Y Cf. A006218, A143127.

%Y See A078651 and A366471 for GPs.

%K nonn,easy,nice

%O 1,2

%A _John W. Layman_, Nov 02 1999