A337300 Partial sums of the geometric Connell sequence A049039.

1, 3, 7, 12, 19, 28, 39, 51, 65, 81, 99, 119, 141, 165, 191, 218, 247, 278, 311, 346, 383, 422, 463, 506, 551, 598, 647, 698, 751, 806, 863, 921, 981, 1043, 1107, 1173, 1241, 1311, 1383, 1457, 1533, 1611, 1691, 1773, 1857, 1943, 2031, 2121, 2213, 2307, 2403

Offset

1,2

Comments

a(n) is Newey's "more complicated" conjectured length of the shortest sequence containing all permutations of 1..n (A062714). It agrees with A062714(n) for n <= 7.

Links

Kevin Ryde, Table of n, a(n) for n = 1..5000

Malcolm Newey, Notes On a Problem Involving Permutations As Subsequences, Stanford Artificial Intelligence Laboratory, Memo AIM-190, STAN-CS-73-340, 1973. Conjectured M(n) formula bottom of page 12.

Formula

a(n) = n^2 - k*n + F(k) where k = floor(log_2(n)) and F(0) = 0 then F(k) = k + 2*F(k-1) [Newey], which is F(k) = 2^(k+1) - k - 2 = A000295(k+1), the Eulerian numbers.

a(n) = n^2 - k*(n+1) + 2*(2^k - 1) where k = floor(log_2(n)).

G.f.: 2*x/(1-x)^3 - ( Sum_{j>=0} x^(2^j) )/(1-x)^2.

a(n) = Sum_{i=1..n} A049039(i). - Gerald Hillier, Jun 18 2016

Prog

(PARI) a(n) = my(k=logint(n, 2)); n^2 - k*(n+1) + (2<<k) - 2;

Crossrefs

Cf. A049039 (first differences), A122793 (arithmetic Connell sums).

Sequence in context: A025742 A122793 A062714 * A039677 A011899 A002498

Adjacent sequences: A337297 A337298 A337299 * A337301 A337302 A337303

Keyword

nonn,easy

Author

Kevin Ryde, Aug 22 2020

Status

approved