login
A337300
Partial sums of the geometric Connell sequence A049039.
4
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
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
KEYWORD
nonn,easy
AUTHOR
Kevin Ryde, Aug 22 2020
STATUS
approved