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

Author

Kevin Ryde, Aug 22 2020

Keywords

• nonn
• easy

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. [But not for n=8. - Pontus von Brömssen, Aug 18 2025]

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.

Crossrefs

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

Programs

PARI

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

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