cp's OEIS Frontend

A049804 a(n) = n mod 4 + n mod 16 + ... + n mod 4^k, where 4^k <= n < 4^(k+1).

%I A049804 #35 Dec 31 2021 09:29:09
%S A049804 0,0,0,0,1,2,3,0,1,2,3,0,1,2,3,0,2,4,6,4,6,8,10,8,10,12,14,12,14,16,
%T A049804 18,0,2,4,6,4,6,8,10,8,10,12,14,12,14,16,18,0,2,4,6,4,6,8,10,8,10,12,
%U A049804 14,12,14,16,18,0,3,6,9,8,11,14,17,16,19,22
%N A049804 a(n) = n mod 4 + n mod 16 + ... + n mod 4^k, where 4^k <= n < 4^(k+1).
%C A049804 From _Petros Hadjicostas_, Dec 11 2019: (Start)
%C A049804 Conjecture: For b >= 2, consider the function s(n,b) = Sum_{1 <= b^j <= n} (n mod b^j) from p. 8 in Dearden et al. (2011). Then s(b*n + r, b) = b*s(n,b) + r*N(n,b) for 0 <= r <= b-1, where N(n,b) = floor(log_b(n)) + 1 is the number of digits in the base-b representation of n. As initial conditions, we have s(n,b) = 0 for 1 <= n <= b. (This is a generalization of a result by _Robert Israel_ in A049802.)
%C A049804 Here b = 4 and a(n) = s(n,4).
%C A049804 We have N(n,2) = A070939(n), N(n,3) = A081604(n), N(n,4) = A110591(n), and N(n,5) = A110592(n).
%C A049804 If A_b(x) = Sum_{n >= 1} s(n,b)*x^n is the g.f. of the sequence (s(n,b): n >= 1) and the above conjecture is correct, then it can be proved that A_b(x) = b * A_b(x^b) * (1-x^b)/(1-x) + x * ((b-1)*x^b - b*x^(b-1) + 1)/((1-x)^2 * (1-x^b)) * Sum_{k >= 1} x^(b^k). (End)
%H A049804 Metin Sariyar, <a href="/A049804/b049804.txt">Table of n, a(n) for n = 1..32000</a>
%H A049804 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 A049804 From _Petros Hadjicostas_, Dec 11 2019: (Start)
%F A049804 Conjecture: a(4*n+r) = 4*a(n) + r*A110591(n) = 4*a(n) + r*(floor(log_4(n)) + 1) for n >= 1 and r = 0, 1, 2, 3.
%F A049804 If the conjecture above is true, the g.f. A(x) satisfies A(x) = 4*(1 + x + x^2 + x^3)*A(x^4) + x*(1 + 2*x + 3*x^2)/(1 - x^4) * Sum_{k >= 1} x^(4^k). (End)
%p A049804 a:= n-> add(irem(n, 4^j), j=1..ilog[4](n)):
%p A049804 seq(a(n), n=1..105);  # _Petros Hadjicostas_, Dec 13 2019 (after _Alois P. Heinz_'s program for A330358)
%t A049804 Table[n * Floor@Log[4, n] - Sum[Floor[n*4^-k]*4^k, {k, Log[4, n]}], {n, 100}] (* _Metin Sariyar_, Dec 12 2019 *)
%t A049804 a[n_] := Sum[Mod[n, 4^j], {j, 1, Length[IntegerDigits[n, 4]] - 1}];
%t A049804 Array[a, 105] (* _Jean-François Alcover_, Dec 31 2021 *)
%o A049804 (PARI) a(n) = sum(k=1, logint(n, 4), n % 4^k); \\ _Michel Marcus_, Dec 12 2019
%Y A049804 Cf. A049802, A049803, A070939, A081604, A110591, A110592, A330358.
%K A049804 nonn
%O A049804 1,6
%A A049804 _Clark Kimberling_