A079944 -id:A079944 - 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).

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

Antti Karttunen, Feb 14 2015

nonn

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.

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

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

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)

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

A086799 Replace all trailing 0's with 1's in binary representation of n.

Original entry on oeis.org

1, 3, 3, 7, 5, 7, 7, 15, 9, 11, 11, 15, 13, 15, 15, 31, 17, 19, 19, 23, 21, 23, 23, 31, 25, 27, 27, 31, 29, 31, 31, 63, 33, 35, 35, 39, 37, 39, 39, 47, 41, 43, 43, 47, 45, 47, 47, 63, 49, 51, 51, 55, 53, 55, 55, 63, 57, 59, 59, 63, 61, 63, 63, 127, 65, 67, 67, 71, 69, 71

Offset: 1

Reinhard Zumkeller, Aug 05 2003

a(k+1) = smallest number greater than k having in its binary representation exactly one 1 more than k has; A000120(a(n)) = A063787(n). - Reinhard Zumkeller, Jul 31 2010
a(n) is the least m >= n-1 such that the Hamming distance D(n-1,m) = 1. - Vladimir Shevelev, Apr 18 2012
The number of appearances of k equals the 2-adic valuation of k+1. - Ali Sada, Dec 20 2024

			a(20) = a('10100') = '10100' + '11' = '10111' = 23.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Binary Carry Sequence
Eric Weisstein's World of Mathematics, Odd Part
Index entries for sequences related to binary expansion of n

Cf. A000051, A000079, A000120, A000265, A001620, A006519, A007814, A023416, A038712, A063787, A086784.

Cf. also A007088, A179857, A220466.

int a(int n) { return n | (n-1); } // Russ Cox, May 15 2007

a086799 n | even n    = (a086799 $ div n 2) * 2 + 1
          | otherwise = n
-- Reinhard Zumkeller, Aug 07 2011

nmax:=70: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := 2^(p+1)*n-1 od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Feb 01 2013

