|
%I #17 Feb 25 2022 07:04:12
%S 1,3,7,12,19,28,39,51,65,81,99,119,141,165,191,218,247,278,311,346,
%T 383,422,463,506,551,598,647,698,751,806,863,921,981,1043,1107,1173,
%U 1241,1311,1383,1457,1533,1611,1691,1773,1857,1943,2031,2121,2213,2307,2403
%N Partial sums of the geometric Connell sequence A049039.
%C 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.
%H Kevin Ryde, <a href="/A337300/b337300.txt">Table of n, a(n) for n = 1..5000</a>
%H Malcolm Newey, <a href="http://i.stanford.edu/TR/CS-TR-73-340.html">Notes On a Problem Involving Permutations As Subsequences</a>, Stanford Artificial Intelligence Laboratory, Memo AIM-190, STAN-CS-73-340, 1973. Conjectured M(n) formula bottom of page 12.
%F 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.
%F a(n) = n^2 - k*(n+1) + 2*(2^k - 1) where k = floor(log_2(n)).
%F G.f.: 2*x/(1-x)^3 - ( Sum_{j>=0} x^(2^j) )/(1-x)^2.
%F a(n) = Sum_{i=1..n} A049039(i). - _Gerald Hillier_, Jun 18 2016
%o (PARI) a(n) = my(k=logint(n,2)); n^2 - k*(n+1) + (2<<k) - 2;
%Y Cf. A049039 (first differences), A122793 (arithmetic Connell sums).
%K nonn,easy
%O 1,2
%A _Kevin Ryde_, Aug 22 2020
|
