|
|
A054519
|
|
Number of increasing arithmetic progressions of nonnegative integers ending in n, including those of length 1 or 2.
|
|
24
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
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)
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1-x)^(-1) * (1 + Sum_{j>=1} x^j/(1-x^j)). - Robert Israel, Oct 15 2015
|
|
EXAMPLE
|
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.
|
|
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
|
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 *)
|
|
PROG
|
(PARI) vector(100, n, n--; sum(k=1, n, n\k) + 1) \\ Altug Alkan, Oct 15 2015
(Magma) [1] cat [&+[Ceiling((k+1)/(i+1)): i in [1..k+1]]: k in [1..60]]; // Marius A. Burtea, Jun 10 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|