Table[BitOr[(n + 1), n], {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 19 2011 *)

a(n)=bitor(n,n-1) \\ Charles R Greathouse IV, Apr 17 2012

def a(n): return n | (n-1)
print([a(n) for n in range(1, 71)]) # Michael S. Branicky, Jul 13 2022

a(n) = n + 2^A007814(n) - 1.
a(n) is odd; a(n) = n iff n is odd.
a(a(n)) = a(n); A007814(a(n)) = a(n); A000265(a(n)) = a(n).
A023416(a(n)) = A023416(n) - A007814(n) = A086784(n).
A000120(a(n)) = A000120(n) + A007814(n).
a(2^n) = a(A000079(n)) = 2*2^n - 1 = A000051(n+1).
a(n) = if n is odd then n else a(n/2)*2 + 1.
a(n) = A006519(n) + n - 1. - Reinhard Zumkeller, Feb 02 2007
a(n) = n OR n-1 (bitwise OR of consecutive numbers). - Russ Cox, May 15 2007
a(2*n) = A038712(n) + 2*n. - Reinhard Zumkeller, Aug 07 2011
a((2*n-1)*2^p) = 2^(p+1)*n-1, p >= 0. - Johannes W. Meijer, Feb 01 2013
Sum_{k=1..n} a(k) ~ n^2/2 + (1/(2*log(2)))*n*log(n) + (3/4 + (gamma-1)/(2*log(2)))*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 24 2022

A067699 Number of comparisons made in a version of the sorting algorithm QuickSort for an array of size n with n identical elements.

Original entry on oeis.org

0, 4, 8, 14, 18, 24, 30, 38, 42, 48, 54, 62, 68, 76, 84, 94, 98, 104, 110, 118, 124, 132, 140, 150, 156, 164, 172, 182, 190, 200, 210, 222, 226, 232, 238, 246, 252, 260, 268, 278, 284, 292, 300, 310, 318, 328, 338, 350, 356, 364, 372, 382

Offset: 1

Karla J. Oty (oty(AT)uscolo.edu), Feb 05 2002

nonn

Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest. Introduction to Algorithms. McGraw-Hill Book Company, 2000. (Gives description of this version of QuickSort.)

Michael S. Branicky, Table of n, a(n) for n = 1..10000
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, preprint, 2016.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms 13:4 (2017), #47.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple generating functions, 2004.
Ralf Stephan, Table of generating functions (ps file).
Ralf Stephan, Table of generating functions (pdf file).

Cf. A063090, A076178, A093418, A096620, A115107, A288964.

from functools import cache
@cache
def b(n): return 0 if n == 0 else b(n//2) + b((n-1)//2) + n + 2 + (n&1)
def a(n): return b(n-1)
print([a(n) for n in range(1, 53)]) # Michael S. Branicky, Aug 08 2022

a(n) = 2*ceiling((n+1)/2)  + a(ceiling(n/2)) + a(floor(n/2)) with a(1) = 0, a(2) = 4 and a(3) = 8.
From Ralf Stephan, Oct 24 2003: (Start)
a(n) = A076178(n-1) + 4*(n-1) for n >= 1.
a(n) = b(n-1) for n >= 1, where b(0) = 0, b(2*n) = b(n) + b(n-1) + 2*n + 2, b(2*n+1) = 2*b(n) + 2*n + 4.
(End)

A063694 Remove odd-positioned bits from the binary expansion of n.

Original entry on oeis.org

0, 1, 0, 1, 4, 5, 4, 5, 0, 1, 0, 1, 4, 5, 4, 5, 16, 17, 16, 17, 20, 21, 20, 21, 16, 17, 16, 17, 20, 21, 20, 21, 0, 1, 0, 1, 4, 5, 4, 5, 0, 1, 0, 1, 4, 5, 4, 5, 16, 17, 16, 17, 20, 21, 20, 21, 16, 17, 16, 17, 20, 21, 20, 21, 64, 65, 64, 65, 68, 69, 68, 69, 64, 65, 64, 65, 68, 69, 68

Offset: 0

Antti Karttunen, Aug 03 2001

a(n) is the formal derivative of x*n (evaluated at x=2 after being lifted to Z[x]) where n is interpreted as a polynomial in GF(2)[x] via its binary expansion. - Keith J. Bauer, Mar 17 2024

In the base 4 expansion of n, change 2 to 0 and 3 to 1. - Paolo Xausa, Feb 27 2025

			a(25) = 17 because 25 = 11001 in binary and when we AND this with 10101 we are left with 10001 = 17.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A004514, A063695 (remove even-positioned bits), A088442.

a063694 0 = 0
a063694 n = 4 * a063694 n' + mod q 2
            where (n', q) = divMod n 4
-- Reinhard Zumkeller, Sep 26 2015

function A063694(n)
  if n le 1 then return n;
  else return 4*A063694(Floor(n/4)) + ((n mod 4) mod 2);
  end if; return A063694;
end function;
[A063694(n): n in [0..120]]; // G. C. Greubel, Dec 05 2022

every_other_pos := proc(nn, x, w) local n, i, s; n := nn; i := 0; s := 0; while(n > 0) do if((i mod 2) = w) then s := s + ((x^i)*(n mod x)); fi; n := floor(n/x); i := i+1; od; RETURN(s); end: [seq(every_other_pos(j, 2, 0), j=0..120)];

a[n_] := BitAnd[n, Sum[2^k, {k, 0, Log[2, n] // Floor, 2}]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 28 2016 *)
A063694[n_] := FromDigits[ReplaceAll[IntegerDigits[n, 4], {2 -> 0, 3 -> 1}], 4];
Array[A063694, 100, 0] (* Paolo Xausa, Feb 27 2025 *)

a(n)=sum(k=0,n,(-1)^k*2^k*floor(n/2^k))  /* since n> ceil(log(n)/log(2)) */

a(n)=if(n<0,0,sum(k=0,n,(-1)^k*2^k*floor(n/2^k))) /* since n> ceil(log(n)/log(2)) */

def A063694(n): return n&((1<<(m:=n.bit_length())+(m&1))-1)//3 # Chai Wah Wu, Jan 30 2023

def A063694(n):
    if (n<2): return n
    else: return 4*A063694(floor(n/4)) + ((n%4)%2)
[A063694(n) for n in range(121)] # G. C. Greubel, Dec 05 2022

a(n) = Sum_{k>=0} (-1)^k*2^k*floor(n/2^k).
a(n) + A063695(n) = n.
a(n) = n - 2*a(floor(n/2)). - Vladeta Jovovic, Feb 23 2003
G.f.: 1/(1-x) * Sum_{k>=0} (-2)^k*x^2^k/(1-x^2^k). - Ralf Stephan, May 05 2003
a(n) = 4*a(floor(n/4)) + (n mod 4) mod 2. - Reinhard Zumkeller, Sep 26 2015
a(n) = Sum_{k>=0} A030308(n,k)*A199572(k). - Philippe Deléham, Jan 12 2023

A079946 Numbers k whose binary expansion begins with two or more 1's and ends with at least one 0.

Original entry on oeis.org

6, 12, 14, 24, 26, 28, 30, 48, 50, 52, 54, 56, 58, 60, 62, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 192, 194, 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 224, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246

Offset: 1

N. J. A. Sloane, Feb 21 2003

a(n) = b(n+1), with b(2n) = 2b(n), b(2n+1) = 2b(n)+2+4[n==0]. - Ralf Stephan, Oct 11 2003

Yifan Xie, Table of n, a(n) for n = 1..10001 (first 1000 terms from Harvey P. Dale)
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, arXiv:math/0305308 [math.NT], 2003.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

A004755 = union of this and A080565. A057547(n) = a(A014486(n)) for n >= 1.

Maple
```
A079946 := n -> 2*(2^(1+A000523(n))+n);
```

Table[Union[FromDigits[Join[{1,1},#,{0}],2]&/@Tuples[{1,0},n]],{n,0,5}]//Flatten (* Harvey P. Dale, Jan 16 2018 *)

for(n=0,6, for(k=2^(n-1),2^n-1,print1((2^n+k)*2,",")))

for(n=1,59,print1((2^(floor(log(n)/log(2))+1)+n)*2,","))

a(n) = n*2 + 4<Ruud H.G. van Tol, May 10 2024

def A079946(n): return n+(1<Chai Wah Wu, Jul 13 2022

a(n) = 2^floor(log_2(4*n))+2*n. - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 22 2003
a(n) = (2^(floor(log_2(n))+1)+n)*2. - Klaus Brockhaus, Feb 23 2003
a(2n) = 2a(n), a(2n+1) = 2a(n) + 2 + 4[n==0]. Twice A004755. - Ralf Stephan, Oct 12 2003

Definition clarified by N. J. A. Sloane, May 10 2024

A007378 a(n), for n >= 2, is smallest positive integer which is consistent with sequence being monotonically increasing and satisfying a(a(n)) = 2n.

Original entry on oeis.org

3, 4, 6, 7, 8, 10, 12, 13, 14, 15, 16, 18, 20, 22, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 36, 38, 40, 42, 44, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 97, 98, 99, 100, 101, 102, 103

Offset: 2

Colin Mallows

This is the unique monotonic sequence {a(n)}, n>=2, satisfying a(a(n)) = 2n.
May also be defined by: a(n), n=2,3,4,..., is smallest positive integer greater than a(n-1) which is consistent with the condition "n is a member of the sequence if and only if a(n) is an even number >= 4". - N. J. A. Sloane, Feb 23 2003
A monotone sequence satisfying a^(k+1)(n) = mn is unique if m=2, k >= 0 or if (k,m) = (1,3). See A088720. - Colin Mallows, Oct 16 2003
Numbers (greater than 2) whose binary representation starts with "11" or ends with "0". - Franklin T. Adams-Watters, Jan 17 2006
Lower density 2/3, upper density 3/4. - Charles R Greathouse IV, Dec 14 2022

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 2..10000
J.-P. Allouche, N. Rampersad and J. Shallit, On integer sequences whose first iterates are linear, Aequationes Math. 69 (2005), 114-127.
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
Benoit Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, arXiv:math/0305308 [math.NT], 2003.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47.
Jeffrey Shallit, k-regular Sequences
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences of the a(a(n)) = 2n family

Cf. A003605. Equals A080653 + 2.
This sequence, A079905, A080637 and A080653 are all essentially the same.
Cf. A088720, A042965.

a := proc(n) option remember; if n < 4 then n+1 else a(iquo(n,2)) + a(iquo(n+1,2)) fi end:
seq(a(n), n = 2..70); # Peter Bala, Aug 03 2022

max = 70; f[x_] := -x/(1-x) + x/(1-x)^2*(2 + Sum[ x^(2^k + 2^(k+1)) - x^2^(k+1) , {k, 0, Ceiling[Log[2, max]]}]); Drop[ CoefficientList[ Series[f[x], {x, 0, max + 1}], x], 2](* Jean-François Alcover, May 16 2012, from g.f. *)
a[2]=3; a[3]=4; a[n_?OddQ] := a[n] = a[(n-1)/2+1] + a[(n-1)/2]; a[n_?EvenQ] := a[n] = 2a[n/2]; Table[a[n], {n, 2, 71}] (* Jean-François Alcover, Jun 26 2012, after Vladeta Jovovic *)

a(n) = my(s=logint(n,2)-1); if(bittest(n,s), n<<1 - 2<Kevin Ryde, Aug 08 2022

from functools import cache
@cache
def a(n): return n+1 if n < 4 else a(n//2) + a((n+1)//2)
print([a(n) for n in range(2, 72)]) # Michael S. Branicky, Aug 04 2022

a(2^i + j) = 3*2^(i-1) + j, 0<=j<2^(i-1); a(3*2^(i-1) + j) = 2^(i+1) + 2*j, 0<=j<2^(i-1).
a(3*2^k + j) = 4*2^k + 3j/2 + |j|/2, k>=0, -2^k <= j < 2^k. - N. J. A. Sloane, Feb 23 2003
a(2*n+1) = a(n+1)+a(n), a(2*n) = 2*a(n). a(n) = n+A060973(n). - Vladeta Jovovic, Mar 01 2003
G.f.: -x/(1-x) + x/(1-x)^2 * (2 + sum(k>=0, t^2(t-1), t=x^2^k)). - Ralf Stephan, Sep 12 2003

More terms from Matthew Vandermast and Vladeta Jovovic, Mar 01 2003

A045654 Number of 2n-bead balanced binary strings, rotationally equivalent to complement.

Original entry on oeis.org

1, 2, 6, 8, 22, 32, 72, 128, 278, 512, 1056, 2048, 4168, 8192, 16512, 32768, 65814, 131072, 262656, 524288, 1049632, 2097152, 4196352, 8388608, 16781384, 33554432, 67117056, 134217728, 268451968, 536870912, 1073774592, 2147483648, 4295033110, 8589934592

Offset: 0

David W. Wilson

			From _Andrew Howroyd_, Jul 06 2025: (Start)
The a(1) = 2 length 2 balanced binary strings are: 01, 10.
The a(2) = 6 strings are: 0101, 1010, 0011, 0110, 1100, 1001.
The a(3) = 8 strings are: 010101, 101010, 000111, 001110, 011100, 111000, 110001, 100011. (End)

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Tilman Piesk, Row sums of triangle derived from A385665
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A000984, A045653, A045655, A045656, A045663, A127804, A385665.

a:= proc(n) option remember;
      2^n+`if`(n::even and n>0, a(n/2), 0)
    end:
seq(a(n), n=0..33);  # Alois P. Heinz, Jul 01 2025

a(n)={if(n==0, 1, my(s=0); while(n%2==0, s+=2^n; n/=2); s + 2^n)} \\ Andrew Howroyd, Sep 22 2019

def A045654(n): return sum(1<<(n>>k) for k in range((~n & n-1).bit_length()+1)) if n else 1 # Chai Wah Wu, Jul 22 2024

a(0)=1, a(2n) = a(n)+2^(2n), a(2n+1) = 2^(2n+1). - Ralf Stephan, Jun 07 2003
G.f.: 1/(1-x) + sum(k>=0, t(1+2t-2t^2)/(1-t^2)/(1-2t), t=x^2^k). - Ralf Stephan, Aug 30 2003
For n >= 1, a(n) = Sum_{k=0..A007814(n)} 2^(n/2^k). - David W. Wilson, Jan 01 2012
Inverse Moebius transform of A045663. - Andrew Howroyd, Sep 15 2019
a(n) = 2*A127804(n-1) for n > 0. - Tilman Piesk, Jul 05 2025
a(n) = Sum_{k=1..n} 2 * n * A385665(n,k) / k. - Tilman Piesk, Jul 07 2025

A080541 In binary representation: keep the first digit and left-rotate the others.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 8, 10, 12, 14, 9, 11, 13, 15, 16, 18, 20, 22, 24, 26, 28, 30, 17, 19, 21, 23, 25, 27, 29, 31, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 64, 66, 68, 70, 72, 74, 76, 78, 80

Offset: 1

Reinhard Zumkeller, Feb 20 2003

Permutation of natural numbers: let r(n,0)=n, r(n,k)=a(r(n,k-1)) for k>0, then r(n,floor(log_2(n))) = n and for n>1: r(n,floor(log_2(n))-1) = A080542(n).

Discarding their most significant bit, binary representations of numbers present in each cycle of this permutation form a distinct equivalence class of binary necklaces, thus there are A000031(n) separate cycles in each range [2^n .. (2^(n+1))-1] (for n >= 0) of this permutation. A256999 gives the largest number present in n's cycle. - Antti Karttunen, May 16 2015

			a(20)=a('10100')='11000'=24; a(24)=a('11000')='10001'=17.

Inverse: A080542.
Cf. A000031, A003986, A053644, A053645, A000523, A007088, A079944, A080413, A080543, A054429, A256999, A257250.
The set of permutations {A059893, A080541, A080542} generates an infinite dihedral group.

f:= proc(n) local d;
   d:= ilog2(n);
   if n >= 3/2*2^d then 2*n+1-2^(d+1) else 2*n - 2^d fi
end proc:
map(f, [$1..100]); # Robert Israel, May 19 2015

A080541[n_] := FromDigits[Join[{First[#]}, RotateLeft[Rest[#]]], 2] & [IntegerDigits[n, 2]];
Array[A080541, 100] (* Paolo Xausa, May 13 2025 *)

def A080541(n): return ((n&(m:=1< 1 else n  # Chai Wah Wu, Jan 22 2023

maxlevel <- 6 # by choice
a <- 1:3
for(m in 1:maxlevel) for(k in 0:(2^(m-1)-1)){
a[2^(m+1)       + 2*k    ] = 2*a[2^m           + k]
a[2^(m+1)       + 2*k + 1] = 2*a[2^m + 2^(m-1) + k]
a[2^(m+1) + 2^m + 2*k    ] = 2*a[2^m           + k] + 1
a[2^(m+1) + 2^m + 2*k + 1] = 2*a[2^m + 2^(m-1) + k] + 1
}
a
# Yosu Yurramendi, Oct 12 2020

(define (A080541 n) (if (< n 2) n (A003986bi (A053644 n) (+ (* 2 (A053645 n)) (A079944off2 n))))) ;; A003986bi gives the bitwise OR of its two arguments. See A003986.
;; Where A079944off2 gives the second most significant bit of n. (Cf. A079944):
(define (A079944off2 n) (A000035 (floor->exact (/ n (A072376 n)))))
;; Antti Karttunen, May 16 2015

From Antti Karttunen, May 16 2015: (Start)
a(1) = 1; for n > 1, a(n) = A053644(n) bitwise_OR (2*A053645(n) + second_most_significant_bit_of(n)). [Here bitwise_OR is a 2-argument function given by array A003986 and second_most_significant_bit_of gives the second most significant bit (0 or 1) of n larger than 1. See A079944.]
Other identities. For all n >= 1:
a(n) = A059893(A080542(A059893(n))).
a(n) = A054429(a(A054429(n))).
(End)
A080542(a(n)) = a(A080542(n)) = n. [A080542 is the inverse permutation.]
From Robert Israel, May 19 2015: (Start)
Let d = floor(log[2](n)).  If n >= 3*2^(d-1) then a(n) = 2*n + 1 - 2^(d+1), otherwise a(n) = 2*n - 2^d.
G.f.: 2*x/(x-1)^2 + Sum_{n>=1} x^(2^n)+(2^n-1)*x^(3*2^(n-1)))/(x-1). (End)

A088705 First differences of A000120. One minus exponent of 2 in n.

Original entry on oeis.org

0, 1, 0, 1, -1, 1, 0, 1, -2, 1, 0, 1, -1, 1, 0, 1, -3, 1, 0, 1, -1, 1, 0, 1, -2, 1, 0, 1, -1, 1, 0, 1, -4, 1, 0, 1, -1, 1, 0, 1, -2, 1, 0, 1, -1, 1, 0, 1, -3, 1, 0, 1, -1, 1, 0, 1, -2, 1, 0, 1, -1, 1, 0, 1, -5, 1, 0, 1, -1, 1, 0, 1, -2, 1, 0, 1, -1, 1, 0, 1, -3, 1, 0, 1

Offset: 0

Ralf Stephan, Oct 10 2003

The number of 1's in the binary expansion of n+1 minus the number of 1's in the binary expansion of n.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Yann Bugeaud and Guo-Niu Han, A combinatorial proof of the non-vanishing of Hankel determinants of the Thue-Morse sequence, Electronic Journal of Combinatorics 21(3) (2014), #P3.26. See F(z) in (1.1). - _N. J. A. Sloane_, Aug 31 2014
Kevin Ryde, Iterations of the Lévy C Curve, see index "turn".
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Index entries for sequences related to binary expansion of n.

Cf. A000120, A007814, A079559.

a088705 n = a088705_list !! n
a088705_list = 0 : zipWith (-) (tail a000120_list) a000120_list
-- Reinhard Zumkeller, Dec 11 2011

add(x^(2^k)/(1+x^(2^k)),k=0..20); series(%,x,1001); seriestolist(%); # To get up to a million terms, from N. J. A. Sloane, Aug 31 2014

a[n_] := If[n<1, 0, If[Mod[n, 2] == 0, a[n/2] - 1, 1]]; Array[a, 60, 0] (* Amiram Eldar, Nov 26 2018 *)

PARI
```
a(n)=if(n<1,0,if(n%2==0,a(n/2)-1,1))
```
PARI
```
a(n)=if(n<1,0,1-valuation(n,2))
```

def A088705(n): return 1-(~n & n-1).bit_length() # Chai Wah Wu, Sep 18 2024

For n > 0: a(n) = A000120(n) - A000120(n-1) = 1 - A007814(n).
Multiplicative with a(2^e) = 1-e, a(p^e) = 1 otherwise. - David W. Wilson, Jun 12 2005
G.f.: Sum{k>=0} t/(1+t), t=x^2^k.
a(0) = 0, a(2*n) = a(n) - 1, a(2*n+1) = 1.
Let T(x) be the g.f., then T(x)-T(x^2)=x/(1+x). - Joerg Arndt, May 11 2010
Dirichlet g.f.: zeta(s) * (2-2^s)/(1-2^s). - Amiram Eldar, Sep 18 2023

A004134 Denominators in expansion of (1-x)^{-1/4} are 2^a(n).

Original entry on oeis.org

0, 2, 5, 7, 11, 13, 16, 18, 23, 25, 28, 30, 34, 36, 39, 41, 47, 49, 52, 54, 58, 60, 63, 65, 70, 72, 75, 77, 81, 83, 86, 88, 95, 97, 100, 102, 106, 108, 111, 113, 118, 120, 123, 125, 129, 131, 134, 136, 142, 144, 147, 149, 153, 155, 158, 160, 165, 167, 170, 172, 176, 178

Offset: 0

N. J. A. Sloane

nonn

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions

Cf. A004130.

Cf. A005187.

Log2[ Denominator[ CoefficientList[ Series[ 1/Sqrt[Sqrt[1 - x]], {x, 0, 61}], x]]] (* Robert G. Wilson v, Mar 23 2014 *)
f[n_] := 3 n - DigitCount[n, 2, 1]; Array[f, 62, 0] (* or *)
a[n_] := If[ OddQ@ n, a[(n - 1)/2] + 3 (n - 1)/2 + 2, a[n/2] + 3 n/2]; a[0] = 0; Array[a, 62, 0] (* Robert G. Wilson v, Mar 23 2014 *)

{a(n) = if( n<0, 0, 3*n - subst( Pol( binary( n ) ), x, 1) ) } /* Michael Somos, Aug 23 2007 */

a(n) = 3*n - hammingweight(n); \\ Joerg Arndt, Mar 23 2014

a(n) = 3*n - A000120(n). Recurrence: a(2n) = a(n) + 3n, a(2n+1) = a(n) + 3n + 2. Proved by Mitch Harris, following a conjecture by Ralf Stephan.

a(n) = A005187(n) + n. - Cyril Damamme, Aug 04 2015

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

Views

Author

Keywords

Crossrefs

Programs

PARI

Scheme

Formula

Extensions

A086799 Replace all trailing 0's with 1's in binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

PARI

Python

Formula

A067699 Number of comparisons made in a version of the sorting algorithm QuickSort for an array of size n with n identical elements.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Formula

A063694 Remove odd-positioned bits from the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

A079946 Numbers k whose binary expansion begins with two or more 1's and ends with at least one 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A007378 a(n), for n >= 2, is smallest positive integer which is consistent with sequence being monotonically increasing and satisfying a(a(n)) = 2n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs