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).

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

Links

Table of n, a(n) for n=1..37.

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.
A079944.
;; 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.

Cf. A005811, A079944, A236840, A255056, A255120, A255121, A255063, A255064, A255072, A255125, A255126, A254119.

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

Adjacent sequences: A255068 A255069 A255070 * A255072 A255073 A255074

Keyword

nonn

Author

Antti Karttunen, Feb 14 2015

Extensions

a(37) added by Antti Karttunen, Feb 19 2015

Status

approved