A255125 Number of times a multiple of four is encountered when iterating from 2^(n+1)-2 to (2^n)-2 with the map x -> x - (number of runs in binary representation of x).

1, 0, 1, 1, 1, 3, 6, 13, 26, 47, 81, 140, 253, 482, 949, 1875, 3666, 7088, 13614, 26100, 50082, 96246, 185131, 356123, 684758, 1316197, 2530257, 4868019, 9378335, 18096921, 34974646, 67669905, 130998912, 253565649, 490501587, 947992195, 1830664188, 3533571444

Offset: 0

Author

Antti Karttunen, Feb 18 2015

Keywords

• nonn

Comments

Also the number of even numbers in range [A255062(n) .. A255061(n+1)] of A255057 (equally, in A255067). See the sum-formulas.

Examples

			For n=5 we start iterating with map m(n) = A236840(n) from the initial value (2^(5+1))-2 = 62. Thus we get m(62) = 60, m(60) = 58, m(58) = 54, m(54) = 50, m(50) = 46, m(46) = 42, m(42) = 36, m(36) = 32 and finally m(32) = 30, which is (2^5)-2. Of the nine numbers encountered, only 60, 36 and 32 are multiples of four, thus a(5) = 3.
		

Links

• A. Karttunen, Ratio a(n)/A255126(n) plotted, with the help of OEIS-server

Crossrefs

Cf. A005811, A059841, A133872, A236840, A255056, A255057, A255061, A255062, A255067, A255071, A255126, A255332.

Similar sequences: A218542, A255063.

Programs

PARI

A005811(n) = hammingweight(bitxor(n, n\2));
write_A255125_and_A255126_and_A255071(n) = { my(k, i, s25, s26); k = (2^(n+1))-2; i = 1; s25 = 0; s26 = 0; while(1, if((k%4),s26++,s25++); k = k - A005811(k); if(!bitand(k+1, k+2), break, i++)); write("b255125.txt", n, " ", s25); write("b255126.txt", n, " ", s26); write("b255071.txt", n, " ", i); };
for(n=1,42,write_A255125_and_A255126_and_A255071(n));

Scheme

(define (A255125 n) (if (zero? n) 1 (let loop ((i (- (expt 2 (+ 1 n)) 4)) (s 0)) (cond ((pow2? (+ 2 i)) s) (else (loop (- i (A005811 i)) (+ s (A133872 i))))))))
;; Alternatively:
(define (A255125 n) (add (COMPOSE A059841 A255057) (A255062 n) (A255061 (+ 1 n))))
(define (A255125 n) (add (COMPOSE A059841 A255067) (A255062 n) (A255061 (+ 1 n))))
(define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (1+ i) (+ res (intfun i)))))))

Formula

a(n) = Sum_{k = A255062(n) .. A255061(n+1)} A059841(A255057(k)).

a(n) = Sum_{k = A255062(n) .. A255061(n+1)} A059841(A255067(k)).

a(n) = A255071(n) - A255126(n).