A330285 The maximum number of arithmetic progressions in a sequence of length n.

0, 0, 1, 3, 7, 12, 20, 29, 41, 55, 72, 90, 113, 137, 164, 194, 228, 263, 303, 344, 390, 439, 491, 544, 604, 666, 731, 799, 872, 946, 1027, 1109, 1196, 1286, 1379, 1475, 1579, 1684, 1792, 1903, 2021, 2140, 2266, 2393, 2525, 2662, 2802, 2943, 3093, 3245, 3402, 3562, 3727

Offset

1,4

Comments

The partial arithmetic density D_n(A) up to n is merely the number of arithmetic progressions, A(s(n)), divided by the total number of nonempty subsets of {s(1), s(2), ..., s(n)}, i.e., A(s(n))/(2^n - 1). As n approaches infinity, D_n(A) converges to zero. Furthermore, the infinite sum of the partial densities for any sequence always converges to the total density D(A). Every infinite arithmetic progression has the same total density, Sum_{n >= 1} a(n)/(2^n - 1) = alpha ~ 1.25568880818612911696845537; sequences with a finite number of progressions have D(A) < alpha; and sequences without any arithmetic progressions have D(A) = 0.

Links

Table of n, a(n) for n=1..53.

Encyclopedia of Mathematics, Density of a sequence

Eric Weisstein's World of Mathematics, Arithmetic Progression

Formula

a(n) = Sum_{i=1..n} Sum_{j=1..i} floor((i - 1)/(j + 1)).

Prog

(PARI) a(n) = sum(i=1, n, sum(j=1, i, floor((i - 1)/(j + 1))))

Crossrefs

Cf. A049988, A130518, A104429, A065825, A092482.

Partial sums of A002541.

Sequence in context: A132273 A130050 A173256 * A002049 A025582 A247556

Adjacent sequences: A330282 A330283 A330284 * A330286 A330287 A330288

Keyword

nonn

Author

Joseph Wheat, Dec 21 2019

Status

approved