cp's OEIS Frontend

A049802 a(n) = n mod 2 + n mod 4 + ... + n mod 2^k, where 2^k <= n < 2^(k+1).

%I A049802 #62 May 15 2025 08:23:27
%S A049802 0,0,1,0,2,2,4,0,3,4,7,4,7,8,11,0,4,6,10,8,12,14,18,8,12,14,18,16,20,
%T A049802 22,26,0,5,8,13,12,17,20,25,16,21,24,29,28,33,36,41,16,21,24,29,28,33,
%U A049802 36,41,32,37,40,45,44,49,52,57,0,6,10,16,16
%N A049802 a(n) = n mod 2 + n mod 4 + ... + n mod 2^k, where 2^k <= n < 2^(k+1).
%C A049802 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
%C A049802 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
%H A049802 Metin Sariyar, <a href="/A049802/b049802.txt">Table of n, a(n) for n = 1..32000</a> (terms 1..1000 from Paolo P. Lava)
%H A049802 B. Dearden, J. Iiams, and J. Metzger, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Dearden/dearden3r.html">A Function Related to the Rumor Sequence Conjecture</a>, J. Int. Seq. 14 (2011), #11.2.3, Example 7.
%F A049802 From _Robert Israel_, Oct 23 2015: (Start)
%F A049802 a(2*n) = 2*a(n).
%F A049802 a(2*n+1) = 2*a(n) + A070939(n) for n >= 1.
%F A049802 G.f. A(x) satisfies A(x) = 2*(1+x)*A(x^2) + (x/(1-x^2))*Sum_{i>=1} x^(2^i). (End)
%p A049802 f:= proc(n) option remember; local m;
%p A049802     if n::even then 2*procname(n/2)
%p A049802     else m:= (n-1)/2; 2*procname(m) + ilog2(m) + 1
%p A049802     fi
%p A049802 end proc:
%p A049802 f(1):= 0:
%p A049802 map(f, [$1..1000]); # _Robert Israel_, Oct 23 2015
%t A049802 Table[n * Floor@Log[2,n] - Sum[Floor[n*2^-k]*2^k, {k, Log[2,n]}], {n, 100}] (* _Federico Provvedi_, Aug 17 2013 *)
%o A049802 (PARI) a(n) = sum(k=1, logint(n, 2), n % 2^k); \\ _Michel Marcus_, Dec 12 2019
%o A049802 (Python) def a(n): return sum(n % 2**k for k in range(n.bit_length())) # _David Radcliffe_, May 14 2025
%Y A049802 Cf. A049803, A049804, A070939, A080277, A330358.
%K A049802 nonn
%O A049802 1,5
%A A049802 _Clark Kimberling_