OFFSET
1,5
COMMENTS
There is the following connection between this sequence and A080277: A080277(n) = n + n*floor(log_2(n)) - a(n). Since A080277(n) is the solution to a prototypical recurrence in the analysis of the algorithm Merge Sort, that is, T(0) := 0, T(n) := 2*T(floor(n/2)) + n, the sequence a(n) seems to be the major obstacle when trying to find a simple, sum-free solution to this recurrence. It seems hard to get rid of the sum. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 21 2006
When n = 2^k with k > 0 then a(n+1) = k. For this reason, when n-1 is a Mersenne prime then n - 1 = M(p) = 2^p - 1 = 2^a(n+1) - 1 and p = a(n+1) is prime. - David Morales Marciel, Oct 23 2015
LINKS
Metin Sariyar, Table of n, a(n) for n = 1..32000 (terms 1..1000 from Paolo P. Lava)
B. Dearden, J. Iiams, and J. Metzger, A Function Related to the Rumor Sequence Conjecture, J. Int. Seq. 14 (2011), #11.2.3, Example 7.
FORMULA
From Robert Israel, Oct 23 2015: (Start)
a(2*n) = 2*a(n).
a(2*n+1) = 2*a(n) + A070939(n) for n >= 1.
G.f. A(x) satisfies A(x) = 2*(1+x)*A(x^2) + (x/(1-x^2))*Sum_{i>=1} x^(2^i). (End)
MAPLE
f:= proc(n) option remember; local m;
if n::even then 2*procname(n/2)
else m:= (n-1)/2; 2*procname(m) + ilog2(m) + 1
fi
end proc:
f(1):= 0:
map(f, [$1..1000]); # Robert Israel, Oct 23 2015
MATHEMATICA
Table[n * Floor@Log[2, n] - Sum[Floor[n*2^-k]*2^k, {k, Log[2, n]}], {n, 100}] (* Federico Provvedi, Aug 17 2013 *)
PROG
(PARI) a(n) = sum(k=1, logint(n, 2), n % 2^k); \\ Michel Marcus, Dec 12 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved