cp's OEIS Frontend

A255071 Number of steps required to reach (2^n)-2 from 2^(n+1)-2 by iterating the map x -> x - (number of runs in binary representation of x).

%I A255071 #33 Mar 06 2015 04:31:47
%S A255071 1,2,3,5,9,16,29,53,97,178,328,608,1134,2126,4001,7552,14292,27115,
%T A255071 51565,98274,187657,358982,687944,1320793,2540702,4896919,9456143,
%U A255071 18291753,35435799,68731296,133436379,259238717,503912508,979923792,1906297165,3709809375,7222584181
%N A255071 Number of steps required to reach (2^n)-2 from 2^(n+1)-2 by iterating the map x -> x - (number of runs in binary representation of x).
%F A255071 a(n) = A255072((2^(n+1))-2) - A255072((2^n)-2).
%F A255071 a(n) = A255061(n+1) - A255061(n).
%F A255071 a(n) = A255125(n) + A255126(n).
%F A255071 a(n) = A255063(n) + A255064(n).
%F A255071 Other identities and observations:
%F A255071 It seems that a(n) <= A213709(n) for all n >= 1. A254119 gives the difference between these two sequences.
%F A255071 From _Antti Karttunen_, Feb 21 2015: (Start)
%F A255071 For n>1, a(n-1) = Sum_{k=A255062(n) .. A255061(n+1)} secondmsb(A255056(k)).
%F A255071 Here secondmsb is implemented by the starting offset 2 version of A079944, and effectively gives the second most significant bit in the binary expansion of n. The formula follows from the semi-regular nature of number-of-runs beanstalk, as in the upper half of any next higher range [A255062(n+1) .. A255061(n+2)] of its infinite trunk (A255056), the beanstalk imitates its behavior in the range [A255062(n) .. A255061(n+1)].
%F A255071 (End)
%o A255071 (PARI)
%o A255071 A005811(n) = hammingweight(bitxor(n,n\2));
%o A255071 A255071(n) = { my(k, i); k = (2^(n+1))-2; i = 1; while(1, k = k - A005811(k); if(!bitand(k+1,k+2),return(i),i++)); };
%o A255071 for(n=1, 48, write("b255071.txt", n, " ", A255071(n)));
%o A255071 (Scheme)
%o A255071 (define (A255071 n) (- (A255072 (- (expt 2 (+ n 1)) 2)) (A255072 (- (expt 2 n) 2))))
%o A255071 (define (A255071shifted n) (add (COMPOSE A079944off2 A255056) (A255062 n) (A255061 (+ 1 n))))
%o A255071 (define (A079944off2 n) (A000035 (floor->exact (/ n (A072376 n))))) ;; Cf.
%o A255071 A079944.
%o A255071 ;; Shifted variant gives: (map A255071shifted (iota 16)) --> (0 1 2 3 5 9 16 29 53 97 178 328 608 1134 2126 4001)
%Y A255071 First differences of A255061 and A255062.
%Y A255071 A255069 gives the first differences of this sequence.
%Y A255071 Cf. A005811, A079944, A236840, A255056, A255120, A255121, A255063, A255064, A255072, A255125, A255126, A254119.
%Y A255071 Analogous sequences: A213709, A219661.
%Y A255071 a(n) differs from A192804(n+1) for the first time at n=11, where a(11) = 328, while A192804(12) = 327.
%K A255071 nonn
%O A255071 1,2
%A A255071 _Antti Karttunen_, Feb 14 2015
%E A255071 a(37) added by _Antti Karttunen_, Feb 19 2015