A023416 -id:A023416 - cp's OEIS frontend

A083652 Sum of lengths of binary expansions of 0 through n.

1, 2, 4, 6, 9, 12, 15, 18, 22, 26, 30, 34, 38, 42, 46, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 136, 142, 148, 154, 160, 166, 172, 178, 184, 190, 196, 202, 208, 214, 220, 226, 232, 238, 244, 250, 256, 262, 268, 274, 280, 286, 292

Offset: 0

Reinhard Zumkeller, May 01 2003

a(n) = A001855(n) + 1 for n > 0;
a(0) = A070939(0)=1, n > 0: a(n) = a(n-1) + A070939(n).
A030190(a(k))=1; A030530(a(k)) = k + 1.
Partial sums of A070939. - Hieronymus Fischer, Jun 12 2012
Young writes "If n = 2^i + k [...] the maximum is (i+1)(2^i+k)-2^{i+1}+2." - Michael Somos, Sep 25 2012

			G.f. = 1 + 2*x + 4*x^2 + 6*x^3 + 9*x^4 + 12*x^5 + 15*x^6 + 18*x^7 + 22*x^8 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
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; DOI: 10.1145/3127585.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36.
Alfred Young, The Maximum Order of an Irreducible Covariant of a System of Binary Forms, Proc. Roy. Soc. 72 (1903), 399-400 = The Collected Papers of Alfred Young, 1977, 136-137.
Index entries for sequences related to binary expansion of n

Cf. A000120, A007088, A023416, A059015, A070939 (base 2), A123753.

A296349 is an essentially identical sequence.

a083652 n = a083652_list !! n
a083652_list = scanl1 (+) a070939_list
-- Reinhard Zumkeller, Jul 05 2012

