A054519 Number of increasing arithmetic progressions of nonnegative integers ending in n, including those of length 1 or 2.

1, 2, 4, 6, 9, 11, 15, 17, 21, 24, 28, 30, 36, 38, 42, 46, 51, 53, 59, 61, 67, 71, 75, 77, 85, 88, 92, 96, 102, 104, 112, 114, 120, 124, 128, 132, 141, 143, 147, 151, 159, 161, 169, 171, 177, 183, 187, 189, 199, 202, 208, 212, 218, 220, 228, 232, 240, 244, 248

Offset: 0

Author

Henry Bottomley, Apr 07 2000

Keywords

• easy
• nonn
• nice

Comments

a(0)=1, a(n) = a(n-1) + sigma_0(n) (A000005). - Ctibor O. Zizka, Nov 08 2008

a(n) is the index of the n-th term of A027750 whose value is 1. - Michel Marcus, Oct 15 2015

From Gus Wiseman, Jun 07 2019: (Start)

Also the number of subsets of {1..n} that are closed under taking the difference of two strictly decreasing terms. For example, the a(0) = 1 through a(6) = 15 subsets are:

{} {} {} {} {} {} {}

{1} {1} {1} {1} {1} {1}

{2} {2} {2} {2} {2}

{1,2} {3} {3} {3} {3}

{1,2} {4} {4} {4}

{1,2,3} {1,2} {5} {5}

{2,4} {1,2} {6}

{1,2,3} {2,4} {1,2}

{1,2,3,4} {1,2,3} {2,4}

{1,2,3,4} {3,6}

{1,2,3,4,5} {1,2,3}

{2,4,6}

{1,2,3,4}

{1,2,3,4,5}

{1,2,3,4,5,6}

(End)

Examples

			a(3)=6 because the six increasing progressions (3), (2,3), (1,2,3), (0,1,2,3), (1,3) and (0,3) all end in 3.
		

Links

• Marius A. Burtea, Table of n, a(n) for n = 0..10000 (term 0..1000 from T. D. Noe).
• Wikipedia, Arithmetic progression

Crossrefs

Cf. A000005, A006218, A027750, A051336. Left edge of A056535.

Cf. A007862, A049988, A175342, A238423, A295370, A325849.

Programs

Magma

[1] cat [&+[Ceiling((k+1)/(i+1)): i in [1..k+1]]: k in [1..60]]; // Marius A. Burtea, Jun 10 2019

Maple

IBI:= {{}}: a[0]:= 1: for n from 1 to 45 do IBI:= IBI union map(t -> t union {n}, select(t -> (t minus map(q -> n-q, t)={}), IBI)); a[n]:= nops(IBI) od: seq(a[n], n=0..45); # Zerinvary Lajos, Mar 18 2007
with(numtheory):a[1]:=2: for n from 2 to 59 do a[n]:=a[n-1]+tau(n) od: seq(a[n], n=0..45); # Zerinvary Lajos, Mar 21 2009
map(`+`, ListTools:-PartialSums(map(numtheory:-tau, [$0..1000])),1); # Robert Israel, Oct 15 2015

Mathematica

a[0]=1; a[n_] := a[n] = a[n-1] + DivisorSigma[0, n]; Table[a[n], {n, 0, 45}] (* Jean-François Alcover, Oct 05 2012, after Ctibor O. Zizka *)
nxt[{n_,a_}]:={n+1,a+DivisorSigma[0,n+1]}; Transpose[NestList[nxt,{0,1},50]][[2]] (* Harvey P. Dale, Oct 15 2012 *)
Table[Length[Select[Subsets[Range[n]],SubsetQ[#,Subtract@@@Reverse/@Subsets[#,{2}]]&]],{n,0,10}] (* Gus Wiseman, Jun 07 2019 *)

PARI

vector(100, n, n--; sum(k=1, n, n\k) + 1) \\ Altug Alkan, Oct 15 2015

Formula

a(n) = A051336(n+1) - A051336(n) = a(n-1) + A000005(n) = A006218(n)+1.

G.f.: (1-x)^(-1) * (1 + Sum_{j>=1} x^j/(1-x^j)). - Robert Israel, Oct 15 2015

a(n) = Sum_{i=1..n+1} ceiling((n+1)/(i+1)). - Wesley Ivan Hurt, Sep 15 2017