login
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).
16
1, 2, 3, 5, 9, 16, 29, 53, 97, 178, 328, 608, 1134, 2126, 4001, 7552, 14292, 27115, 51565, 98274, 187657, 358982, 687944, 1320793, 2540702, 4896919, 9456143, 18291753, 35435799, 68731296, 133436379, 259238717, 503912508, 979923792, 1906297165, 3709809375, 7222584181
OFFSET
1,2
FORMULA
a(n) = A255072((2^(n+1))-2) - A255072((2^n)-2).
a(n) = A255061(n+1) - A255061(n).
a(n) = A255125(n) + A255126(n).
a(n) = A255063(n) + A255064(n).
Other identities and observations:
It seems that a(n) <= A213709(n) for all n >= 1. A254119 gives the difference between these two sequences.
From Antti Karttunen, Feb 21 2015: (Start)
For n>1, a(n-1) = Sum_{k=A255062(n) .. A255061(n+1)} secondmsb(A255056(k)).
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)].
(End)
PROG
(PARI)
A005811(n) = hammingweight(bitxor(n, n\2));
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++)); };
for(n=1, 48, write("b255071.txt", n, " ", A255071(n)));
(Scheme)
(define (A255071 n) (- (A255072 (- (expt 2 (+ n 1)) 2)) (A255072 (- (expt 2 n) 2))))
(define (A255071shifted n) (add (COMPOSE A079944off2 A255056) (A255062 n) (A255061 (+ 1 n))))
(define (A079944off2 n) (A000035 (floor->exact (/ n (A072376 n))))) ;; Cf.
;; Shifted variant gives: (map A255071shifted (iota 16)) --> (0 1 2 3 5 9 16 29 53 97 178 328 608 1134 2126 4001)
CROSSREFS
First differences of A255061 and A255062.
A255069 gives the first differences of this sequence.
Analogous sequences: A213709, A219661.
a(n) differs from A192804(n+1) for the first time at n=11, where a(11) = 328, while A192804(12) = 327.
Sequence in context: A022857 A000691 A192804 * A103285 A000049 A000050
KEYWORD
nonn
AUTHOR
Antti Karttunen, Feb 14 2015
EXTENSIONS
a(37) added by Antti Karttunen, Feb 19 2015
STATUS
approved