Accumulate[Length/@(IntegerDigits[#,2]&/@Range[0,60])] (* Harvey P. Dale, May 28 2013 *)
a[n_] := (n + 1) IntegerLength[n + 1, 2] - 2^IntegerLength[n + 1, 2] + 2;Table[a[n], {n, 0, 58}] (* Peter Luschny, Dec 02 2017 *)

{a(n) = my(i); if( n<0, 0, n++; i = length(binary(n)); n*i - 2^i + 2)}; /* Michael Somos, Sep 25 2012 */

a(n)=my(i=#binary(n++));n*i-2^i+2 \\ equivalent to the above

def A083652(n):
    s, i, z = 1, n, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A083652(n) for n in range(0, 59)]) # Peter Luschny, Nov 30 2017

def A083652(n): return 2+(n+1)*(m:=(n+1).bit_length())-(1<Chai Wah Wu, Mar 01 2023

a(n) = 2 + (n+1)*ceiling(log_2(n+1)) - 2^ceiling(log_2(n+1)).
G.f.: g(x) = 1/(1-x) + (1/(1-x)^2)*Sum_{j>=0} x^2^j. - Hieronymus Fischer, Jun 12 2012; corrected by Ilya Gutkovskiy, Jan 08 2017
a(n) = A123753(n) - n. - Peter Luschny, Nov 30 2017

A372475 Length of binary expansion (or number of bits) of the n-th squarefree number.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8

Offset: 1

Gus Wiseman, May 09 2024

			The 10th squarefree number is 14, with binary expansion (1,1,1,0), so a(10) = 4.

For prime instead of squarefree we have A035100, 1's A014499, 0's A035103.
Restriction of A070939 to A005117.
Run-lengths are A077643.
For weight instead of length we have A372433 (restrict A000120 to A005117).
For zeros instead of length we have A372472, firsts A372473.
Positions of first appearances are A372540.
A030190 gives binary expansion, reversed A030308.
A048793 lists positions of ones in reversed binary expansion, sum A029931.
A371571 lists positions of zeros in binary expansion, sum A359359.
A371572 lists positions of ones in binary expansion, sum A230877.
A372515 lists positions of zeros in reversed binary expansion, sum A359400.
Cf. A003714, A023416, A049093, A049094, A059015, A069010, A073642, A145037, A211997, A368494, A372474, A372516.

IntegerLength[Select[Range[1000],SquareFreeQ],2]

from math import isqrt
from sympy import mobius
def A372475(n):
    def f(x): return n+x-sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return int(m).bit_length() # Chai Wah Wu, Aug 02 2024

a(n) = A070939(A005117(n)).

a(n) = A372472(n) + A372433(n).

A008687 Number of 1's in 2's complement representation of -n.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 2, 2, 1, 4, 3, 3, 2, 3, 2, 2, 1, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3, 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3

Offset: 0

R. H. Hardin

a(A127904(n)) = n and a(m) < n for m < A127904(n). - Reinhard Zumkeller, Feb 05 2007
a(n) = A000120(A010078(n)), n>0; a(n) = A023416(A004754(n-1)), n>1. - Reinhard Zumkeller, Dec 04 2015
Conjecture: a(n)+1 is the length of the Hirzebruch (negative) continued fraction for the Stern-Brocot tree fraction A007305(n)/A007306(n). - Andrey Zabolotskiy, Apr 17 2020
Terms a(n); n >= 2 can be generated recursively, as follows. Let S(0) = {1}, then for k >=1, let S(k) = {S(k-1)+1, S(k-1)}, where +1 means +1 on every term of S(k-1); see Example. Each step of the recursion gives the next 2^k terms of the sequence. - David James Sycamore, Jul 15 2024

			Using the above recursion for a(n); n >= 2, we have:
 S(0) = {1} so a(2) = 1;
 S(1) = {2,1} so a(3,4) = 2,1;
 S(2) = {3,2,2,1}, so a(5,6,7,8) = 3,2,2,1;
As irregular table the sequence for n >= 2 begins:
  1;
  2,1;
  3,2,2,1;
  4,3,3,2,3,2,2,1;
  5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1;
  6,5,5,4,5,4,4,3,5,4,3,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1;
and so on (the k-th row contains 2^k terms; k>=0). - _David James Sycamore_, Jul 15 2024

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Michael Gilleland, Some Self-Similar Integer Sequences
Wikipedia, Two's complement

This is Guy Steele's sequence GS(4, 3) (see A135416).
Cf. A000120, A004754, A010078, A023416, A290251.
Cf. A007305, A007306, A061313, A088696.

a008687 n = a008687_list !! n
a008687_list = 0 : 1 : c [1] where c (e:es) = e : c (es ++ [e+1,e])
-- Reinhard Zumkeller, Mar 07 2011

a[0] = 0; a[1] = 1; a[n_] := a[n] = Mod[n,2] + a[Mod[n,2] + Floor[n/2]]; Array[a, 96, 0] (* Jean-François Alcover, Aug 12 2017, after Reinhard Zumkeller *)

a(n) = if(n<2,n, n--; logint(n,2) - hammingweight(n) + 2); \\ Kevin Ryde, Apr 14 2021

a(n) = A023416(n-1) + 1.
a(n) = if n<=1 then n else (n mod 2) + a((n mod 2) + floor(n/2)). - Reinhard Zumkeller, Feb 05 2007
a(n) = if n<2 then n else a(ceiling(n/2)) + n mod 2. - Reinhard Zumkeller, Jul 25 2006
Min{m: a(m)=n} = if n>0 then A083318(n-1) else 0. - Reinhard Zumkeller, Jul 25 2006

A124757 Zero-based weighted sum of compositions in standard order.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 3, 4, 5, 6, 0, 1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 0, 1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 5, 6, 7, 8, 8, 9, 10, 11, 9, 10, 11, 12, 12, 13, 14, 15, 0, 1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 5, 6, 7, 8, 8, 9, 10, 11, 9, 10, 11, 12, 12, 13, 14

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

Sum of all positions of 1's except the last in the reversed binary expansion of n. For example, the reversed binary expansion of 14 is (0,1,1,1), so a(14) = 2 + 3 = 5. Keeping the last position gives A029931. - Gus Wiseman, Jan 17 2023

			Composition number 11 is 2,1,1; 0*2+1*1+2*1 = 3, so a(11) = 3.
The table starts:
  0
  0
  0 1
  0 1 2 3

Alois P. Heinz, Rows n = 0..14, flattened

Cf. A066099, A070939, A029931, A011782 (row lengths), A001788 (row sums).
Row sums of A048793 if we delete the last part of every row.
For prime indices instead of standard comps we have A359674, rev A359677.
Positions of first appearances are A359756.
A003714 lists numbers with no successive binary indices.
A030190 gives binary expansion, reverse A030308.
A230877 adds up positions of 1's in binary expansion, length A000120.
A359359 adds up positions of 0's in binary expansion, length A023416.
Cf. A059015, A065359, A069010, A073642, A083652, A359400, A359402, A359678.

Table[Total[Most[Join@@Position[Reverse[IntegerDigits[n,2]],1]]],{n,30}]

For a composition b(1),...,b(k), a(n) = Sum_{i=1..k} (i-1)*b(i).

For n>0, a(n) = A029931(n) - A070939(n).

A030130 Binary expansion contains a single 0.

Original entry on oeis.org

0, 2, 5, 6, 11, 13, 14, 23, 27, 29, 30, 47, 55, 59, 61, 62, 95, 111, 119, 123, 125, 126, 191, 223, 239, 247, 251, 253, 254, 383, 447, 479, 495, 503, 507, 509, 510, 767, 895, 959, 991, 1007, 1015, 1019, 1021, 1022, 1535, 1791, 1919, 1983, 2015, 2031, 2039

Offset: 1

Toby Donaldson (tjdonald(AT)uwaterloo.ca)

From Reinhard Zumkeller, Aug 29 2009: (Start)
A023416(a(n)) = 1;
apart from the initial term the sequence can be seen as a triangle read by rows, see A164874;
A055010 and A086224 are subsequences, see also A000918 and A036563. (End)
Zero and numbers of form 2^m-2^k-1, 2 <= m, 0 <= k <= m-2. - Zak Seidov, Aug 06 2010

			23 is OK because it is '10111' in base 2.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A000918, A023416, A036563, A055010, A086224, A140977, A160502, A164874, A190620.

long int element (long int i) { return (pow(2,g(i))-1-pow(2,(pow(2*g(i)-1,2)-1-8*i)/8));} long int g(long int m) {if (m==0) return(1); return ((sqrt(8*m-7)+3)/2);}

a030130 n = a030130_list !! (n-1)
a030130_list = filter ((== 1) . a023416) [0..]
-- Reinhard Zumkeller, Mar 31 2015, Dec 07 2012

[0] cat [k:k in [0..2050]| Multiplicity(Intseq(k,2),0) eq 1]; // Marius A. Burtea, Feb 06 2020

Sort[Flatten[{{0}, Table[2^n - 2^m - 1, {n, 2, 50}, {m, 0, n - 2}]}]] (* Zak Seidov, Aug 06 2010 *)
Select[Range[0,2100],DigitCount[#,2,0]==1&] (* Harvey P. Dale, Dec 19 2021 *)

print1("0, ");for(k=1,2039,my(v=digits(k,2));if(vecsum(v)==#v-1,print1(k,", "))) \\ Hugo Pfoertner, Feb 06 2020

from math import isqrt, comb
def A030130(n): return (1<<(a:=(isqrt(n-1<<3)+1>>1)+1))-(1<Chai Wah Wu, Dec 19 2024

a(n) = 2^(g(n))-1-2^(((2*g(n)-1)^2-1-8*n)/8) with g(n)=int((sqrt(8*n-7)+3)/2) for all n>0 and g(0)=1. - Ulrich Schimke (ulrschimke(AT)aol.com)
a(n+1) = A140977(a(n)) for any n > 1. - Rémy Sigrist, Feb 06 2020
Sum_{n>=2} 1/a(n) = A160502. - Amiram Eldar, Oct 06 2020
a(n) = (A190620(n-1)-1)/2. - Chai Wah Wu, Dec 19 2024

More terms from Erich Friedman

Offset fixed by Reinhard Zumkeller, Aug 24 2009

A059009 Numbers having an odd number of zeros in their binary expansion.

Original entry on oeis.org

0, 2, 5, 6, 8, 11, 13, 14, 17, 18, 20, 23, 24, 27, 29, 30, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59, 61, 62, 65, 66, 68, 71, 72, 75, 77, 78, 80, 83, 85, 86, 89, 90, 92, 95, 96, 99, 101, 102, 105, 106, 108, 111, 113, 114, 116, 119, 120, 123, 125, 126, 128, 131

Offset: 0

Patrick De Geest, Dec 15 2000

Positions of ones in A059448 for n >= 1. - John Keith, Mar 09 2022

			18 is in the sequence because 18 = 10010_2. '10010' has three zeros. - _Indranil Ghosh_, Feb 04 2017

Indranil Ghosh, Table of n, a(n) for n = 0..25000 (terms 0..1000 from T. D. Noe)
Jeffrey Shallit, Additive Number Theory via Automata and Logic, arXiv:2112.13627 [math.NT], 2021.

Cf. A000069, A001969, A059010, A059011, A059012, A059013, A059014, A059448.

Cf. A023416.

a059009 n = a059009_list !! (n-1)
a059009_list = filter (odd . a023416) [1..]
-- Reinhard Zumkeller, Jan 21 2014

a:= proc(n) option remember;
  if n::even then -a(n/2) + 3*n + 1 else a((n-1)/2) + n + 1 fi
end proc:
a(0):= 0:
seq(a(n),n=0..100); # Robert Israel, Feb 23 2016

Select[Range[0,150],OddQ[Count[IntegerDigits[#,2],0]]&] (* Harvey P. Dale, Oct 22 2011 *)

is(n)=hammingweight(bitneg(n,#binary(n)))%2 \\ Charles R Greathouse IV, Mar 26 2013

a(n) = if(n==0,0, 2*n + (logint(n,2) - hammingweight(n) + 1) % 2); \\ Kevin Ryde, Mar 11 2021

i=j=0
while j<=800:
    if bin(i)[2:].count("0")%2:
        print(str(j)+" "+str(i))
        j+=1
    i+=1 # Indranil Ghosh, Feb 04 2017

maxrow <- 4 # by choice
onezeros <- 1
for(m in 1:(maxrow+1)){
  row <- onezeros[2^(m-1):(2^m-1)]
  onezeros <- c(onezeros, c(1-row, row) )
}
a <- which(onezeros == 0)
a
# Yosu Yurramendi, Mar 28 2017

a(0) = 0, a(2*n) = -a(n) + 6*n + 1, a(2*n+1) = a(n) + 2*n + 2. a(n) = 2*n + 1/2(1-(-1)^A023416(n)) = 2*n + A059448(n). - Ralf Stephan, Sep 17 2003

A059448 The parity of the number of zero digits when n is written in binary.

Original entry on oeis.org

0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1

Offset: 1

Henry Bottomley, Feb 02 2001

Old name was: "If A_k are the terms from 2^(k-1) through to 2^k-1, then A_(k+1) is B_k A_k where B_k is A_k with 0's and 1's swapped, starting from a(1)=0; also parity of number of zero digits when n is written in binary. a(0) not given as it could be 1 or 0 depending on the definition or formula used." - Michel Dekking, Sep 11 2020
The sequence (when prefixed by 0) is overlap-free [Allouche and Shallit].
From Vladimir Shevelev, May 23 2017: (Start)
Theorem: The sequence is cubefree.
Here we show only that the sequence contains no three consecutive equal terms. Indeed, using the recursions below, we have
a(4*n)=a(n), a(4*n+1)=1-a(n), a(4*n+2)=1-a(n), a(4*n+3)=a(n), n >= 1, and our statement easily follows. In general, the Theorem could be proved either directly (cf. A269027) or using the remark below from Jeffrey Shallit and the well-known fact [first proved not later than 1912 by Axel Thue (private communication from Jean-Paul Allouche)] that the Thue-Morse sequence is cubefree.
Note that, by the formulas modulo 4, the sequence is constructed over four terms {a(4*n),a(4*n+1),a(4*n+2),a(4*n+3)} which, starting with a(4), are either {0,1,1,0} or {1,0,0,1}, the first elements of which form {a(n)}. (End)

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 26, Problem 23.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Jeffrey Shallit, Arseny M. Shur, and Stefan Zorcic, New constructions for 3-free and 3+-free binary morphisms, arXiv:2310.15064 [math.CO], 2023. Mentions this sequence.
Index entries for sequences related to binary expansion of n
Index entries for characteristic functions

Characteristic function of A059009.
Cf. A298952 (complement), A242179 (values +-1).
Cf. A023416 (A080791), A054429, A010059, A010060, A106400.

a059448 = (`mod` 2) . a023416  -- Reinhard Zumkeller, Mar 01 2012

s1:=[];
for n from 1 to 200 do
t1:=convert(n,base,2); t2:=subs(1=NULL,t1); s1:=[op(s1),nops(t2) mod 2]; od:
s1;

Table[Boole[OddQ[Count[IntegerDigits[n, 2], 0]]], {n, 1, 105}] (* Jean-François Alcover, Apr 05 2013 *)

a(n)=(#binary(n)-hammingweight(n))%2;
vector(99,n,a(n)) /* Joerg Arndt, Sep 11 2020 */

def A059448(n): return (n.bit_length()^n.bit_count())&1 # Chai Wah Wu, Jul 26 2023

a(2n) = 1 - a(n); a(2n+1) = a(n) = 1 - a(2n). If 2^k <= n < 2^(k+1) then a(n) = 1 - a(n-2^(k-1)). a(n) = A023416(n) mod 2 = A059009(n) - 2n = 2n + 1 - A059010(n) = |A010060(n) - A030300(n-1)|.
Let b(1)=1 and b(n) = b(n-ceiling(n/2)) - b(n-floor(n/2)); then for n >= 1, a(n) = (1/2)*(1-b(2n+1)). - Benoit Cloitre, Apr 26 2005
Alternatively, if x is the sequence, then x = 010 mu^2(x), where mu is the Thue-Morse morphism sending 0 to 01 and 1 to 10. - Jeffrey Shallit, Jun 06 2016
a(n) = A010059(A054429(n)) = (1+A008836(A163511(n)))/2. - Antti Karttunen, May 30 2017
Alternatively, if x is the sequence, then x = 0 tau(x), where tau is the "twisted" Thue-Morse morphism sending 0 to 10 and 1 to 01. Note that tau^2 = mu^2, giving x = 010 mu^2(x). - Michel Dekking, Sep 30 2020

Name changed by Michel Dekking, Sep 11 2020

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

A087116 Number of maximal groups of consecutive zeros in binary representation of n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 2, 2, 3, 2, 3, 3, 3, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 1, 2, 1, 2, 2

Offset: 0

Reinhard Zumkeller, Aug 14 2003

nonn

The following four statements are equivalent: a(n) = 0; n = 2^k - 1 for some k; A087117(n) = 0; A023416(n) = 0.

			G.f. = 1 + x^2 + x^4 + x^5 + x^6 + x^8 + x^9 + 2*x^10 + x^11 + x^12 + x^13 + x^14 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Cf. A087118, A087119, A087120, A023416, A007088.
Cf. A023416, A087117.
Cf. A033264, A003817, A069010.
Essentially the same as A033264.

a087116 0 = 1
a087116 n = f 0 n where
   f y 0 = y
   f y x = if r == 0 then g x' else f y x'
           where (x', r) = divMod x 2
                 g z = if r == 0 then g z' else f (y + 1) z'
                       where (z', r) = divMod z 2
-- Reinhard Zumkeller, Mar 31 2015

a[n_] := SequenceCount[IntegerDigits[n, 2], {Longest[0..]}];
Table[a[n], {n, 0, 101}] (* Jean-François Alcover, Oct 18 2021 *)

a(n) = if (n == 0, 1, hammingweight(bitxor(n, n>>1)) >> 1);
vector(102, i, a(i-1))  \\ Gheorghe Coserea, Sep 17 2015

def A087116(n):
    return sum(1 for d in bin(n)[2:].split('1') if len(d)) # Chai Wah Wu, Nov 04 2016

a(n) = A033264(n) for n > 0 since strings of 0's alternate with strings of 1's. - Jonathan Sondow, Jan 17 2016
a(n) = a(2*n + 1) = a(4*n + 2) - 1, if n > 0. - Michael Somos, Nov 04 2016
a(n) = A069010(A003817(n)-n) for n > 0. - Chai Wah Wu, Nov 04 2016

A099393 a(n) = 4^n + 2^n - 1.

Original entry on oeis.org

1, 5, 19, 71, 271, 1055, 4159, 16511, 65791, 262655, 1049599, 4196351, 16781311, 67117055, 268451839, 1073774591, 4295032831, 17180000255, 68719738879, 274878431231, 1099512676351, 4398048608255, 17592190238719

Offset: 0

Ralf Stephan, Oct 20 2004

Number of occurrences of letter 2 in the (n+1)-st Peano word.
In binary representation, a leading one followed by n zeros then by n ones. - Reinhard Zumkeller, Feb 07 2006
The number of involutions in group G_n G_{n+1} = G_n(operation) D_8. For example, Q_8->1 involution; D_8->5 involutions - Roger L. Bagula, Aug 08 2007

			n=5: a(5)=4^5+2^5-1=1024+32-1=1055 -> '10000011111'.

Vincenzo Librandi, Table of n, a(n) for n = 0..170
A. M. Cohen and D. E. Taylor, On a Certain Lie Algebra Defined By a Finite Group, American Mathematical Monthly, volume 114, number 7, August-September 2007, pages 633-638. Also preprint. a(n) = t_n in proof of theorem 6.2.
Sergey Kitaev and Toufik Mansour, The Peano curve and counting occurrences of some patterns, arXiv:math/0210268 [math.CO], 2002. Section 3 lemma 1, d_2^n = a(n-1).
Sergey Kitaev, Toufik Mansour, and Patrice Séébold, Generating the Peano curve and counting occurrences of some patterns, Journal of Automata, Languages and Combinatorics, volume 9, number 4, 2004, pages 439-455. Also at ResearchGate. Section 4, |P_n|_r = a(n-1).
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

See the formula section for the relationships with A000120, A000217, A000225, A002378, A007582, A020522, A023416, A030101, A063376, A070939, A083420, A279396.

[4^n + 2^n - 1: n in [0..60]]; // Vincenzo Librandi, Apr 26 2011

LinearRecurrence[{7,-14,8},{1,5,19},30] (* Harvey P. Dale, Sep 06 2015 *)

a(n)=4^n+2^n-1; \\ Charles R Greathouse IV, Sep 24 2015

def A099393(n): return ((1<Chai Wah Wu, Mar 10 2025

a(n) = A063376(n)-1.
a(n) = A020522(n) + A000225(n+1) = A083420(n) - A020522(n); A000120(a(n)) = n+1; A023416(a(n))=n; A070939(a(n)) = 2*n+1; 2*A020522(n)+1 = A030101(a(n)). - Reinhard Zumkeller, Feb 07 2006
a(n) = 2^(2*n-1) + 2*a(n-1) + 1. - Roger L. Bagula, Aug 08 2007
From Mohammad K. Azarian, Jan 15 2009: (Start)
G.f.: 1/(1-4*x) + 1/(1-2*x) - 1/(1-x).
E.g.f.: e^(4*x) + e^(2*x) - e^x. (End)
a(n) = A279396(n+4, 4). - Wolfdieter Lang, Jan 10 2017
a(n) = A002378(2^n) - 1 = 2*A000217(2^n) - 1 = 2*A007582(n) - 1. - Peter Munn, Nov 20 2022

cp's OEIS Frontend

A083652 Sum of lengths of binary expansions of 0 through n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Python

Formula

A372475 Length of binary expansion (or number of bits) of the n-th squarefree number.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A008687 Number of 1's in 2's complement representation of -n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A124757 Zero-based weighted sum of compositions in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A030130 Binary expansion contains a single 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Haskell

Magma

Mathematica

PARI

Python

Formula

Extensions

A059009 Numbers having an odd number of zeros in their binary expansion.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica