OFFSET
1,2
COMMENTS
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
KEYWORD
nonn,easy
AUTHOR
Kevin Ryde, Aug 22 2020
STATUS
approved